§ 3. Метод простой итерации

Простейшим итерационным методом решения систем линейных уравнений является метод простой итерации. Система уравнений

преобразуется к виду

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

Всякая система

Имеет вид (2) и при эквивалентна системе (1). В то же время всякая система (2), эквивалентная (1), записывается в виде (4) с матрицей .

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

Доказательство. Для всякого решения системы (2) имеет место , поэтому справедливо неравенство или . Отсюда следует существование и единственность решения однородной системы , а следовательно, и системы (2). Пусть X — решение системы (2). Из (2) и (3) получаем уравнение относительно погрешности :

Из (5) получаем равенство

Отсюда следует, что . Теорема доказана.

Качество итерационного процесса удобно характеризовать скоростью убывания отношения погрешности после итераций к начальной погрешности:

Можно гарантировать, что величина , если , т.е. при

Если существуют постоянные , такие, что при

то нормы и называются эквивалентными. Имеем

Таким образом, если условие доказанной теоремы выполнено для нормы , то утверждение справедливо относительно любой эквивалентной ей нормы.

Любые две нормы в конечномерном пространстве эквивалентными. В частности, нормы , вычисляемые соответственно по формулам (2), (3), (4), приведенным во введении к настоящей главе, эквивалентны между собой вследствие справедливости цепочки неравенств

Лемма. Пусть все собственные значения матрицы В лежат в круге , причем собственным значениям, по модулю равным q, соответствуют жордановы клетки размерности 1. Тогда существует матрица с нормой .

Доказательство. Положим . Собственными значениями матрицы будут . Преобразуем матрицу к жордановой форме

где принимают значения 0 или 1. После умножения на получим

Если , то согласно условиям леммы, . Отсюда следует, что . Если , то

Таким образом, .

Теорема (о необходимом и достаточном условии сходимости метода простой итерации). Пусть система (2) имеет единственное решение. Итерационный процесс (3) сходится к решению системы (2) при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы В по модулю меньше 1.

Доказательство. Достаточность. Возьмем произвольное q в пределах . Условие леммы выполнено по отношению к этому , поэтому существует матрица D такая, что при . Поскольку , то

Поэтому

и

при . Следовательно, и .

Если — координатные орты, , то . Пусть - некоторая норма, тогда

Поэтому при любой норме имеем

Соотношения (8), (9) означают также, что любые нормы погрешности убывают быстрее любой геометрической прогрессии со знаменателем, большим .

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

Задача 1. Пусть все собственные значения матрицы В, за исключением простого лежат внутри единичного круга и система (2) имеет решение X. Решением системы будут также все . Доказать, что итерационный процесс (3) сходится к одному из таких решений.