§ 9. Метод сопряженных градиентов

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

с симметричной положительно определенной матрицей А.

Предположим, что мы имеем некоторое начальное приближение . Обозначим через невязку начального приближения; здесь X — точное решение системы (1). Поставим следующую задачу — построить многочлен степени , удовлетворяющий условию , такой, что значение функционала , где находится из соотношения

будет минимальным. Так как

то данная задача может быть переформулирована следующим образом. Требуется найти такой, что норма невязки будет минимальной.

Покажем, что эта задача всегда разрешима единственным образом. Пусть

где — собственные векторы А, соответствующие собственным значениям А. Представление (3) всегда возможно, так как матрица А симметрична и невырождена. Вектор имеет вид

и

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

Таким образом, в точке минимума должны выполняться равенства

Пусть . Из курса линейной алгебры известно, что векторы образуют линейно независимую систему (пространство Крылова). Действительно, допустим противное. Тогда существуют постоянные , не равные нулю одновременно, такие, что . Подставляя вместо его разложение из (3), получим

Таким образом, так как , то должны выполняться равенства

т.е. коэффициенты должны удовлетворять системе уравнений (5). Определитель матрицы системы (5) совпадает с определителем Вандер-монда и отличен от нуля, поскольку все А, различны по предположению. Отсюда следует, что равенства (5) могут выполняться только при . Таким образом, векторы действительно образуют линейно независимую систему.

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

После нахождения коэффициентов , значение из (2) находится следующим образом. Имеем

откуда следует

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

Покажем, что образуют базис в . Доказательство проведем индукцией по . Для утверждение . Предположим, что для векторы образуют базис в , как следствие, являются линейно независимыми). Покажем, что система также линейно независима. Предполагая противное, получим

Тогда . С другой стороны, в силу (4), вектор ортогонален векторам , образующим базис в а значит и всем векторам из Так как по предположению , то это возможно лишь при , что противоречит исходной посылке о линейной зависимости .

Полученное противоречие доказывает линейную независимость .

Так как образуют базис в , то соотношения (4) означают, что вектор ортогонален всему подпространству , что в свою очередь может быть (по доказанному выше) записано в виде

Покажем, что векторы также образуют базис в . Вектор по доказанному имеет вид

и этот вектор ортогонален векторам . Коэффициент не Равен нулю. Действительно, предполагая , получим

Тогда по построению , откуда , что противоречит ортогональности векторов и .

Предположим, что векторы не образуют линейно независимую систему. Тогда . С другой стороны,

Но по доказанному выше векторы линейно независимы при , т.е. .

Полученное противоречие показывает, что векторы , действительно образуют базис в . Тогда вектор может быть разложен по этой системе единственным образом

Так как по построению ортогонален при при то из (7) следует, что . Тогда (7) имеет вид

Из разложений

и условия получаем . Тогда из (8) имеем

Но , откуда , и уравнение (8) может быть переписано в виде

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

Подставляя в (9) вместо его выражение и применяя к обеим частям равенства оператор , получим

По доказанному выше, метод (10) эквивалентен исходному методу (2), который определен однозначно. Отсюда следует, что коэффициенты находятся из условий (6) ортогональности невязок единственным образом; система уравнений для определения этих коэффициентов имеет вид

На первом шаге, когда известно значение и надо найти из условия минимума функционала , получаем формулу Метода наискорейшего градиентного спуска

или, что то же самое,

т.е. .

Покажем конечность итерационного процесса (10), т. е. что за конечное число итераций при отсутствии ошибок округления мы получим точное решение исходной системы (1). Пусть, как и ранее, , где — собственные векторы А, отвечающие различным собственным значениям. Обозначим через линейную оболочку векторов . Так как все находятся из соотношений (9), (12), то и образуют в нем ортогональный базис. Вектор и по доказанному выше ортогонален векторам . Это возможно только в случае .

Таким образом, производя q итераций по формулам (13), (9), мы получим точное решение системы уравнений (1) при условии отсутствия ошибок округления.

Оценим скорость сходимости метода. Для этого применим прием, который уже употреблялся при оценке скорости сходимости метода наискорейшего градиентного спуска. Пусть — приближения, получаемые при решении уравнения (1) линейным оптимальным процессом. Тогда по доказанному в § 6 погрешности удовлетворяют соотношению

и имеет место оценка

Отсюда, в частности, следует, что

Получим оценку скорости сходимости линейного оптимального процесса в других нормах. Пусть . (Нетрудно видеть, что . Тогда

и

т.е.

Так как

где , то из (15) следует оценка

Применяя к обеим частям (14) матрицу А, получим уравнение, связывающее невязки на и нулевом шагах линейного оптимального процесса

По построению вектор минимизирует функционал среди векторов вида (2) или, что то же самое, минимизирует среди векторов таких, что имеет вид (2). Тогда , откуда

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

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