Обобщенный метод сопряженных градиентов.

Во многих практически важных приложениях возникает необходимость решения СЛАУ

,

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

Рассмотрим один из подходов к построению обобщенного метода сопряженных градиентов. Обратимся к минимизации следующей квадратичной функции

.

Из конечномерности пространства следует, что существует , доставляющее минимум данной функции, т. е.

.

Потребуем, чтобы матрица была положительно определена.

Будем строить итерационные приближения к следующим образом. Для заданного k определим k+ 1 векторов так, чтобы векторы были линейно независимы. Вдоль направлений определим k+ 1 параметр . Будем строить по итерационному правилу

,

требуя, чтобы параметры минимизировали , что равносильно требованию .

Рассмотрим некоторое . Тогда условие записывается как . Преобразуем последнее равенство:

то есть

.

Перед тем как определить , отметим попутно, что

,

или окончательно

.

Это соотношение удобно использовать при вычислении невязки.

Соотношение для можно переписать как систему линей-ных уравнений

,

где

Будем строить векторы направлений в виде

,

причем параметры определим из условия сопряженной орто-гональности

.

Аналогично тому как это было сделано для традиционного метода сопряженных градиентов, умножим соотношение для вектора сопряженного направления слева сначала на A, а затем на :

.

Для левая часть здесь равна нулю. Справа под знаком суммы отличным от нуля будет лишь одно слагаемое, соответствующее . Тогда

.

Вернемся к уравнению для . В силу диагональности из всех отличным от нуля является коэффициент, соответствующий , а именно

.

Отметим, что матрица будет невырожденной при .

Суммируя изложенное выше, запишем алгоритм обобщенного метода сопряженных градиентов:

1. Вычислить: .

2. Вычислить в цикле ():

2.1. ;

2.2. ;

2.3. ;

2.4. ;

2.5. .

В таком виде алгоритм соответствует обобщенному методу сопряженных невязок. К его достоинствам относятся, во-первых, свойство получения решения за конечное (не более n) число итерационных шагов, и, во-вторых, монотонное уменьшение нормы невязки с ростом . Данному методу присущи следующие недостатки. Во-первых, при расчете приходится использовать все k предыдущих векторов направлений, что при больших k делает метод трудно применимым в силу ограниченности объема оперативной памяти компьютера. Во-вторых, при расчете используются k предыдущих векторов .

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

1. Задается целое число и выполняется s итераций. Затем вычисляется . Полагается и итерационный процесс перезапускается.

2. Одновременно хранится s последних векторов . При этом после расчета очередного последнее исключается. Нижний предел в сумме при расчете равен k-s+ 1.

В обоих случаях одновременно хранится не более s векторов . Теоретическое свойство сходимости за конечное число итераций в этих случаях теряется. На практике, однако, при наличии хорошего предобусловливания любая из указанных версий достаточно быстро сходится к решению.