Численные методы и математическое моделирование

А.А. БАЛАКИН  

ЧИСЛЕННЫЕ МЕТОДЫ 
И МАТЕМАТИЧЕСКОЕ 
МОДЕЛИРОВАНИЕ

À.À. Áàëàêèí
×èñëåííûå ìåòîäû è ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå: Ó÷åáíîå ïîñîáèå / À.À. Áàëàêèí – Äîëãîïðóäíûé: Èçäàòåëüñêèé Äîì «Èíòåëëåêò», 2022. – 288 ñ.

ISBN 978-5-91559-297-0

Ó÷åáíîå ïîñîáèå ïî âû÷èñëèòåëüíîé ìàòåìàòèêå íà îñíîâå
êóðñà ëåêöèé àâòîðà íà ôàêóëüòåòå Âûñøàÿ øêîëà îáùåé è
ïðèêëàäíîé ôèçèêè Íèæåãîðîäñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà, áàçîâîãî ôàêóëüòåòà Èíñòèòóòà ïðèêëàäíîé ôèçèêè ÐÀÍ.
Êíèãà îõâàòûâàåò ýíöèêëîïåäè÷åñêè øèðîêèé êðóã âîïðîñîâ,
îòíîñÿùèõñÿ ê ïðèáëèæåííîìó ðåøåíèþ ìíîãî÷èñëåííûõ çàäà÷. Îðèåíòèðîâàííîñòü íà ïðèêëàäíûå çàäà÷è, âîçíèêàþùèå â
ðàçëè÷íûõ îáëàñòÿõ íàóêè è òåõíèêè, îïðåäåëèëà ñòèëü ïîäà÷è
ìàòåðèàëà. Îñíîâíîé óïîð â êíèãå ñäåëàí íà èçëîæåíèå èäåéíîé ÷àñòè, íà îïðåäåëåíèå âû÷èñëèòåëüíîé ñëîæíîñòè, óñòîé÷èâîñòè è ïðèìåíèìîñòè òîãî èëè èíîãî àëãîðèòìà, îñîáåííîñòåé èõ èñïîëüçîâàíèÿ â íåñòàíäàðòíûõ çàäà÷àõ.
Ó÷åáíîå ïîñîáèå ðàññ÷èòàíî íà ñòóäåíòîâ, àñïèðàíòîâ è ïðåïîäàâàòåëåé ôèçè÷åñêèõ è èíæåíåðíûõ ñïåöèàëüíîñòåé, èíæåíåðîâ è íàó÷íûõ ðàáîòíèêîâ, à òàêæå âñåõ èíòåðåñóþùèõñÿ
÷èñëåííûìè ìåòîäàìè è ìàòåìàòè÷åñêèì ìîäåëèðîâàíèåì.

© 2019, À.À. Áàëàêèí
© 2022, ÎÎÎ Èçäàòåëüñêèé Äîì
«Èíòåëëåêò», îðèãèíàë-ìàêåò,
îôîðìëåíèå

ISBN 978-5-91559-297-0

ОГЛАВЛЕНИЕ

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9

Глава 1. Общие вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . .
11

1.1. Численное моделирование . . . . . . . . . . . . . . . . . . . . . . . .
11
1.2. Погрешность вычислений . . . . . . . . . . . . . . . . . . . . . . . .
16
1.3. Корректность вычислений . . . . . . . . . . . . . . . . . . . . . . . .
19
1.4. Элементарные вычисления . . . . . . . . . . . . . . . . . . . . . . . .
21
1.4.1. Возведение в степень . . . . . . . . . . . . . . . . . . . . . . .
21
1.4.2. Полиномы и цепные дроби . . . . . . . . . . . . . . . . . . .
21
1.4.3. Повышение сходимости рядов . . . . . . . . . . . . . . . . .
23
1.4.4. Рекуррентные соотношения и суммы . . . . . . . . . . . .
24

Глава 2. Системы линейных уравнений . . . . . . . . . . . . . . . .
27

