Метод Фібоначчі

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

Припустимо, що є інтервал невизначеності і відомо значення функції всередині цього інтервалу (див. рис. 13.15).

Рисунок 13.15 – Унімодальна цільова функція. Геометрична інтерпретація метода Фібоначчі

Якщо можна обчислити функцію всього один раз в точці , то де слід помістити точку , для того щоб отримати найменший можливий інтервал невизначеності?

Припустимо і , причому , як показано на рис. 13.15, і ці значення будуть фіксовані, якщо відомі і . Якщо знаходиться в інтервалі , то:

1. Якщо , то новим інтервалом невизначеності буде довжиною .

2. Якщо , те новим інтервалом невизначеності буде довжиною .

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

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

На n- ому обчисленні n-у точку потрібно помістити симетрично по відношенню до ( -1)-ї точки. Положення цієї останньої точки в принципі залежить від нас. Для того щоб отримати найбільше зменшення інтервалу на даному етапі, слід поділити навпіл попередній інтервал. Тоді точка буде співпадати з точкою . Однак при цьому ми не одержуємо жодної нової інформації. Звичайно точки і знаходяться одна від одної на достатній відстані, щоб визначити, в якій половині, лівій чи правій, знаходиться інтервал невизначеності. Вони розміщуються на відстані по обидві сторони від середини відрізка ; можна самостійно задати величину або вибрати цю величину рівній мінімально можливій відстані між двома точками. (Припустимо, що в нашому прикладі інженер може регулювати температуру з інтервалом в 1С°, тому .)

Інтервал невизначеності буде мати довжину , отже, (рис. 13.16, нижня частина).

Рисунок 13.16 – Геометрична інтерпретація ітераційного процесу Фібоначчі

На попередньому етапі точки і повинні бути поміщені симетрично всередині інтервалу з на відстані від кінців цього інтервалу. Отже, (рис. 13.16, середня частина).

Зауваження. З рисунку зрозуміло, що на передостанньому етапі залишається в якості внутрішньої точки.

Аналогічно

. (рис. 13.16, верхня частина)

В загальному випадку

при 1<j<="" p=""> </j

Таким чином,

, (13.2)

,

,

і т.д.

Якщо визначити послідовність чисел Фібоначчі наступним чином:

та для тоді

, (13.3)

Якщо початковий інтервал має довжину , то

.

Тобто . (13.4)

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

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

. (13.5)

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

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

. (13.6)

Якщо та , тоді можна розглянути чотири випадки (рис. 13.17).

Рисунок 13.17 – Геометрична інтерпретація алгоритму визначення цільової функції на і-му кроці ітерації

Приклад 1. Використати метод Фібоначчі для пошуку мінімуму функції в інтервалі (0,1) при 10-кратному обчисленні функції.

Розв‘язок. Остаточний інтервал невизначеності має довжину

З точністю до шостого знаку після коми мінімум досягається в точці , і в цій точці .