Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування
покладають . Тоді
якщо , то , .
інакше , .
якщо n=1, то і зупиняються. Значення цільової функції в цій точці і буде мінімумом функції. Інакше повертаються до 3-го кроку.
Відмітимо, що на кожному кроці методу Фібоначчі точка, що лежить середині відрізку локалізації, ділить його у відношенні двох послідовних чисел Фібоначчі.
2. Визначення найменшого значення функції на заданому відрізку за допомогою методів одновимірної оптимізації
Визначимо найменше значення функції на відрізку з точністю , використовуючи
метод дихотомії:
Розіб’ємо відрізок навпіл і візьмемо дві симетричні відносно центру точки такі, що , де і відкинемо ту з точок, до якої ближче виявилась одна з двох знову поставлених точок з максимальним значенням.
Обчислюємо значення функції в цих точках:
Оскільки , то нові межі відрізка і . В цьому звуженому проміжку знову розраховуємо дві точки, симетричні відносно його середини і значення функції в цих точках. Процедура буде продовжуватись до тих пір, поки не буде виконуватись умова .
В нашому випадку . Тому знову розраховуємо дві точки:
Оскільки то нові межі відрізка і . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.
нові межі відрізка , . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.
нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.
нові межі відрізка , . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.
нові межі відрізка , . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.
нові межі відрізка , . Перевіряємо умову зупинки: . Отже продовжуємо процедуру.
нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.
нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.
нові межі відрізка , . Перевіряємо умову зупинки: . Продовжуємо процедуру.
нові межі відрізка , .
Перевіряємо умову зупинки: . Отже в якості точки локального мінімуму можна наближено прийняти середину відрізку . Тоді мінімальне значення вихідної функції буде рівним:
.
метод золотого перерізу
На першій ітерації відрізок ділимо двома симетричними відносно центра точками за формулами:
Обчислюємо значення функції в цих точках:
Той із кінців відрізка, до якого серед знову поставлених точок ближче опинилась та, значення функції в якій максимальне, відкидаємо. Тобто, оскільки , то покладаємо, що . Тепер обчислюємо значення функції в нових точках:
Так як і в методі дихотомії процедура буде продовжуватись до тих пір, поки не буде виконуватись умова . Отже перевіримо умову зупинки:
. Тому знову аналогічно шукаємо нові межі відрізка. Оскільки маємо:
Перевіряємо умову зупинки: , тому продовжуємо процедуру.
Перевіряємо умову зупинки: , тому продовжуємо процедуру.
Знову перевіряємо умову зупинки: