інома порядку більше 3 - досить складне завдання, а звуження інтервалу для унімодальної функції - досить проста.
Метод квадратичної апроксимації
Щоб функція мала мінімум всередині відрізка вона повинна бути, принаймні, квадратичної. Для побудови квадратичної функції досить трьох точок:
M 1 (x 1, y 1), M 2 (x 2, y 2), M 3 (x 3, y 3).
Можна задати апроксимацію функції поліномом виду:
P 2 (x)=a 0 + a 1 (xx 1) + a 2 (xx 1) (xx 2)
і вибрати a 0, a 1, a 0 так, щоб:
P 2 (x 1)=y 1
P 2 (x 2)=y 2
P 2 (x 3)=y 3
Звідси випливає, що
a 0=y 1,
Знайдемо стаціонарну точку x * полінома P 2 (x):
Так як функція унімодального на даному інтервалі і поліном P 2 (x) теж унімодального функція, то x * є прийнятною оцінкою істинного оптимуму.
Метод квадратичної апроксимації зручно застосовувати після локалізації точки мінімуму методом золотого перетину або методом Фібоначчі. Це пояснюється тим, що для двічі диференціюється многочлен другого порядку досить добре апроксимує функцію в околі точки мінімуму.
1.3 Методи з використанням інформації про похідної функції
У методах прямого пошуку при обчисленні значень функції, що мінімізується f (x) неминуче виникають похибки, до яких чутливі алгоритми прямого пошуку, засновані на порівнянні значень функції в окремих точках. Якщо унімодального функція f (x) неперервно диференційовна на відрізку мінімізації, то точку х * найменшого значення функції можна обчислювати як корінь рівняння:
f (x)=0
за допомогою тих чи інших методів чисельного рішення нелінійних рівнянь. У цьому випадку на точність рішення задачі вирішальний вплив справляє похибка обчислення похідної функції. Розглянемо деякі методи одновимірної мінімізації, засновані на використанні похідною функції, що мінімізується.
Метод середньої точки
Будемо шукати мінімум функції f (x) безперервно диференціюється і строго унімодальної на відрізку [a, b]. У цьому випадку єдиною точкою x * [a, b] мінімуму буде стаціонарна точка, в якій f (x *)=0. Відзначимо, що безперервно диференціюється унімодального на відрізку функція може мати на ньому більше однієї стаціонарної точки. На відрізку визначаються дві точки ak, bk, в яких похідні мають різні знаки, f (ak) f (bk) lt; 0. Шуканий оптимум знаходиться між ними. Ділимо інтервал навпіл:, якщо f (xk) gt; 0 ( lt; 0), то з двох інтервалів залишаємо той, на кінцях якого похідна має різні знаки.
Метод середньої точки нагадує метод дихотомії, але сходиться до згаданої значенням х * швидше. Оскільки для методу середньої точки після обчислення n значень похідною минимизируемой на відрізку [0, 1] функції f (x) для довжини інтервалу невизначеності отримуємо.
Таким чином, для однакового зменшення значення ln в методі середньої точки потрібно обчислити вдвічі менше значень похідної функції в порівнянні з числом значень самої функції в методі дихотомії.
Метод Ньютона (метод дотичних)
Якщо строго унімодального на відрізку [a, b] функція f (x) двічі неперервно диференційовна на цьому відрізку, то точку x * мінімуму цієї функції можна знайти шляхом вирішення рівняння f (x)=0 методом Ньютона , іноді званим методом дотичних. Вибираємо x 0 - початкове наближення, зване зазвичай початковою точкою. Лінеарізуем функцію f (x) в околі початкової точки, наближено замінивши дугу графіка цієї функції дотичної в точці (x 0, f (x 0)). Виберемо в якості наступного наближення до х * точку x 1 перетину дотичної з віссю абсцис.
У загальному випадку збіжність методу Ньютона істотно залежить від вибору початкової точки x 0. Тому кажуть, що метод Ньютона володіє локальної збіжністю в тому сенсі, що треба вибрати гарне початкове наближення, що потрапляє в таку околиця точки х *, де f (x) gt; 0. Однак перевірка виконання цієї умови не завжди можлива. Достатньою умовою монотонної збіжності методу Ньютона будуть сталість в інтервалі між точками x 0 і х * знака похідної f (x) і збіг його зі знаком f (x). Виявляється, що в цьому випадку метод Ньютона володіє квадратичної швидкістю збіжності в деякій околиці точки х *.
Метод січних
Метод січних схожий на метод Ньютона, але будується не дотична до графіка похідної, а січна. Геометрична інтерпретація цього методу полягає в тому, що в якост...
