1. Метод Гаусса решения систем линейных алгебраических уравнений. Выбор главного элемента.
Метод Гаусса.
Решаем СЛАУ:
Выполняем n-1 шаг вперёд (приведение матрицы к верхнеугольной), потом n-1 шаг назад (нахождение х)
По аналогичной формуле преобразуются все нижеследующие строчки.
На (n-2)-ом шаге получается треугольная матрица.
Метод Гаусса с выделением главного элемента.
1) В текущей строке находится
2) Переставляются столбцы (то есть переименовываются хi в хj и наооборот), чтобы оказался спереди.
Метод дает выше точность для матриц большой размерности
2. Метод простой итерации и метод Гаусса-Зейделя решения систем линейных алгебраических уравнений. Исследование сходимости.
Метод простой итерации решения СЛАУ.
Сходится, если хотя бы одна норма у B < 1 по модулю, т.е., например, если max|| < 1.
Этот метод имеет ограниченную область сходимости.
Доказательство:
Напишем это же самое в развёрнутом виде:
Метод Зейделя.
Усовершенствуем предыдущую систему:
Свойства:
-
Скорость сходимости увеличивается.
-
Можно останавливаться в середине итерации (в середине цикла).
-
Области сходимости той же мощности (некоторые матрицы, которые методом последовательных приближений сходятся, методом Зейделя сходиться не будут, и наоборот).
-
Нет требования к симметричности или положительности .
Метод обеспечения сходимости метода Зейделя.
то две СЛАУ равносильны
тогда
Выбор H, чтобы все || < 1 у HA
Итерационный процесс:
1)
2) Если 1) не дало результата (процесс не стал сходиться).
Ищем блоки 2*2, если их нечётное количество, то останется 1 блок 1*1=ann
3) и т. д.
3. Обращение матриц методом окаймления.
А:
На k-ом шаге находится обратная матрица углового минора kk, при этом известна обратная матрица для предыдущего углового минора (k-1)(k-1).
Будем искать Аk-1 в виде (матрица):
Pk-1 rk
qk 1/k
Аk*Ak-1 = E = [Ak-1 Uk; Vk k]*[ Pk-1 qk; rk 1/k] =
[Ak-1*Pk-1+Uk*qk Ak-1*rk+Uk*1/k; Vk*Pk-1+k*qk Vk*rk+k*1/k] =
= [Ek-1 0; 0 1]
(1) Ak-1*Pk-1+Uk*qk = E;
(2) Ak-1*rk+Uk*1/k = 0;
(3) Vk*Pk-1+k*qk = 0T;
(4) Vk*rk+k*1/k = 1;
Следовательно:
rk = -Аk-1-1 * Uk/k; (5)
Где Аk-1-1 известна на предыдущем шаге.
Подставим (5) в (4):
Vk*(-Аk-1-1*Uk/k) + k/k = 1; k = k - Vk*Аk-1-1*Uk;
Подставим в (5):
rk = -Аk-1-1 * Uk/k;
Выразим из (1) Pk-1 и подставим в (3):
qk = -Vk*Аk-1/k;
Pk-1 = Аk-1-1 + (Аk-1*Uk*Vk Аk-1-1)/k.
4. Преобразование Хаусхолдера.
(Для приведения матрицы n*n к виду Хессенберга ровно за n-2 итерации)
Некоторые определения (воспоминания).
D – диагональная:
Q – ортогональная:
R – правая (верхняя) прямоугольная:
L – левая (нижняя) треугольная:
H – Хессенберга : 1) правая, верхняя
2) левая, нижняя
Подобные матрицы: если Q, что B = QTAQ (у подобных матриц одинаковые собственные значения)
Конец воспоминаний
Выполняется n-2 шага (начиная с последней строки, и далее вверх).
На каждом шаге:
Исключаем нулевые элементы в очередной строке (j<i-1),
Пример i-ого шага: работаем со строкой l = n-i+1
До
главн. диаг. i =4
1) Рассчитывается величина
2)
3) ( это скаляр )
4) ( это матрица)
5) - (первую Р не транспонируем, т.к. матрица симметричная)
5. QR – разложение матрицы.
Задача представить матрицу А в виде произведения: , где Q – ортогональная ( -- верхнетреугольная.
Теорема: Если А – верхняя матрица Хессенберга, то у неё существует
QR – разложение, и оно осуществляется последовательным уничтожением поддиагональных нулей.
Уничтожаем а21 : (в общем случае: аij, где j = i+1)
Берём , где
Получаем:
Домножим слева на
Получим:
Алгоритм:
1) Находим
2)
…
n-1)
6. Нахождение собственных чисел при помощи QR-разложения. Основные свойства полученной последовательности подобных матриц.
Нахождение всех у матрицы при помощи QR – разложения.
Первоначально матрицы надо привести к виду Хессенберга. После этого можно запускать итерационный процесс.
-- раскладываем
-- перемножаем
-- раскладываем
-- перемножаем
…
Делаем, пока сумма квадратов элементов на диагонали не станет значительно больше суммы квадратов элементов под диагональю; либо пока матрица не перестаёт меняться (этот второй критерий используется, если есть комплексно-сопряжённые ).
Свойства метода.
Свойства итерационной последовательности (А(i)).
1) В пределе получается верхне-блочнотреугольная матрица, в которой на диагонали стоят в порядке убывания, а блоки 2*2 соответствуют комплексно-сопряжённым .
2) Если исходная была симметричная матрица (при действительных ), то получится диагональная матрица, если не симметричная, то треугольная.
Скорость сходимости определяется тем, как стремятся к нулю недиагональные элементы:
Все поддиагональные элементы на каждом шаге уменьшаются, что приводит к уменьшению суммы квадратов элементов под диагональю.
7. Нахождение собственных чисел при помощи QR-разложения со сдвигом.
Нахождение всех у матрицы при помощи QR – разложения со сдвигом.
Это пример, когда обычный метод QR-разложения работает медленно.
Алгоритм разложения со сдвигом:
-- раскладываем
-- перемножаем
где -- некоторые числа.
Свойства метода, свойства полученной последовательности матриц
1) тот же (В пределе получается верхне-блочнотреугольная матрица, в которой на диагонали стоят в порядке убывания величины -l, а блоки 2*2 соответствуют комплексно-сопряжённым .)
2) скорость сходимости: a i j 0 так же, как 0
Если , то скорость -- быстрее, чем у обычного метода
Если то после (n-1) итерации все аij = 0.
8. Численное решение обыкновенных дифференциальных уравнений методом Рунге-Кутта 4-го порядка. Критерии точности и сходимости. Выбор оптимальной величины шага интегрирования.
Метод Рунге-Кутта 4-ого порядка. Общая часть: Поставка задачи.
1) Задача Коши
2) Система ДУ
3) Уравнение с высшими производными
тоже Задача Коши, как 1) и 2)
1), 2), 3) – одно и тоже (один вид постановки задачи может быть преобразован к другому)
Пример этого преобразования:
Для системы 5-ого порядка:
Алгоритм Рунге-Кутта:
Тогда,
Для системы: всё точно также, только стоят вектора над k, f, y.
Распишем вектора в нормальном виде.
При описании k надо не забыть, что это 2-мерная матрица 4*n:
Критерий устойчивости:
Критерий точности:
(Для многомерного случая вместо берется у матрицы частных производных )
Критерий увеличения (уменьшения) шага:
(при динамическом определении шага)
если crit > порог 1, то надо уменьшить шаг, если Crit < порог 2 < порог 1, то можно шаг увеличить.
Алгоритм:
-
Считаем у матрицы частных производных в
-
Берём
-
Делаем 1-ый шаг и считаем
-
Устанавливаем пороги:
9. Численное решение обыкновенных дифференциальных уравнений методом прогноза и коррекции. Области применимости метода.
Метод прогноза и коррекции 4-ого порядка.
Таких методов много, отличаются значением коэффициентов коррекции.
Алгоритм:
-
Считаем методом RK4 (первые 3 шага)
Дальше собственно метод:
Делаем расчёты, исходя из прогноза, для которого нужна основа, например, 4 точки (поскольку метод 4-ого порядка) в качестве начальных условий.
-
Расчёт предсказания:
-
Изменение предсказания:
-
Изменение производной:
-
Коррекция:
-
Значение в точке xi+1:
Гарантированная погрешность.
Свойства:
-
2 раза расчёт f на каждом шаге (остальные f рассчитаны ранее)
-
Погрешность < a = o(h5)=
Достоинства метода: 1) маленькая погрешность
2) всего 2 раза высчитываем функцию.
Недостатки метода: не может работать самостоятельно, сначала надо прорешать несколько шагов методом RK.
10. Метод прогонки для решения систем линейных алгебраических уравнений с трехдиагональной матрицей.
Решение трёх-диагональных СЛАУ методом прогонки.
Решение (алгоритм):
Ищем решение в виде: , где и неизвестные пока функции.
Подставим в исходную систему:
1, 1 берутся из 1-ого начального условия:
Алгоритм.
-
Находим 1, 1 из 1-ого начального условия.
-
Прямая прогонка: i = 1, 2, …, n-1
cчитаем все i+1 и i+1
-
Из последнего начального условия находим xn
-
Обратная прогонка: i = n, n-1, …, 1