Численные методы линейной алгебры

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 стационарный итерационный процесс сходится.