Метод золотого перерізу — метод пошуку екстремуму дійсної функції однієї змінної на заданому відрізку. В основі методу лежить принцип поділу відрізка в пропорціях золотого перерізу. Є одним з найпростіших чисельних методів розв'язку задач оптимізації. Вперше представлений Джеком Кіфером у 1953 році.
Опис методу Нехай задано функцію . Тоді для того, щоб знайти невизначене значення цієї функції на заданому відрізку, що відповідає критерію пошуку (нехай це буде мінімум), розглянутий відрізок ділиться в пропорції золотого перерізу в обох напрямках, тобто вибираються дві точки та такі, що:
, де — пропорція золотого перерізу. Таким чином:
Тобто точка ділить відрізок у відношенні золотого перерізу. Аналогічно ділить відрізок у тій же пропорції. Ця властивість і використовується для побудови ітеративного процесу.
Алгоритм На першій ітерації заданий відрізок ділиться двома симетричними відносно центру точками і розраховуються значення в цих точках. Після чого той з кінців відрізка, до якого серед двох знову поставлених точок ближче виявилася та, значення в якій максимальне (для випадку пошуку мінімуму), відкидають. На наступній ітерації в силу показаній вище властивості золотого перерізу вже треба шукати лише одну нову точку. Процедура триває, допоки не буде досягнута задана точність.
Формалізація Крок 1. Задаються початкові межі відрізка і точність . Крок 2. Розраховують початкові точки поділу: і значення в них цільової функції: . Якщо (для пошуку максимуму змінити нерівність на ), то Інакше . Крок 3. Якщо , то і зупинитися. Інакше повернутися до кроку 2.
Метод чисел Фібоначчі В силу того, що в асимптотиці метод золотого перерізу може бути трансформований у так званий метод чисел Фібоначчі. Однак при цьому в силу властивостей чисел Фібоначчі кількість ітерацій строго обмежена. Це зручно, якщо відразу задано кількість можливих звернень до функції. Крок 1. Задаються початкові межі відрізка і кількість ітерацій , розраховують початкові точки поділу: цільової функції: . Крок 2. . Якщо , то . Інакше . Крок 3. Якщо , то і зупинитися. Інакше повернутися до кроку 2.
Література
Див. також Золотий переріз Послідовність Фібоначчі Пошук Фібоначчі