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

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

Опис методу

Нехай задано функцію $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}}=\phi ={\frac {1+{\sqrt {5}}}{2}}=1.618\ldots

, де

\phi

— пропорція золотого перетину.

Таким чином:

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

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

Алгоритм

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

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

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

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

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

Крок 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. $n=n-1$ $\text{[math]}$ .
- Якщо $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.
- Якщо $n=1$ , то $x={\frac {x_{1}+x_{2}}{2}}$ і зупинитися.
- Інакше повернутися до кроку 2.

Література

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

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.