2.1. Определения и свойства матриц . . . . . . . . . . . . . . . . . . . .
28
2.2. Метод исключения переменных . . . . . . . . . . . . . . . . . . . .
29
2.3. Улучшения метода Гаусса . . . . . . . . . . . . . . . . . . . . . . . .
33
2.4. Разреженные матрицы . . . . . . . . . . . . . . . . . . . . . . . . . .
35
2.4.1. Прогонка для трехдиагональных матриц . . . . . . . . . .
35
2.4.2. Прогонка для пятидиагональных матриц . . . . . . . . . .
36
2.4.3. Формула Шермана–Моррисона . . . . . . . . . . . . . . . .
37
2.4.4. Циклическая прогонка . . . . . . . . . . . . . . . . . . . . . .
38
2.5. Итерационные методы . . . . . . . . . . . . . . . . . . . . . . . . . .
40
2.5.1. Метод простой итерации. . . . . . . . . . . . . . . . . . . . .
40
2.5.2. Псевдо-собственные числа . . . . . . . . . . . . . . . . . . .
41
2.5.3. Метод Гаусса–Зайделя . . . . . . . . . . . . . . . . . . . . . .
42
2.6. Метод отражений . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44

Оглавление

Глава 3. Собственные значения и векторы . . . . . . . . . . . . . .
46

3.1. Элементы общей теории . . . . . . . . . . . . . . . . . . . . . . . . .
46
3.2. Метод Якоби . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
3.3. Метод QR-итераций . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
3.4. Частичная проблема собственных значений . . . . . . . . . . . .
53
3.4.1. Метод линеаризации . . . . . . . . . . . . . . . . . . . . . . .
53
3.4.2. Степенной метод . . . . . . . . . . . . . . . . . . . . . . . . . .
54

Глава 4. Системы нелинейных уравнений. . . . . . . . . . . . . . .
56

4.1. Локализация корней. . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
4.2. Интервальные методы . . . . . . . . . . . . . . . . . . . . . . . . . .
57
4.2.1. Метод деления пополам . . . . . . . . . . . . . . . . . . . . .
60
4.2.2. Методы хорд и прочие . . . . . . . . . . . . . . . . . . . . . .
61
4.3. Метод простых итераций . . . . . . . . . . . . . . . . . . . . . . . .
62
4.4. Метод Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
4.4.1. Метод секущих . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
4.4.2. Метод Мюллера . . . . . . . . . . . . . . . . . . . . . . . . . .
66
4.5. Метод спуска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
4.6. Улучшение метода Ньютона . . . . . . . . . . . . . . . . . . . . . .
68
4.7. Сравнение сходимости методов . . . . . . . . . . . . . . . . . . . .
69
4.8. Корни полиномов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71

Глава 5. Поиск минимума функции . . . . . . . . . . . . . . . . . . .
73

5.1. Метод золотого сечения . . . . . . . . . . . . . . . . . . . . . . . . .
73
5.2. Метод парабол . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
5.3. Метод Брента . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
5.4. Метод спуска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
5.5. Метод переменной метрики . . . . . . . . . . . . . . . . . . . . . . .
79
5.6. Сопряженные направления . . . . . . . . . . . . . . . . . . . . . . .
81
5.7. Метод оврагов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
5.8. Минимизация с ограничениями . . . . . . . . . . . . . . . . . . . .
83

Глава 6. Интерполяция данных . . . . . . . . . . . . . . . . . . . . . .
85

6.1. Линейная интерполяция . . . . . . . . . . . . . . . . . . . . . . . . .
86
6.2. Интерполяция полиномами . . . . . . . . . . . . . . . . . . . . . . .
86
6.3. Точность интерполяции полиномами . . . . . . . . . . . . . . . . .
90
6.4. Полиномы Чебышева . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
6.5. Рациональная интерполяция . . . . . . . . . . . . . . . . . . . . . .
96

Оглавление
5

6.6. Локальная интерполяция . . . . . . . . . . . . . . . . . . . . . . . .
99
6.6.1. Табличные функции . . . . . . . . . . . . . . . . . . . . . . . .
100
6.6.2. Кусочно-линейная интерполяция . . . . . . . . . . . . . . .
101
6.6.3. Триангуляция Делоне . . . . . . . . . . . . . . . . . . . . . . .
102
6.6.4. Локальный сплайн . . . . . . . . . . . . . . . . . . . . . . . . .
104
6.7. Глобальный сплайн . . . . . . . . . . . . . . . . . . . . . . . . . . . .
105
6.8. Многомерная интерполяция . . . . . . . . . . . . . . . . . . . . . . .
107
6.9. Кривые Безье . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
109

Глава 7. Аппроксимация функций . . . . . . . . . . . . . . . . . . . .
111

