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

Этот метод относится к группе методов сопряженных направлений, при которых шаги итерационной процедуры минимизации целевой функции предпринимаются в сопряженных направлениях. Два 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 алгоритма повторяются с заменой на , а вычисления заканчиваются при , где - заданная точность.