13.4 Метод “золотого перетину”
З кожних трьох значень цільової функції, які були обчислені в інтервалі невизначеності в подальшому використовуються лише два, а третє не дає додаткової інформації і в подальшому не використовується. В методі золотого перетину цільова функція обчислюється в точках інтервалу невизначеності, які розташовані таким чином, щоб кожне обчислене значення цільової функції давало нову корисну інформацію.
Рисунок 13.11 – Позначення, які використовуються в методі золотого перетину
Суть цього методу полягає в наступному. Інтервал невизначеності ділиться на дві нерівні частини, відношення довжини більшого відрізку до довжини всього інтервалу дорівнює відношенню довжини меншого відрізку до довжини більшого відрізку. На рис. 13.11 показаний інтервал невизначеності Z, який складається з відрізків z1 i z2, відношення довжин яких визначається правилом золотого перетину.
Крім
того, z1
+ z2
= Z. Із першого рівняння витікає
.
Підставивши значення Z з другого рівняння
і поділивши обидві частини на
,
отримаємо
Розв’язуючи це квадратне рівняння, знаходимо для додатнього кореня значення
На рис. 13.12 показано ділення інтервалу невизначеності в цьому відношенні і нанесені відповідні значення цільової функції, які дозволяють зменшити інтервал невизначеності в 1/ 0,618 раз.
Рисунок 13.12 – Метод золотого перетину
На цій стадії ще не видно переваг методу золотого перетину в порівнянні з методом дихотомії, однак їх добре видно при подальшому діленні інтервалу, так як виявляється, що одне із значень цільової функції, яке необхідно обчислити на наступному кроці, вже відомо. Тому, щоб зменшити невизначеність ще в 1/ 0,618 раз, потрібно додатково обчислити тільки одне значення цільової функції в точці, яка визначається правилом золотого перетину.
При n > 2 ефективність методу золотого перетину вища, ніж у метода дихотомії, так як при кожному наступному обчисленні цільової функції інтервал невизначеності скорочується в 1/ 0,618 раз. Після обчислення N значень цільової функції коефіцієнт дроблення інтервалу невизначеності складає
f = 0,618 N-1.
Метод золотого перетину дозволяє відмітити цікаву закономірність: найбільше скорочення наступних інтервалів невизначеності досягається при обчисленні цільової функції в точках, рівновіддалених від його центру. Якщо продовжувати таким чином і кожного разу, обчислюючи цільову функцію, скорочувати інтервал невизначеності, то будуть справедливими наступні відношення:
ZJ-2 = ZJ-1 + ZJ, 1 <="" n,<="" i="">
де ZJ довжина інтервалу невизначеності після обчислення J-го значення цільової функції.
На рис.
13.13 представлений алгоритм вибору
наступної точки пошуку. Задана точність
може, звичайно, змінюватися вибором
значення. Для функції
,
пошук відбувався в інтервалі (0, 2).
Рисунок 13.13 - Послідовність етапів вибору наступної точки пошуку
Істинний мінімум знаходиться в точці 1,76322211, де значення функції дорівнює -0, 0972601313.
Рисунок 13.14 - Схема алгоритму метода „золотого перетину”
При розробці програм для рішення задач однопораметричної оптмізації використовують наступні співвідношення:
