Решение систем линейных алгебраических уравнений для больших разреженных матриц (стр. 4 из 6)
Доказательство. Доказательство повторяет доказательство принципа сжимающих отображений, поскольку эта теорема является частным случаем этого принципа.
Отметим, что для сходимости достаточно выполнение неравенства для какой-то одной нормы. Это условие является легко проверяемым, хотя лишь достаточным. Необходимое и достаточное условие сходимости является проверяется более сложным образом и дается следующим утверждением.
Теорема 4 (Необходимое и достаточное условие сходимости). Для сходимости итерационного метода необходимо и достаточно выполнения неравенства
ρ(G) < 1.
Доказательство. Из соображений краткости, ограничимся случаем, когда собственные векторы матрицы G образуют базис в Rn. Это всегда так, например, если G – симметрична. Очевидно, что сходимость итерационного метода эквивалентная сходимости к нулю последовательности {ε(k)}.
1. Докажем достаточность. Пусть ρ(G) < 1. Рассмотрим произвольное начальное приближение и разложим его по базису собственных векторов
.Тогда
.По условиям теоремы все собственные числа по модулю меньше единицы, поэтому c учетом |λi|k| → 0 при k → ∞ (i = 1,2,...,n) выполняются соотношения kε(k)k = kλk1ε(0)1 e1 + ... + λknε(0)n enk ≤
≤ |λ1|k|ε(0)1 | + ... + |λn|k|ε(0)n | → 0, k → ∞.
2. Докажем необходимость. Пусть итерационный метод сходитсяпри любом начальном приближении. Предположим противное, т.е. что ρ(G) ≥ 1. Это значит, что существует как минимум один собственный вектор e, такой, что Ge = λe c |λ| ≡ ρ(G) ≥ 1. Выберем начальное приближение так: ε(0) = e. Тогда имеем
ε(k) = Gkε(0) = λke.
Поскольку |λ| ≥ 1, последовательность {ε(k)} не сходится к нулю при данном начальном приближении, т.к. kε(k)k = |λ|k ≥ 1. Полученное противоречие и доказывает необходимость.
Важным свойством итерационного метода является его симметризуемость. В частности, она используется для его ускорения (т.е. модификации, позволяющей достичь той же точности за меньшее число итераций).
Определение 9. Итерационный метод является симметризуемым, если существует такая невырожденная матрица W (матрица симметризации), что W(E − G)W−1 является симметричной и положительно определенной.
Для симметризуемого метода выполняются свойства:
1. собственные числа матрицы перехода G вещественны;
2. наибольшее собственное число матрицы G меньше единицы;
3. множество собственных векторов матрицы перехода G образует базис векторного пространства.
Для симметризуемого метода всегда существует так называемый экстраполированный метод, который сходится всегда, независимо от сходимости исходного метода. Он дается формулой x(k+1) = Gγx(k) + gγ, Gγ = γG + (1 − γ)E, gγ = γg.
Оптимальное значение параметра γ определяется соотношением
,где M(G) и m(G) – максимальное и минимальное собственные числа G.
Рассмотрим далее классические итерационные методы.
3.2 Метод простой итерации
Метод простой итерации является простейшим примером итерационных методов. Он дается формулой x(k+1) = (E − A)x(k) + b, G = E − A, Q = E.
Сходится при M(A) < 2.
Для симметричной положительно определенной матрицы A) симметризуем и экстраполированный метод имеет вид
x
.3.3 Метод Якоби
Метод Якоби определяется формулой
. (4)Запишем его в матричных обозначениях (в безиндексном виде). Представим матрицу A в виде
A = D − CL − CU,
где D – диагональная матрица, CL – верхняя треугольная, а CU – нижняя треугольная. Если A имеет вид
a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
A = a31 a32 a33 ... a3n ,
... ...
an1 an2 an3 ... ann
то D, CL и CU даются формулами
D,
... .. 0 0 0 ... ann
0 0 0 ... 0 0 a12 a13 ... a1n
a21 0 0 ... 0 0 0 a23 ... a2n
C 
.Используя матричные обозначения, формулу метода Якоби можно записать так: x(k+1) = Bx(k) + g,
где матрица перехода B дается формулой
B = D−1(CU + CL) = E − D−1A
а g = D−1b.
Достаточным условием сходимости метода Якоби является диагональное преобладание. Если A – положительно определенная симметричная матрица, то метод Якоби симметризуем.
3.4 Метод Гаусса-Зейделя
Запишем последовательность формул метода Якоби более подробно
 |  , |
 |  , |
 | = −a31x(1k) − a32x(2k) − ... − a3nx(2k) + b3, ... |
 |  . |
Если посмотреть внимательно на них, то видно, что при вычислении последних компонент вектора x(k+1) уже известны предыдущие компоненты x(k+1), но они не используются. Например, для последней компоненты имеется формула
.В ней в левой части присутствует n − 1 компонент
предыдущей итерации, но к этому моменту уже вычислены компоненты текущей итерации 
. Естественно их использовать при вычислении 
. Перепишем эти формулы следующим образом, заменяя в левой части уравнений компоненты x(k) на уже найденные компоненты x(k+1): | a11x(1k+1) |  , |
 |  , |
 | = −a31x(1k+1) − a32x(2k+1) − ... − a3nx(2k) + b3, ... |
 |  . |
Эти формулы лежат в основе метода Гаусса–Зейделя:
. (5)В матричном виде метод Гаусса–Зейделя записывается таким образом:
x(k+1) = Lx(k) + g,
где L = (E − L)−1U, g = (E − L)−1D−1b, L = D−1CL, U = D−1CU.
В общем случае метод несимметризуем.
Есть интересный исторический комментарий [Д2]: метод был неизвестен Зейделю, а Гаусс относился к нему достаточно плохо.
Замечание. Хотя для положительно определенных симметричных матриц метод Гаусса-Зейделя сходится почти в два раза быстрее метода Якоби, для матриц общего вида существуют примеры, когда метод Якоби сходится, а метод Гаусса-Зейделя расходится.
3.5 Метод последовательной верхней релаксации (SOR) Дается формулами