Новые многофункциональные материалы и нанотехнологии

НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИМ.Н.И.ЛОБАЧЕВСКОГО
НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ
УЧЕБНО-НАУЧНЫЙ И ИННОВАЦИОННЫЙ КОМПЛЕКС
"НОВЫЕ МНОГОФУНКЦИОНАЛЬНЫЕ МАТЕРИАЛЫ И
НАНОТЕХНОЛОГИИ"



Фаддеев М.А., Марков К.А.

ЧИСЛЕННЫЕ МЕТОДЫ
(
Учебное пособие)

Мероприятие 1.2. Совершенствование образовательных технологий, укрепление материально-технической базы учебного процесса

Учебные дисциплины: «Информатика», «Численные методы»
Специальности, направления: «Физика», «Нанотехнология»,
«Нанотехнология в электронике», «Микроэлектроника и полупроводниковые приборы», «Электроника и наноэлектроника»


ННГУ, 2010

2
В любой науке столько истины,
сколько в ней математики.

Иммануил Кант

ВВЕДЕНИЕ
Все естественные науки используют вычисления в своей практике.
Еще в V веке до нашей эры философ Пифагор, которого можно назвать основоположником математической физики, утверждал, что всё сущее управляется числами. Все значительные этапы в развитии физики сопровождались разработкой новых разделов математики. Величайший физик и математик Исаак Ньютон при формулировке основ механики, которые были изложены в его знаменитых «Математических началах натуральной философии», опубликованных в 1687 году, разработал дифференциальное и интегральное исчисление. Примерно 50 лет спустя
Леонард Эйлер создал вариационное исчисление, решая актуальные задачи строительной механики. Создание молекулярно-кинетической теории теплоты происходило вместе с развитием теории вероятностей.
Классическая электродинамика дала мощный импульс исследованиям дифференциальных уравнений в частных производных. Исследование устойчивости динамических систем привело великого математика и физика Анри Пуанкаре к разработке теории бифуркаций. Квантовая механика базируется на теории операторов в гильбертовом пространстве. Аналогичное влияние решения физических проблем на развитие новых разделов математики наблюдается в областях квантовой хромодинамики, нелинейных колебаний, теории единого поля и т.д.
Во все времена практика решения прикладных задач демонстрировала недостаточность имеющихся в наличии аналитических методов математики и необходимость разработки численных методов. Например, невозможность при интегрировании представить первообразную функцию в аналитическом виде приводит к использованию квадратурных формул приближенного вычисления определенного интеграла. Приближенный характер результатов численных методов не является принципиальным препятствием к их использованию, так как в физике применяются те численные методы, погрешность которых может быть сделана ниже приемлемой точности результата данной задачи.

3
Принципиально новая фаза в развитии численных методов наступила с началом широкого использования компьютерной техники в физических исследованиях. Важнейшее достоинство компьютеров – высокая скорость выполнения математических операций – позволило в исторически короткий срок создать новые сравнительно простые и эффективные алгоритмы. Современные компьютеры за доли секунды выполняют огромное количество арифметических действий с многоразрядными числами, что обеспечивает требуемую точность результатов. При этом отпала необходимость в использовании множества хитроумных приемов вычислений «с помощью карандаша и бумаги», каждый из которых разрабатывался для довольно узкого класса задач.
Повсеместное распространение персональных компьютеров обеспечивает широкую доступность численных методов. При этом у начинающих исследователей часто возникают трудности выбора конкретного метода для решения поставленной задачи.
Количество численных методов, разработанных к настоящему времени, огромно. Одни обладают большей общностью, другие имеют весьма специальное назначение и используются для узкого круга физических задач. Таким образом, начинающие исследователи нуждаются в информации, позволяющей выбрать оптимальный численный метод.
Положение с учебной литературой по численным методам в настоящее время не является благополучным. Сохранились в небольшом количестве старые учебники: толстые, добротные, изобилующие вышеупомянутыми специальными приемами вычислений
«с помощью бумаги и карандаша». Большая часть объема таких томов посвящена доказательствам, которые существенны для математиков, но для физиков-экспериментаторов имеют чисто академический интерес. К тому же изучение таких учебников требует солидной математической подготовки, и поэтому тяжело для студентов первого и второго курсов, которым уже приходится обращаться к некоторым численным методам.
С другой стороны, существуют многочисленные методические пособия из нескольких страниц, содержащие перечисление названий методов и список формул. Учебно-методическая ценность таких опусов близка к нулю. Наконец, имеются современные учебные пособия (как правило, переводы зарубежных изданий), в которых изложены численные методы, адаптированные к современным компьютерам. К сожалению, такие учебники издаются недостаточными тиражами,

