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

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

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

Пусть задана функция $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.

См. также

• Золотое сечение
• Числа Фибоначчи