Метод золотого сечения. Симметричные методы
Материал из MachineLearning.
Содержание |
Постановка задачи
В данной статье рассмотрены симметричные методы поиска экстремума функции одного переменного.
Пусть дана функция , необходимо найти минимум этой функции на заданном отрезке
(задача максимума решается аналогично).
Предполагается, что производная функции либо не существует, либо сложно вычислима, что не позволяет свести задачу к поиску корней производной
.
Методы заключаются в построении последовательности отрезков , стаягивающихся к точке
.
Проанализируем симметричные методы поиска и оценим их эффективность и точность.
Требования к функции
Рассматривая все функции, пусть даже непрерывные, можно построить такой пример, что , хотя
.
Гарантировать применимость рассматриваемых методов можно только для унимодальных функций.
Определение : Функция называется унимодальной на отрезке
, если ∃! точка минимума
на этом отрезке такая, что для любых точек
этого отрезка
Другими словами унимодальная функция монотонна на обе стороны от точки минимума . Аналогично определяется унимодальная функция и для задачи на максимум. Унимодальные функции могут быть непрерывными, разрывными, дискретными...
Далее будем рассматривать только унимодальные функции. При этом предполагаем, что они определены в достаточном количестве точек.
Симметричные методы
В классе симметричных методов на каждом шаге выбирается две точки отрезка и
, симметрично расположенных относительно центра этого отрезка. Дальнейшие действия определяются свойством унимодальной функции:
Пусть функция унимодальна на отрезке
, а ее минимум достигается в точке
. Для любых точек
и
этого отрезка и таких, что
верно следующее:
- если
, то точка минимума
,
- если
, то точка минимума
.
Исходя из определения методов, видно, что всякий симметричный метод полностью определяется заданием отрезка и правилом выбора первой точки. Тогда другая точка
находится по правилу общему для всех симметричных методов:
.
Соответственно, методы различаются способом выбора симметричных точек и
.
Метод деления отрезка пополам
Описание метода
Параметры на входе: - достаточно малые положительные константы.
1. Повторять:
- 2.
;
- 3. Если
, то
;
- 4. Если
, то
;
5. пока ;
6. .
Анализ метода
Считаем, что один шаг - это один этап цикла (п. 2-4).
Изначальная длина отрезка составляет .
После первого шага: ,
После -го шага:
.
Если мы останавливаемся на -м шаге, то погрешность результата составит:
Таким образом, чтобы погрешность вычисления была менее , должна выполняться оценка на число шагов:
На каждом шаге необходимо вычислить значение функции в 2х точках, соответственно, при шагах вычисляется
значений.
Недостаток:
- Информация о значении функции в точках
и
используется только на одном шаге.
Метод золотого сечения
Определение:
Говорят, что точка осуществляет золотое сечение отрезка
, если
В качестве и
выберем точку золотого сечения отрезка и симметричную ей. Если
, то при указанном выборе точек получаем, что
- точка золотого сечения отрезка
, а
- точка золотого сечения отрезка
. Таким образом, на каждом шаге, кроме первого, необходимо вычислять значение только в одной точке, вторая берется из предыдущего шага.
Описание метода
Параметр на входе: - достаточно малая положительная константа, погрешность метода.
1.
2. Повторять:
- 3. Если
, то
;
- 4. Если
, то
;
5. пока ;
6. .
Анализ метода
Считаем, что один шаг - это один этап цикла (п. 3-4), . Тогда, считая длину отрезка на каждом шаге
, получаем:
;
;
;
Нетрудно проверить, что
, где
-числа Фибоначчи.
С другой стороны, выполняется равенство:
Чтобы погрешность вычисления была менее , должна по крайней мере выполняться оценка на число шагов:
Тогда значение будет вычисляться в точках.
Недостаток:
- Неустойчивость относительно ошибок округления: мы получаем приблизительные значения чисел
и
, дальнейшие вычисления только накапливают ошибки, что может привести к нарушению условия вложенности отрезков
и расходимости процесса.
Пусть вычисляется с погрешностью
Тогда имеем:
Из (1):
.
Подставляем (2):
.
Известно, что последовательность сходится при
, В то же время
, поэтому
.
При этом числа Фибоначчи растут со скоростью геометрической прогрессии, знаменателем которой является число . Вследствие этого при фиксированной точности "раскачка" процесса происходит довольно быстро.
Рекомендации в выборе параметров
Для сходимости процесса необходимо согласовывать точность вычисления величины
с заданной точностью
результата.
Из (3) получаем, что при
и
,
будет выполняться
Числовой пример
Заключение
Список литературы
- Карманов В.Г. Математическое программирование: Учебное пособие. - М.:ФИЗМАТЛИТ, 2004
- Горячев Л.В. Одномерная минимизация. Методические указания к самостоятельной работе студентов по курсу “Методы оптимизации” - кафедра процессов управления ДВГУ, 2003