Метод Фібоначчі: Від Основної Ідеї До Практичного Прикладу

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

Метод Фібоначчі: Яку Задачу Розв’язує Цей Підхід

Почнімо з постановки задачі. Нехай задано функцію

\[
f(x), \qquad x \in [a,b].
\]

Потрібно знайти таку точку \( x^* \) на відрізку \( [a,b] \), у якій функція набуває найменшого значення:

\[
f(x^*)=\min_{x\in[a,b]} f(x).
\]

Іншими словами, ми шукаємо мінімум функції на певному проміжку. Але як зробити це без перевірки великої кількості точок? Саме тут і використовують методи одномірної оптимізації. Зокрема, метод Фібоначчі дозволяє не перебирати значення безсистемно, а крок за кроком звужувати відрізок, на якому міститься точка мінімуму.

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

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

Числа Фібоначчі: Чому Метод Фібоначчі Спирається Саме На Них

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

Послідовність чисел Фібоначчі задається рекурентно:

\[
\begin{gathered}
F_1=1,\qquad F_2=1,
\\[4pt]
F_k=F_{k-1}+F_{k-2}, \qquad k>2.
\end{gathered}
\]

Перші її елементи мають вигляд:

\[
F_3=2,\quad F_4=3,\quad F_5=5,\quad F_6=8,\quad F_7=13,\quad F_8=21,\dots
\]

Саме ці числа використовують для вибору положення внутрішніх точок на поточному інтервалі. Крім того, вони допомагають пов’язати довжину початкового відрізка з потрібною точністю пошуку.
Нехай \( \varepsilon \) — задана похибка. Тоді вибирають найменше число \( F_n \), для якого виконується нерівність

\[
F_n \geq \frac{b-a}{\varepsilon}.
\]

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

Тут корисно помітити ще одну важливу річ. Якщо потрібно отримати точніший результат, тобто взяти менше \( \varepsilon \), тоді значення

\[
\frac{b-a}{\varepsilon}
\]

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

Початковий Інтервал: Як Обчислюють Внутрішні Точки

Після того як вибрано потрібне число \( F_n \), можна перейти до побудови двох внутрішніх точок на відрізку \( [a_0,b_0]=[a,b] \). Саме в цих точках на першому кроці обчислюють значення функції.

Точки \( x_1^{(0)} \) і \( x_2^{(0)} \) задаються формулами

\[
x_1^{(0)}=a_0+\frac{F_{n-2}}{F_n}\cdot (b_0-a_0), \qquad
x_2^{(0)}=a_0+\frac{F_{n-1}}{F_n}\cdot (b_0-a_0).
\]

Ці точки лежать усередині відрізка \( [a_0,b_0] \), причому вони розташовані в такому порядку:

\[
a_0<x_1^{(0)}<x_2^{(0)}<b_0.
\]

Чому це важливо підкреслити? Бо надалі саме порядок точок дозволяє коректно зрозуміти, яку частину інтервалу можна відкинути після порівняння значень функції.

Далі обчислюють \( f\left(x_1^{(0)}\right) \) та \( f\left(x_2^{(0)}\right) \), а потім порівнюють отримані значення. Якщо \( f\left(x_1^{(0)}\right)\leq f\left(x_2^{(0)}\right) \), то за умовою унімодальності це означає, що точка мінімуму не лежить правіше \( x_2^{(0)} \). Отже, праву частину інтервалу можна відкинути, і новий інтервал пошуку має вигляд \( [a_1,b_1]=[a_0,x_2^{(0)}] \).

Якщо ж \( f \left(x_1^{(0)}\right)>f \left(x_2^{(0)}\right) \), то точка мінімуму не лежить лівіше \( x_1^{(0)} \). У такому разі відкидають ліву частину, і новий інтервал стає таким: \( [a_1,b_1]=[x_1^{(0)},b_0] \).

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

Метод Фібоначчі: Як Послідовно Звужується Інтервал Пошуку

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

Якщо \( f \left(x_1^{(0)}\right)\leq f \left(x_2^{(0)}\right) \), то покладають

\[
a_1=a_0, \qquad b_1=x_2^{(0)}, \qquad x_2^{(1)}=x_1^{(0)},
\]

а нову точку \( x_1^{(1)} \) обчислюють за формулою

\[
x_1^{(1)}=a_1+\frac{F_{n-3}}{F_{n-1}}\cdot (b_1-a_1).
\]

Якщо ж \( f \left(x_1^{(0)}\right)>f \left(x_2^{(0)}\right) \), то беруть

