2.2.1.5. Метод сопряженных градиентов (Флетчера-Ривса)

 

Алгоритм метода:

здесь:

• ;          *
• ;
• ;
• - шаг вычисляется из условия наибольшего убывания функции в точках последовательности, построенной по закону (5.1): .       *

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

 

Геометрическая интерпретация метода

 

 

Критерии окончания метода такие же, как и в методе градиентного спуска.

Начальными параметрами метода являются:  (дополнительно или ).

 

Вычисление шага может быть выполнено способами A и C, описанными в методе градиентного наискорейшего  спуска.

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

 

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

 

 

Для неквадратичных функций, используется модификация метода сопряженных градиентов, называемая методом Полака-Рибьера  [1].

 

Пример 2.6.

 

Дано: .

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

 

Решение:

 

Итерация 0 алгоритма (соответствует начальной точке) – см. пример 2.1.

 

Итерация 1 алгоритма (k=0)

 

Результаты итерации совпадают с 1-й итерацией метода наискорейшего градиентного спуска – см. пример 2.2.

 

;      ;

 

;                                   .

 

Итерация 2 алгоритма (k=1)

 

;         ;

;

;

 

.

Используем способ A вычисления шага :

 

Вычислим значение функции в точке :

 

;

.

 

Найдем минимум функции :

 - значение шага;

- значит, функция  принимает минимальное значение.

 

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

 

;               ;

 

;

 

.

 

Очевидно, что на 2-й итерации найдены координаты стационарной точки с точностью .