7.1. Среднеквадратичная аппроксимация . . . . . . . . . . . . . . . . .
112
7.2. Метод наименьших квадратов . . . . . . . . . . . . . . . . . . . . .
113
7.3. Линейная регрессия . . . . . . . . . . . . . . . . . . . . . . . . . . . .
114
7.4. Сглаживание данных . . . . . . . . . . . . . . . . . . . . . . . . . . .
116
7.5. Логистическая регрессия . . . . . . . . . . . . . . . . . . . . . . . .
117
7.6. Метод итерированного веса . . . . . . . . . . . . . . . . . . . . . . .
119
7.7. Аппроксимация Паде . . . . . . . . . . . . . . . . . . . . . . . . . . .
119
7.8. Выбросоустойчивая аппроксимация . . . . . . . . . . . . . . . . . .
123

Глава 8. Численное дифференцирование . . . . . . . . . . . . . . .
125

8.1. Проблемы численного дифференцирования . . . . . . . . . . . .
125
8.2. Использование интерполяции . . . . . . . . . . . . . . . . . . . . .
126
8.3. Метод Рунге–Ромберга . . . . . . . . . . . . . . . . . . . . . . . . . .
129
8.4. Регуляризация дифференцирования . . . . . . . . . . . . . . . . .
130
8.5. Вычисление лапласиана . . . . . . . . . . . . . . . . . . . . . . . . .
131

Глава 9. Численное интегрирование. . . . . . . . . . . . . . . . . . .
133

9.1. Формулы трапеций и средних . . . . . . . . . . . . . . . . . . . . .
134
9.2. Формулы Симпсона и Боде . . . . . . . . . . . . . . . . . . . . . . .
136
9.3. Формула Эйлера–Маклорена . . . . . . . . . . . . . . . . . . . . . .
138
9.4. Процесс Эйткена . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
139
9.5. Формула Гаусса–Кристоффеля . . . . . . . . . . . . . . . . . . . . .
141
9.6. Метод Филона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
143
9.7. Интегралы с особенностями . . . . . . . . . . . . . . . . . . . . . .
144
9.7.1. Переменный предел интегрирования . . . . . . . . . . . . .
144
9.7.2. Несобственные интегралы . . . . . . . . . . . . . . . . . . . .
145
9.7.3. Кратные интегралы . . . . . . . . . . . . . . . . . . . . . . . .
146
9.8. Метод Монте-Карло . . . . . . . . . . . . . . . . . . . . . . . . . . . .
147

Оглавление

Глава 10. Дискретные преобразования . . . . . . . . . . . . . . . . .
150

10.1. Дискретное преобразование Фурье . . . . . . . . . . . . . . . . . .
150
10.2. Быстрое преобразование Фурье . . . . . . . . . . . . . . . . . . . .
154
10.3. Варианты преобразования Фурье . . . . . . . . . . . . . . . . . . .
155
10.3.1. Преобразование Фурье действительных функций. . . .
155
10.3.2. Синус-преобразование . . . . . . . . . . . . . . . . . . . . . .
156
10.3.3. Косинус-преобразования . . . . . . . . . . . . . . . . . . . .
157
10.4. Применение преобразования Фурье . . . . . . . . . . . . . . . . . .
159
10.4.1. Огибающая функции. . . . . . . . . . . . . . . . . . . . . . .
159
10.4.2. Тригонометрическая интерполяция . . . . . . . . . . . . .
159
10.4.3. Свертка функций . . . . . . . . . . . . . . . . . . . . . . . . .
160
10.4.4. Улучшение изображений . . . . . . . . . . . . . . . . . . . .
161
10.4.5. Оптимальная фильтрация . . . . . . . . . . . . . . . . . . .
163
10.5. Оконное преобразование Фурье . . . . . . . . . . . . . . . . . . . .
163
10.6. Вейвлет-преобразование . . . . . . . . . . . . . . . . . . . . . . . . .
166

Глава 11. Обыкновенные дифференциальные уравнения . . . .
170

11.1. Общие сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
170
11.2. Метод Эйлера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
172
11.3. Метод Рунге–Кутта 2-го порядка . . . . . . . . . . . . . . . . . . .
175
11.4. Метод Рунге–Кутта 4-го порядка . . . . . . . . . . . . . . . . . . .
176
11.5. Метод Рунге–Кутта с подбором шага . . . . . . . . . . . . . . . .
177
11.6. Регуляризация уравнений . . . . . . . . . . . . . . . . . . . . . . . .
178
11.7. Быстропеременная правая часть . . . . . . . . . . . . . . . . . . . .
181
11.7.1. Метод усреднения . . . . . . . . . . . . . . . . . . . . . . . .
182
11.7.2. Быстрые и медленные движения . . . . . . . . . . . . . . .
183
11.7.3. Особые точки . . . . . . . . . . . . . . . . . . . . . . . . . . .
184
11.8. Специальные методы . . . . . . . . . . . . . . . . . . . . . . . . . . .
185
11.8.1. Метод Адамса . . . . . . . . . . . . . . . . . . . . . . . . . . .
185
11.8.2. Уравнения 2-го порядка . . . . . . . . . . . . . . . . . . . . .
187
11.8.3. Неявные схемы . . . . . . . . . . . . . . . . . . . . . . . . . .
188
11.8.4. Метод Пикара . . . . . . . . . . . . . . . . . . . . . . . . . . .
188

