Метод Золотого Перетину: Як Знайти Мінімум Функції

Мінімізація функції однієї змінної — це випадок, коли на відрізку потрібно знайти таку точку, де значення функції найменше. Звучить просто, але як зробити це швидко й без зайвих обчислень? Саме тут добре працює метод золотого перетину. Він дозволяє послідовно звужувати проміжок пошуку й не діяти навмання. У цій статті розберемо, звідки беруться ключові числа методу та як працює алгоритм на відрізку.

Метод Золотого Перетину: Пропорція Поділу Відрізка

Почнемо з базової конструкції. Маємо відрізок \( [a,b] \) і хочемо поділити його точкою так, щоб частини були нерівні, але поділ мав особливу властивість. Нехай \( c\in(a,b) \). Тоді «золотим» називають такий поділ, коли відношення всього відрізка до більшої частини дорівнює відношенню більшої частини до меншої:

\[
\frac{b-a}{b-c}=\frac{b-c}{c-a}=r.
\]

Тут \( r \) — сталий коефіцієнт, який задає пропорцію поділу. Тепер зробимо важливий крок: виразимо \( r \) з цієї умови.

Позначимо довжини частин:

\[
L=b-a,\qquad x=b-c,\qquad L-x=c-a.
\]

Тоді з умови золотого перетину маємо:

\[
\frac{L}{x}=\frac{x}{L-x}.
\]

Перемножимо навхрест:

\[
L \cdot (L-x)=x^2.
\]

Розкриємо дужки:

\[
L^2-L \cdot x=x^2.
\]

Перенесемо все в одну сторону:

\[
x^2+L \cdot x-L^2=0.
\]

Це квадратне рівняння відносно \( x \). Розв’яжемо його:

\[
x=\frac{-L+\sqrt{L^2+4 \cdot L^2}}{2}=\frac{-L+\sqrt{5} \cdot L}{2}=L\cdot\frac{\sqrt{5}-1}{2}.
\]

Отже, частка \( \frac{x}{L} \) дорівнює:

\[
\frac{x}{L}=\frac{\sqrt{5}-1}{2}.
\]

А коефіцієнт \( r \) — це:

\[
r=\frac{L}{x}=\frac{1}{\frac{\sqrt{5}-1}{2}}=\frac{2}{\sqrt{5}-1}=\frac{\sqrt{5}+1}{2}.
\]

Тобто

\[
r=\frac{1+\sqrt{5}}{2}\approx 1.618.
\]

Саме це число й визначає, як ми будемо ставити точки в алгоритмі мінімізації. Зручно, правда?

Запуск Алгоритму: Вибір Двох Точок і Перше Порівняння

Добре, тепер переходимо до мінімізації \( f(x) \) на \( [a,b] \). Потрібні дві внутрішні точки, щоб порівняти значення функції й відкинути частину відрізка. Назвемо їх \( c \) і \( d \), де \( a<c<d<b \).

У методі золотого перетину точки беруть так, щоб вони ділили відрізок у «золотій» пропорції. Найзручніше записати через \( r \):

\[
d=a+\frac{1}{r} \cdot (b-a),
\qquad
c=b-\frac{1}{r} \cdot (b-a).
\]

Тут важливо: точки симетричні відносно середини за частками довжин, а не за відстанями. Якщо хочете той самий запис без \( r \), просто підставимо \( \frac{1}{r}=\frac{\sqrt{5}-1}{2} \):

\[
d=a+\frac{\sqrt{5}-1}{2} \cdot (b-a),
\qquad
c=b-\frac{\sqrt{5}-1}{2} \cdot (b-a).
\]

Далі робимо те, що й визначає метод: обчислюємо і порівнюємо \( f(c) \) та \( f(d) \). І тут виникає ключове питання: яку частину відрізка можна сміливо відкинути?

