Метод золотого сечения


Метод золотого сечения

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

Содержание

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

Пусть задана функция 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) На первой итерации заданный отрезок делится двумя симметричными относительно его центра точками и рассчитываются значения в этих точках.
  • 2) После чего тот из концов отрезка, к которому среди двух вновь поставленных точек ближе оказалась та, значение в которой максимально (для случая поиска минимума), отбрасывают.
  • 3) На следующей итерации в силу показанного выше свойства золотого сечения уже надо искать всего одну новую точку.
  • 4) Процедура продолжается до тех пор, пока не будет достигнута заданная точность.

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

  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)\!.
    • Если y_1 \ge y_2\! (для поиска max изменить неравенство на y_1 \le y_2\!), то  a=x_1 \!
    • Иначе b=x_2\!.
  3. Шаг 3.
    • Если |b-a|<\varepsilon \!, то x=\frac{a+b}{2}\! и останов.
    • Иначе возврат к шагу 2.

Алгоритм взят из источника: Джон Г.Мэтьюз, Куртис Д.Финк "Численные методы. Использование 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\!.
    • Если y_1>y_2\!, то a=x_1,\; x_1=x_2,\; x_2=b-(x_1-a),\;y_1=y_2,\;y_2=f(x_2)\!.
    • Иначе b=x_2,\;x_2=x_1,\;x_1=a+(b-x_2),\;y_2=y_1,\;y_1=f(x_1)\!.
  3. Шаг 3.
    • Если n=1\!, то x=x_1=x_2\! и останов.
    • Иначе возврат к шагу 2.

Литература

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

См. также


Wikimedia Foundation. 2010.

Смотреть что такое "Метод золотого сечения" в других словарях:

  • метод золотого сечения — метод золотой пропорции Применительно к оценке бизнеса, метод определения ставки дисконтирования, когда основная часть ставки (примерно 62 %) вычисляется как обычно, напр., по модели САРМ, и к ней прибавляется дополнительная часть (примерно 38 %) …   Справочник технического переводчика

  • Метод золотого сечения (метод золотой пропорции) — (golden section method) применительно к оценке бизнеса, метод определения ставки дисконтирования,когда основная часть ставки (примерно 62%) вычисляется как обычно, напр., по модели САРМ, и к ней прибавляется дополнительная часть (примерно 38%),… …   Экономико-математический словарь

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

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

  • Метод Ньютона — Метод Ньютона, алгоритм Ньютона (также известный как метод касательных)  это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном… …   Википедия

  • Метод Нелдера — Мида — Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вв …   Википедия

  • Метод сопряжённых градиентов — Метод сопряженных градиентов метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за шагов. Содержание 1 Основные понятия …   Википедия

  • Метод Хука — Дживса (англ. Hooke  Jeeves), также как и алгоритм Нелдера Мида, служит для поиска безусловного локального экстремума функции и относится к прямым методам, то есть опирается непосредственно на значения функции. Алгоритм делится на две… …   Википедия

  • Метод роя частиц — (МРЧ)  метод численной оптимизации, для использования которого не требуется знать точного градиента оптимизируемой функции. МРЧ был доказан Кеннеди, Эберхартом и Ши[1] [2] и изначально предназначался для имитации социального поведения.… …   Википедия

  • Метод потенциалов — является модификацией симплекс метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Содержание… …   Википедия

Книги



Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.