Итерационные методы

Они дают возможность найти решение системы, как предел бесконечного вычислительного процесса, позволяющего по уже найденным   приближениям к решению   построить следующее, более   точное   приближение.    Привлекательной чертой таких  методов является  их самоисправляемость и простота   реализации на ЭВМ. Если в точных методах ошибка  в  вычислениях,   когда   она не компенсируется случайно другими ошибками, неизбежно ведет к ошибкам в результате, то в случае сходящегося итерационного процесса ошибка в каком-то приближении исправляется в последующих вычислениях, и такое исправление   требует,   как  правило,   только   нескольких  лишних шагов   единообразных вычислений.   Итерационный   метод,  для  того чтобы  начать  по  нему вычисления,  требует знания одного или нескольких начальных приближений к решению.

Условия и скорость сходимости каждого итерационного процесса существенно зависят от свойств уравнении, т. е. от свойств матрицы системы, и от выбора начальных приближений.

Итерационных процессов для систем линейных уравнений построено большое число. Мы же остановимся только на двух основных и начнем рассмотрение с метода простой итерации.

Пусть дана система линейных   алгебраических уравнений Ах = f с неособенной матрицей. В методе   простой   итерации   ее   предварительно   приводят к виду

х = Вх + Ь,                                                         (1)

где

B = -C-1D,    b=C-1f,    C + D = A,    detC ≠ 0.

Предположим,     что     известно     приближение      к точному  решению    системы. Все следующие приближения определим правилом

xk+l = Bxk + b,      k = 0, 1, 2, ...                (2)

Если    последовательность    приближений    хk    сходится к некоторому предельному вектору х', то  он будет решением  системы.  Действительно,  если  в  равенстве   (3.56) перейти  к  пределу  при  k→∞,  считая,  что хk→ х',  то в пределе получим х' = Вх' + b. Выясним условия сходимости последовательности xk.

Теорема 1. Для того чтобы последовательности приближений xk сходилась, достаточно, чтобы все собственные значения матрицы В были по модулю меньше  единицы:

   |λi|<1      (i=1,2,…n)                                         (3)

Доказательство.    Найдем    выражение    любого приближения хk через х°:

(4)

Отсюда и из (3) сразу следует, что при k→∞  Bk → 0  и

E + В+ ...  + Вk-1→Е + В + В2 + ... =(Е-В)-1,

откуда  хk→ (Е-В)- 1b = х*.

Что касается необходимости условия (3), то ответ на такой вопрос дает

Теорема 2. Если требовать, чтобы последовательность хk сходилась к x* при любом начальном приближении х°, то условие (3) является и необходимым.

Доказательство. Пусть для всякого начального приближения х° будет k→х*. Имеем

x* - xk = (Bx*+ b) - (Bxk-l + b) = В (x* - xk-1) = ... =Bk(x* - x°).

При k→∞  разность х* - хk стремится к нулю, поэтому последний член цепи равенства должен стремиться к нулю, каким бы ни был вектор  х*-хk. Отсюда следует, что Bk→0, последнее же будет лишь в том случае, когда верно неравенство (3).

Применение теорем 1 и 2 требует знания границ собственных значений матрицы В; нахождение их часто является нелегкой задачей. Укажем более простые, но только достаточные признаки сходимости.

Теорема 3. Для того чтобы последовательность приближений xk в методе простой итерации сходилась, достаточно, чтобы какая-либо норма матрицы В была .меньше единицы.

Доказательство. Если ||B||>1, то все собственные значения матрицы В по модулю меньше единицы, и по теореме 1 последовательность xk сходится.

Непосредственным следствием теоремы 3 и равенств, определяющих кубическую и октаэдрическую норму матрицы, является

Теорема 4. Последовательность xk в методе простой итерации сходится, если для матрицы В выполняется одно из неравенств:

1) 

2) 

Для многих приложений важно знать, какой является скорость сходимости x* - xk, и уметь оценить погрешность x* - xk замены точного решения х* системы приближением xk.

Теорема 5. Если какая-либо норма матрицы В, согласованная с рассматриваемой нормой вектора х, меньше единицы, то верна следующая оценка погрешности приближения в методе простой итерации:

                                 (5)

Доказательство. Для xk выше дано выражение (3.58), и так как ||B||< 1, то x* = (Е + В + В2 + ...)b. Поэтому

х* - xk = (Bk + Bk+1 + …) b - Bkx°                                    (6)

и, стало быть,

Часто за x° принимают вектор b. В этом случае оценка (5) немного упростится; подставляя х° = b в (6), получим

                                                (7)