Якщо \( f(c)>f(d) \), то мінімум не лежить у \( [a,c] \). Тоді залишаємо \( [a_1,b_1]=[c,b] \).
Якщо \( f(d)>f(c) \), то мінімум не лежить у \( [d,b] \). Тоді залишаємо \( [a_1,b_1]=[a,d] \).

Чому це працює? Бо метод застосовують для унімодальної функції на \( [a,b] \): вона має лише один мінімум на цьому відрізку. Тож порівняння в двох точках показує, в який бік розташований мінімум. Логіка дуже практична: порівняли — відкинули — звузили.

Метод Золотого Перетину: Зменшення Інтервалу, Критерій Зупинки та Наближена Відповідь

Тепер найприємніше: після першого кроку інтервал стає коротшим, причому в сталу кількість разів. Подивимося це прямо з формул.

Початкова довжина:

\[
L_0=b-a.
\]

Після відкидання частини відрізка лишається відрізок довжини

\[
L_1=b_1-a_1=\frac{1}{r} \cdot (b-a)=\frac{L_0}{r}.
\]

Отже, на кожному кроці (якщо робити все за правилами) довжина «інтервалу невизначеності» множиться на \( \frac{1}{r} \). Тоді після \( n \) кроків:

\[
L_n=b_n-a_n=\frac{b-a}{r^n}.
\]

Це вже готова оцінка швидкості звуження. І тут природно виникає практичне питання: коли зупинятися?

Зазвичай задають точність \( \varepsilon>0 \) і зупиняють процес, коли

\[
b_n-a_n<\varepsilon.
\]

Тоді з формули для \( L_n \) отримуємо умову на кількість кроків:

\[
\frac{b-a}{r^n}<\varepsilon \quad\Longrightarrow\quad r^n>\frac{b-a}{\varepsilon}.
\]

Логарифмуємо (за будь-якою основою, зручно — натуральним логарифмом):

\[
n>\frac{\ln\left(\frac{b-a}{\varepsilon}\right)}{\ln(r)}.
\]

Тобто кількість ітерацій можна оцінити заздалегідь (найменше ціле \( n \), яке задовольняє цю нерівність). Це дуже зручно, бо ви одразу розумієте, скільки разів доведеться обчислювати \( f(x) \).

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

А як отримати відповідь у вигляді конкретної точки?

Після зупинки маємо малий інтервал \( [a_n,b_n] \), у якому лежить мінімум. Тоді як просте наближення часто беруть:

\[
x^*\approx \frac{a_n+b_n}{2},
\]

або ж обирають з останніх точок ту, де значення функції менше. У наступному розділі, на прикладах, це буде видно дуже наочно.

Практика Методу: Розрахунки Крок за Кроком

Переходимо до практичних обчислень і подивімося, як метод золотого перетину звужує інтервал пошуку на реальних числах. Тут важливо не лише отримати відповідь, а й побачити логіку кожного кроку. Тоді в наступних задачах ви зможете повторити алгоритм уже самостійно.

Приклад 1. Знайти мінімум функції \( f(x)=(x-2)^2+1 \) на відрізку \( [a,b]=[1,3] \) з точністю \( \varepsilon=0.1 \) використовуючи метод золотого перетину

Розглянемо функцію \( f(x)=(x-2)^2+1 \) на \( [1,3] \). На цьому відрізку вона є унімодальною, бо має лише один мінімум поблизу \( x=2 \). Це означає, що порівняння \( f(c) \) і \( f(d) \) дозволяє безпечно відкидати частину інтервалу.

Беремо

\[
r=\frac{1+\sqrt{5}}{2}\approx 1.618,
\qquad
\frac{1}{r}\approx 0.618.
\]

Починаємо з \( [a_0,b_0]=[1,3] \). Будуємо дві точки:

\[
\begin{gathered}
d_0=a_0+\frac{1}{r}(b_0-a_0)=1+0.618\cdot 2=2.236,
\\[6pt]
c_0=b_0-\frac{1}{r}(b_0-a_0)=3-0.618\cdot 2=1.764.
\end{gathered}
\]

