3.4.1. Каноническая форма метода простой итерации

Для построения канонической формы метода простой итерации [9, 10] систему уравнений (3.22) запишем в виде

, (3.26)

где a_ii0.

Второй член правой части (3.26) будет

, (3.27)

где D=[a_ii] – диагональная матрица.

Подставляя (3.27) в (3.26) получим

,

в матричной форме

x^(k+1)-x^(k)=D^-1(b-Ax^(k))

или в канонической форме

D + Ax^(k)=b, =1, k=0, 1, 2,…

3.4.2. Каноническая форма метода Зейделя

Для решения системы (3.22) методом Зейделя, метод можно записать в следующей форме

, (3.28)

где a_ii0. Из формулы (3.28) получим формулы для последовательного вычисления (к=0, 1, 2,…)

. (3.29)

В матричной форме (3.29) примет вид

x^(k+1)=D^-1(b-Ux^(k)-Lx^(k+1)), (3.30)

где D – диагональная матрица, U и L – соответственно, верхняя и нижняя треугольные матрицы, так что

A=L+D+U. (3.31)

Из формул (3.30) и (3.31) после простых преобразований получим каноническую форму метода Зейделя [9, 11]

(D+L)(x^(k+1)-x^(k))+Ax^(k)=b, (3.32)

где =1, k=0, 1, 2,…

Для ускорения сходимости итерационного процесса, можно привести метод Зейделя (3.32) к методу релаксации, вводя итерационный параметр , тогда имеем

(D+L) +Ax^(k)=b, k=0, 1, 2,… (3.33)

Отметим, что при 1<<2 метод (3.33) называется верхней релаксацией, при 0<<1 – нижней релаксацией, при =1 – полной релаксацией или методом Зейделя.

3.4.3. Теоремы двухслойных итерационных методов

Двухслойные итерационные методы в канонической форме записываются в виде

В + Ax^(k)=b, (3.34)

где В – вещественная невырожденная матрица, _k+1 – последовательность итерационных параметров, х⁽⁰⁾ – произвольный начальный вектор.

Имея, вектор погрешности

z^(k)=x^(k)-x, где х – точное решение. Можно преобразовать (3.34), для этого значения

x^(k+1)=z^(k+1)+x, x^(k)=z^(k)+x подставляем в (3.34). Тогда получим

В + Az^(k)=0 (3.35)

у которого вектор погрешности z^(k) является решением и условие сходимости итерационного процесса (3.34) может быть переписано так:

. (3.36)

Из (3.35) выделим вектор погрешности z^(k+1)

z^(k+1)=(E-_k+1B^-1A)z^(k)=S_kz^(k) ,

где S_k=E-_k+1B^-1A – матрица перехода. Тогда

z^(k)= S_k-1S_k-2…S₁S₀z⁽⁰⁾=Т_k0z⁽⁰⁾ ,

где Т_k0= S_k-1S_k-2…S₁S₀ – разрешающая матрица.

При стационарном итерационном процессе, когда _k+1=

S₀=S₁=…=S_k-1=S. Если S=S^* , то .

Теорема 3.4 [8, 9]. Для сходимости стационарного итерационного процесса (3.34) с матрицей перехода S необходимо и достаточно, чтобы все собственные значения матрицы S были по модулю меньше единицы.

Доказательство

Пусть выполнено (3.36), тогда

. (3.37)

Так как начальное приближение х⁽⁰⁾ в (3.34) произвольно, то из (3.37) получаем

. (3.38)

Пусть Т – некоторая неособенная матрица. Запишем матрицу S в канонической форме Жордана

S=TJT^-1 ,

где

J= , 1+2+…+m=n.

Здесь J_p – клетка Жордана порядка p:

J_p= , где _p – собственные значения матрицы S. Тогда S^k=TJ^kT^-1 . Поэтому из (3.38) следует, что

. (3.39)

Так как

,

то видно, что для выполнения (3.39) необходимо, чтобы _p<1. Теорема доказана.

Теорема 3.5 [8, 9]. Для того, чтобы стационарный итерационный процесс (3.34) с матрицей перехода S сходился достаточно, чтобы норма матрицы S была меньше единицы.

Доказательство

Доказательство следует из того, что если , то и _p<1. Следовательно, по теореме 3.4 стационарный итерационный процесс сходится.