Сами вычисления в методе последовательных приближений просты. Но зато сложно найти такую систему х = ц){х), которая была бы эквивалентна исходной системе/(jr) == О и одновременно обеспечивала бы сходимость.

Сходимость метода нередко удается улучшить. В методе простых итераций найденное приближение д:+ используетея только для вычисления следующей итерации. Можно использовать его уже на данной итерации для вычисления следующих компонент:

4+"=ф*(-г -г". -.41". 4". 4%.. 4)- (46)

Сходимость этого варианта метода тоже линейная; детально ее исследовать не будем. При ручных расчетах можно еще ускорить сходимость за счет перестановок отдельных уравнений на основе анализа их невязок rf =

= дг] -ф,(д;*) = 4"~4*"> "° Д"" расчетов на ЭВМ это неудобно, ибо обычно такой анализ полуинтуитивен и плохо алгоритмизируется.

2. Метод Ньютона. Пусть известно некоторое приближение лг*- к корню X. Как и для одной переменной, запишем исходную систему (43) в виде/(д;+ Лдг) = 0, где Лдг = лг -д;-. Разлагая эти уравнения в ряды и ограничиваясь первыми дифференциалами, т. е. линеаризуя функцию, получим

2А!.) = /,(д:(.)), lkn. (47)

Это система уравнений, линейных относительно приращений A;f; все коэффициенты этой системы выражаются через последнее приближение хК Решив эту систему (например, методом исключения), найдем новое приближение х+> = х- + АхК

Как и для одной переменной, метод Ньютона можно формально свести к методу последовательных приближений, положив (f{x) = x - [df/dx]-f(x), где [df/dx] есть матрица, обратная матрице производных. Аналогично проводится теоретический анализ условий сходимости. Однако достаточное условие сходимости, записанное в координатной форме, здесь имеет настолько сложный вид, что проверить его выполнимость почти никогда не удается. Отметим только очевидный результат: в достаточно малой окрестности корня итерации сходятся, если det [df/dx] Ф О, причем сходимость квадратичная.

Следовательно, если нулевое приближение выбрано удачно, то метод Ньютона сходится, причем очень быстро (обычно за 3 - 5 итераций). Поэтому на практике этот метод используют чаще всего.

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

<ge. В самом деле, вблизи корня ньютоновские итерации сходятся квадратично, поэтому если этот критерий выполнен, то л:+ -дгЦяе-е. Выбирая е?%i Ю-10-е, можно получить решение с десятком верных знаков.

вычисления в методе Ньютона несколько сложнее, чем при простых итерациях, ибо на каждой итерации требуется находить матрицу производных и решать систему линейных уравнений. Поэтому в некоторых учебниках рекомендуют такой прием: вычислить матрицу [dfldx] только на начальной итерации и использовать ее на всех остальных итерациях.

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

3. Методы спуска. Рассмотрим функцию Ф(лг)=: \ fk{x)\.

k = i

Она неотрицательна и обращается в нуль в том и только в том случае, если f{x) = 0. Таким образом, решение исходной системы уравнений (43) будет одновременно нулевым минимумом скалярной функции многих переменных Ф{х).

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

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

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

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

UkiAxiri,, IsSfesc/i, (48)

г= 1

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

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

У <Л. или У

a-ki

< 1, или

к 1фк

< 1. (52)

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

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

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

ЛГ+l==ЛГ + Л7?s. Rs = E-AAJ\ (49)

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

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

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

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

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

х = Сх+а. (50)

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

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

1 / v

Xk = - bk- aixA, Issfe.n. (51)