Обчислюємо:

\[
\begin{gathered}
f(c_0)=(1.764-2)^2+1=1.056,
\\[6pt]
f(d_0)=(2.236-2)^2+1=1.056.
\end{gathered}
\]

Маємо рівність \( f(c_0)=f(d_0) \), тому інтервал можна звузити будь-яким із двох симетричних способів. Для визначеності залишимо

\[
[a_1,b_1]=[1,2.236].
\]
Тепер важлива деталь. Точка \( c_0=1.764 \) належить новому інтервалу \( [a_1,b_1] \), тому її можна використати як робочу точку наступного кроку без повторного обчислення. Тобто

\[
d_1=c_0=1.764,
\qquad
f(d_1)=f(c_0)=1.056.
\]
Другу точку знаходимо за формулою:

\[
c_1=b_1-\frac{1}{r}(b_1-a_1)=2.236-0.618\cdot 1.236=1.472,
\]

і рахуємо нове значення:

\[
f(c_1)=(1.472-2)^2+1=1.279.
\]

Оскільки \( f(c_1)>f(d_1) \), мінімум правіше, тому

\[
[a_2,b_2]=[c_1,b_1]=[1.472,2.236].
\]

Далі переносимо точку, значення якої вже відоме. У новому інтервалі зберігається \( d_1=1.764 \), тому

\[
c_2=d_1=1.764,
\qquad
f(c_2)=f(d_1)=1.056.
\]

Тепер визначаємо іншу точку:

\[
d_2=a_2+\frac{1}{r}(b_2-a_2)=1.472+0.618\cdot 0.764=1.944,
\]

і обчислюємо:

\[
f(d_2)=(1.944-2)^2+1=1.003.
\]

Оскільки \( f(c_2)>f(d_2) \), залишаємо

\[
[a_3,b_3]=[c_2,b_2]=[1.764,2.236].
\]

Тепер у цьому інтервалі зберігається точка \( d_2=1.944 \), тому

\[
c_3=d_2=1.944,
\qquad
f(c_3)=f(d_2)=1.003.
\]

Іншу точку рахуємо:

\[
d_3=a_3+\frac{1}{r}(b_3-a_3)=1.764+0.618\cdot 0.472=2.056,
\]

а далі:

\[
f(d_3)=(2.056-2)^2+1=1.003.
\]

Маємо рівність \( f(c_3)=f(d_3) \), тому для визначеності візьмемо

\[
[a_4,b_4]=[1.764,2.056].
\]

У цьому інтервалі зберігається точка \( c_3=1.944 \), тому

\[
d_4=c_3=1.944,
\qquad
f(d_4)=f(c_3)=1.003,
\]

а іншу точку знаходимо:

\[
c_4=b_4-\frac{1}{r}(b_4-a_4)=2.056-0.618\cdot 0.292=1.876,
\]

і обчислюємо:

\[
f(c_4)=(1.876-2)^2+1=1.015.
\]

Оскільки \( f(c_4)>f(d_4) \), беремо

\[
[a_5,b_5]=[c_4,b_4]=[1.876,2.056].
\]

Далі зберігається точка \( d_4=1.944 \), тому

\[
c_5=d_4=1.944,
\qquad
f(c_5)=f(d_4)=1.003.
\]

Іншу точку визначаємо:

\[
d_5=a_5+\frac{1}{r}(b_5-a_5)=1.876+0.618\cdot 0.180=1.987,
\]

та обчислюємо:

\[
f(d_5)=(1.987-2)^2+1=1.
\]

Оскільки \( f(c_5)>f(d_5) \), отримуємо

\[
[a_6,b_6]=[c_5,b_5]=[1.944,2.056].
\]

Тепер

\[
b_6-a_6=2.056-1.944=0.112,
\]

тому робимо ще крок. Точка \( d_5=1.987 \) залишається в інтервалі, отже

