Итерационные методы
Они дают возможность найти решение системы, как предел бесконечного вычислительного процесса, позволяющего по уже найденным приближениям к решению построить следующее, более точное приближение. Привлекательной чертой таких методов является их самоисправляемость и простота реализации на ЭВМ. Если в точных методах ошибка в вычислениях, когда она не компенсируется случайно другими ошибками, неизбежно ведет к ошибкам в результате, то в случае сходящегося итерационного процесса ошибка в каком-то приближении исправляется в последующих вычислениях, и такое исправление требует, как правило, только нескольких лишних шагов единообразных вычислений. Итерационный метод, для того чтобы начать по нему вычисления, требует знания одного или нескольких начальных приближений к решению. Условия и скорость сходимости каждого итерационного процесса существенно зависят от свойств уравнении, т. е. от свойств матрицы системы, и от выбора начальных приближений. Итерационных процессов для систем линейных уравнений построено большое число. Мы же остановимся только на двух основных и начнем рассмотрение с метода простой итерации. Пусть дана система линейных алгебраических уравнений Ах = f с неособенной матрицей. В методе простой итерации ее предварительно приводят к виду х = Вх + Ь, (1) где B = -C-1D, b=C- Предположим,
что известно
приближение 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 через х°:
Отсюда и из (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. Если какая-либо норма матрицы В, согласованная с рассматриваемой нормой вектора х, меньше единицы, то верна следующая оценка погрешности приближения в методе простой итерации:
Доказательство. Для xk выше дано выражение (3.58), и так как ||B||< 1, то x* = (Е + В + В2 + ...)b. Поэтому х* - xk = (Bk + Bk+1 + …) b - Bkx° (6) и, стало быть,
Часто за x° принимают вектор b. В этом случае оценка (5) немного упростится; подставляя х° = b в (6), получим |