Начала вычислительных методов для физиков. От традиционных до вейвлет- анализа

А.Д. ЮНАКОВСКИЙ 
НАЧАЛА ВЫЧИСЛИТЕЛЬНЫХ 
МЕТОДОВ ДЛЯ ФИЗИКОВ

ОТ ТРАДИЦИОННЫХ ДО ВЕЙВЛЕТ-АНАЛИЗА

Второе издание

À.Ä. Þíàêîâñêèé
Íà÷àëà âû÷èñëèòåëüíûõ ìåòîäîâ äëÿ ôèçèêîâ. Îò òðàäèöèîííûõ äî âåéâëåò-àíàëèçà: Ó÷åáíîå ïîñîáèå / À.Ä. Þíàêîâñêèé –
2-å èçä. – Äîëãîïðóäíûé: Èçäàòåëüñêèé Äîì «Èíòåëëåêò», 2023. –
320 ñ.

ISBN 978-5-91559-309-0

Íàó÷èòüñÿ ñ÷èòàòü – îäíà èõ îñíîâíûõ çàäà÷ ôèçèêà, âîîðóæèâøåãîñÿ êîìïüþòåðîì.  íàñòîÿùåå âðåìÿ øèðîêî èñïîëüçóåòñÿ ðàçëè÷íûå ïàêåòû  ïðîãðàììíîãî îáåñïå÷åíèÿ, à èõ íåâîçìîæíî ïðèìåíÿòü
ãðàìîòíî è ýôôåêòèâíî áåç ãëóáîêîãî ïîíèìàíèÿ ÷èñëåííûõ ìåòîäîâ, íà êîòîðûõ âõîäÿùèå â ýòè ïàêåòû  ïðîãðàììû îñíîâàíû. Îñíîâíàÿ öåëü êíèãè ñîñòîèò â ðàññìîòðåíèè ïîíÿòíûõ è äîñòàòî÷íî
ïðîñòûõ â íàïèñàíèè àëãîðèòìîâ, îðèåíòèðîâàííûõ ãëàâíûì îáðàçîì íà ðåøåíèå òèïè÷íûõ çàäà÷ òåîðåòè÷åñêîé ôèçèêè è ÿâëÿþùèõñÿ, áåçóñëîâíî, íåîáõîäèìîé ÷àñòüþ àðñåíàëà ëþáîãî ôèçèêà-òåîðåòèêà. Îòîáðàíî ñðàâíèòåëüíî íåáîëüøîå ÷èñëî ìåòîäîâ, õîðîøî çàðåêîìåíäîâàâøèõ ñåáÿ â ïðàêòè÷åñêîé ðàáîòå. Ïðè îïèñàíèè òåõ èëè
èíûõ ìåòîäîâ îñîáîå âíèìàíèå îáðàùàåòñÿ ñ îäíîé ñòîðîíû íà âûäåëåíèå êðóãà çàäà÷, äëÿ êîòîðûõ îíè íàèáîëåå ýôôåêòèâíû, à ñ äðóãîé - óêàçûâàþòñÿ âîçìîæíûå ''ïîäâîäíûå êàìíè''.
 ïðàêòè÷åñêèõ ïðèëîæåíèÿõ âîçíèêàåò ïðîáëåìà áûñòðîòû è ýôôåêòèâíîñòè ÷èñëåííûõ àëãîðèòìîâ. Ðàññìîòðåíû áûñòðîå ïðåîáðàçîâàíèå Ôóðüå (ÁÏÔ) è âåéâëåò- ïðåîáðàçîâàíèå.
Êíèãà ïðåäíàçíà÷åíà äëÿ øèðîêîãî êðóãà ñïåöèàëèñòîâ, çàíèìàþùèõñÿ ìîäåëèðîâàíèåì ôèçè÷åñêèõ ïðîöåññîâ íà êîìïüþòåðå, à
òàêæå äëÿ àñïèðàíòîâ è ñòóäåíòîâ ñòàðøèõ êóðñîâ óíèâåðñèòåòîâ.

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

ISBN 978-5-91559-309-0

Ðåöåíçåíòû:

äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê Ã.Ì. Æèñëèí,
äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê Ñ.Í. Ñëóãèí

ОГЛАВЛЕНИЕ

Предисловие ко второму изданию . . . . . . . . . . . . . . . . . . . . . .
7

Предисловие рецензентов . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9

Глава 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11