\[
a_1=x_1^{(0)}, \qquad b_1=b_0, \qquad x_1^{(1)}=x_2^{(0)},
\]

а нову точку \( x_2^{(1)} \) знаходять так:

\[
x_2^{(1)}=a_1+\frac{F_{n-2}}{F_{n-1}}\cdot (b_1-a_1).
\]

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

Що отримуємо в підсумку? Не точний аналітичний розв’язок, а достатньо вузький інтервал, усередині якого міститься точка мінімуму. Саме тому метод Фібоначчі належить до чисельних методів наближеного пошуку.

Після завершення алгоритму виникає природне запитання: яку саме точку брати як наближене значення точки мінімуму? Оскільки наприкінці маємо малий інтервал \( [a_k,b_k] \), усередині якого міститься шукана точка, то на практиці найчастіше беруть середину цього інтервалу:

\[
x^* \approx \frac{a_k+b_k}{2}.
\]

Тоді наближене мінімальне значення функції обчислюють так:

\[
f_{\min}\approx f\left(\frac{a_k+b_k}{2}\right).
\]

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

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

Метод Фібоначчі: Практичне Застосування Крок За Кроком

Тепер перейдемо до практичної частини. Саме на конкретному прикладі найкраще видно, як метод Фібоначчі працює в обчисленнях і як послідовні кроки приводять до наближеного мінімального значення функції. Такий розбір допомагає краще зрозуміти логіку методу і впевненіше застосовувати його під час розв’язування задач.

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

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

Спочатку визначимо, яке число Фібоначчі потрібно взяти. Маємо

\[
\frac{b-a}{\varepsilon}=\frac{3-1}{0.1}=20.
\]

Послідовність чисел Фібоначчі має вигляд

\[
F_1=1,\quad F_2=1,\quad F_3=2,\quad F_4=3,\quad F_5=5,\quad F_6=8,\quad F_7=13,\quad F_8=21.
\]

Найменше число, яке задовольняє умову

\[
F_n\geq \frac{b-a}{\varepsilon},
\]

це \( F_8=21 \). Отже, починаємо з інтервалу

\[
[a_0,b_0]=[1,3].
\]

Будуємо дві внутрішні точки:

\[
\begin{gathered}
x_1^{(0)}=a_0+\frac{F_6}{F_8}\cdot (b_0-a_0)=1+\frac{8}{21}\cdot 2=1.762,
\\[6pt]
x_2^{(0)}=a_0+\frac{F_7}{F_8}\cdot (b_0-a_0)=1+\frac{13}{21}\cdot 2=2.238.
\end{gathered}
\]

Обчислюємо значення функції:

\[
\begin{gathered}
f\left(x_1^{(0)}\right)=(1.762-2)^2+1\approx 1.057,
\\[6pt]
f\left(x_2^{(0)}\right)=(2.238-2)^2+1\approx 1.057.
\end{gathered}
\]

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

\[
[a_1,b_1]=[1,2.238].
\]

Тут корисно звернути увагу на одну особливість саме цього прикладу. Функція \( f(x)=(x-2)^2+1 \) є симетричною відносно точки \( x=2 \). Тому точки \( 1.762 \) і \( 2.238 \), які однаково віддалені від \( 2 \), дають однакові значення функції.

Тепер важливо помітити таке: точка \( x_1^{(0)}=1.762 \) залишилася всередині нового інтервалу. Отже, її зручно використати повторно, і значення \( f(1.762)\approx 1.057 \) вже не треба обчислювати ще раз.

Для нового інтервалу \( [a_1,b_1]=[1,2.238] \) будуємо лише одну нову точку:

\[
x_1^{(1)}=a_1+\frac{F_5}{F_7}\cdot (b_1-a_1)=1+\frac{5}{13}\cdot (2.238-1)=1.476.
\]

Друга точка вже відома з попереднього кроку:

\[
x_2^{(1)}=x_1^{(0)}=1.762.
\]

Тепер маємо

\[
\begin{gathered}
f\left(x_1^{(1)}\right)=(1.476-2)^2+1\approx 1.275,
\\[6pt]
f\left(x_2^{(1)}\right)=f(1.762)\approx 1.057.
\end{gathered}
\]

Оскільки \( f \left(x_1^{(1)}\right)>f \left(x_2^{(1)}\right) \), мінімум лежить правіше точки \( x_1^{(1)} \). Тому беремо новий інтервал

\[
[a_2,b_2]=[1.476,2.238].
\]

Для інтервалу \( [a_2,b_2] \) точку \( x_1^{(2)}=x_2^{(1)}=1.762 \) використовують повторно. Нову точку знаходимо так:

\[
x_2^{(2)}=a_2+\frac{F_5}{F_6}\cdot (b_2-a_2)=1.476+\frac{5}{8}\cdot (2.238-1.476)=1.952.
\]

Обчислюємо

\[
\begin{gathered}
f\left(x_1^{(2)}\right)=f(1.762)\approx 1.057,
\\[6pt]
f\left(x_2^{(2)}\right)=(1.952-2)^2+1\approx 1.002.
\end{gathered}
\]

Оскільки \( f \left(x_1^{(2)}\right)>f \left(x_2^{(2)}\right) \), одержуємо новий інтервал

\[
[a_3,b_3]=[1.762,2.238].
\]

Переходимо далі. Точка \( x_1^{(3)}=x_2^{(2)}=1.952 \) вже відома, тому її значення функції повторно не обчислюємо. Нову точку знаходимо за формулою

\[
x_2^{(3)}=a_3+\frac{F_4}{F_5}\cdot (b_3-a_3)=1.762+\frac{3}{5}\cdot (2.238-1.762)=2.048.
\]

Отже,

\[
\begin{gathered}
f\left(x_1^{(3)}\right)=f(1.952)\approx 1.002,
\\[6pt]
f\left(x_2^{(3)}\right)=(2.048-2)^2+1\approx 1.002.
\end{gathered}
\]

Маємо рівність. Як і раніше, можна звузити інтервал у будь-який бік. Візьмемо, наприклад,

\[
[a_4,b_4]=[1.762,2.048].
\]

Тепер для інтервалу \( [a_4,b_4] \) маємо \( x_2^{(4)}=x_1^{(3)}=1.952 \), а нову точку обчислюємо так:

\[
x_1^{(4)}=a_4+\frac{F_2}{F_4}\cdot (b_4-a_4)=1.762+\frac{1}{3}\cdot (2.048-1.762)=1.857.
\]

Тоді

\[
\begin{gathered}
f\left(x_1^{(4)}\right)=(1.857-2)^2+1\approx 1.020,
\\[6pt]
f\left(x_2^{(4)}\right)=f(1.952)\approx 1.002.
\end{gathered}
\]

Оскільки \( f\left(x_1^{(4)}\right)>f\left(x_2^{(4)}\right) \), беремо новий інтервал

\[
[a_5,b_5]=[1.857,2.048].
\]

Тепер довжина інтервалу дорівнює

\[
b_5-a_5=2.048-1.857=0.191.
\]

Це все ще більше за \( 0.1 \), тому робимо ще один крок. На завершальному етапі як наближене значення точки мінімуму беремо середину останнього достатньо малого інтервалу. Для наочності можна спочатку звузити інтервал до

\[
[a_6,b_6]=[1.952,2.048],
\]

оскільки точка мінімуму міститься всередині нього. Його довжина дорівнює

\[
b_6-a_6=2.048-1.952=0.096<0.1.
\]

Отже, умову точності виконано.

Тепер як наближене значення точки мінімуму беремо середину останнього інтервалу:

\[
x^*\approx \frac{a_6+b_6}{2}=\frac{1.952+2.048}{2}=2.
\]

Тоді наближене мінімальне значення функції дорівнює

\[
f_{\min}\approx f(2)=(2-2)^2+1=1.
\]

Отже, методом Фібоначчі ми отримали

\[
x^*\approx 2,
\qquad
f_{\min}\approx 1.
\]

Це повністю узгоджується з точним результатом, адже для функції \( f(x)=(x-2)^2+1 \) мінімум справді досягається при \( x=2 \), а мінімальне значення дорівнює \( 1 \). Крім того, на цьому прикладі добре видно ще одну важливу рису методу: після кожного звуження інтервалу одна з точок і значення функції в ній зберігаються, а отже, наступні обчислення виконуються економніше.

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

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

1. Метод дихотомії: Послідовне звуження інтервалу — У цій статті йтиметься про простий спосіб пошуку мінімуму через поділ інтервалу та порівняння значень функції в близьких точках.
2. Рівномірний пошук: Перший крок до мінімізації — У цій темі йтиметься про те, як знаходити мінімум функції через послідовний перегляд точок на відрізку з однаковим кроком.
3. Метод Ньютона: Швидкий пошук точки мінімуму — У цій статті буде показано, як використовувати похідні для швидшого наближення до точки мінімуму функції однієї змінної.

Метод Фібоначчі в Коді: Напишіть Власний Пошук Мінімуму

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