Нехай f(x) є унімодальною функцією на відрізку [a,b] і має неперервну похідну на цьому відрізку, а точка є точкою мінімуму. Отже, у точці маємо:
(5.6)
при цьому
Отже задачу пошуку мінімуму (5.1) можна замінити на задачу пошуку кореня рівняння (5.6), тобто застосувати методи розв’язку нелінійних рівнянь до рівняння відносно похідної функції.
а) метод бісекції. Оскільки і , то в точці мінімуму похідна змінює знак. Тому для пошуку мінімуму відрізок ділиться на дві частини і виключається той відрізок, де похідна не змінює знак. Продовжуючи цей процес зменшується той відрізок , всередині якого функція досягає мінімуму. Метод бісекції збігається за законом:
(5.7)
б) метод Ньютона. Застосування методу Ньютона для розв’язку рівняння дає наступну розрахункову формулу:
(5.8)
Він має квадратичну збіжність і ітераційний процес закінчується при виконанні умови: .
Для збіжності методу необхідно і достатньо, щоб виконувалися умови:
тобто друга і третя похідні були знакосталі на відрізку локалізації.
3 ЗАВДАННЯ
1 Написати основні співвідношення для мінімізації методом золотого перетину функції з таблиці завдань.
2 Провести оцінку числа обумовленості задачі мінімізації для зазначеної в таблиці відносної похибки функції і визначити максимально можливу точність обчислення точки мінімуму.
3 Написати програму і на ЕОМ розрахувати з максимально можливою точністю точку мінімуму функції.
4 ТАБЛИЦЯ ІНДИВІДУАЛЬНИХ ЗАВДАНЬ
№ | Функція f(x) | Характер екстремуму | Відносна похибка df(x) |
min | 10-8 | ||
min | 10-8 | ||
min | 10-9 | ||
min | 10-9 | ||
min | 10-8 | ||
min | 10-9 | ||
min | 10-9 | ||
min | 10-8 | ||
min | 10-9 | ||
min | 10-8 | ||
min | 10-8 | ||
min | 10-9 |
5 КОНТРОЛЬНІ ПИТАННЯ
1 Етапи пошуку мінімуму функції.
2 Що таке локальний і глобальний мінімум?
3 Визначення унімодальної функції.
4 Абсолютне число обумовленості задачі мінімізації.
5 Метод оптимально пасивного пошуку.
6 Метод розподілу відрізка навпіл.
7 Метод золотого перетину.
8 Метод бісекції.
9 Метод Ньютона.
10 Необхідна і достатня умова збіжності методу Ньютона.