Метод простой итерации и метод Зейделя

1. Метод простой итерации. Этот метод при определённых условиях применим и к решению систем линейных уравнений, поскольку любую систему A·X = b можно рассматривать как уравнение вида F(X) = X, где F(X) = (I_n – D·A)·X + D·b с любой невырожденной (n´ n)- матрицей D, в банаховом пространстве ⁿR. Действительно,

F(X) = X Û (I_n – D·A)·X + D·b = X Û I_n·X – D·A·X + D·b = X Û

Û D·A·X = D·b Û A·X = b.

Последняя эквивалентность в этой цепочке обусловлена невырожденностью матрицы D.

Для применимости этого метода функция F(X) = (I_n – D·A)·X + D·b должна быть сжимающим отображением, т.е. удовлетворять условию ||F(X) – F(Y)|| £ c·||X – Y|| при некотором 0 < c < 1 и любых X, Y Î ⁿR. Ясно, что F(X) = B·X + e, где B = I_n – D·A, e = D·b.

Теорема (достаточное условие сходимости метода простой итерации). Пусть для некоторой матричной нормы верно ||B|| < 1. Тогда отображение F(X) = B·X + e будет сжимающим, а значит, метод простой итерации X_n+1 = F(X_n) будет сходиться при любом начальном приближении X₀ к единственному решению X уравнения F(X) = X. При этом

|| X – X_n|| £ , ||X_n+1 – X|| £ ||B||·||X_n – X||.

Доказательство. Нужно обосновать только сжимаемость отображения F – все остальные утверждения следуют из теоремы о неподвижной точке сжимающего отображения в банаховом пространстве.

Имеем ||F(X) – F(Y)|| = ||B·(X – Y)|| £ ||B||·||X – Y||, т.е. в качестве коэффициента сжатия можно взять c = ||B|| < 1. Если положить X₀ = e, то X₁ = B·e + e, и из доказанная ранее оценка || X – X_n|| £ приводит к нужному неравенству || X – X_n|| £ .

Теорема доказана.

Пример. Решить систему с точностью до 0, 001:

.

–

система в виде X = B·X + e, где , и

||B||_¥ = max{0, 4+0, 2+0, 3+0, 05; 0, 2+0, 2+0, 3+0, 1;

0, 05+0, 3+0, 5+0, 1; 0, 5+0, 1+0, 1+0, 1} = 0, 95 < 1.

Поэтому применим метод простой итерации:

В этой таблице D_n = ||X_n – X_n–1||_¥ , а вычисления ведутся пока D_n ³ D – заданной точности вычислений.

Если оценивать количество итераций по формуле || X – X_n|| £ , то получим , т.е. n+1 < . Таким образом, иногда метод сходится быстрее этой оценки.

Возникает вопрос: для любой ли матрицы A можно найти такую обратимую матрицу D, что ||B|| = ||I_n + D·A|| < 1 для некоторой матричной нормы? Ответ, конечно, утвердителен: например, если взять D = –A^–1, то ||B|| = ||0|| = 0 < 1. В некоторых случаях матрицу D найти легко:

Лемма (о матрицах с диагональным преобладанием).

(1) Если матрица А с диагональным преобладанием по строкам: (1 £ i £ n), то ||I_n – D·A||_¥ < 1 для диагональной матрицы D с элементами d_i = a_ii^–1 по диагонали. В этом случае итерационный процесс X_k+1 = (I_n – D·A)·X_k + e сходится при любом начальном приближении X₀ к единственному решению системы уравнений A·X = b = D^–1·e.

(2) Если матрица А с диагональным преобладанием по столбцам: (1 £ j £ n), то ||I_n – A·D||₁ < 1 для диагональной матрицы D с элементами d_i = a_ii^–1 по диагонали. В этом случае итерационный процесс Y_k+1 = (I_n – A·D)·Y_k + e сходится при любом начальном приближении Y₀ к единственному решению системы линейных уравнений A·D·Y = e. Таким образом, вектор D·Y является решением системы A·X = b = e.

(3) Любая матрица элементарными преобразованиями строк (столбцов) приводится к виду с диагональным преобладанием по строкам (столбцам). Таким образом, любую систему линейных уравнений A·X = b можно преобразованиями строк привести к виду, пригодному для применения метода простой итерации.

Доказательство. (1) Если матрица А с диагональным преобладанием по строкам, то матрица C = D·A имеет элементы c_{i j} = (1 £ £ n). Поэтому для матрицы B = I_n – D·A при любом 1 £ i £ n справедливы равенства b_ii = 0, b_ij = и , так что ||B||_¥ = < 1.

