§ 8. Разновидности методов последовательных приближений

В методах последовательных приближений решения системы исходят из произвольного начального вектора и получают векторы по рекуррентной формуле

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

Будем называть метод стационарным, если не зависит от

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

где квадратная матрица и вектор. Естественно требовать от методов последовательных приближений, что при подстановке в правую часть (1) и (2) вместо точного решения системы мы слева снова получили В случае линейного метода первого порядка это приведет к равенству

или

В этом случае мы можем переписать (2) в виде

причем квадратные матрицы, не зависящие от и такие, что

Выражение (5) можно также записать в виде

Наконец, если существует матрица то выражение (5) можно записать в виде

При этом должно быть

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

Разнообразные схемы, осуществляющие линейные методы последовательных приближений первого порядка, можно считать реализацией формул (5), (7) или (8).

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

или же сложенная с некоторой постоянной. Разным способам минимизации и задания нормы будут соответствовать различные методы решения систем уравнений. Как мы видели в § 5, в случае симметрической положительно определенной матрицы А можно минимизировать функцию

Один из способов такой минимизации там был рассмотрен. Этот способ можно обобщить. Выбираем какое-то направление, определяемое вектором с. Так же как и в § 5, найдем, что принимает наименьшее значение при где

Если возьмем вместо а величину то будем иметь:

Таким образом, если то при любом

Идея многих способов минимизации а следовательно и решения системы заключается в следующем. Задаются начальным приближением Определяют закон выбора векторов (они могут зависеть от Определяют закон выбора коэффициентов (они могут зависеть от На каждом шаге в качестве последующего вектора рассматривают

где а было определено выше.

Если А не является симметрической положительно определенной матрицей, то можно вместо системы рассматривать систему где - симметрическая положительно определенная

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