Демидович Б. П., Марон И. А. Основы вычислительной математики. М.: Наука, 1966, стр 294.

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

Приведем решаемую систему 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(0) - некоторое начальное приближение к решению (обычно полагают x(0)=d).

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


x1(k+1) = c11x1(k) + c12x2(k) + ... + c1nxn(k) + d1
x2(k+1) = c21x1(k) + c22x2(k) + ... + c2nxn(k) + d2
...
xn(k+1) = cn1x1(k) + cn2x2(k) + ... + cnnxn(k) + dn

Таким образом i-тая компонента (k+1)-го приближения к решению вычисляется по формуле
xi(k+1) = å nj=1 cijxj(k), i=1, ..., n (1.14)

Имеет место следующая:

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

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

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

|aii| >å nj = 1, j ¹ i|aij|, 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 ||) e / || C || (1.18)

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

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

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

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

Назад