Глава XVI. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ

§ 1. Идея метода

Рассмотрим задачу о нахождении максимума квадратичной функции

где и – -мерные векторы евклидова пространства , – положительно определенная квадратичная форма, задаваемая матрицей .

Сначала заметим, что градиент функции равен и точка максимума функции может быть найдена из уравнения

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

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

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

Найдем точку , в которой достигается условный максимум функции на прямой . Продолжим это построение по индукции. Пусть уже построено -мерное гиперпространство и в нем найдена точка , в которой функция достигает условного максимума.

Обозначим градиент функции в точке . Примем, далее, за гиперпространство пространство, натянутое на и прямую, проходящую через в направлении . Пространство состоит из векторов вида

, (16.1)

где , а скаляр пробегает значения от до .

Наконец, – это точка, в которой достигает условного максимума на пространстве . Таким образом, получаем такие последовательности:

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

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

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

при . (16.2)

В частности, векторы и при принадлежат в силу (16.1), откуда

а следовательно, и вообще

при . (16.3)

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

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

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

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

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

а) . (16.4)

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

. (16.5)

Отсюда ясно, что и (16.4) верно. Из (16.5) также следует, что

б) Векторы и при ортогональны относительно матрицы , т. е.

при . (16.6)

Поскольку матрица симметрична,

Поэтому для определенности будем считать, что . По определению

После очевидного преобразования получим

но для любого

поэтому

Далее, вектор есть разность двух векторов из , и так как при , можно применить соотношение (16.2)

Окончательно,

при .

в) Система векторов линейно независима, т. е. не существует чисел , не все из которых равны нулю, таких, что

В самом деле, предположим противное, и пусть, например, . Тогда

где положено

Умножая справа и слева это равенство на , получим в силу (16.6)

но это невозможно, поскольку (утверждение а)) и квадратичная форма положительно определена.

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

. (16.7)

Это утверждение можно доказать и непосредственно по индукции. Для утверждение очевидно, так как всякая точка прямой может быть представлена и в виде , если учесть, что , так же как и , лежит на этой прямой и . В общем случае предположим, что (16.7) верно для , т. е. всякий вектор вида