Математическая энциклопедия - сопряженных градиентов метод

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

Структура С. г. м. как прямого метода основана на процессе последовательной A-ортогонализации системы векторов, представляющем собой обычный процесс ор-тогонализации (см. Ортогонализации метод )относительно скалярного произведения ( х, у)=х ^Т Ау. Если {s1, s2,. . ., sn} есть A-ортогональный оазис пространства, то точное решение х* системы при любом начальном приближении х 0 может быть получено из разложения

где r0=b-Ах0 -невязка х 0. ВС. г. м. A-ортогональные векторы s1, s2,. . ., sn строятся процессом A-ортогонализации невязок r0, r1,. . ., rn_1 последовательности приближений х 0, x1,. . ., xn-1, вычисляемых по формулам

Построенные таким образом векторы r0, rl,. . .,rn_1 и s1, s2,. . ., sn обладают следующими свойствами:

Расчетные формулы С. г. м. даются следующими рекуррентными соотношениями (см. [1]):

Процесс заканчивается при нек-ром для к-рого rk=0. При этом x*=xk. Момент обрыва процесса определен начальным приближением х 0. Из рекуррентных соотношений (2) следует, что векторы r0, rl,. . ., ri являются линейными комбинациями векторов r0, Аr0,...,А ⁱr0. Так как векторы r0, rl,. . ., ri ортогональны, то обращение в нуль ri возможно лишь тогда, когда векторы r0, Аr0,. . ., А ⁱr0 линейно зависимы, напр. когда в разложении r0 по базису из собственных векторов Атолько iкомпонент отличны от нуля. Этим соображением можно руководствоваться при выборе начального приближения.

С. г. м. относится к классу методов, в к-рых за решение принимается вектор, минимизирующий нек-рый функционал. Для вычисления этого вектора строится итерационная последовательность, сходящаяся к точке минимума. Последовательность х 0, х1,. . ., х n в (2) осуществляет минимизацию функционала f(x)=(Ax, х)-2(b, х). На 1-м шаге процесса (2) вектор si совпадает с направлением скорейшего спуска (градиентом) для поверхности f(x)=c в ( п-i )-мерном эллипсоиде, представляющем собой сечение поверхности плоскостью, сопряженной направлениям s1, s2,. . ., si-1.

Описанный процесс С. г. м. или близкие к нему имеют много различных названий: метод Ланцоша, метод Хестенса, метод Штифеля и т. д. Из всех методов, осуществляющих минимизацию функционала, С. г. м. является наилучшим в стратегич. плане: он дает максимальную минимизацию за га шагов. Однако вычисления (2) в реальных условиях машинной арифметики чувствительны к ошибкам округления, и условия (1) могут быть нарушены. Это препятствует окончанию процесса за n шагов. Поэтому С. г. м. продолжают за питераций, рассматривая его как бесконечный итерационный процесс минимизации функционала. Известны модификации схемы вычислений (2), более устойчивые к ошибкам округления (см. [3], [4]).

Лит.:[1] Фаддеeв Д. К., Фaддеева В. Н., Вычислительные методы линейной алгебры, М., 1983; [2] Березин И. С., Жидкoв Н. П., Методы вычислений, т. 2, М., 1960; [3] Воеводин В. В., Численные методы алгебры, М., 1966; [4] Бахвалов Н. С., Численные методы, М., 1974.

Г. Д. Ким.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985