4 имеют высокую розничную цену и поэтому недоступны подавляющему числу студентов.
По мнению авторов, которые преподают курс численных методов на физическом факультете ННГУ, студенты нуждаются в учебном пособии, в котором должны быть изложены самые элементарные методы, необходимые начинающему физику. Этот минимальный набор должен, прежде всего, содержать простейшие методы приближенного вычисления значений функций: интерполяцию и аппроксимацию. В набор должны быть включены методы численного интегрирования и дифференцирования. Многие важные практические задачи физики требуют применения численных методов решения нелинейных уравнений и систем линейных уравнений.
Для логической связности изложения оказалось необходимым включить в пособие разделы вычисления конечных разностей, определителей матриц и обратных матриц.
При отборе материала авторы ограничивались самыми элементарными методами, которые обеспечивают приемлемую погрешность при реализации этих методов на персональных компьютерах.
Настоящее издание не содержит методов решения дифференциальных уравнений, так как, по мнению авторов, эта тема требует подробной разработки и изложения в отдельном учебном пособии. Также авторы отказались от систематического изложения в данном издании теории погрешностей, так как по этой теме уже опубликовано большое количество удачных учебников и методических указаний.
Предлагаемое учебное пособие ориентировано в первую очередь на студентов, магистрантов и аспирантов физического факультета. Не возбраняется использование данного издания школьниками, занимающимися научной работой на физическом факультете в рамках научного общества учащихся.
Авторы надеются, что настоящее учебное пособие будет полезным и для студентов других факультетов физико-математических и естественно-научных направлений.
В процессе подготовки данного издания авторам оказывали помощь многие сотрудники физического факультета ННГУ. Авторы благодарны всем, кто взял на себя труд ознакомится с рукописью и дать полезные советы. Особую благодарность авторы выражают профессорам В.Р.
Фидельману, Е.В. Чупрунову, доцентам В.А. Бурдову, Н.С. Будникову,

5
Г.М. Максимовой, О.А. Морозову, ассистенту М.О. Марычеву и инженеру Е.А. Конькову. Авторы признательны рецензентам данной работы – сотрудникам кафедры теоретической механики механико- математического факультета ННГУ, в первую очередь декану механико- математического факультета, д.ф.-м.н. А.К. Любимову, доцентам А.Ф.
Ляхову и Д.Т. Чекмареву, а также доценту кафедры математического обеспечения ЭВМ факультета вычмслительной математики и кибернетики, к.ф.-м.н. В.А.Гришагину за многочисленные ценные рекомендации.

6
Глава 1. КОНЕЧНЫЕ РАЗНОСТИ
Различные численные методы используют величины, которые называются конечными разностями.
Пусть y = f (x) – некоторая заданная функция. Обозначим
∆
x
≡ h постоянное конечное приращение аргумента (шаг).
Определение. Величина
∆y ≡ ∆ f (x) = f (x+∆x)
−
f
(x)
≡ f (x+h)
−
f
(x)

(1.1) называется первой конечной разностью функции y = f (x).
При заданном постоянном шаге h конечная разность является функцией аргумента x.
Конечные разности высших порядков определяются индуктивно:
∆
n
y =
∆(∆
n
−1
y
), n = 2, 3, ...

(1.2)
В частности, согласно определению (1.2), вторая конечная разность представляется как разность первых конечных разностей
∆
2
y
=
∆(∆y) = ∆ (f (x+h)
−
f
(x)) и может быть выражена в следующем виде через значения исходной функции:
∆
2
y = f
(x+2
∆x)
−

