Итерационные методы решения систем линейных алгебраических уравнений

Материал из Викиверситета
Перейти к навигации Перейти к поиску

Метод простой итерации[править]

приводим к виду, удобному для итерации:

Самый простой метод: из -го уравнения выражаем . Возможно только если диагональные элементы матрицы ненулевые. Иногда приводят к виду , где - специально выбираемый числовой параметр. Описание: Выбираем начальное приближение

Если система получена по вышеописанному (самому простому) методу, то МПИ называется методом Якоби.

Теорема. Пусть выполнено условие , тогда
  1. решение системы
  2. при начальном приближении МПИ сходится и справедлива оценка погрешности
Доказательство. решение СЛАУ при любой правой части однородная система имеет только нулевое решение

Пусть - решение системы так как , то и 1. доказано.

- верное

при получаем при


Замечание. При получаем: .


Апостериорная оценка погрешности:

Если , то справедлива апостериорная оценка:

Доказательство.


Критерий окончания итерационного процесса: , где . Если - симметричная, положительно определенная матрица, то , часто приводят к виду

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

Тогда . Если известны не сами и , а их оценки или или . В случае то метод сходится медленно.

Метод Зейделя - модификация метода Якоби[править]

где , ,

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

Введем: - верхняя и нижняя треугольные матрицы.

удовлетворяет:

Теорема. Пусть , где - одна из норм . Тогда метод Зейделя сходится со скоростью геометрической прогресии с . (без доказательства)
Теорема. Пусть выполнено условие . Тогда метод Зейделя сходится и верна оценка погрешности: , где
Доказательство. :

Неравенство верно для при


Теорема. - симметричная положительно определенная матрица. Тогда метод Зейделя сходится со скоростью геометрической прогресии (без доказательства)

Апостериорная оценка: Если , то .

Возьмем

Для данного критерий окончания: , где

Геометрическая интерпретация метода Зейделя

Расчетные формулы:

Метод Якоби
Замечание. Метод Якоби ориентирован на системы с матрицами, близкими к диагональным, а метод Зейделя - на матрицы, близкие к нижним треугольным.


Метод релаксации[править]

После вычисления -ой компоненты по методу Зейделя (-го приближения) Производится дополнительно смещение этой компоненты на величину , где - параметр релаксации. То есть -я компонента -го приближения вычисляется по формуле:

Компактная формула:

При получаем метод Зейделя. Если - метод последовательной верхней релаксации. Если - метод последовательной нижней релаксации. Если - симметричная и положительно определенная матрица, то метод релаксации сходится. Иногда можно выбрать так, чтобы метод сходился существенно быстрее, чем метод Якоби и Зейделя. Выбор параметра - зачастую экспериментально.