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

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

Опис методу

Нехай задано функцію $f(x):[a,b]\to ℝ,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\dots$, де $\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$ і точність $\epsilon$.
2. Крок 2. Розраховують початкові точки поділу: $x_1=b-\frac{(b-a)}{\varphi },x_2=a+\frac{(b-a)}{\varphi }$ і значення в них цільової функції: $y_1=f(x_1),y_2=f(x_2)$.
   • Якщо $y_1\ge y_2$ (для пошуку максимуму змінити нерівність на $y_1\le y_2$), то $a=x_1$
   • Інакше $b=x_2$.
3. Крок 3.
   • Якщо $|b-a|<\epsilon$, то $x=\frac{a+b}{2}$ і зупинитися.
   • Інакше повернутися до кроку 2.

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

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

1. Крок 1. Задаються початкові межі відрізка $a,b$ і кількість ітерацій $n$, розраховують початкові точки поділу: $x_1=a+(b-a)\frac{F_{n-2}}{F_n},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=\frac{x_1+x_2}{2}$ і зупинитися.
   • Інакше повернутися до кроку 2.

Література

1. Шаблон:Книга-ру
2. Шаблон:Книга-ру
3. Шаблон:Книга-ру
4. Шаблон:Книга
5. Шаблон:Книга-ру
6. Шаблон:Книга-ру
7. Шаблон:Книга-ру
8. Шаблон:Книга-ру
9. Шаблон:Книга-ру

Див. також

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