2 f (x+
∆x) + f (x)

(1.3)
Пример 1. Рассмотрим степенную функцию y = x
3

и последовательно вычислим ее конечные разности различных порядков:

∆y = 3x
2
h +
3xh
2
+ h
3
,
∆
2
y =
6xh
2
+
6 h
3
,
∆
3
y =
6 h
3
,

∆
n
y =
0 (n
≥ 3).
Приведенный пример демонстрирует, что конечная разность произвольного порядка является, вообще говоря, функцией аргумента x и содержит постоянный параметр h. Численное значение любой конечной разности относится к конкретной точке x (конечно, кроме тех случаев, когда конечная разность является константой).

7
Пример 1 со степенной функцией показывает, что конечные разности такой функции постепенно понижают свой показатель степени каждый раз на единицу. Так как показатель этой степенной функции положительный, то некоторая конечная разность становится уже константой (в приведенном примере третья), а следующие конечные разности тождественно равны нулю.
Аналогичным свойством последовательного понижения степени обладают конечные разности полиномов. Пусть полином степени n представлен в стандартной форме:
P
n
(x) =
∑
=
⋅
n
i
i
i
x
c
0
,

(1.4) где c
i
(i = 0, 1, …, n)
− известные числовые коэффициенты.
Пользуясь определением (1.1), запишем первую конечную разность этого полинома:
∆P
n
(x) = P
n
(x+h)
− P
n
(x) =
∑
=
n
i
i
c
0
[(x+h)
i
− x
i
].
(1.5)
Круглые скобки раскрываем по биному Ньютона. В каждом i-м слагаемом суммы (1.5) взаимно уничтожаются степени x
i
со старшим показателем i. В последнем, n-м слагаемом суммы (1.5) уничтожится член со степенью x
n
, а в остальных слагаемых он отсутствует.
Следовательно, первая конечная разность
∆P
n
(x) есть полином степени
(n
−1).
Соберем члены с одинаковыми степенями аргумента x в сумме (1.5) и перепишем конечную разность (1.5) в виде:
∆P
n
(x) =
∑
−
=
⋅
1 0
n
i
i
i
x
b
,

(1.6) где b
i
(i = 0, 1, …, n
−1) − определенные коэффициенты, которые выражаются через величины c
i
и шаг h.
Для дальнейшего нам потребуется коэффициент b
n
−
1

при старшей степени аргумента x
n
−
1
. Преобразования суммы (1.5) к виду (1.6) дают, что b
n
−
1

равен nhc
n

8
Теперь найдем вторую конечную разность исходного полинома
P
n
(x). Согласно определению (1.2) нетрудно получить, что вторая конечная разность
∆
2
P
n
(x) есть полином степени (n
−2), который можно представить в виде следующей суммы с коэффициентами d
i

(i = 0, 1, …,
n
−2):
∆
2
P
n
(x) =
2 0
∑
−
=
⋅
n
i
i
i
x
d

(1.7)
Расчет коэффициента d
n
−
2
при старшем члене полинома (1.7) дает значение:
d
n
−
2
= (n
− 1) h b
n
−
1
= n
(n
− 1) h
2
c
n

(1.8)
Продолжая рассчитывать конечные разности более высоких порядков, получим, что n-я конечная разность исходного полинома (1.4) равна постоянной величине:
∆
n
P
n
(x) = n! h
n
c
n

(1.9)
Очевидно, что следующие конечные разности тождественно равны нулю:
∆
k
P
n
(x) = 0, где k > n.
Вычисления конечных разностей можно рассматривать как действие некоторого оператора
∆ на функцию f (x), которое определяется соотношением (1.1):
∆ [f (x)] = f (x+h)
−
f
(x).
Непосредственно из определения доказывается свойство линейности оператора
∆:
∆(u + v) = ∆u + ∆v , ∆(Cy) = C∆y,


(1.10)

где u, v и y
−
произвольные функции аргумента x, а С – константа.
Также из определения оператора
∆ следует полезное свойство конечных разностей:
∆
m
(
∆
n
y
) =
∆
m+n
y .

