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

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

1. Понятие о методах сопряженных направлений.

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

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

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

Под методом сопряженных направлений для минимизации квадратичной функции (10.33) будем понимать метод

в котором направления взаимно сопряжены, а шаги

получаются как решение задач одномерной минимизации:

Теорема 10.4. Метод сопряженных направлений позволяет найти точку минимума квадратичной функции (10 33) не более чем за шагов.

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

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

В этом методе направления строят правилу

где

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

сопряженными относительно матрицы А. Более того, градиенты оказываются взаимно ортогональными.

Пример 10.5. Применим метод сопряженных градиентов для минимизации квадратичной функции — из примера 10.1. Запишем виде где

Возьмем начальное приближение

1-й шаг метода совпадает с первым шагом метода наискорейшего спуска. Поэтому (см. пример 10.1)

2-й шаг. Вычислим

Так как то и решение оказалось найденным за два шага.

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

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

или к виду

Преимущество формул (10 36), (10.37) в том, что они не содержат явным образом матрицу А.

Минимизацию функции методом сопряженных градиентов производят в соответствии с формулами

Коэффициенты вычисляют по одной из формул (10.36), (10.37).

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

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

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