Введение ........................................................ 5
Глава 1. Основы машинной арифметики ............................. 7
1.1 Представление чисел в ЭВМ .................................. 7
1.2 Приближение чисел в системе с плавающей точкой.
Абсолютная и относительная погрешности ..................... 9
1.3 Арифметические действия над числами в машинной
арифметике ................................................ 12
1.4 Взаимное уничтожение (Потеря точности при вычитании
близких чисел) ............................................ 13
1.5 Об IEEE-арифметике ........................................ 15
1.6 Понятие устойчивых и неустойчивых алгоритмов .............. 17
1.7 Почти некорректные и плохо обусловленные задачи ........... 19
Глава 2. Точные методы решения систем линейных алгебраических
уравнений ............................................. 22
2.1 Матрицы исключения ........................................ 23
2.2 LU-разложение ............................................. 24
2.3 Метод Гаусса решения систем линейных алгебраических
уравнений ................................................. 29
2.4 Об устойчивости метода Гаусса решения систем линейных
алгебраических уравнений .................................. 30
2.5 Ортогональные матрицы ..................................... 31
2.6 Элементарные матрицы перестановок ......................... 33
2.7 Матрицы перестановок ...................................... 33
2.8 PLU-разложение невырожденных матриц ....................... 34
2.9 Метод Гаусса с частичным выбором главного элемента ........ 37
2.10 Метод Гаусса с полным выбором главного элемента ........... 39
2.11 Метод прогонки решения систем с трехдиагональной
матрицей .................................................. 40
2.12 Положительно определенные матрицы ......................... 41
2.13 Нормы векторов и матриц ................................... 46
2.14 0бусловленность матриц .................................... 49
2.15 Итерационное уточнение .................................... 54
2.16 Масштабирование уравнений и неизвестных ................... 55
2.17 Ортогональные методы решения систем линейных
алгебраических уравнений .................................. 57
2.18 0и-разложение матрицы ..................................... 58
2.19 Метод вращений решения систем линейных алгебраических
уравнений ................................................. 60
2.20 Приведение матрицы к верхней форме Хессенберга (верхнему
почти треугольному виду) .................................. 61
2.21 Матрицы отражений (Хаусхолдера) ........................... 63
2.22 НU-разложение ............................................. 67
2.23 Метод отражений решения систем линейных алгебраических
уравнений ................................................. 69
2.24 Сингулярное разложение матрицы ............................ 70
2.25 Решение прямоугольных и вырожденных систем ................ 74
Глава 3. Итерационные методы решения систем линейных
алгебраических уравнений .............................. 77
3.1 Метод простой итерации решения систем линейных
алгебраических уравнений (метод Якоби, метод
одновременных смещений) ................................... 77
3.2 Метод простой итерации с оптимальным выбором параметров ... 81
3.3 Метод Зейделя (Гаусса-Зейделя, метод последовательных
смещений) ................................................. 84
3.4 Многочлены Чебышева ....................................... 91
3.5 Метод Ричардсона (ускорение по Чебышеву) .................. 94
3.6 Градиентные итерационные методы ........................... 97
3.7 Метод наискорейшего спуска ................................ 99
3.8 Метод сопряженных направлений ............................ 100
3.9 Метод сопряженных градиентов ............................. 102
З.10 Предобуславливание ....................................... 104
Глава 4. Задачи на собственные значения ....................... 106
4.1 Задачи на собственные значения (спектральные задачи)...... 106
4.2 Частичная проблема собственных значений .................. 106
4.2.1 Степенной метод (прямая итерация) нахождения
максимального по модулю собственного значения
симметричной матрицы .............................. 106
4.2.2 Обратная итерация нахождения минимального по
модулю собственного значения симметричной
матрицы ........................................... 109
4.2.3 Исчерпывание вычитанием ........................... 110
4.2.4 Роль сдвигов в частичной проблеме собственных
значений .......................................... 112
4.2.5 Границы спектра матрицы ........................... 114
4.3 Полная проблема собственных значений ..................... 115
4.3.1 Метод вращений решения полной проблемы
собственных значений для симметричной матрицы
(Метод Якоби) ..................................... 115
4.3.2 Полная проблема собственных значений для
симметричной трехдиагональной приводимой
матрицы ........................................... 120
4.3.3 QR- и QL-алгоритмы решения полной проблемы
собственных значений для симметричных матриц ...... 122
4.3.3.1 Введение ................................. 122
4.3.3.2 QL-преобразование ........................ 122
4.3.3.3 QL-алгоритм .............................. 122
4.3.3.4 Свойства QL-алгоритма .................... 123
4.3.4 Связь между QL-алгоритмом, степенным методом и
обратной итерацией ................................ 124
4.3.5 Сходимость основного QL-алгоритма ................. 126
4.3.6 Приведение задачи нахождения корней
алгебраического уравнения к полной проблеме
собственных значений .............................. 129
Глава 5. Решение нелинейных уравнений ......................... 130
5.1 Метод бисекции (метод деления отрезка пополам) ........... 130
5.2 Метод простой итерации ................................... 131
5.3 Случай одного уравнения .................................. 133
5.4 Случай системы уравнений ................................. 136
5.5 Метод Ньютона (касательных) для случая одной
переменной ............................................... 137
5.6 Метод Ньютона для нелинейных систем ...................... 140
5.7 Метод секущих или метод хорд ............................. 142
Литература .................................................... 144
|
