Метод золотого перетину

Метод золотого перетину — метод пошуку екстремуму дійсної функції однієї змінної на заданому відрізку. В основі методу лежить принцип поділу відрізка в пропорціях золотого перетину. Є одним з найпростіших чисельних методів розв'язку задач оптимізації. Вперше представлений Джеком Кіфером у 1953 році.

Опис методу

Нехай задано функцію ${\displaystyle f(x):\;[a,\;b]\to \mathbb {R} ,\;f(x)\in \mathrm {C} ([a,\;b])}$. Тоді для того, щоб знайти невизначене значення цієї функції на заданому відрізку, що відповідає критерію пошуку (нехай це буде мінімум), розглянутий відрізок ділиться в пропорції золотого перетину в обох напрямках, тобто вибираються дві точки ${\displaystyle x_{1}}$ та ${\displaystyle x_{2}}$ такі, що:

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

${\displaystyle {\frac {b-a}{b-x_{1}}}={\frac {b-a}{x_{2}-a}}=\phi ={\frac {1+{\sqrt {5}}}{2}}=1.618\ldots }$, де ${\displaystyle \phi }$ — пропорція золотого перетину.

Таким чином:

${\displaystyle {\begin{array}{ccc}x_{1}&=&b-{\frac {(b-a)}{\phi }}\\x_{2}&=&a+{\frac {(b-a)}{\phi }}\end{array}}}$

Тобто точка ${\displaystyle x_{1}}$ ділить відрізок ${\displaystyle [a,\;x_{2}]}$ у відношенні золотого перерізу. Аналогічно ${\displaystyle x_{2}}$ ділить відрізок ${\displaystyle [x_{1},\;b]}$ у тій же пропорції. Ця властивість і використовується для побудови ітеративного процесу.

Алгоритм

1. На першій ітерації заданий відрізок ділиться двома симетричними відносно центру точками і розраховуються значення в цих точках.
2. Після чого той з кінців відрізка, до якого серед двох знову поставлених точок ближче виявилася та, значення в якій максимальне (для випадку пошуку мінімуму), відкидають.
3. На наступній ітерації в силу показаній вище властивості золотого перетину вже треба шукати лише одну нову точку.
4. Процедура триває, допоки не буде досягнута задана точність.

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

1. Крок 1. Задаються початкові межі відрізка ${\displaystyle a,\;b}$ і точність ${\displaystyle \varepsilon }$.
2. Крок 2. Розраховують початкові точки поділу: ${\displaystyle x_{1}=b-{\frac {(b-a)}{\phi }},\quad x_{2}=a+{\frac {(b-a)}{\phi }}}$ і значення в них цільової функції: ${\displaystyle y_{1}=f(x_{1}),\;y_{2}=f(x_{2})}$.
   • Якщо ${\displaystyle y_{1}\geq y_{2}}$ (для пошуку максимуму змінити нерівність на ${\displaystyle y_{1}\leq y_{2}}$), то ${\displaystyle a=x_{1}}$
   • Інакше ${\displaystyle b=x_{2}}$.
3. Крок 3.
   • Якщо ${\displaystyle |b-a|<\varepsilon }$, то ${\displaystyle x={\frac {a+b}{2}}}$ і зупинитися.
   • Інакше повернутися до кроку 2.

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

В силу того, що в асимптотиці ${\displaystyle \phi =\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}}$метод золотого перетину може бути трансформований у так званий метод чисел Фібоначчі. Однак при цьому в силу властивостей чисел Фібоначчі кількість ітерацій строго обмежена. Це зручно, якщо відразу задано кількість можливих звернень до функції.

1. Крок 1. Задаються початкові межі відрізка ${\displaystyle a,\;b}$ і кількість ітерацій ${\displaystyle n}$, розраховують початкові точки поділу: ${\displaystyle x_{1}=a+(b-a){\frac {F_{n-2}}{F_{n}}},\quad x_{2}=a+(b-a){\frac {F_{n-1}}{F_{n}}}}$ цільової функції: ${\displaystyle y_{1}=f(x_{1}),\;y_{2}=f(x_{2})}$.
2. Крок 2. ${\displaystyle n=n-1}$.
   • Якщо ${\displaystyle y_{1}>y_{2}}$, то ${\displaystyle a=x_{1},\;x_{1}=x_{2},\;x_{2}=b-(x_{1}-a),\;y_{1}=y_{2},\;y_{2}=f(x_{2})}$.
   • Інакше ${\displaystyle b=x_{2},\;x_{2}=x_{1},\;x_{1}=a+(b-x_{2}),\;y_{2}=y_{1},\;y_{1}=f(x_{1})}$.
3. Крок 3.
   • Якщо ${\displaystyle n=1}$, то ${\displaystyle x={\frac {x_{1}+x_{2}}{2}}}$ і зупинитися.
   • Інакше повернутися до кроку 2.

Література

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

Див. також

• Золотий перетин
• Послідовність Фібоначчі
• Пошук Фібоначчі