Итерационные методы решения систем ЛАУ. Метод простой итерации. Условия сходимости и критерий остановки итераций.

Общая схема больш-ва итерационных методов реш-я СЛАУ (1) с невырожденной матрицей  и заданным вектором пр. части  имеет вид ,  (2)

где – матрица итерационного метода,  – начальное приближение итерационного процесса. Последоват-ть ,  - итерационные приближения искомого решения.

Итерационный метод, в котором для вычисления каждого нового  используется лишь  - итерационный методом 1 порядка, или одношаговым  итерационным методом.   

Итерационный процесс (2) приводит к решению задачи (1) ó вып-ся условия:

1. последовательность векторов , , сходится.

2. предел данной последовательности является решением (1).

Из 2 =>  матрица  и вектор могут быть заданы в виде: ,  (3)

где  – единичная матрица,  – невырожденная матрица: выполнено условие 1.

Для произвольных невырожденных матриц  и  существует единственное значение вектора  такое, что  и с учетом выбора (3):

Разнообразие итерационных методов связано с выбором конкретного вида матрицы - переобусловливателя. Если матрица  одинакова для всех итераций, то итерационный процесс называется стационарным. Среди нестационарных традиционно используются переобусловливатели вида , где  для каждой итерации выбирается из расчета наибольшей скорости сходимости. С точки зрения алгоритмической реализации итерационный процесс (2), (3) удобно представить в виде  (5)

При (5), в отличие от (2), (3), не нужен явный вид м-цы и выч-е очередного итерационного приближения сводится к решению СЛАУ:  (5')

Метод простой итерации: Стационарный одношаговый итерационный метод вида  (6). По (2) . По (5) .

Теорема. Пусть  – симметричная положительно определенная матрица , тогда итерационный метод (6) сходится при .

Доказательство: Спектральная норма симметричной матрицы определяется: . Если  – симметричная матрица, то матрица  также будет симметричной и . Тогда . Из положительной определенности матрицы   следует, что при  выполняется оценка , из которой следует, что . 

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

Доказательство: Поиска оптимального зн-я итер-го параметра  = определение условия минимума как функции от . Найдем явный вид данной функции.

.

Несложно заметить, что  и  => в интервале значений  функция  принимает минимальное значение. Поскольку функция  определяется максимальным значением модулей двух линейных функций, то минимум такой функции может достигаться только в точке равенства модулей данных линейных функций. Ур-е  имеет единственный корень на интервале : . При этом .   Теорема доказана.

Скорость сходимости метода простой итерации зависит от отношения  даже в случае оптимального выбора итерационного параметра. Для симметричных положительно определенных м-ц , . => , где  – число обусловленности . Для плохо обусловленных матриц (не близко к 1) значение  велико, и тогда по (7) (эфф-ть м-да может ухудшаться при )