Глава 2. Теория интерполяции . . . . . . . . . . . . . . . . . . . . . .
17
2.1. Интерполяция многочленами . . . . . . . . . . . . . . . . . . . . . .
19
2.2. Интерполяционная формула Лагранжа . . . . . . . . . . . . . . .
21
2.3. Итерационный метод интерполяции Эйткена . . . . . . . . . . .
22
2.4. Метод Ньютона, или метод разделенных разностей. . . . . . .
23
2.5. Ромбовидная диаграмма . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.6. Погрешность многочленной аппроксимации . . . . . . . . . . . .
29
2.7. Опасности, связанные с полиномиальной интерполяцией: пример Рунге . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
2.8. Интерполяционный многочлен Эрмита . . . . . . . . . . . . . . .
31
2.9. Интерполирование с помощью рациональных функций . . . .
32
2.10. Метод наименьших квадратов . . . . . . . . . . . . . . . . . . . .
33
2.11. Сплайн-интерполяция . . . . . . . . . . . . . . . . . . . . . . . . . .
36
2.12. Пример-предостережение . . . . . . . . . . . . . . . . . . . . . . . .
42
2.13. Тригонометрическое интерполирование . . . . . . . . . . . . . . .
43

Глава 3. Чиcленное интегрирование и дифференцирование . .
45
3.1. Формулы прямоугольников и трапеций . . . . . . . . . . . . . . .
47
3.2. Формула Симпсона . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
3.3. Единый метод нахождения формул численного интегрирования
54
3.4. Метод Филона интегрирования быстроосциллирующих функций
56
3.5. Несобственные интегралы . . . . . . . . . . . . . . . . . . . . . . . .
57
3.6. Экстраполяция по Ричардсону . . . . . . . . . . . . . . . . . . . . .
58
3.7. Численное дифференцирование, ошибка аппроксимации . . .
59

Оглавление

3.8. Дифференцирование с помощью интегрирования . . . . . . . .
63
3.9. Операторно-символическое представление формул численного
дифференцирования . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64

Глава 4. Методы решения задач линейной алгебры. . . . . . . .
67
4.1. Некоторые сведения из линейной алгебры . . . . . . . . . . . . .
68
4.2. Число обусловленности . . . . . . . . . . . . . . . . . . . . . . . . . .
71
4.3. Решение систем линейных алгебраических уравнений методом исключения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
4.4. Метод прогонки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
4.5. Устойчивость счета по методу прогонки . . . . . . . . . . . . . .
77
4.6. Вычисление определителей и обратных матриц . . . . . . . . .
78
4.7. Определение собственных значений методами преобразований
подобия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
4.8. Итерационные методы определения собственных значений . .
82
4.9. Методы прямой и обратной итерации . . . . . . . . . . . . . . . .
83
4.10. LR- и QR-методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
4.11. Метод Годунова использования резонанса для спектрального
анализа конечномерных кососимметрических операторов . . .
94
4.12. Теория возмущений. . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
4.12.1. Возмущение решений линейных уравнений . . . . . . .
98
4.12.2. Возмущение собственных значений и собственных
векторов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
100
4.13. Функции матриц . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
102

Глава 5. Методы решений нелинейных уравнений
и поиска минимума . . . . . . . . . . . . . . . . . . . . . . . . . . .
108
5.1. Метод половинного деления . . . . . . . . . . . . . . . . . . . . . .
109
5.2. Метод простой итерации. . . . . . . . . . . . . . . . . . . . . . . . .
110
5.3. Метод хорд (секущих) . . . . . . . . . . . . . . . . . . . . . . . . . .
112
5.4. Метод Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
113
5.5. Нахождение корней полиномов . . . . . . . . . . . . . . . . . . . .
115
5.6. Нахождение комплексных корней трансцендентных уравнений
119
5.7. Методы решения систем нелинейных уравнений . . . . . . . . .
120
5.8. Метод дифференцирования по параметру . . . . . . . . . . . . .
122
5.9. Методы нахождения минимума . . . . . . . . . . . . . . . . . . . .
123
5.9.1. Поиск по деформируемому многограннику . . . . . . . . .
126
5.9.2. Метод сопряженных градиентов . . . . . . . . . . . . . . . .
128
5.10. Сравнение свойств методов . . . . . . . . . . . . . . . . . . . . . .
129

