Простейшим итерационным методом для решения СЛАУ является метод простой итерации (МПИ), основным недостатком которого является его низкя скорость сходимости. Здесь исходная СЛАУ (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): , которая определяет действия данного алгоритма на каждой итерации. Очевидно, что эти действия сводятся к умножению матрицы на вектор длины (), что потребует операций, и к последующему сложению двух векторов длины (), что потребунт еще операций. В итоге, каждая итерация МПИ требует операций, тогда в целом количество арифметических операций, необходимых для решения СЛАУ МПИ, определиться как
,
где - это количество итераций, затраченных в МПИ для достижения заданной точности решения . Очевидно, что в итоге вычислительная сложность МПИ (как и любого другого итерационного метода) определяетсяколичеством итераций .