Петров И.Б., Лобанов А.И. Лекции по вычислительной математике: Учебное пособие - М: Интернет-Университет Информационных Технологий, 2006. — 523 с: ил., табл.- (Серия «Основы информационных технологий»)
В курсе лекций рассматриваются основные понятия и методы вычислительной математики. Курс содержит как лекции, посвященные классическим численным методам анализа и линейной алгебры, так и решению дифференциальных уравнений. Особое внимание уделяется решению систем уравнений в частных производных гиперболического типа. Большинство лекций снабжено задачами для рассмотрения на семинарских занятиях и для самостоятельного решения.
Оглавление
Предисловие..............................................................13
Лекция 1. Предмет вычислительной математики. Обусловленность задачи, устойчивость алгоритма, погрешности вычислений. Задача численного дифференцирования....................................15
1.1. Обусловленность задачи........................................17
1.2. Влияние выбора вычислительного алгоритма на результаты вычислений ...............19
1.3. Экономичность вычислительного метода . . . ............21
1.4. Погрешность метода ............................................22
1.5. Элементы теории погрешностей................................23
1.6. Задача численного дифференцирования......................24
1.7. Задачи..............................................................28
1.8. Задачи для самостоятельного решения........................30
Литература..............................................................31
Лекция 2. Численное решение систем линейных алгебраических уравнений ..........32
2.1. Постановка задачи ..............................................32
2.2. Согласованные нормы векторов и матриц....................34
2.3. Обусловленность СЛАУ. Число обусловленности матрицы . 36
2.4. Прямые методы решения СЛАУ................................39
2.4.1. Метод исключения Гаусса..............................40
2.4.2. Модификация метода Гаусса для случая линейных систем с трехдиагональными матрицами — метод прогонки..................................................44
2.4.3. LU-разложение..........................................45
2.4.4. Метод Холецкого (метод квадратного корня) .... 46
2.5. Итерационные методы решения СЛАУ........................48
2.5.1. Метод простой итерации................................48
2.5.2. Влияние ошибок округления на результат численного решения..................50
2.5.3. Методы Якоби, Зейделя, верхней релаксации .... 51
2.6. Вариационные итерационные методы........................54
2.6.1. Связь между вариационной задачей и задачей решения СЛАУ ............54
2.6.2. Методы градиентного и наискорейшего спуска ... 56
2.6.3. Метод минимальных невязок..........................56
2.6.4. Метод сопряженных градиентов..... ..............57
2.7. О спектральных задачах..........................................58
Литература..............................................................70
Лекция 3. Численное решение переопределенных СЛАУ. Метод наименьших квадратов....................................................72
3.1. Пример использования метода наименьших квадратов (МНК) ........72
3.2. Понятие о методах решения плохо обусловленных СЛАУ ..... 79
3.3. Задачи..............................................................80
3.4. Задачи для самостоятельного решения........................82
Литература..............................................................83
Лекция 4. Численные методы решения экстремальных задач ... 85
4.1. Поиск безусловного минимума функции......................85
4.2. Методы спуска....................................................91
4.2.1. Метод покоординатного спуска........................91
4.2.2. Метод градиентного спуска............................96
4.2.3. Метод наискорейшего спуска..........................96
4.3. Задачи математического программирования..................98
4.4. Задачи...............................101
4.5. Задачи для самостоятельного решения............102
Литература...............................103
Лекция 5. Численное решение нелинейных алгебраических уравнений и систем..................104
5.1. Сжимающие отображения. Итерации. Метод простых итераций(МПИ)...........................104
5.2. Метод Ньютона.........................108
5.3. О вариационных подходах к решению нелинейных систем уравнений............................112
5.4. Метод Чебышёва построения итерационных процессов высшего порядка.......................112
5.5. Разностные отображения в нелинейной динамике.....113
5.6. Задачи...............................124
5.7. Задачи для самостоятельного решения............131
Литература...............................132
Лекция 6. Интерполяция функций..................133
6.1. Постановка задачи интерполяции...............133
6.2. Кусочно-линейная интерполяция...............134
6.3. Интерполяция обобщенными полиномами.........135
6.4. Полиномиальная (алгебраическая) интерполяция .....136
6.5. Теорема об остаточном члене интерполяции.........137
6.6. Интерполяционный полином в форме Ньютона ......139
6.6.1. Разделенные и конечные разности..........139
6.6.2. Интерполяционный полином в форме Ньютона .. 141
6.7. Многочлены Чебышёва и минимизация остаточного члена интерполяции..........................141
6.8. Обусловленность задачи интерполяции. Постоянная Лебега 142
6.9. Интерполяция с кратными узлами..............143
6.9.1. Замечание о тригонометрической интерполяции . ...... 145
6.10. Кусочно-многочленная глобальная интерполяция(сплайны) 145
6.11. В-сплайны............................151
6.12. Интерполяция функций двух переменных..........154
6.13. Задачи...............................155
6.14. Задачи для самостоятельного решения............159
Литература...............................160
Лекция 7. Численное интегрирование................162
7.1. Квадратурные формулы интерполяционного типа (формулы Ньютона—Котеса)........ 162
7.2. Оценка погрешности квадратурных формул.........166
7.3. Кратные интегралы.......................168
7.4. Квадратурные формулы Гаусса.................169
7.5. Вычисление интегралов от функций с особенностями ... 173
7.6. Идея метода Монте-Карло...................174
7.7. Задачи...............................175
7.8. Задачи для самостоятельного решения............178
Литература...............................180
Лекция 8. Численные методы решения задачи Коши для систем обыкновенных дифференциальных уравнений..........181
8.1. Базовые понятия.........................181
8.2. Методы Рунге-Кутты......................186
8.3. Методы Адамса.........................197
8.4. Оценка погрешности......................200
8.4.1. Автоматический выбор шага интегрирования .... 200
8.5. Устойчивость методов Рунге-Кутты..............202
8.6. Задачи...............................207
8.7. Задачи для самостоятельного решения............212
Литература...............................216
Лекция 9. Численные методы решения жестких систем обыкновенных дифференциальных уравнений.................218
9.1. Явление жесткости. Предварительные сведения.......218
9.2. Сингулярно-возмущенные задачи...............224
9.3. Решение линейных ЖС ОДУ и вычисление матричной экспоненты .............................229
9.4. Численные методы решения ЖС ОДУ. Семейства неявных методов Рунге-Кутты и Розенброка..............230
9.5. Формулы дифференцирования назад и методы Гира. Представление Нордсика.......................236
9.6. Задачи для самостоятельного решения............239
Литература...............................245
Лекция 10. Численное решение краевых задач для систем обыкновенных дифференциальных уравнений...............247
10.1. Краевая задача для линейной системы ОДУ первого порядка 247
10.2. Метод дифференциальной прогонки. Понятие о жестких краевых задачах.........................250
10.3. Краевая разностная задача Штурма-Лиувилля для обыкновенного дифференциального уравнения второго порядка ....... 253
10.4. Пятиточечная прогонка.....................257
10.5. Матричная прогонка......................258
10.6. Численное решение нелинейных краевых задач.......259
10.6.1. Метод стрельбы.....................259
10.6.2. Метод квазилинеаризации (метод Ньютона).....260
10.6.3. Аппроксимация граничных условий.........260
Часть 1
10.7. Краевые задачи на собственные значения для обыкновенных дифференциальных уравнений .....263
10.8. Решение краевой задачи методом Фурье...........264
10.9. Задачи...........................................................266
10.10. Задачи для самостоятельного решения............270
Литература...............................274
Лекция 11. Исследование разностных схем для эволюционных уравнений на устойчивость и сходимость ................275
11.1. Постановка некоторых задач для уравнений математической физики ..........................275
11.2. Основные определения — сходимость, аппроксимация, устойчивость ..............................279
11.2.1. Основные определения.................279
11.2.2. Необходимое условие сходимости разностной схемы Куранта, Фридрихса, Леви (условие КФЛ) .... 285
11.3. Элементы теории устойчивости разностных схем......287
11.4. Задачи...............................302
11.5. Задачи для самостоятельного решения............305
Литература...............................307
Лекция 12. Численное решение дифференциальных уравнений в частных производных параболического типа на примере уравнения теплопроводности ........................308
12.1. Постановки задач для уравнений параболического типа . . 308
12.2. Разностные схемы для численного решения нелинейного уравнения теплопроводности...........312
12.2.1. Неявная схема с нелинейностью на нижнем слое . . 312
12.2.2. Схема с нелинейностью на верхнем слое.......312
12.3. Разностные схемы для численного решения многомерного уравнения теплопроводности...........315
12.4. Исследование сходимости разностных схем для многомерного уравнения теплопроводности......318
12.5. Задачи...............................320
12.6. Задачи для самостоятельного решения............325
Литература...............................330
Лекция 13. Численные методы решения уравнений в частных производных гиперболического типа (на примере уравнения переноса) 332
13.1. Простейшее линейное уравнение переноса .........332
13.2. Квазилинейные уравнения гиперболического типа. Характеристики квазилинейных уравнений.............334
13.3. Численные методы решения уравнений в частных производных гиперболического типа на примере линейного уравнения переноса.......................336
13.4. Численные методы решения уравнений в частных производных гиперболического типа для квазилинейного уравнения переноса .........................342
13.5. Методы регуляризации численных решений с большими градиентами...........................347
13.6. Гибридные схемы (метод Р. П. Федоренко)..........350
13.7. Схемы с уменьшением полной вариации (Total Variation Diminishing, схемы Хартена)..................351
13.8. Идеи построения сеточно-характеристических методов и анализ разностных схем в пространстве неопределенных коэффициентов.........................354
13.9. Задачи...............................362
13.10. Задачи для самостоятельного решения............374
Литература...............................379
Лекция 14. Введение в методы численного решения уравнений газовой динамики......................381
14.1. Формы записи одномерных уравнений газовой динамики . 381
14.2. Методы Лакса-Вендроффа и Мак-Кормака.........385
14.3. Сеточно-характеристический метод для численного решения уравнений газовой динамики (М.-К. М. Магомедова—А. С. Холодова)..........................386
14.4. Разностная схема И.М. Гельфанда для численного решения одномерной системы уравнений газовой динамики.....388
14.5. Метод частиц в ячейках Харлоу (PIC method:P&rticle-In-Cell) ......390
14.6. Задачи для самостоятельного решения............395
Литература...............................397
Лекция 15. Численное решение уравнений в частных производных гиперболического типа с большими градиентами решений .... 399
15.1. Потоковая форма представления разностных схем.....399
15.2. Гибридные схемы........................400
15.3. Гибридные схемы и пространство неопределенных коэффициентов ............................401
15.4. Метод коррекции потоков Бориса—Бука...........404
15.5. TVD-схемы............................405
15.6. ENO-схемы............................408
15.7. Разностные схемы для квазилинейного уравнения переноса 410
15.8. Однопараметрическое семейство неявных схем.......412
15.9. TVD-схемы для квазилинейного уравнения с антидиффузией.................................413
15.lO. TVD-схемы для линейных систем уравнений гиперболического типа ............................415
15.1 ІМетод С. К. Годунова......................417
Литература...............................420
Лекция 16. Численное решение уравнений в частных производных эллиптического типа на примере уравнений Лапласа и Пуассона .....424
16.1. Постановка задачи. Простейшая разностная схема «крест». Устойчивость схемы «крест».......424
16.2. Методы решения сеточных уравнений............428
16.2.1. Метод простых итераций................429
16.2.2. Метод простых итераций с оптимальным параметром 430
16.2.3. Чебышёвское ускорение метода простых итераций . 434
16.2.4. Метод переменных направлений...........437
16.2.5. Методы Якоби, Зейделя, верхней релаксации .... 440
16.3. Попеременно-треугольный итерационный метод......442
16.4. Сводка результатов по итерационным методам решения сеточных уравнений................445
16.5. Основные идеи многосеточного метода Р. П. Федоренко .......... 446
16.6. Построение разностных схем для эллиптических уравнений на нерегулярных сетках. Монотонные схемы (подход А.С.Холодова)..........................448
16.7. Задачи...............................451
16.8. Задачи для самостоятельного решения............452
Литература...............................458
Лекция 17. Понятие о методах конечных элементов ........459
17.1. Вариационный подход Ритца .................460
17.2. Общая схема метода Ритца...................462
17.3. Формулировка проекционного метода Галеркина......465
17.4. Пример построения схемы конечных элементов.......467
17.5. Построение базисных функций................469
17.6. МКЭ для нестационарных уравнений.............474
17.7. Решение нелинейных уравнений с помощью МКЭ.....477
17.8. Задачи для самостоятельного решения............478
Литература...............................478
Лекция 18. Методы расщепления...................479
18.1. Понятие о методах расщепления ...............479
18.2. Метод расщепления первого и второго порядка точности пот................................480
18.2.1. Локально-одномерные схемы.............480
18.2.2. Схемы Кранка-Никольсон..............482
18.2.3. Общая формулировка методов расщепления .... 482
18.2.4. Схемы расщепления для уравнения теплопроводности483
18.3. Методы двуциклического покомпонентного расщепления . 484
18.4. Методы расщепления с факторизацией оператора.....489
18.4.1. Факторизованная схема расщепления........489
18.4.2. Неявная схема расщепления с приближенной факторизацией ........................490
18.4.3. Метод «предиктор-корректор».............491
Литература...............................493
Лекция 19. Применение вариационных принципов для построения разностных схем...........................494
19.1. Пример использования принципа наименьшего действия (Гамильтона)...........................494
19.2. Вариационные схемы для решения задач газовой динамики 498
19.3. Вариационная схема для уравнения теплопроводности на криволинейной сетке......................502
19.4. Задачи для самостоятельного решения............507
Литература...............................509
Приложение. Параллельные вычисления на кластерах из персональных компьютеров в математической физике ..510
1. Введение.............................510
2. Расчет электрического поля установки РС-20 с использованием кластера из персональных компьютеров .......512
3. Математическая модель и выбор численного метода .... 513
4. Модели организации параллельных вычислений для комплексов с распределенной памятью ......514
Потоковая модель..........................515
Статическая модель.........................516
5. Выбор модели организации параллельных вычислений ........517
5.1. Потоковая модель....................518
5.2. Динамическая модель..................519
5.3. Статическая модель...................519
6. Заключение ...........................521
Литература...............................522
Часть 2
