logo

Решение контрольных по математике!!!

26. Метод Флетчера-Ривса

Одним из самых известных методов сопряженных градиентов является Метод Флетчера – Ривса. Приведем описание этого метода для минимизации произвольной целевой функции .

В методе Флетчера – Ривса направления одномерного поиска определяются на основании градиента целевой функции . Задается начальная точка , в ней вычисляется значение градиента . В направлении антиградиента производится одномерный поиск и находится следующая точка:

, , . (3.24)

Последующие итерации основаны на вычислении градиента , формулах методов спуска (1.16) и методов сопряженных градиентов (3.18):

, , , (3.25)

, . (3.26)

Итерации продолжаются до тех пор, пока выполняется условие

,

Где – допустимая погрешность.

Вектор , построенный по формулам (3.25), для квадратичной функции является направлением спуска. Действительно, если , то с учетом свойств (3.19) получим:

.

Заметим, что при метод Флетчера – Ривса превращается в метод наискорейшего спуска.

По формулам (3.24)–(3.26) составим алгоритм метода Флетчера – Ривса.

Алгоритм метода Флетчера – Ривса.

Входные параметры: – начальная точка поиска, – процедура вычисления функции, – допустимая погрешность.

Выходной параметр – конечная точка поиска.

1. Вычислить , и положить .

2. Вычислить , .

3. Положить , .

4. Вычислить , .

5. Положить .

6. Если , то перейти к шагу 2.

7. Остановиться.

В этом алгоритме на шаге 2 выполняется одномерный поиск точки минимума из текущей точки поиска в направлении . Направление поиска вычисляется на шагах 4, 5. Для повышения эффективности одномерного поиска производят масштабирование направления поиска и используют вектор направления единичной длины. Шаг перехода в следующую точку поиска обозначен через . Итерации продолжаются, пока длина вектора больше заданной допустимой погрешности.

Достоинством метода Флетчера – Ривса является то, что его скорость сходимости значительно превышает скорость сходимости метода наискорейшего спуска. Он требует хранения в памяти малого количества информации в виде нескольких -мерных векторов. Уменьшить объем памяти можно применением модификации предыдущего алгоритма.

Алгоритм 2 метода Флетчера – Ривса.

Входные параметры: – начальная точка поиска, – процедура вычисления функции, – допустимая погрешность.

Выходной параметр – конечная точка поиска.

1. Вычислить , и положить .

2. Вычислить , .

3. Положить .

4. Вычислить , , .

5. Положить , .

6. Если , то перейти к шагу 2.

7. Остановиться.

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

Пример 3.3. На рис. 3.5 представлена траектория минимизации квадратичной функции (1.3) методом Флетчера – Ривса, включающая лучшие точки итераций. Для вычисления точки минимума с допустимой погрешностью 10–3 метод затратил 3 итерации, причем значение функции 1,3∙10–14 найдено за две итерации при погрешности вычисления точки минимума 8,8∙10–8, а последняя итерация использована для проверки критерия окончания вычислений. Значения функции вычислены 19 раз. При этом траектория минимизации квадратичной функции методом Флетчера – Ривса такая же, как и траектория минимизации этой же функции модифицированным методом Ньютона с направлением спуска из примера 2.5, представленная на рис. 2.4.

Рис. 3.5. Минимизация квадратичной функции методом Флетчера-Ривса

Пример 3.4. На рис. 3.6 представлена траектория поиска минимума функции Розенброка методом Флетчера – Ривса. До уменьшения шага с допустимой погрешностью 10–3 метод затратил 49 итераций и 461 вычисление функции. Метод проскочил мимо точки минимума, отмеченной звездочкой.

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

При нарушении условий сопряженности направлений метод Флетчера – Ривса начинает вычислять направления, движение вдоль которых неэффективно для минимизации функции. В связи с этим процесс построения сопряженных направлений вида (3.25) целесообразно вести циклами, начиная каждый цикл с направления наискорейшего спуска, то есть с антиградиента: как и в начальной итерации метод, запускается из текущей точки поиска по антиградиенту. Такое обновление работы метода называется повторным стартом или Рестартом. С помощью рестартов эффективность метода Флетчера – Ривса можно существенно повысить. Для этого в приведенных алгоритмах через или итераций переходят не к шагу 2, а к шагу 1.

Рис. 3.6. Минимизация функции Розенброка методом Флетчера-Ривса

Пример 3.5. На рис. 3.7 представлена траектория минимизации функции Розенброка методом Флетчера – Ривса с рестартами, которые выполняются через каждые итераций. Для нахождения точки минимума с допустимой погрешностью 10–3 метод затратил 24 итерации и 327 вычислений функции.

Рис. 3.7. Минимизация функции Розенброка методом Флетчера – Ривса

С рестартами

 
Яндекс.Метрика
Наверх