- Метод золотого сечения
-
Метод золотого сечения — метод поиска значений действительно-значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации
Содержание
Описание метода
Пусть задана функция . Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки и такие, что:
- , где — пропорция золотого сечения.
Таким образом:
То есть точка делит отрезок в отношении золотого сечения. Аналогично делит отрезок в той же пропорции. Это свойство и используется для построения итеративного процесса.
Алгоритм
- 1) На первой итерации заданный отрезок делится двумя симметричными относительно его центра точками и рассчитываются значения в этих точках.
- 2) После чего тот из концов отрезка, к которому среди двух вновь поставленных точек ближе оказалась та, значение в которой максимально (для случая поиска минимума), отбрасывают.
- 3) На следующей итерации в силу показанного выше свойства золотого сечения уже надо искать всего одну новую точку.
- 4) Процедура продолжается до тех пор, пока не будет достигнута заданная точность.
Формализация
- Шаг 1. Задаются начальные границы отрезка и точность .
- Шаг 2. Рассчитывают начальные точки деления: и значения в них целевой функции: .
- Если (для поиска max изменить неравенство на ), то
- Иначе .
- Шаг 3.
- Если , то и останов.
- Иначе возврат к шагу 2.
Алгоритм взят из источника: Джон Г.Мэтьюз, Куртис Д.Финк "Численные методы. Использование MATLAB". — М, СПб: "Вильямс", 2001. — 716 с.
Метод чисел Фибоначчи
В силу того, что в асимптотике , метод золотого сечения может быть трансформирован в так называемый метод чисел Фибоначчи. Однако при этом в силу свойств чисел Фибоначчи количество итераций строго ограничено. Это удобно, если сразу задано количество возможных обращений к функции.
Алгоритм
- Шаг 1. Задаются начальные границы отрезка и число итераций , рассчитывают начальные точки деления: и значения в них целевой функции: .
- Шаг 2. .
- Если , то .
- Иначе .
- Шаг 3.
- Если , то и останов.
- Иначе возврат к шагу 2.
Литература
- Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
- Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
- Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
- Максимов Ю.А., Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
- Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
- Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
- Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1973. — С. 832 с илл..
- Джон Г.Мэтьюз, Куртис Д.Финк . Численные методы. Использование MATLAB. — 3-е издание. — М., СПб.: Вильямс, 2001. — С. 716.
См. также
Методы оптимизации Одномерные Метод золотого сечения • Дихотомия • Метод парабол • Перебор по сетке • Метод Фибоначчи • Троичный поиск Прямые методы Метод Гаусса • Метод Нелдера — Мида • Метод Хука — Дживса • Метод конфигураций • Метод Розенброка Первого порядка Градиентный спуск • Метод Зойтендейка • Покоординатный спуск • Метод сопряжённых градиентов • Квазиньютоновские методы • Алгоритм Левенберга — Марквардта Второго порядка Метод Ньютона • Метод Ньютона — Рафсона Стохастические Метод Монте-Карло • Имитация отжига • Эволюционные алгоритмы • Дифференциальная эволюция • Муравьиный алгоритм • Метод роя частиц Методы линейного
программированияСимплекс-метод • Алгоритм Гомори • Метод эллипсоидов • Метод потенциалов Методы нелинейного
программированияПоследовательное квадратичное программирование Категории:- Алгоритмы поиска
- Алгоритмы оптимизации
- , где — пропорция золотого сечения.
Wikimedia Foundation. 2010.