Двухшаговый метод сопряженных градиентов (МСГ) для самосопряженной и положительно определенной матрицы

Метод сопряженных градиентов (МСГ, CGM-Conjugate Gradient Method) – это двухшаговый итерационный метод описываемый в общем случае неявным процессом (1) из 2.4.4.

Рис.22. Подпрограмма CG однотактового двушагового по невязке метода сопряженных градиентов

На рис. 22 представлен алгоритм и подпрограмма явного однотактового и двухшагового по невязке МСГ [7].

Векторы , для которых выполняется условие

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

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

Доказано [2], что для симметричной матрицы с помощью МСГ получается точное решение СЛАУ за конечное число шагов. Как правило, это число шагов меньше или много меньше размерности матрицы. Асимптотический знаменатель сходимости для вещественной симметричной положительно определенной матрицы не хуже, чем в методе с чебышевским набором параметров

(1)

Формула для асимтотического знаменателя сходимости МCГ (1) свидетельствует о наилучшей сходимости среди вариационных методов. Так, в примерах, приведенных в п. 2.4.4 на рис. 21, он везде показывает более высокую сходимость. В примере на рис. 21 (а) заданная точность решения достигается за , а на рис. 21 (г) за .

Однако для СЛАУ с неэрмитовой матрицей МСГ, как правило, не сходится. В этом случае применяется метод бисопряженных градиентов (BCG)[7]. Однако, в общем случае метод BCG численно неустойчив, требует настройки в каждом конкретном случае, и поэтому его описание выходит за рамки данного пособия.