4. Итерационные методы решения линейных систем

Иногда дополняют, а иногда заменяют прямые методы.

Решая линейную систему (1) общего вида методом исключения, попутно можно проверить, насколько хорошо она обусловлена. Решение, найденное прямым методом, из-за ошибок округления будет приближенным. Нетрудно проверить, что поправки к нему удовлетворяют уравнениям

где — невязки (7). Это линейная система с той же матрицей, что исходна система (1). Решим ее, используя ранее найденные коэффициенты (т. е. почти не увеличивая общего объема вычислений). Ранее отмечалось, что в методе Гаусса невязки малы. Если величины тоже окажутся малыми, то система хорошо обусловлена; если большими то плохо. В последнем случае зачастую удается уточнить решение, рассматривая (48) как итерационный процесс Ньютона и делая 2—3 итерации.

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

(49)

Однако каждая итерация этого процесса требует арифметических действий, т. е. вдвое больше, чем прямое обращение матрицы по методам Гаусса или Жордана. Поэтому в практических вычислениях этот процесс теперь не применяют.

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

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

Подобные линейные системы зачастую выгодно решать итерационными методами. Современные итерационные методы мы рассмотрим в главе XII, посвященной эллиптическим уравнениям. Здесь упомянем только два старых метода, уже не используемых в практических вычислениях, но удобных для некоторых теоретических оценок.

Один из них — стационарный метод простых итераций, основанный на приведении системы к эквивалентной системе специального вида:

Запись итерационного процесса очевидна. Для сходимости итераций достаточно, если какая-нибудь норма . В этой задаче известно даже необходимое и достаточное условие сходимости — модули всех собственных значений матрицы С должны быть меньше единицы; но на практике этим условием трудно воспользоваться, ибо найти собственные значения обычно сложнее, чем решить линейную систему.

К виду (50) систему можно привести, например, выделением диагональных элементов

В этой записи легко учесть наличие нулей в матрице А и при умножении матрицы на вектор суммировать только по ненулевым элементам. При использовании различных норм матрицы достаточные условия сходимости итераций принимают вид

что означает преобладание диагональных элементов матрицы (сравните условия устойчивости метода прогонки ).

Если метод сходится, то корень уравнения существует. Таким образом, преобладание диагональных элементов матрицы в смысле одного из неравенств (52) является признаком того, что система линейных уравнений (1) имеет решение, т. е. . Этим признаком мы будем часто пользоваться при исследовании разрешимости неявных разностных схем.

Заметим, что чем меньше тем быстрей сходятся итерации. Наилучшие современные методы основаны на специальных способах выбора матрицы С, при которых ее норма становится минимальной в некотором смысле.

Второй — метод Зейделя. Для уравнения (51) он имеет такой вид:

Необходимое и достаточное условие его сходимости не совпадает с условием сходимости простых итераций, и в разных условиях он может быть выгоден или невыгоден. Отметим один признак сходимости: если матрица А—эрмитова и положительно определенная, то метод Зейделя в форме (53) совпадает с методом покоординатного спуска для решения задачи на минимум квадратичной формы ; как будет показано в главе VII, метод покоординатного спуска сходится, что обеспечивает сходимость метода Зейделя в данном случае.