Методи полиномиальной апроксимації - студопедія
У методах прямого пошуку ми не мали жодної інформації про функції, що мінімізується за винятком її значень в обраних нами точках і припущення, що вона неперервна і є унімодальної функцією на даному відрізку. Якщо функцію в деякому околі точки її мінімуму можна досить точно замінити (апроксимувати) многочленом, то для її мінімізації доцільно використовувати так звані методи поліноміальної апроксимації. Їх загальна особливість полягає в обчисленні коефіцієнтів многочлена за відомими значеннями функції в окремих точках і подальшому перебуванні мінімуму цього многочлена з використанням необхідних і достатніх умов екстремуму. Обмежимося розглядом методу квадратичної апроксимації функції, що мінімізується f (x), в якому графік цієї функції наближено замінюють параболою, що проходить через три відомі точки [х i. fi), i = 1, 2, 3, де fi = f (xi).
Відомо ..., що через три різні точки, що не лежать на одній прямій, можна провести тільки одну параболу у = ах 2 + b х + с. a ≠ 0. Коефіцієнти а. b. з задовольняють системі лінійних алгебраїчних рівнянь (СЛАР)
Визначник цієї СЛАР
є визначник Вандермонда і відрізняється від нуля, коли х 1, х 2, х 3попарно різні. В цьому випадку СЛАР має рішення, і до того ж єдине. Його можна записати у вигляді
Якщо знайдені вирази для коефіцієнтів а і b підставити в необхідна умова у '= 2ах + b = 0 екстремуму функції, то отримаємо її єдину стаціонарну точку
де і sij = xi- xj. i. j = 1, 2, 3. Так як у "= 2а = const. то в точці при а> 0 маємо мінімум функції у (х), а при a <0 — максимум.
Якщо відомий відрізок, на якому мінімізується функція унімодальне, то немає необхідності обчислювати значення коефіцієнта а. Досить цей відрізок прийняти в якості відрізка [x 1, x 3], а точку х 2∈ (x 1, x 3) вибрати довільно в інтервалі (x 1, x 3). У цьому випадку маємо f 1≥ f 2и f 3≥ f 2, звідки
На першому кроці методу квадратичної апроксимації за допомогою (2.18) обчислюють і потім Для обчислень на другому кроці з чотирьох точок і xi. i = 1, 2, 3, вибирають нову трійку точок за таким правилом:
Далі з (2.18) знаходять а потім описану процедуру повторюють на третьому кроці і так далі до тих пір, поки довжина інтервалу невизначеності. в якому гарантовано лежить шукана точка x * мінімуму функції f (x), не стане менше заданого найбільшого допустимого значення # 949; *. Відзначимо, що підтвердженням наближення до точки x * і правильності обчислень може служити зменшення значення функції у (x) в знайденої точці в порівнянні із значенням на попередньому кроці.
Приклад 2.5. Застосуємо описану модифікацію методу квадратичної апроксимації для знаходження мінімуму функції
на відрізку [2, 8]. Графік цієї функції наведено на рис. 2.12. Процес ітерацій закінчимо, якщо довжина інтервалу невизначеності не перевищуватиме 0.15. На першому кроці виберемо Результати обчислень з урахуванням (2.19) зведені в табл. 2.6.
Після виконання п'ятого кроку приходимо до висновку, що точка х * мінімуму функції f (x) розташована в інтервалі (2,949, 3,076) довжини 0,127. Точне значення х * = 3 відповідає мінімальному значенню f (x *) = 0.