Этот метод относится к группе методов сопряженных направлений, при которых шаги итерационной процедуры минимизации целевой функции предпринимаются в сопряженных направлениях. Два n-мерных вектора x и y называют сопряженными по отношению к матрице H (или H-сопряженными), если скалярное произведение (x,Hy)=0. Здесь H – симметричная положительно определенная матрица размером n x n [11].

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

(49)

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

Наиболее существенна при методах сопряженных направлений проблема эффективного построения таких направлений. Метод Флетчера - Ривса решает эту проблему путем преобразования на каждом шаге антиградиента - в направлении , H – сопряженном с ранее найденными направлениями . Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции (49).

Направление вычисляются по формулам:

,

(50)

Величины выбираются так, чтобы направления были H-сопряженными: (51)

В результате для квадратичной функции:

(52)

Итерационный процесс минимизации имеет вид

, где (53)

- называют величиной шага, а n-мерный вектор - направлением спуска на k-том шаге. Величина шага выбирается из условий минимума функции в направлении движения:

(54)

Для квадратичной функции (55)

Алгоритм сопряженных градиентов состоит в следующем:

1. В точке вычисляется ;

2. На k-ом шаге по формулам (55) и (53) определяется шаг и точка ;

3. Вычисляются величины и ;

4. Если , то точка является минимумом функции. В противном случае из соотношения:

(56)

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

Пример 9. Найти минимум функции . Начальная точка (9; -7; 11) [2] .

Решение: Итерационный процесс приведен в таблице 4.

Таблица 4.

№ итерации | x1 | x2 | x3 | F
1 | 9 | -7 | 11 | 418
2 | -0,481 | 0,111 | 7,83 | 37,14
3 | 1,206 | 2,827 | 4,862 | 4,965
4 | 0,999 | 2 | 3 | 4,26E-14

Оптимальное значение найдено на 4 шаге.

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