\[
c_6=d_5=1.987,
\qquad
f(c_6)=f(d_5)=1.
\]

Іншу точку обчислюємо:

\[
d_6=a_6+\frac{1}{r}(b_6-a_6)=1.944+0.618\cdot 0.112=2.013,
\]

а далі:
\[
f(d_6)=(2.013-2)^2+1=1.
\]

За рівності інтервал можна звузити в будь-який бік. Для визначеності візьмемо

\[
[a_7,b_7]=[1.944,2.013],
\qquad
b_7-a_7=0.069<0.1.
\]

Отже, умова точності виконана. Як стандартне наближення точки мінімуму беремо середину:

\[
x^*\approx \frac{a_7+b_7}{2}=\frac{1.944+2.013}{2}=1.979.
\]

А якщо орієнтуватися на найменше з уже отриманих значень, то добре підходить точка

\[
x^*\approx 1.987,
\qquad
f(x^*)\approx 1.
\]

Це узгоджується з тим, що справжній мінімум для цієї функції досягається при \( x=2 \) і дорівнює \( f_{\min}=1 \). Тобто метод дав близьку відповідь і зробив це через послідовне, контрольоване звуження відрізка.

Приклад 2. Визначити кількість ітерацій необхідних для знаходження мінімум функції \( f(x)=(x-2)^2+1 \) на відрізку \( [a,b]=[1,3] \) з точністю \( \varepsilon=0.1 \) використовуючи метод золотого перетину

Тепер перевіримо, чи узгоджується кількість кроків із тим, що ми отримали в попередньому прикладі. Використовуємо оцінку

\[
n>\frac{\ln\left(\frac{b-a}{\varepsilon}\right)}{\ln(r)},
\qquad
r=\frac{1+\sqrt{5}}{2}.
\]

Для \( [1,3] \) маємо \( b-a=2 \), тому

\[
\frac{b-a}{\varepsilon}=\frac{2}{0.1}=20,
\qquad
n>\frac{\ln(20)}{\ln(r)}.
\]

Беремо \( r\approx 1.618 \). Тоді \( \ln(20)\approx 2.996 \), \( \ln(1.618)\approx 0.481 \), звідси

\[
n>\frac{2.996}{0.481}\approx 6.225.
\]

Отже, достатньо \( n=7 \) ітерацій. Це добре узгоджується з практичним результатом: після сьомого кроку ми отримали інтервал довжини \( 0.069 \), який уже менший за \( \varepsilon=0.1 \).

Куди Рухатися Далі: Ще Кілька Методів Мінімізації

Ми розібрали метод золотого перетину і побачили, як він крок за кроком звужує інтервал. А що, як хочеться мати інші варіанти й розуміти, коли який спосіб дає кращий результат? Ось теми, які логічно продовжують цю статтю.

Метод Фібоначчі: Точний план кроків — Поговоримо, як числа Фібоначчі задають послідовність перевірок і допомагають заздалегідь спланувати пошук мінімуму.
Метод дихотомії: Просте розділення інтервалу — Розберемо ідею перевірки двох близьких до середини точок та покажемо, як швидко звузити область пошуку.
Рівномірний пошук: Стартове наближення — Пояснимо, як пройти інтервал рівними кроками, знайти найкращий проміжок і підготувати основу для точніших методів.

Метод Золотого Перетину в Коді: Напишіть Свій Пошук Мінімуму

Тепер уявіть, що блок-схема нижче — це не просто картинка, а готовий план для вашого невеликого навчального завдання. Чому б не взяти її як підказку й не написати на улюбленій мові програмування компактну програму, яка знаходить мінімальне значення унімодальної функції за методом золотого перетину? Такий проєкт добре показує, як теорія швидко перетворюється на практичний інструмент, який можна запускати знову і знову на різних функціях. А ще це чудовий спосіб перевірити себе: чи однаково впевнено ви розумієте метод і на папері, і в коді.

Метод Золотого Перетину: Мінімізація Функції Однієї Змінної