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

Пусть А — симметрическая положительно определенная матрица. Рассмотрим функцию

Это — целая рациональная функция второй степени относительно компонент вектора х. Поверхности образуют в -мерном пространстве семейство эллипсоидов с общим, центром

Учитывая симметричность матрицы А, преобразуем разность Получим:

Так как А — положительно определенная матрица, то

причем знак равенства достигается лишь при

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

Берем произвольный начальный вектор Будем смещаться, начиная с точки, определенной вектором по нормали к эллипсоиду до тех пор, пока эта нормаль не коснется какого-то эллипсоида семейства Получим новую точку. Вектор, проведенный в эту точку, обозначим через х. Отыщем этот вектор. Введем обозначение

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

принимает наибольшее значение при условии Функцию, стоящую под знаком производной, можно записать в виде

Таким образом,

Используя неравенство Буняковского, получим:

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

Найдем теперь такое а, при котором принимает наименьшее значение. Используя (6) при найдем, что искомое а, которое мы обозначим через равно

Итак,

На рис. 1 показана геометрическая картина нашего построения при

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

Рис. 1.

Рассмотрим его несколько позже. В настоящем параграфе будем получать иначе. Рассмотрим векторное уравнение

Оно определяет гиперплоскость измерения. Уравнению (11) удовлетворяет вектор Ему удовлетворяет и Действительно,

где через обозначен вектор

Как и раньше можно показать, что вектор имеет направление нормали к эллипсоиду

при Вектор касается этого эллипсоида в той же точке. Следовательно,

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

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

Так как вектор ортогонален к гиперплоскости, то и должен быть ортогонален к Это дает

Будем теперь отыскивать такое а, что принимает наименьшее значение. Так как

то искомое значение а, которое мы будем обозначать через х равно

Итак,

На следующем шаге мы перейдем к гиперплоскости измерений, определенной уравнениями (11) и

В силу ортогональности и

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

Проекцию нормального к эллипсоиду при вектора на гиперплоскость — вектор будем разыскивать в виде

Нужно потребовать ортогональность и Но

Условие ортогональности и записывается так:

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

Поэтому вектор будет представляться в виде

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

Отметим следующие свойства членов этих последовательностей. В силу самого построения будем иметь:

Далее, при получим:

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

Наконец, рассмотрим при Пусть, для определенности Тогда

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

Методу сопряженных градиентов можно дать простую алгебраическую трактовку. Будем таким же способом, как это делалось ранее, ортогонализировать систему векторов

Полученные при этом векторы будут обладать следующими свойствами:

1. Вектор является линейной комбинацией векторов

Это свойство очевидно, если вспомнить ход процесса как он определен выше.

2. Вектор ортогонален к наименьшему линейному многообразию, содержащему векторы

Действительно, если то утверждение тривиально.

Если же то и каждый из векторов не

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

векторам базиса, будет ортогональным и ко всему линейному многообразию.

3. Вектор тогда и только тогда, когда линейно зависимы.

Если то векторы как ненулевые взаимно ортогональные векторы линейно независимы. Это может быть только в том случае, если порождающие их векторы также линейно независимы. Если же 0, то (39) дает линейную зависимость векторов

4. Если то коэффициент в (39) отличен от нуля.

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

5. Каждый из векторов может быть представлен как линейная комбинация векторов

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

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

Рассмотрим теперь наряду с обычным скалярным произведением скалярное произведение, определенное равенством (27) предыдущего параграфа. Последовательность векторов можно ортогонализировать в смысле этого скалярного произведения.

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

Для этих векторов будут справедливы высказанные нами утверждения 1—5. Кроме того, системы векторов будут связаны некоторыми соотношениями. Векторы при принадлежат линейному многообразию, порожденному векторами а вектор ортогонален к этому многообразию. Таким образом, мы будем иметь:

Аналогично показывается, что

Воспользуемся равенствами (40) и (41) для установления формул, связывающих векторы Пусть векторы

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

Помножим обе части равенства (42) скалярно на В силу ортогональности векторов при и равенства (41) получим:

Итак,

Умножим это равенство скалярно на В силу (40) будем иметь:

Коэффициент отличен от нуля. Действительно, если то условие означает, что векторы линейно зависимы, если же то условие означает линейную зависимость векторов И то и другое невозможно. Скалярное произведение также отлично от нуля. Поэтому Так как векторы определяются с точностью до постоянного множителя, то мы всегда можем считать Тогда из (45) получаем:

Обозначим через решение уравнения

Подставляя в (47) вместо их выражения по (48), получим:

Итак,

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

Умножим скалярно равенство (51) на

При этом получим:

После умножения на будем иметь:

или

Итак,

где определяются равенствами (54).

Нетрудно заметить, что коэффициенты можно также вычислять по формулам:

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

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

Метод сопряженных градиентов можно обобщить на случай произвольной неособенной матрицы А. Пусть В — некоторая положительная определенная симметрическая матрица. Выбираем произвольные векторы и строим последовательности векторов при помощи рекуррентных формул:

Эти последовательности будут обладать указанными выше свойствами, конечно с заменой матрицы А на матрицу В. В частности, Следовательно,

Пусть теперь

где -произвольный начальный вектор и -произвольная неособенная матрица. Тогда из (59) следует:

Итак, если последовательно, начиная с выбранного вычислять векторы

то получим Для векторов из (62) получим:

Если вспомнить, что и сравнить (63) и соответствующее равенство (58) для то получим при любом

Таким образом, (58) можно переписать в виде

Это и будут формулы, соответствующие (29) — (34) для несимметричного случая.

Рассмотрим два частных случая.

1-й случай. Выбираем и При этом получим

2-й случай. Выбираем и При этом получим:

Относительно применения этих формул можно сказать то же, что было сказано выше о применении формул