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

Приведем решаемую систему Ax=b эквивалентным преобразованием к виду:

x = C x + d	(1.11)

Это возможно сделать многими способами. Например, умножим слева обе части равенства 0 = -A x + b на произвольную невырожденную матрицу H и прибавим вектор x к правой и левой части полученного равенства:

x = x - H A x + H b = (E - H A) x + H b

Отсюда находим:

C ≡ E - HA, d ≡ H b.	(1.12)

Матрицу H нужно выбирать так, чтобы C обладала определенными свойствами, о которых будет сказано ниже (теорема 1.1).

Итерационный процесс (то есть процесс последовательных приближений) метода простой итерации описывается формулой:

x(k+1) = C x(k) + d, k = 0, 1, ...,	(1.13)

где x⁽⁰⁾ - некоторое начальное приближение к решению (обычно полагают x⁽⁰⁾=d).

В координатной форме метод простой итерации записывается следующим образом:

x₁^(k+1) = c₁₁x₁^(k) + c₁₂x₂^(k) + ... + c_1nx_n^(k) + d₁
x₂^(k+1) = c₂₁x₁^(k) + c₂₂x₂^(k) + ... + c_2nx_n^(k) + d₂
...
x_n^(k+1) = c_n1x₁^(k) + c_n2x₂^(k) + ... + c_nnx_n^(k) + d_n

Таким образом i-тая компонента (k+1)-го приближения к решению вычисляется по формуле

xi(k+1) = ∑ nj=1 cijxj(k), i=1, ..., n	(1.14)

Имеет место (см.[1, стр.323]) следующая:

ТЕОРЕМА 1.1 Для сходимости последовательных приближений {x^(k)} метода простой итерации к точному решению системы (1.11) достаточно, чтобы || C || < 1.

Таким образом, если некоторая норма матрицы C меньше единицы, то итерационный процесс, основанный на формуле (1.13), гарантированно сходится к искомому решению при любом начальном приближении x⁽⁰⁾.

ЗАДАЧА 1.1 Доказать, что если матрица A обладает свойством

|a_ii| > ∑ ⁿ_{j = 1, j} ≠ i|a_ij|, i = 1, ..., n,

то к неравенству || C || ₁ < 1 для C из формулы (1.12) приводит матрица

ТЕОРЕМА 1.2 Пусть || C || < 1, тогда при использовании метода простой итерации справедлива следующая оценка:

|| x - x(k+1) || ≤ || C || || x(k+1) - x(k) || / (1-|| C ||)	(1.15)

ДОКАЗАТЕЛЬСТВО: Из равенств

x = Cx + d,
x^(k+1) = C x^(k) + d

путем вычитания получим

x - x(k+1) = C ( x - x(k) ).	(1.16)

Перенесем x^(k+1) вправо и вычтем вектор x^(k) из левой и правой части полученного равенства:

x - x^(k+1) = x^(k+1) - x^(k) + C (x - x^(k)).

Теперь будем оценивать норму вектора x-x^(k+1) пользуясь неравенством треугольника и определением согласованности норм:

|| x - x ^(k) || ≤ || x ^(k+1) - x ^(k) || + ||C|| || x - x ^(k) ||.

Отсюда получаем оценку:

|| x - x(k) || ≤ || x(k+1) - x(k) || / (1-|| C ||)	(1.17)

Кроме того из (1.16) следует:

|| x - x ^(k+1) || ≤ || C || || x - x ^(k) ||.

Учитывая (1.17), окончательно получаем:

|| x - x^(k+1) || ≤ || C || || x^(k+1) - x^(k) || / (1-|| C ||)

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

Эта теорема позволяет сформулировать следующее условие окончания итерационного процесса при достижении задaнной точности e:

|| x(k+1) - x(k) || ≤ (1-|| C ||) ε / || C ||	(1.18)

Действительно, в этом случае из теоремы 1.2 следует:

|| x - x (k+1) || ≤ ε.	(1.19)

При выполнении неравенства (1.18) решение системы A x = b полагают равным x^(k+1) (с точностью ε).

Из формул (1.15), (1.18) также видно, что чем меньше норма || C ||, тем быстрее сходимость итераций к решению.