Методи поліноміальної інтерполяції
Нехай після проведення k випробувань має місце ситуація III (рис. 3.7, див. попередній пост):
яка в силу унімодальності функції Q(х) гарантує, що точка мінімуму x:* перебуватиме всередині інтервалу [аk, bk]
Надалі сукупність точок (ak, xk, bk), що призводить до ситуації III, називатимемо сукупністю «вдалих точок».
Розглянемо клас методів, які називаються методами поліноміальної інтерполяції, основна ідея яких полягає в тому, що за інформацією про m випробування (xi, Q(xi)) i = 1, 2, …, m будується інтерполюючий поліном φn(х) ступеня n ≤ m - 1, що володіє наступними властивостями:
φn(х) є рівномірним наближенням функції, що мінімізується на інтервалі [аk, bk]: точка мінімуму х* полінома φn(х) визначається досить просто.
Зазначені властивості полінома φn(х) дозволяють кожному кроці пошуку використовуватиме скорочення поточного інтервалу невизначеності як інформацію про точках випробувань xi, а й інформацію про значення функції Q (xi) у цих точках.
Для трьох точок випробувань (m = 3) як поліном φn(х) уметоді квадратичної інтерполяції F 5 використовується інтерполяційний багаточлен Лагранжа:
який має мінімум xmin у внутрішній точці інтервалу [аk, bk] лише тоді, коли α2 > 0. тобто тоді, коли для сукупності «вдалих точок» виконується нерівність:
У цьому випадку з умови dφ2/dx = 0 неважко отримати, що
Після проведення випробування у точці х здійснюється скорочення інтервалу невизначеності, що містить точку мінімуму х*, та визначається нова сукупність «вдалих точок». При цьому можливі наступні чотири випадки.
Неважко бачити, що для випадків 1 та 3 поточний інтервал невизначеності [ak+1, bk+1] скорочується точно вдвічі:
а для випадків 2 та 4, про врахування умови (3.71), має місце верхня оцінка:
Блок-схема методу F 5 , реалізує пошук мінімуму унімодальної функції Q (х), на яку задана вихідна сукупність «вдалих точок» (а, х0, b), наведено на рис. 3.9.
Для чотирьох точок випробувань (m = 4) пошук мінімуму унімодальної функції можна ввести за допомогою методу кубічної інтерполяції F 6 який відрізняється від методу F 5 тим, що в ньому в якості інтерполіруючого полінома φn(х) використовується кубічна парабола:
Не порушуючи спільності розгляду, припустимо, що сукупність «вдалих точок» на кожному кроці пошуку наводиться до одиничного інтервалу за допомогою перетворення
Тоді, взявши ці точки як вузли інтерполяції, для визначення коефіцієнтів інтерполюючого полінома (3.72) запишемо систему лінійних рівнянь:
Інтерполіруюча функція (3.72) має один максимум і один мінімум, якщо виконується нерівність:
У цьому випадку точка мінімуму х* полінома φ3(х) визначається за формулою
Подальша процедура пошуку мінімуму унімодальної функції Q(х) за методом кубічної інтерполяції F* аналогічна процедурі методу F5, оскільки пов'язана зі скороченням інтервалу невизначеності [ak, bk] та вибором нової сукупності «вдалих точок» для (k+1)-го кроку з уже проведених випробувань у точках (аk, bk, хk, хr, х*).
У зв'язку з вищесказаним при пошуку мінімуму унімодальної функції з високим ступенем точності ε необхідно послідовно застосовувати спочатку методи скорочення інтервалуневизначеності, доки не буде отримана сукупність «вдалих точок», а потім методи поліноміальної інтерполяції. Причому при мінімізації функції, що володіє на інтервалі невизначеності великими по величині похідними вищих порядків, доцільно використовувати методи F 1 - F 4 , а в тих випадках, коли функція, що мінімізується, є гладкою функцією, близькою до квадратичної параболі, - методи F 5 і F 6 .