(1.11)

Для общности последующих выражений доопределим понятие конечной разности нулевого порядка:

9
∆
0
y
= y.

(1.12)

Теперь, пользуясь определением оператора
∆, можно записать:
f
(x + h) = f (x) +
∆ f (x)
или
f
(x + h) = (1 +
∆) f (x),

где символ
∆ используется как оператор.
Использование последней формулы n раз дает соотношение:
f
(x + nh) = (1 +
∆)
n
f (x) .

(1.13)
Степень круглой скобки можно выразить по биному Ньютона:
f
(x + nh) =
∑
=
∆
⋅
n
k
k
k
n
x
f
C
0
)
(
,
(1.14) где
k
n
C
− биномиальный коэффициент (число сочетаний из n по k).
Последнее выражение означает, что значения произвольной функции в (n + 1) равноотстоящих точках выражаются через конечные разности порядков от 0 до n.
Наконец, найдем общее выражение для n-й конечной разности произвольной функции f(x). Для этого воспользуемся очевидным операторным тождеством:
∆ = (1 + ∆)
−

1.
Возведем это тождество в n-ю степень, и подействуем им на произвольную функцию f(x), причем в правой части используем бином
Ньютона:
∆
n
f
(x) = [(1 +
∆)
−

1]
n
f (x) =
= (1 +
∆)
n
⋅ f (x)
−

1
n
C
(1 +
∆)
n
−
1
f (x) +
2
n
C
(1 +
∆)
n
−
2
f (x)
−
...
+ (
−1)
n
f (x).
Используя уравнение (1.13), представим выражение n-й конечной разности функции f(x) в виде следующей знакопеременной суммы:
∆
n
f
(x) = f (x+nh)
−

1
n
C f
[x+(n
−
1)h] +
2
n
C f
[x+(n
−
2)h]
−
...
(
−
1)
n
f
(x).

10
(1.15)

То же самое выражение можно получить, n-кратно применяя исходные определения (1.1) и (1.2).
Следовательно, n-я конечная разность любой функции f(x)
выражается через n последовательных значений этой функции,
вычисляемых в равноотстоящих точках, интервалы между
которыми задаются постоянным шагом h.
Часто в задачах, решаемых численными методами, некоторая функция f(x) задается таблицей значений y
i
= f(x
i
) в нескольких точках x
i

(i = =1, ... , n, где n – определенное конечное число). Тогда конечные разности заданной функции в точках x
i
удобно вычислять по определению (1.1) и рекуррентному соотношению (1.2) и при этом размещать в таблице специального вида, приведенной в следующем примере.
Пример 2. Функция f (x) задана в десяти равноотстоящих точках x
i

(i= 1, ... , 10), которые указаны во втором столбце таблицы 1.1. В третьем столбце записаны соответствующие значения функции y
i
= f
(x
i
). В первом столбце приведены индексы значений (порядковые номера).
Таблица 1.1
i
x
i

y
i

∆y
i
∆
2
y
i
∆
3
y
i
∆
4
y
i
1 0,1 2,9850
-0,0448
-0,0294 0,0008 0,0001 2
0,2 2,9402
-0,0742
-0,0286 0,0009 0,0006 3
0,3 2,8660
-0,1028
-0,0277 0,0015
-0,0001 4
0,4 2,7632
-0,1305
-0,0262 0,0014 0,0005 5
0,5 2,6327
-0,1567
-0,0248 0,0019 0,0001 6
0,6 2,4760
-0,1815
-0,0229 0,0020 0,0003 7
0,7 2,2945
-0,2044
-0,0209 0,0023 8
0,8 2,0901
-0,2253
-0,0186

9 0,9 1,8648
-0,2439

10 1,0 1,6209


Остальные столбцы служат для размещения конечных разностей от первого до четвертого порядков, вычисленных в точках x
i
Каждая конечная разность, расположенная в клетке таблицы 1.1, получена как разность значений в соседнем столбце слева, причем вычитаемым является число в той же строке, а уменьшаемым – число в

11 следующей. Пустой правый нижний угол таблицы объясняется тем, что исходных данных недостаточно для расчета соответствующих конечных разностей по определению (1.2). Согласно выражению (1.15), для вычисления n-й конечной разности функции f(x) в некоторой точке x
0
требуются n значений этой функции: в точке x
0
и еще в (n–1) равноотстоящих точках x
i
= x
0
+ i h (i = 1, …, n – 1).
Конечные разности, определенные формулами (1.1) и (1.2) и рассмотренные в данном параграфе, строго математически называются правыми конечными разностями. Для решения большинства прикладных задач вполне достаточно таких конечных разностей.
Справедливости ради заметим, что в математике определяются и используются также левые и центральные конечные разности. Для знакомства с ними отсылаем читателя к более полным курсам численных методов и к специальной литературе [1,3,4].

12
Глава 2. ИНТЕРПОЛЯЦИЯ
§ 2.1. Постановка проблемы интерполяции
Одной из важнейших проблем вычислительной математики является приближение функций. Часто при решении прикладных задач приходится сталкиваться со следующей ситуацией.
Из теоретических соображений следует, что некоторая величина y является функцией f(x) непрерывного аргумента x, причем явный вид функции f(x) неизвестен. В то же время известно конечное количество значений функции y
i
на ограниченном интервале аргумента x
∈ [a, b] в точках x
i

(i = 0, 1, ... , n). Эти точки x
i

(i = 0, 1, ... , n) называются узлами.
Иначе говоря, исходная информация об исследуемой функции может быть записана в виде таблицы, содержащей n + 1 упорядоченных пар чисел.
Таблица 2.1

x
0
x
1
…
x
n
y
0
= f(x
0
)
y
1
= f(x
1
)
…
y
n
= f(x
n
)
Пример графического изображения исходных данных таблицы 2.1 приведен на рис. 2.1.






Рис. 2.1. Пример графика исходных данных, предназначенных для интерполяции. Черными кружками обозначены значения y
i
функции
f
(x) в узлах интерполяции x
i
(i = 0, 1, ... , n).
y=f
(x)
x
x
i
y
i
a
=
x
0
b
=
x
n

13
Проблема заключается в вычислении значения функции y = f (x) для произвольного аргумента x из интервала [a, b], но не совпадающего ни с одним из узлов x
i
(i = 0, 1, ... , n). Численные методы решения поставленной проблемы можно разделить на две группы, называемые интерполяцией
и
аппроксимацией.
Методы интерполяции рассмотрены в данной главе, аппроксимации посвящена следующая глава.
Принцип интерполяции заключается в построении новой функции
F
(x), которая называется интерполирующей
функцией
или интерполянтом
. Функция F(x) принадлежит к определенному классу и в точках x
i

(i = 0, 1, ... , n) принимает те же значения, что и функция f(x)
F
(x
i
) = y
i
=
f(x
i
) ,
i
= 0, 1, ... , n .
(2.1)
Значения аргумента x
i

(i = 0, 1, ... , n) при этом называются узлами

Каталог: books -> met files
met files -> Учебно-методическое пособие предназначено для студентов института биологии и биомедицины, специализирующихся на кафедре молекулярной биологии и биомедицины, обучающихся по направление подготовки: 06. 03
met files -> Л. В. Ошевенский, врач высшей категории
met files -> Н. И. Лобачевского О. Ю. Ангелова Е. М. Дмитриева маркетинг. Рабочая тетрадь учебно-методическое пособие
met files -> Методические указания Курс: Физиология человека и животных Раздел: Функциональные системы Нижний Новгород 2007
met files -> А. А. Пономаренко в настоящем пособии изложены методы оказания первой доврачебной помощи на месте происшествия. Приведены основы и принципы базовых реанимационных мероприятий. Приведены алгоритмы действий на месте прои
met files -> Председатель методической комиссии биологического факультета ннгу, д п. н
met files -> Физиология эмоций
met files -> Интерактивные формы и методы обучения в высшей школе
met files -> Учебная дисциплина: Методы анализа документов в социологии Специальности, направления: Социология 040201, Социальная работа 040101 Нижний Новгород 2010