Глава 12. Уравнения в частных производных . . . . . . . . . . . .
191

12.1. Классификация уравнений . . . . . . . . . . . . . . . . . . . . . . . .
191
12.2. Точные решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
194
12.3. Вариационное приближение . . . . . . . . . . . . . . . . . . . . . . .
195
12.4. Сеточные методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
198

Оглавление
7

12.5. Метод операторной экспоненты . . . . . . . . . . . . . . . . . . . .
200
12.6. Разностные методы . . . . . . . . . . . . . . . . . . . . . . . . . . . .
202
12.6.1. Метод разностной аппроксимации . . . . . . . . . . . . . .
203
12.6.2. Интегро-интерполяционный метод . . . . . . . . . . . . . .
204
12.6.3. Метод неопределенных коэффициентов . . . . . . . . . .
206
12.7. Устойчивость схем . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
207
12.7.1. Метод разделения переменных . . . . . . . . . . . . . . . .
209
12.7.2. Принцип максимума . . . . . . . . . . . . . . . . . . . . . . .
212
12.7.3. Примеры неустойчивостей . . . . . . . . . . . . . . . . . . .
213
12.8. Сходимость схем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
215
12.9. Явные разностные схемы . . . . . . . . . . . . . . . . . . . . . . . .
218
12.10. Граничные условия . . . . . . . . . . . . . . . . . . . . . . . . . . . .
221
12.11. Параболические уравнения . . . . . . . . . . . . . . . . . . . . . . .
226
12.12. Уравнение переноса . . . . . . . . . . . . . . . . . . . . . . . . . . . .
228
12.12.1. Схемы бегущего счета. . . . . . . . . . . . . . . . . . . . .
231
12.12.2. Монотонные схемы . . . . . . . . . . . . . . . . . . . . . . .
233
12.12.3. Диссипативные схемы . . . . . . . . . . . . . . . . . . . . .
234
12.12.4. Ложная сходимость . . . . . . . . . . . . . . . . . . . . . .
235
12.13. Волновое уравнение . . . . . . . . . . . . . . . . . . . . . . . . . . .
237
12.13.1. Схема «крест» . . . . . . . . . . . . . . . . . . . . . . . . . .
238
12.13.2. Неявная схема . . . . . . . . . . . . . . . . . . . . . . . . . .
239
12.13.3. Двухслойная акустическая схема . . . . . . . . . . . . .
240
12.13.4. Инварианты . . . . . . . . . . . . . . . . . . . . . . . . . . . .
242
12.14. Уравнения гидродинамики . . . . . . . . . . . . . . . . . . . . . . .
242
12.14.1. Схема расчета . . . . . . . . . . . . . . . . . . . . . . . . . .
244
12.14.2. Метод частиц-в-ячейках . . . . . . . . . . . . . . . . . . .
246
12.14.3. Метод Лакса–Вендроффа . . . . . . . . . . . . . . . . . .
248

Глава 13. Краевые задачи . . . . . . . . . . . . . . . . . . . . . . . . . .
250

13.1. Метод стрельбы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
250
13.2. Метод установления . . . . . . . . . . . . . . . . . . . . . . . . . . . .
252
13.3. Вариационный метод . . . . . . . . . . . . . . . . . . . . . . . . . . .
256
13.4. Обоснование вариационного метода . . . . . . . . . . . . . . . . .
259
13.5. Метод конечных элементов . . . . . . . . . . . . . . . . . . . . . . .
261

Глава 14. Интегральные уравнения . . . . . . . . . . . . . . . . . . .
264

14.1. Виды интегральных уравнений . . . . . . . . . . . . . . . . . . . . .
265
14.2. Разностный метод . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
266

Оглавление

14.3. Метод итераций. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
267
14.4. Замена вырожденным ядром . . . . . . . . . . . . . . . . . . . . . .
268
14.5. Регуляризация некорректных задач . . . . . . . . . . . . . . . . . .
270

Приложение A. Случайные числа . . . . . . . . . . . . . . . . . . .
272

