- •1. Метод Данилевского
- •1.1 Метод Гаусса.
- •1.2 Метод Гаусса с выбором главного элемента. ( )
- •1.3 Метод оптимального исключения ( )
- •1.4 Метод прогонки.
- •II. Методы, основанные на разложении матрицы коэффициентов.
- •2.1. Метод квадратного корня (случай эрмитовой матрицы)
- •2.2 Частный случай метода квадратного корня (случай симметричной матрицы)
- •2.3 Схема Халецкого (случай матрицы с отличными от 0 глав. Минорами).
- •Приближенные (итерационные) методы.
- •2.1 Метод простой итерации.
- •2.2 Метод Якоби.
- •2.3 Метод Зейделя.
- •2. Решение полной проблемы собственных чисел.
- •1. Метод Данилевского
- •2. Итерационный метод вращений.
- •Решение нелинейных уравнений.
- •1.2.1 Метод половинного деления (метод дихотомии).
- •1.2.2 Метод Ньютона или метод касательных
- •1) Существование производных 1-го и 2-го порядков;
- •1.2.3 Метод хорд. Метод секущих.
- •1.2.4 Метод простой итерации.
- •III. Решение дифференциальных уравнений.
- •Задачи с начальными условиями для оду (задача Коши).
- •Численные методы решения дифференциальных уравнений Одношаговые методы. Метод Эйлера и его модификации
- •Одношаговые методы. Метод Эйлера и его модификации.
- •1 Метод Эйлера
- •2. Метод Рунге-Кутта.
- •Многошаговые методы
- •1. Формулировка методов
- •Постановка линейных краевых задач для оду 2-го порядка.
- •Конечно-разностный метод решения краевой задачи.
II. Методы, основанные на разложении матрицы коэффициентов.
Такие методы основаны на представлении матрицы А коэффициентов системы в форме произведения треугольных матриц. Это позволяет свести решение заданной системы к последовательному решению двух систем с треугольными матрицами, что является задачей более простой, так как в них неизвестные находятся последовательно. Иногда вводят еще диагональную матрицу.
2.1. Метод квадратного корня (случай эрмитовой матрицы)
Найдем такую правую треугольную матрицу и диагональную матрицу , элементы которой равны 1 или –1, чтобы имела представление
(2)
Если матрицы и найдены, то заданная система (1) может быть решена следующим путем:
,
где есть нижняя треугольная матрица и – вспомогательный вектор. Решение системы (1) равносильно решению двух треугольных систем
Замечание: Алгоритм – разложения может оказаться численно неустойчивым, гарантировать устойчивость алгоритма можно в двух случаях – для положительно определенных матриц А и матриц с диагональным преобладанием.
2.2 Частный случай метода квадратного корня (случай симметричной матрицы)
Идея метода:
Метод основан на разложении матрицы на множители,
, (3)
где
И решение системы (1) сводится к решению двух систем с треугольными матрицами:
(4)
Прямой ход:
Перемножая матрицы и и приравнивая матрице , из (3) получим формулы для определения
Обратный ход:
После того, как матрица найдена, решаем задачу (4).
2.3 Схема Халецкого (случай матрицы с отличными от 0 глав. Минорами).
Рассматриваем систему уравнений (1), где матрица размера такая, что ее главные миноры отличны от нуля.
,
Теорема 1. Если главные миноры матрицы отличны от нуля:
то матрицу можно представить в форме
,
где
.
Отсюда искомый вектор х может быть вычислен из цепи уравнений
Эта схема вычислений называется схемой Халецкого.
Решение систем линейных алгебраических уравнений (ЛАУ)
Приближенные (итерационные) методы.
2.1 Метод простой итерации.
Пусть дана система ЛАУ с неособенной матрицей.
(1)
Тем или иным способом система (1) может быть преобразована к эквивалентной ей системе вида
, (2)
где – тот же вектор неизвестных, а и – некоторые новые матрица и вектор соответственно.
В методе простой итерации (МПИ) решение системы (2) и, следовательно, решение исходной системы (1) ищется как предел последовательности векторов при :
, (3)
где – начальное приближение к точному решению системы.
Теорема 2. Пусть . Тогда при любом начальном приближении МПИ (3) сходится к единственному решению задачи (2) и при всех справедливы оценки погрешности:
1) (апостериорная); (6)
2) (априорная)1. (7)
Замечание 1. Априорная оценка (7) позволяет подсчитывать заранее число итераций , достаточное для получения решения с заданной точностью при выбранном начальном приближении . Для этого нужно найти наименьшее целое решение неравенства относительно переменной . Апостериорной оценкой (6) удобно пользоваться в процессе вычислений и останавливать этот процесс, как только выполнится неравенство
. (6`)
Иногда используется более простое условие остановки итерационного процесса . Это неравенство будет гарантией выполнения неравенства только в том случае, когда .
Замечание 2. (О выборе начального приближения). Согласно теореме 1, сходимость МПИ (3) гарантируется при любом начальном приближении . Очевидно, итераций потребуется тем меньше, чем ближе к . Если нет никакой дополнительной информации о решении задачи (2) (например, может быть известным решение близкой задачи или грубое решение данной задачи) за обычно принимают вектор свободных членов системы (2). Априорная оценка (7) принимает вид
.
Таким образом, если задана точность , то
,
откуда получаем априорную нижнюю оценку числа итераций при :
. (8)
Неравенство (8) обычно дает завышенное число итераций .
Непосредственным следствием теоремы 2 и равенств
; ,
определяющих кубическую и октаэдрическую норму матрицы, являются следующие оценки погрешности приближенного решения :
, , (9)
если выполнено условие , и
, , (10)
если выполнено условие .
Эти оценки можно еще усилить соответственно так:
(9`)
и . (10`)
МПИ в координатной форме имеет вид: