5.3 Поліноміальна апроксимація
Використання методів виключення інтервалів, що розглядалися у попередньому підрозділі, накладає єдину вимогу до досліджуваної функції: вона повинна бути унімодальною. При цьому вказані методи можна використовувати для аналізу як неперервних так і перервних функцій, а також у випадках, коли змінні приймають значення з дискретної множини. Логічна структура пошуку за допомогою методів виключення інтервалів базується на простому порівнянні значень функції у двох пробних точках. Крім того, при такому порівнянні до розрахунку приймається тільки відношення порядку на множині значень функції і не враховується величина різниці між значеннями функції.
У даному підрозділі розглядаються методи пошуку, що дозволяють врахувати відносні зміни значень функції і як наслідок у ряді випадків є більш ефективними, ніж методи виключення інтервалів. Але виграш по ефективності досягається за рахунок введення додаткової вимоги, відповідно якої функції повинні бути достатньо гладкими.
Основна ідея методів пов’язана з можливістю апроксимації гладкої функції поліномом та послідуючого використання поліному апроксимації для оцінювання координати точки оптимуму. Необхідними умовами ефективної реалізації такого підходу є унімодальність та неперервність функції, що досліджується. Відповідно до теореми Вейєрштраса [3], якщо функція неперервна на деякому інтервалі, то її з будь-яким ступенем точності можна апроксимувати поліномом достатньо високого порядку.
Таким чином, якщо функція унімодальна і знайдено поліном, який достатньо точно її апроксимує, то координату точки оптимуму функції можна оцінювати шляхом обчислення координати точки оптимуму поліному. Відповідно до теореми Вейєрштраса, якість оцінювання координати точки оптимуму, які отримуються за допомогою поліному апроксимації можна підвищити двома способами: використанням поліному більш високого порядку та звуженням інтервалу апроксимації.
Другий спосіб взагалі кращий, оскільки побудова поліному апроксимації вище третього порядку є надто складною процедурою.
Найпростішим варіантом поліноміальної інтерполяції є квадратична апроксимація, що заснована на тому факті, що функція, що має мінімум на деякому інтервалі, повинна бути хоча б квадратичною. Таким чином, під час реалізації методу оцінювання з використанням квадратичної апроксимації припускається, що в обмеженому інтервалі можна апроксимувати функцію квадратичним поліномом, а потім використовувати побудовану схему для оцінювання координати дійсного мінімуму функції.
Якщо задана послідовність точок x1, x2, x3, і відомі відповідні цим точкам значення функції f1, f2, f3, то можна визначити постійні величини a0, a1 і a2 таким чином, що значення квадратичної функції
q(x)= a0 + a1(x-x1) + a2(x-x1)(x-x2)
співпадуть зі значеннями f(x) у трьох вказаних точках. Перейдемо до обчислення q(x) в кожній із трьох заданих точок. По-перше, так як f1= f(x1)=q(x1)= a0 , маємо a0=f1. Далі, оскільки f2= f(x2)=q(x2)= f1+a1 (x2 - x1), розв’язуючи дане рівняння отримаємо коефіцієнт a1=(f2- f1)/(x2 - x1).
Якщо x = x3
f3= f(x3)=q(x3)= f1 + (f2- f1)/(x2 - x1) (x3 - x1) + a2(x3 - x1) (x3 - x2).
Так само розв’язавши останнє рівняння щодо a2, отримаємо значення
Таким чином, по трьох заданих точках та відповідних значеннях функції можна оцінити параметри a0, a1 і a2 за допомогою наведених вище формул квадратичного поліному апроксимації.
Якщо точність апроксимації досліджуваної функції у інтервалі від x1 до x3 за допомогою квадратичного поліному є достатньо високою то відповідно даної стратегії пошуку побудований поліном можна використовувати для оцінювання координати точки оптимуму. При цьому нагадаємо, що стаціонарні точки функції однієї змінної визначаються шляхом прирівнювання до нуля її першої похідної і знаходження коренів отриманого таким чином рівняння. В даному випадку з рівняння
можнa отримати = (x2+x1)/2 - (a1 /2a2).
Оскільки функція f(x) на розглянутому інтервалі має властивість унімодальності, а квадратичний поліном апроксимації є також унімодальною функцією, то можна очікувати, що величина буде придатним оцінюванням координати точки дійсного оптимуму x* .
Приклад 5.4. Розглянемо процедуру оцінювання координати точки мінімуму функції f(x) = 2x2 +(16/x) на інтервалі 1 x 5. Нехай x1=1, x3=5, a x2 є середньою точкою інтервалу, тобто x1=3. Обчислимо відповідні значення функції: f1=18, f2= 23,33, f3=53,2.
Для того, щоб оцінити , необхідно знайти значення параметрів a1 і а2 функції апроксимації. Маємо
Підстановка цих значень у формулу для дозволяє отримати: x = (3+1)/2 - (8/3)/[2(46/15)]=1,565. Точний мінімум досягається при x*=1,5874.
Метод послідовного оцінювання з використанням квадратичної апроксимації. Цей метод, який був розроблений Пауеллом, заснований на послідовному використовуванні процедури оцінювання за допомогою квадратичної апроксимації. Схема алгоритму описується таким чином. Нехай x1 - початкова точка, x - обрана величина кроку по вісі x.
Крок 1. Обчислити x2= x1+x.
Крок 2. Обчислити f(x1) та f(x2).
Крок 3. Якщо f(x1)>f(x2), то x3= x1+2x. Якщо f(x1) f(x2), то x3= x1-x.
Крок 4. Обчислити f(x) та знайти
Fмін=min{ f1, f2, f3 } , Xмін = точка xi , яка є Fмін .
Крок 5. За трьома точками x1, x2, x3 обчислити .
Крок 6. Перевірка щодо закінчення пошуку.
а) Різність Fмін - f() досить мала?
б) Різність Xмін - досить мала?
Якщо обидві вимоги виконуються, закінчити пошук. В протилежному випадку перейти до кроку 7.
Крок 7. Обрати "найкращу" точку (хмін або ) та дві точки по обидва боки від неї. Позначити ці точки у природному порядку та перейти до кроку 4.
Відзначимо, що під час першої реалізації кроку 5 границі інтервалу, який має точку мінімуму, не обов'язково встановлюються. При цьому отримана точка може знаходитися за точкою x3. Для того, щоб виключити можливість дуже великого екстраполяційного пересування, слід провести після кроку 5 додаткову перевірку і у випадку, коли точка знаходиться дуже далеко від x3, замінимо точкою, координата якої обчисляється з урахуванням встановленої раніше довжини кроку.
Приклад 5.5. Мінімізувати функцію f(x)=2x2+(16/x).
Нехай початкова точка x1=1 і довжина кроку x=1. Для перевірки відносно закінчення пошуку використовуються такі параметри збіжності:
Ітерація 1
Крок 1. x2= x1+x=2 .
Крок 2. f(x1)=18, f(x2)=16 .
Крок 3. f(x1)>f(x2), тобто слід покласти, що x3=1+2=3 .
Крок 4. f(x3)=23,33, Fмін=16, Xмін= x2.
Крок 5.
Крок 6. Перевірка щодо закінчення пошуку:
Таким чином, продовжуємо пошук.
Крок 7. Обираємо як "найкращу" точку, а x1=1 та x2=2 - як точки, що її оточують. Позначимо ці точки у природному порядку і перейдемо до ітерації 2, яка починається з кроку 4.
Ітерація 2.
Крок 4. x1=1, f1=18, x2= 1,714, f2=15,210=Fмін , Xмін= x2, x3=2, f3=16 .
Крок 5.
Крок 6. Перевірка щодо закінчення пошуку:
Крок 7. Обираємо як "найкращу" точку, а x1=1 та x2=1,714 - як точки, що її оточують.
Ітерація 3.
Крок 4. x1=1, f1=18, x2= 1,65 , f2=15,142=Fмін ,
Xмін= x2, x3=1,174, f3=15,210 .
Крок 5.
Крок 6. Перевірка щодо закінчення пошуку:
(a)
(б)
Таким чином, пошук закінчено.