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

Простейшим итерационным методом для решения СЛАУ является метод простой итерации (МПИ), основным недостатком которого является его низкая скорость сходимости. Здесь исходная СЛАУ (1) преобразуется к виду

(2)

где - матрица, - вектор длины , а решение СЛАУ (2) находится как предел последовательности

(3)

Ключевым вопросом при изучени итерационных методов является вопрос их сходимости (к точному решению СЛАУ). Надо выяснить, каким условиям должна удовлетворять матрица в (2) и (3), чтобы итерационный процесс (3) сходился.

Лемма 1. Для того, чтобы матричный ряд

где - единичная матрица, сходился, необходимо и достаточно, чтобы все собственные значения (СЗ) матрицы по модулю были меньше 1:

.

При выполнении этого условия матрица имеет обратную, и справедливо равенство:

Лемма 2. Для того, чтобы необходимо и достаточно, чтобы чтобы все СЗ матрицы по модулю были меньше 1.

Лемма 3. Модули собственных значений матрицы не превосходят любую из ее норм.

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

Доказательство. Достаточность. Найдем точное решение СЛАУ (2):

.

Найдем выражение для в формуле (3) через :

По лемме 1 матричный ряд в правой части (4) сходится к матрице , кроме того в силу необходимого условия сходимости ряда его k-ый член стремится к нулю, т.е.

.

Тогда переходя к пределу при в формуле (4), получим:

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

,

что и требовалось доказать.

Необходимость. Пусть для любого начального приближения векторная последовательность , построенная по формуле (3), сходится к : . Рассмотрим

. (5)

Поскольку , то . Поэтому, если в (5) перейти к пределу, получим:

.

Тогда в соответствии с леммой 2 из последнего равенства следует, что все СЗ матрицы по модулю были меньше 1, что и требовалось показать.

Применение доказанной теоремы требует знание границ спектра (спектр – множество собственных значений) матрицы . На практике эти границы не всегда можно легко определить, поэтому сформулируем еще некоторые достаточные условия сходимости МПИ.

Теорема 2. Для того, чтобы векторная последовательность , построенная по формуле (3), сходилась к решению СЛАУ (1) (и (2)) , достаточно, чтобы какая-либо норма матрицы была меньше 1:

.

Доказательство очевидно вытекает из предыдущей теоремы и леммы 3.

Следствие. Если для матрицы выполняется

,

или

,

то

.

Предположим, что МПИ, построенный по формуле (3) для решения СЛАУ (1) (и (2)) сходится. В общем случае итерационный процесс (3) даст точное решение за бесконечное число итераций. В силу этого при решении СЛАУ итерационным методом с самого начала задается абсолютная погрешность , приемлемая для получаемого приближенного решения. На каждом итерационном шаге происходит проверка достижения заданной точности. Эта проверка может происходить следующим образом: если , то итерационный процесс завершается, и полагается равным , иначе переход на очередной итерационный шаг.

Пусть матрица СЛАУ (1) имеет диагональное преобладание по строкам, т.е. для ее элементов выполняются соотношения:

.

Тогда переход от вида (1) к виду (2) СЛАУ, определяющему сходящийся МПИ, можно провести следующим образом:

Последняя система имеет уже вид (2), для которого

.

Поскольку для исходной матрицы в силу ее диагонального преобладания выполнялись соотношения , то при делении каждого i-го соотношения на получим:

.

А значения - это значения модулей внедиагональных элементов полученной выше матрицы :

.

Тогда для полученной матрицы выполняются соотношения:

,

Но учитывая, что , последние неравенства можно переписать в виде:

,

а это означает (по следствию из теоремы 2), что МПИ сходится к точному решению СЛАУ (1):

.

Замечание 1. МПИ является одним из самых медленных итерационных методов решения СЛАУ.

Замечание 2 (вычислительная сложность МПИ). Основная расчетная формула МПИ – это формула (3): , которая определяет действия данного алгоритма на каждой итерации. Очевидно, что эти действия сводятся к умножению матрицы на вектор длины ( ), что потребует операций, и к последующему сложению двух векторов длины ( ), что потребунт еще операций. В итоге, каждая итерация МПИ требует операций, тогда в целом количество арифметических операций, необходимых для решения СЛАУ МПИ, определиться как

,

где - это количество итераций, затраченных в МПИ для достижения заданной точности решения . Очевидно, что в итоге вычислительная сложность МПИ (как и любого другого итерационного метода) определяетсяколичеством итераций .