Поліноміальна апроксимація

Використання методів виключення інтервалів, що розглядалися у попередньому підрозділі, накладає єдину вимогу до досліджуваної функції: вона повинна бути унімодальною. При цьому вказані методи можна використовувати для аналізу як неперервних, так і перервних функцій, а також у випадках, коли змінні приймають дискретні значення. Структура пошуку методами виключення інтервалів базується на простому порівнянні значень функції у двох пробних точках. Крім того, при такому порівнянні до розрахунку приймається тільки відношення порядку на множині значень функції і не враховується величина різниці між значеннями функції.

У даному підрозділі розглядаються методи пошуку, що дозволяють врахувати відносні зміни значень функції і як наслідок у ряді випадків є ефективнішими, ніж методи виключення інтервалів. Однак, виграш по ефективністю досягається за рахунок введення додаткової вимоги – функ­ції повинні бути достатньо гладкими.

Основна ідея методів пов’язана з можливістю апроксимації гладкої функції поліномом та наступного використання поліному апроксимації для оцінювання координати точки оптимуму. Необхідними умовами ефективної реалізації такого підходу є унімодальність та неперервність функції, що досліджується. Відповідно до теореми Вейєрштраса [3], якщо функція неперервна на деякому інтервалі, то її з будь-яким ступенем точності можна апроксимувати поліномом достатньо високого порядку.

Таким чином, якщо функція унімодальна і знайдено поліном, який достатньо точно її апроксимує, то координату точки оптимуму функції можна оцінювати шляхом обчислення координати точки оптимуму полінома. Відповідно до теореми Вейєрштраса, якість оцінювання координати точки оптимуму, які отримуються за допомогою полінома апроксимації можна підвищити двома способами: використанням полінома більш високого порядку та звуженням інтервалу апроксимації. Другий спосіб взагалі кращий, оскільки побудова полінома апроксимації вище третього порядку є надто складною процедурою.

Найпростішим варіантом є квадратична апроксимація, яка основана на тому факті, що функція, яка має мінімум на деякому інтервалі, повинна бути хоча б квадратичною. Таким чином, під час реалізації методу оцінювання з використанням квадратичної апроксимації припускається, що в обмеженому інтервалі можна апроксимувати функцію квадратичним поліномом, а потім використовувати побудовану схему для оцінювання координати дійсного мінімуму функції.

Якщо задана послідовність точок x₁, x₂, x₃, і відомі відповідні цим точкам значення функції f₁, f₂, f₃, то можна визначити постійні величини a₀, a₁ і a₂ таким чином, що значення квадратичної функції

q (x) = a₀ + a₁ (x-x₁) + a₂ (x-x₁)(x-x₂)

збіжуться зі значеннями f (x) у трьох вказаних точках. Перейдемо до обчислення q (x) в кожній із трьох заданих точок. По-перше, оскільки f₁= = f (x₁) =q (x₁) = a₀, маємо a₀=f₁. Далі, оскільки f₂= f (x₂) =q (x₂) = f₁+a₁ (x₂ - x₁), розв’язуючи дане рівняння отримаємо коефіцієнт a₁= (f₂- f₁)/(x₂ - x₁).

Якщо x = x₃

f₃= f (x₃) =q (x₃) = f₁ + (f₂- f₁)/(x₂ - x₁) (x₃ - x₁) + a₂ (x₃ - x₁) (x₃ - x₂).

Так само розв’язавши останнє рівняння щодо a₂, отримаємо значення

Таким чином, за трьома заданими точками та відповідними значеннями функції можна оцінити параметри a₀, a₁ і a₂ за допомогою наведених вище формул квадратичного полінома апроксимації. Якщо точність апроксимації досліджуваної функції в інтервалі від x₁ до x₃ за допомогою квадратичного полінома є достатньо високою, то побудований поліном можна використовувати для оцінювання координати точки оптимуму. При цьому, нагадаємо, що стаціонарні точки функції однієї змінної визначаються шляхом прирівнювання до нуля її першої похідної і знаходження коренів отриманого таким чином рівняння. В даному випадку з рівняння

можнa отримати c= (x₂+x₁) /2 - (a₁ /2a₂).

Оскільки функція f (x) на розглянутому інтервалі має властивість унімодальності, а квадратичний поліном апроксимації є також унімодальною функцією, то можна очікувати, що величина c буде придатним оцінюванням координати точки дійсного оптимуму x*.

Приклад 5.4. Розглянемо процедуру оцінювання координати точки мінімуму функції f(x) = 2x² +(16/x) на інтервалі 1£ x£ 5. Нехай x₁=1, x₃=5, a x₂ є середньою точкою інтервалу, тобто x₁=3. Обчислимо відповідні значення функції: f₁=18, f₂= 23,33, f₃=53,2.

Для того, щоб оцінити c, необхідно знайти значення параметрів a₁ і а₂ функції апроксимації. Маємо

Підстановка цих значень у формулу для c дозволяє отримати: x = = (3+1)/2 - (8/3)/[2(46/15)]=1,565. Точний мінімум досягається при x* = = 1,5874.