Глава 6. Приближенные методы решения обыкновенных
дифференциальных уравнений . . . . . . . . . . . . . . . . . . .
131
6.1. Разложение решения в ряд Тейлора . . . . . . . . . . . . . . . . .
133
6.2. Методы Рунге–Кутта . . . . . . . . . . . . . . . . . . . . . . . . . . .
134
6.3. Модификация Рунге–Кутта–Мерсона . . . . . . . . . . . . . . . .
138

Оглавление
5

6.4. Метод Адамса. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
139
6.5. Формулы Бутчера . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
141
6.6. Метод Нистрема . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
142
6.7. Применение матричной экспоненты для решения задачи Коши
142
6.8. Жесткие уравнения . . . . . . . . . . . . . . . . . . . . . . . . . . . .
145
6.8.1. Линейные жесткие системы . . . . . . . . . . . . . . . . . .
150
6.8.2. Системные методы численного интегрирования . . . . .
151
6.8.3. Безитерационные схемы типа схем Розенброка. . . . . .
153
6.9. Методы решения краевых задач . . . . . . . . . . . . . . . . . . . .
154
6.9.1. Ортонормировка решения . . . . . . . . . . . . . . . . . . . .
155
6.9.2. Конечно-разностный метод . . . . . . . . . . . . . . . . . . .
157
6.9.3. Метод дифференциальной прогонки . . . . . . . . . . . . .
158
6.10. Осреднение быстрых вращений . . . . . . . . . . . . . . . . . . . .
161
6.10.1. Стробоскопический метод. Качественные соображения
162
6.11. Задачи на собственные значения . . . . . . . . . . . . . . . . . . .
164

Глава 7. Гармонический анализ . . . . . . . . . . . . . . . . . . . . . .
167
7.1. Конечные ряды Фурье . . . . . . . . . . . . . . . . . . . . . . . . . .
168
7.1.1. Свойства матрицы ДПФ . . . . . . . . . . . . . . . . . . . . .
177
7.2. Быстрое преобразование Фурье (БПФ) . . . . . . . . . . . . . . .
179
7.3. Свертки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
185
7.4. Конечное суммирование ряда Фурье . . . . . . . . . . . . . . . . .
186
7.5. Сходимость тригонометрических рядов. Явление Гиббса . . .
189
7.6. Теоремы Котельникова и Агеева . . . . . . . . . . . . . . . . . . .
192
7.7. Быстрое преобразование Ханкеля . . . . . . . . . . . . . . . . . . .
195

Глава 8. Вейвлет-преобразование. . . . . . . . . . . . . . . . . . . . .
200
8.1. «Недостатки» преобразования Фурье . . . . . . . . . . . . . . . .
201
8.1.1. Концепция стационарности . . . . . . . . . . . . . . . . . . .
203
8.2. Частотно-временной анализ . . . . . . . . . . . . . . . . . . . . . . .
206
8.3. Непрерывное преобразование вейвлетов . . . . . . . . . . . . . .
210
8.3.1. Свойства вейвлет-преобразования . . . . . . . . . . . . . . .
213
8.3.2. Получение дополнительных результаьов . . . . . . . . . .
218
8.3.3. Локальный спектр энергии . . . . . . . . . . . . . . . . . . .
219
8.3.4. Глобальный спектр энергии . . . . . . . . . . . . . . . . . . .
219
8.3.5. Мера локальной перемежаемости . . . . . . . . . . . . . . .
220
8.3.6. Мера контрастности . . . . . . . . . . . . . . . . . . . . . . . .
220
8.4. Использование дискретного преобразования вейвлетов . . . .
221
8.4.1. Диадное вейвлет-преобразование дискретных сигналов
222
8.5. Фреймы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
223
8.6. Кратномасштабное разложение. . . . . . . . . . . . . . . . . . . . .
224
8.6.1. Аксиоматическое описание . . . . . . . . . . . . . . . . . . .
224
8.6.2. Примеры масштабирующих или скейлинг функций . . .
228
8.6.3. Базис Хаара . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
230

Оглавление