A.1. Простейшие генераторы . . . . . . . . . . . . . . . . . . . . . . . . .
272
A.2. Современные генераторы . . . . . . . . . . . . . . . . . . . . . . . .
274
A.3. Распределения случайных чисел . . . . . . . . . . . . . . . . . . .
276
A.3.1. Метод трансформаций . . . . . . . . . . . . . . . . . . . . . .
276
A.3.2. Метод отношения однородных . . . . . . . . . . . . . . . . .
277

Приложение B. Элементы статистической обработки данных
279

B.1. Моменты распределения . . . . . . . . . . . . . . . . . . . . . . . . .
279
B.2. Моменты функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
281
B.3. Корреляционная функция . . . . . . . . . . . . . . . . . . . . . . . .
283

Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
285

ПРЕДИСЛОВИЕ

Курс вычислительной математики является одним из основных
в рамках базового образования для студентов-физиков. Причина
такого внимания состоит в том, что огромное многообразие физических явлений описывается схожими, а зачастую и одинаковыми математическими моделями. Появление возможности быстрого поиска их приближенных решений дало огромный толчок в
развитии естественных наук, и в первую очередь физики. Многие
считавшиеся труднорешаемыми задачи теперь являются рутинной
операцией. Более того, усовершенствование компьютерной техники
и численных методов послужило одной из причин бурного развития многих областей нелинейной физики: стохастики, солитоники,
теории коллапсов, турбулентности и много другого.
В настоящее время есть множество книг по вычислительной
математике и численным методам. Однако большинство из них написано многие десятилетия назад. Соответственно, классические
методы вычислительной математики уже реализованы в значительном числе свободных и проприетарных библиотек функций. Их повторная программная реализация имеет смысл только для очень
простых алгоритмов вычислений, а в большинстве случаев целесообразно использовать уже оптимизированные библиотечные функции для более сложных алгоритмов решения задач линейной алгебры, быстрого преобразования Фурье, решения многомерных систем
нелинейных уравнений, задач оптимизации (нахождения минимума) функции многих переменных и других.
В данной книге основной упор сделан на изложение идейной
части, на определения вычислительной сложности, устойчивости
и применимости того или иного алгоритма, на особенности их использования в нестандартных задачах, оставляя строгое обоснование и оптимизацию на долю классических книг по вычислитель

Предисловие

ной математике. Кроме того, в книге изложены довольно современные методы решения дифференциальных уравнений, которые появились в последние 20–30 лет и попросту не успели войти в классические учебники. В первую очередь к таким методам относятся
метод операторной экспоненты (разд. 12.5), методы регуляризации
дифференциальных уравнений (разд. 11.6) и явные методы решения уравнений в частных производных (разд. 12.9), допускающие
эффективное распараллеливание даже в вычислительных системах
с распределенной памятью (компьютерных кластерах). Наконец,
в книгу включены отдельные методы вычислительной геометрии
(разд. 6.6), позволяющие элегантно решать ряд задач интерполяции.
Книга состоит из 14 глав, которые условно можно разбить на
три крупных блока: методы решения систем линейных и нелинейных уравнений (главы 2–5), методы аппроксимации функций и операторов (главы 6–10), методы решения дифференциальных и интегро-дифференциальных уравнений (главы 11–14). В приложениях
рассмотрены вспомогательные вопросы о генерации псевдослучайных чисел и элементах статистической обработки данных. Каждую
из глав книги можно читать независимо. Однако в последующих
главах используются классические методы, представленные ранее
и доступные в целом ряде программных пакетов и библиотек.
Большинство представленных численных методов можно условно разбить на две большие группы: сеточные и вариационные. Сеточные методы основаны на замене непрерывной функции ее дискретным аналогом, определенным в конечном числе точек координат. Это позволяет построить интерполяционную формулу и заменить точные производные на производные этой формулы при построении численной схемы решения. Различные варианты сеточных методов представлены в главах 6, 8–14. Вариационные методы, наоборот, основаны на приближении решения заданной функцией, зависящей от небольшого числа параметров (часто порядка 10). Цель вариационных методов состоит в поиске оптимальных параметров, минимизирующих ошибку аппроксимации решения. Основным недостатком вариационных методов является сложность выбора подходящей аппроксимирующей функции, так как
именно ее свойства будут определять вид получившегося приближенного решения. Поэтому вариационные методы в основном используют при поиске решений более трудоемких задач (главы 7, 13
и 14), в которых классические сеточные методы слишком медленны.
Автор благодарен Н. Н. Кралиной и И. А. Кокориной за внимательное прочтение книги и помощь в ее оформлении. Все рисунки
рассчитаны и построены с помощью пакета программ MathGL.