Метод золотого сечения | это... Что такое Метод золотого сечения? (original) (raw)

Метод золотого сечения — метод поиска значений действительно-значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации

Содержание

Описание метода

Пусть задана функция f(x):\;[a,\;b]\to\mathbb{R},\;f(x)\in\mathrm{C}([a,\;b])\!. Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки x_1\! и x_2\! такие, что:

Иллюстрация выбора промежуточных точек метода золотого сечения.

\frac{b-a}{b-x_1}=\frac{b-a}{x_2-a}=\varphi=\frac{1+\sqrt{5}}{2}=1.618\ldots, где \varphi\! — пропорция золотого сечения.

Таким образом:

\begin{array}{ccc} x_1 &=& b-\frac{(b-a)}{\varphi}\\ x_2 &=& a+\frac{(b-a)}{\varphi} \end{array}\!

То есть точка x_1\! делит отрезок [a,\;x_2]\! в отношении золотого сечения. Аналогично x_2\! делит отрезок [x_1,\;b]\! в той же пропорции. Это свойство и используется для построения итеративного процесса.

Алгоритм

Формализация

  1. Шаг 1. Задаются начальные границы отрезка a,\;b\! и точность \varepsilon\!.
  2. Шаг 2. Рассчитывают начальные точки деления: x_1 = b-\frac{(b-a)}{\varphi},\quad x_2 = a+\frac{(b-a)}{\varphi}\! и значения в них целевой функции: y_1=f(x_1),\;y_2=f(x_2)\!.
  3. Шаг 3.

Алгоритм взят из источника: Джон Г.Мэтьюз, Куртис Д.Финк "Численные методы. Использование MATLAB". — М, СПб: "Вильямс", 2001. — 716 с.

Метод чисел Фибоначчи

В силу того, что в асимптотике \varphi=\lim_{n\to\infty}\frac{F_{n+1}}{F_{n}}, метод золотого сечения может быть трансформирован в так называемый метод чисел Фибоначчи. Однако при этом в силу свойств чисел Фибоначчи количество итераций строго ограничено. Это удобно, если сразу задано количество возможных обращений к функции.

Алгоритм

  1. Шаг 1. Задаются начальные границы отрезка a,\;b\! и число итераций n\!, рассчитывают начальные точки деления: x_1 = a+(b-a)\frac{F_{n-2}}{F_n},\quad x_2 = a+(b-a)\frac{F_{n-1}}{F_n}\! и значения в них целевой функции: y_1=f(x_1),\;y_2=f(x_2)\!.
  2. Шаг 2. n=n-1\!.
  3. Шаг 3.

Литература

  1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
  2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
  3. Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
  4. Максимов Ю.А., Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
  5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
  6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
  7. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1973. — С. 832 с илл..
  8. Джон Г.Мэтьюз, Куртис Д.Финк . Численные методы. Использование MATLAB. — 3-е издание. — М., СПб.: Вильямс, 2001. — С. 716.

См. также

Просмотр этого шаблона Методы оптимизации
Одномерные Метод золотого сечения • Дихотомия • Метод парабол • Перебор по сетке • Метод Фибоначчи • Троичный поиск
Прямые методы Метод Гаусса • Метод Нелдера — Мида • Метод Хука — Дживса • Метод конфигураций • Метод Розенброка
Первого порядка Градиентный спуск • Метод Зойтендейка • Покоординатный спуск • Метод сопряжённых градиентов • Квазиньютоновские методы • Алгоритм Левенберга — Марквардта
Второго порядка Метод Ньютона • Метод Ньютона — Рафсона
Стохастические Метод Монте-Карло • Имитация отжига • Эволюционные алгоритмы • Дифференциальная эволюция • Муравьиный алгоритм • Метод роя частиц
Методы линейного программирования Симплекс-метод • Алгоритм Гомори • Метод эллипсоидов • Метод потенциалов
Методы нелинейногопрограммирования Последовательное квадратичное программирование