СОПРЯЖЕННЫХ ГРАДИЕНТОВ МЕТОД

Значение СОПРЯЖЕННЫХ ГРАДИЕНТОВ МЕТОД в математической энциклопедии:

метод решения системы линейных алгебраич. уравнений Ах=b с положительно определенной матрицей А. Это прямой и итерационный метод одновременно: при любом начальном приближении он сходится за конечное число итераций, давая точное решение. В С. г. м. матрица системы не меняется в процессе вычислений, на каждой итерации она используется лишь для умножения на вектор. Поэтому порядок систем, решаемых на ЭВМ, может быть высоким, он определяется объемом числовой информации, задающей матрицу.
Структура С. г. м. как прямого метода основана на процессе последовательной A-ортогонализации системы векторов, представляющем собой обычный процесс ор-тогонализации (см. Ортогонализации метод )относительно скалярного произведения ( х, у)=х ^Т Ау. Если {s₁, s₂,. . ., s_n} есть A-ортогональный оазис пространства, то точное решение х* системы при любом начальном приближении х ₀ может быть получено из разложения

где r₀=b-Ах₀ -невязка х ₀. ВС. г. м. A-ортогональные векторы s₁, s₂,. . ., s_n строятся процессом A-ортогонализации невязок r₀, r₁,. . ., r_n_₁ последовательности приближений х ₀, x₁,. . ., x_n-1, вычисляемых по формулам

Построенные таким образом векторы r₀, r_l,. . .,r_n_₁ и s₁, s₂,. . ., s_n обладают следующими свойствами:

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

Процесс заканчивается при нек-ром для к-рого r_k=0. При этом x*=x_k. Момент обрыва процесса определен начальным приближением х ₀. Из рекуррентных соотношений (2) следует, что векторы r₀, r_l,. . ., r_i являются линейными комбинациями векторов r₀, Аr₀,...,А ⁱr₀. Так как векторы r₀, r_l,. . ., r_i ортогональны, то обращение в нуль r_i возможно лишь тогда, когда векторы r₀, Аr₀,. . ., А ⁱr₀ линейно зависимы, напр. когда в разложении r₀ по базису из собственных векторов Атолько iкомпонент отличны от нуля. Этим соображением можно руководствоваться при выборе начального приближения.
С. г. м. относится к классу методов, в к-рых за решение принимается вектор, минимизирующий нек-рый функционал. Для вычисления этого вектора строится итерационная последовательность, сходящаяся к точке минимума. Последовательность х ₀, х₁,. . ., х _n в (2) осуществляет минимизацию функционала f(x)=(Ax, х)-2(b, х). На 1-м шаге процесса (2) вектор s_i совпадает с направлением скорейшего спуска (градиентом) для поверхности f(x)=c в ( п-i )-мерном эллипсоиде, представляющем собой сечение поверхности плоскостью, сопряженной направлениям s₁, s₂,. . ., s_i-1.
Описанный процесс С. г. м. или близкие к нему имеют много различных названий: метод Ланцоша, метод Хестенса, метод Штифеля и т. д. Из всех методов, осуществляющих минимизацию функционала, С. г. м. является наилучшим в стратегич. плане: он дает максимальную минимизацию за га шагов. Однако вычисления (2) в реальных условиях машинной арифметики чувствительны к ошибкам округления, и условия (1) могут быть нарушены. Это препятствует окончанию процесса за n шагов. Поэтому С. г. м. продолжают за питераций, рассматривая его как бесконечный итерационный процесс минимизации функционала. Известны модификации схемы вычислений (2), более устойчивые к ошибкам округления (см. [3], [4]).

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