Теорема Самарского о сходимости стационарных методов

Теорема. Пусть , и , тогда итерационный процесс

(3.15)

сходится при любом выборе начального приближения .

Метод Якоби

Представим матрицу A в виде суммы трех матриц , где

- нижняя треугольная матрица с 0 на главной диагонали.

- верхняя треугольная матрица с 0 на главной диагонали.

.

Для метода Якоби имеем и :

.

. (3.16)

Запишем метод в координатной форме:

для всех .

для всех .

Предполагается, что для всех .

Алгоритм метода Якоби

· Задание исходных матрицы A и вектора правой части f.

· Проверка выполнения условия для всех .

· Задание начального приближения .

Строго говоря, задавать любое начальное приближение для любого итерационного метода нельзя. При формулировке любого итерационного метода обычно оговариваются условия выбора . Если этих условий нет, то часто берут или . От выбора зависит скорость сходимости метода, поэтому иногда прибегают к подбору.

· Выполнение следующей итерации . Вычисление очередного приближения .

· Проверка условия сходимости. Обычно используют критерий , где - норма.

· В случае выполнения условия - печать решения и невязки, количества выполненных итераций.

Возможные ошибки

· Плохое начальное приближение.

· Ошибки при организации суммирования.

· Замена в формулах известного приближения на искомое .

· Ошибка с индексами переменных.

· Неправильно переписанная формула метода.

· Ошибка в критерии условия сходимости.

Теорема сходимости метода Якоби

Теорема. Пусть с диагональным преобладанием, тогда метод Якоби сходится для любого начального приближения.

Рекомендации

· Если задача не подходит под условие теоремы, то это еще не значит, что метод нельзя использовать.

· При составлении программы рекомендуется придумать новую вспомогательную задачу с матрицей с диагональным преобладанием, решение для которой заранее известно. Отладив программу для вспомогательной задачи, приступайте к решению своей конкретной задачи.

· На практике проверить достаточные условия сходимости бывает довольно трудно или невозможно. Поэтому часто метод и его параметры подбирают эмпирически.

Метод Зейделя

Для метода Зейделя берут и :

.

. (3.17)

Запишем метод в координатной форме:

для всех .

Теорема сходимости метода Зейделя

Теорема. Пусть , тогда метод Зейделя сходится для любого начального приближения.

Метод верхней релаксации

Положим и - параметр >0:

.

(3.18)

Запишем метод в координатной форме:

для .

Итак,

.

,

и т.д.

Теорема сходимости метода верхней релаксации

Теорема. Пусть и , тогда метод верхней релаксации сходится для любого начального приближения.

Метод итерации

Решаем систему уравнений . Предполагаем, что для всех .

Разрешим первое уравнение системы относительно , второе уравнение относительно и т.д. В результате получим следующую систему уравнений:

, (3.19)

где , при и при .

Следовательно, систему (3.19) можно записать в виде .