8.6.4. Система Радемахера . . . . . . . . . . . . . . . . . . . . . . . .
232
8.6.5. Базис Фабера и Шаудера . . . . . . . . . . . . . . . . . . . .
233
8.7. Ортогональные вейвлеты . . . . . . . . . . . . . . . . . . . . . . . .
235
8.8. Вейвлеты и детализация пространств Wj . . . . . . . . . . . . . .
237
8.8.1. Отсутствие симметрии для ортонормированных вейвлетов с компактным носителем . . . . . . . . . . . . . . . . . .
240
8.9. Примеры вейвлетов . . . . . . . . . . . . . . . . . . . . . . . . . . . .
241
8.9.1. Контрпример всплеска, не порожденного КМФ . . . . .
245
8.10. Применение преобразования вейвлетов к модельным сигналам
245
8.11. Борьба с явлением Гиббса . . . . . . . . . . . . . . . . . . . . . . .
249
8.12. Скелет максимумов . . . . . . . . . . . . . . . . . . . . . . . . . . . .
253
8.12.1. Продолжения сигналов, сохраняющие свойство полного восстановления . . . . . . . . . . . . . . . . . . . . . . . .
255
8.12.2. Важность пространственной инвариантности . . . . . .
255

Глава 9. Вейвлеты Добеши . . . . . . . . . . . . . . . . . . . . . . . . .
257
9.1. Границы носителей вейвлетов Добеши . . . . . . . . . . . . . . .
258
9.2. Основная теорема . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
259
9.3. Моменты вейвлетов и представление полиномов . . . . . . . . .
261
9.4. Конструирование вейвлета DAUB4 . . . . . . . . . . . . . . . . . .
263

Глава 10. Быстрые алгоритмы преобразования вейвлетов . . .
269
10.1. Койфлеты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
274

Глава 11. Симметрия вейвлетов и линейность фазы фильтров
276

Глава 12. Вейвлеты в медицине . . . . . . . . . . . . . . . . . . . . . .
278
12.1. Рекомендации по применению алгоритмов фильтрации . . . .
281

Глава 13. Обобщения и новые идеи . . . . . . . . . . . . . . . . . . .
284

Глава 14. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
286

Глава 15. Оценка результатов . . . . . . . . . . . . . . . . . . . . . . .
288

Приложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
298
П1. Формулы суммирования Пуассона . . . . . . . . . . . . . . . . . .
298
П2. Chirp-z-алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
298
П3. Нестационарная самофокусировка . . . . . . . . . . . . . . . . . .
299
П4. Применение метода Нистрема . . . . . . . . . . . . . . . . . . . . .
302

Дополнение к главе 6. Компактные схемы . . . . . . . . . . . .
304
Д.1. Основы проекционного метода . . . . . . . . . . . . . . . . . . . . .
304
Д.2.Операторный компактный неявный метод . . . . . . . . . . . . .
307
Д.3.Схема повышенной точности . . . . . . . . . . . . . . . . . . . . . .
311

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

ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ

Со времени первого издания в публикациях по применению численных методов к обыкновенным дифференциальным уравнениям
все чаще появляются ссылки на таблицы Бутчера и барьеры Бутчера. Этот материал добавлен в гл. 6.
За эти годы сильно развилась вычислительная техника, что привело к расширению области обработки сигналов и объемной информации, особенно в области медицины и прогнозирования поведения
временных рядов.
Наиболее популярной системой для разложений функций в L2
всегда была тригонометрическая система Фурье {e2πint}n∈Z. Аппарат быстрого преобразования Фурье, приведенный в разделе «Гармонический анализ», существенно сокративший время выполнения
преобразования, расширил область его применения.
Однако, система Фурье имеет ряд существенных недостатков:
1) она рассчитана на периодические функции;
2) она не локализована, т. е. функции этой системы не убывают
при t → ∞.
С первым недостатком люди давно научились справляться с помощью разного рода периодизаций, и т. д. Второй оказался куда
более сложным.
Спасти ситуацию смог бы только переход к другому базису,
который состоял бы из локализованных функций.
Так продолжалось до открытия вейвлетов, которые, похоже, решили эту сложнейшую и актуальную научную проблему.
Предположим, что мы хотим изучить какой-то сигнал, например, временной ряд. Идея многомасштабного анализа (относящиеся сюда английские термины multiscale и multiresolution) состоит в
том, чтобы взглянуть на сигнал сначала под микроскопом, потом —
через лупу, потом отойти на пару шагов, потом посмотреть совсем
издалека. На этой идее и основано вейвлет-преобразование.

Предисловие ко второму изданию