Все остальные утверждения следуют из общей теории сжимающих отображений.

(2) Все вычисления для обоснования неравенства ||I_n – A·D||₁ < 1 аналогичны предыдущим. Поэтому при любом начальном приближении Y₀ сходится итерационный процесс Y_k+1 = (I_n – A·D)·Y_k + e. Переходя к пределу в итерационном соотношении, получим Y = (I_n – A·D)·Y + e Û A·D·Y = e. Все остальные утверждения следуют из общей теории сжимающих отображений.

(3) Это очевидно, т.к. обратимую матрицу A можно элементарными преобразованиями строк привести к диагональному виду, который, очевидно, обладает свойствами диагонального преобладания.

Лемма доказана.

Пример. Решить систему с точностью до 0, 001:

.

(переписали систему A·X = b в виде X = B·X + e). При этом нетрудно убедиться, что ||B||₁ > 1, ||B||_¥ > 1, ||B||₂ > 1 (?!), так что метод простой итерации напрямую неприменим.

В то же время, исходная матрица A = системы удовлетворяет свойству диагонального преобладания по столбцам. Поэтому можно воспользоваться леммой о матрицах с диагональным преобладанием: D = . При этом

B = I₄ – A·D» , ||B||₁ < 1.

Применяем метод простой итерации Y_k+1 = (I_n – A·D)·Y_k + b для решения системы A·D·Y = b и находим X = D·Y:

В последней строке этой таблицы приведены решение X исходной системы и норма невязки, соответствующей этому решению.

Замечание: При применении метода простой итерации могут возникнуть проблемы (см., например, [1, стр. 271]), которые состоят в том, что ранее сходимости может случиться переполнение (числа становятся слишком большие даже для ЭВМ). Эти нюансы подробно обсуждать не будем.

2. Метод Зейделя. Покомпонентная запись метода простой итерации X_n+1 = B·X_n + e приведена в нижеследующих формулах слева. Здесь x_j⁽ⁱ⁾ – j- я компонента вектора X_i – приближения, вычисленного на i- й итерации. Метод Зейделя, покомпонентные формулы которого приведены справа допускает использование при вычислении компоненты x_i⁽ⁿ⁺¹⁾ вектора X_n+1 уже вычисленных предыдущих его компонент x₀⁽ⁿ⁺¹⁾, …, x_i–1⁽ⁿ⁺¹⁾.

Для того чтобы записать эти формулы в матричном виде, введём две матрицы, связанные с матрицей B:

.

Тогда метод Зейделя можно записать в матричном виде следующим образом:

X_n+1 = C·X_n+1 + D·X_n + e Û (I_n – C)·X_n+1 = D·X_n + e Û

Û X_n+1 = (I_n – C)^–1·D·X_n + e.

Здесь матрица I_n – C – верхнетреугольная с ненулевыми элементами по диагонали, а потому обратима.

Таким образом, формально говоря, метод Зейделя – это частный случай метода простой итерации с матрицей U = (I_n – C)^–1·D. Однако, сходится метод Зейделя, как правило, быстрее. Это утверждение далеко не очевидно, т.к. нельзя даже утверждать, что при выполнении условия ||B|| < 1 будет выполнено условие ||U|| < 1.

Пример: Если B = , то С = , D = и I₂ – C = , (I₂ – C)^–1 = , U = (I₂ – C)^–1·D = . Кроме того, ||B||₁ = 0, 9 < 1, но ||U||₁ = 1, 1 > 1.

Таким образом, непосредственно применить изложенную выше теорию не удаётся. Тем удивительнее следующая теорема, доказательство которой можно найти в [9, стр. 235].

Теорема (о методе Зейделя). Если ||B||₁ < 1 или ||B||_¥ < 1, то метод Зейделя сходится, причём, как правило, несколько быстрее метода последовательных приближений.

Пример. Решить систему с точностью до 0, 001:

.

–

система в виде X = B·X + e, где , и

||B||_¥ = max{0, 4+0, 2+0, 3+0, 05; 0, 2+0, 2+0, 3+0, 1;

0, 05+0, 3+0, 5+0, 1; 0, 5+0, 1+0, 1+0, 1} = 0, 95 < 1.

Поэтому можно применить метод Зейделя:

Сравнение проведённых вычислений с расчётами по методу простой итерации в первом примере этого параграфа показывает, что в данном случае метод Зейделя сходится хуже. Таким образом, оговорка “как правило” в сформулированной выше теореме не случайна.