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

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

он вырабатывает сопряженные направления при помощи рекурсии

в которой Кроме того,

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

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

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

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

Тогда -сопряженные направления рекурсивно вырабатываются по формуле

Для применений, которые мы будем рассматривать, Кроме тото, при отрицательно определенном знаменатель отличен от нуля и будут линейно независимыми (упр. 10).

Переписывая (6.11), получаем

а из того, что сопряжены, следует, что

Ортогональность эквивалентна -сопряженности.

Если единичная матрица, то -сопряженность совпадает с ортогональностью. Это следует из того, что если — сопряженные направления, то это представляет собой обычное определение ортогональности.

Таким образом, используя (6.10) и (6.11) и заменяя на получаем метод построения ортогональных векторов.

Построение ортогональных направлений. Пусть даны и мы хотим на основе векторов (обратите внимание на определить ортогональные векторы используя (6.10) и (6.11). Пусть а в общем случае для используя (6.11), положим

Для наших целей более удобно определять ортогональные векторы рекурсивно, полагая а для

Ясно, что отличаются от только скалярным множителем и ортогональны. Для частного случая

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

Точно так же, как (6.12) было получено из (6.11), получим

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

Используя определяем из (6.11). Тогда сопряжены. Теперь могут быть использованы, чтобы получить по (6.13). Положим тогда ей ортогональны.

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

Упрощения. Вследствие ортогональности формулы (6.11) и (6.13) значительно упрощаются. Используя выражение (6.14), находим, что

так что (6.11) принимает вид

Аналогично из (6.12) получаем

Тк что (6.13) принимает вид

где

Между выражениями (6.16) и (6.17) существует много важных зависимостей. Из ортогональности и из (6.17) следует, что

Воспользовавшись уравнением (6.16) и сопряженностью получаем

Далее уравнения (6.19) и (6.20) дают

Теперь будет показано, что

Так как то из (6.17) имеем

так что

Теперь, предполагая, что и применяя (6.16), получаем

Тогда из выражений (6.17), (6.21) и (6.23) получаем

что подтверждает справедливость выражения (6.22) для всех Комбинируя (6.22) и (6.16), теперь можно получить

для всех

Основные соотношения алгоритма. Используя выведенные соотношения, можно представить (6.16) и (6.17) в их окончательной форме. Если подставим (6.18) и (6.21) в (6.16), то получим

Перепишем также (6.17) в виде

где согласно (6.24) и (6.20)

Уравнения (6.25) и (6.26) составляют основу процедуры сопряженных градиентов для максимизации Если дано то, используя (6.25) и (6.26), рекурсивно получаем сопряженные и ортогональные

Алгоритм сопряженных градиентов. В используемом далее отображении полагаем

Исходный шаг. Выберем произвольно, положим и определим Положим

Шаг . Дано Определяется

Вычисляется Следует заменить на и перейти к шагу Процедура прерывается при

Доказательство сходимости. Теперь следует показать, что процедура сопряженных градиентов ведет себя согласно уравнениям (6.25) и (6.26). Если это так, то построенные будут сопряженными и процедура максимизирует квадратичную функцию за конечное число шагов.

Прежде всего необходимо обратить внимание на некоторые особенности. Если даны произвольные точка х и направление то

Предположим, что Тогда, поскольку

Следовательно, в точке

и из (6.29) получаем

Решая это уравнение относительно получаем

Итак, максимум квадратичной функции положительном и отрицательном направлениях из х достигается в точке при из (6.30).

Теперь мы установим, что эта процедура вырабатывает направления определяемые по (6.25) и (6.26). Если

то благодаря (6.28) уравнение (6.25) удовлетворяется. Поэтому необходимо лишь доказать, что получаемые по (6.26), такие же, как и в (6.31). Очевидно, Для проведения математической индукции предположим, что

Так как процедура вычисляет то из (6.30)

По предположению индукции отсюда имеем

или согласно Тогда из выражения (6.29)

и справедливость уравнения (6.31) подтверждается, так как, рассматривая (6.26), видим, что

Таким образом, процедура сопряженных градиентов в точности такая же, как и рекурсия, представленная соотношениями (6.25) и (6.26). Очевидно, что процедура сопряженных градиентов вырабатывает направления Этим устанавливается, что направления (6.11) и (6.28) не могут быть нулевыми. Векторы также удовлетворяют требованиям, при которых имеет смысл формула (6.13).

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

Упражнения

(см. скан)

(кликните для просмотра скана)

(см. скан)

Дополнительные замечания

Сопряженные направления были предложены в 1952 г. для решения линейных уравнений Хестенесом и Стифелом (см. упр. 6.7). Другие методы сопряженных направлений содержатся в работе Розенброка и в связанной с этой работой статье Флетчера и Пауэлла (см. также Флетчер, 1964; Пауэлл, 1962; Стифель; Мартин и Ти, а для обзора Флетчер, 1965).

Другие подходы включают методы Коллатца; Недлера и Мида; Химсворса и других, метод параллельных касательных Шаха и др. (1961, 1964 г.). Сравнение методов для решения задачи без ограничений может быть найдено у Брукса.

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