Вейвлет-анализ является одним из наиболее мощных и при этом
гибких средств исследования и обработки радиотехнических сигналов: помимо возможностей их фильтрации и сжатия, анализ в
базисе вейвлет-функций позволяет:
— решать задачи идентификации, моделирования, аппроксимации стационарных и нестационарных процессов;
— исследовать вопросы наличия разрывов в производных;
— осуществлять поиск точек соединения данных;
— отыскивать признаки фрактальности информации, т. е. исследовать функции, не имеющие производных ни в одной своей точке.
Вейвлеты (всплески) в настоящее время широко применяются в
инженерных задачах теории обработки информации, при численном
решении дифференциальных уравнений, в некоторых теоретических
задачах теории приближений и теории функций. Идеи, заложенные
в это преобразование, проникают в такую, казалось бы, далекую от
них область, как история. Вот что пишет в своей книге «Средневековье крупным планом» профессор О. С. Воскобойников: “я хотел
бы попробовать вместе с вами, читатель, посмотреть на средневековый мир с разных планов: через «рыбий глаз», через стандартный
50-миллиметровый «штатник», через «длиннофокусник» и, наконец,
в режиме «макро». Именно смена фоторежимов, как мне кажется,
даст нам с вами возможность рассмотреть наших далеких предков с должной степенью четкости. Иногда нам потребуется глубина резкости, для этого мы закроем диафрагму. Иногда, напротив,
чтобы выделить индивидуальные, портретные черты, задний план
придется размыть. Иной раз линия горизонта окажется важнее, чем
травинки и листья на деревьях. Читателю следует приготовиться к
частой, иногда неожиданной смене фокусного расстояния”.
Во втором издании исправлены замеченные опечатки. В первый
раздел добавлен пункт «Тригонометрическое интерполирование».
Расширен раздел поиска минимума функции. Добавлены «Метод
Адамса», «Барьеры Бутчера» и «Метод Нистрема» в раздел «Поиск
решений ОДУ».
Раздел «Вейвлеты» добавлен во второе издание. В нем описана
теория непрерывного и дискретного вейвлет-преобразования сигналов и развитые в последнее время новые способы получения информации об исходном сигнале.
Изменен раздел «Приложения». Убран спецефический раздел расчета лазеров на свободных электронах. Добавлены «Методы суммирования Пуассона» и «Chirp-z алгоритм», а также пункт «Обобщения и новые идеи».

ПРЕДИСЛОВИЕ РЕЦЕНЗЕНТОВ

В книге обсуждаются вопросы, принадлежащие, на наш взгляд,
к числу наиболее важных для научного работника, которому предстоит заниматься различного рода вычислениями. Среди вычислительных задач, которые часто приходится решать как в теоретических, так и прикладных работах, естественно, много стандартных:
задачи для систем линейных уравнений, интерполирование, быстрое преобразование Фурье, численное интегрирование дифференциальных уравнений и т. п. В настоящей книге, как нам представляется, удачно объединены наиболее устоявшиеся элементы теории
хорошо зарекомендовавших себя численных методов с описанием
новых направлений их развития. В каждом конкретном случае автор пытался, насколько это возможно, отразить в своем изложении то, чем реально занимаются профессионалы в соответствующей области.
Еще одна отличительная черта книги — развитие идеи о возможности и целесообразности комбинирования различных численно-аналитических методов как при исследовании, так и при решении задач. Знакомство с изложенным в ней материалом должно
помочь читателю в дальнейшем изучении численных алгоритмов.
Совершенствование численных методов снимает многие ограничения на сложность изучаемых математических моделей.
В книге приведен целый ряд известных контрпримеров для популярных методов решения. Это очень полезно для обучения правильной диагностике симптомов численного «нездоровья», что, в
свою очередь, требует определенного уровня понимания используемых методов.
В настоящее время развивается тенденция мыслить модулями,
системами или преобразованиями, отображающими вход и выход

Предисловие рецензентов

в подпрограмму, реализующую выбранный метод, в соответствии
с некоторыми четко определенными правилами. Такой подход, на
первый взгляд оптимизирующий процесс вычислений, при бездумном использовании оказывается поверхностным. Книга А. Д. Юнаковского способствует выработке понимания, что для получения
правильных результатов недостаточно рассматривать даже очень
известные подпрограммы как некий черный ящик. Он должен стать
для пользователя по крайней мере «серым», а лучше бы вообще
прозрачным!
Несомненно, книга содержит интересный и нужный материал,
чем привлечет внимание не только студентов и аспирантов, но и
специалистов в области численных методов, и будет содействовать
развитию конструктивных численных методов изучения возникающих прикладных задач.