2.2. Методи поліноміальної апроксимації

2.2.1. Основний зміст методу

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

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

Якщо цільова функція в точках x₁, x₂, x₃ приймає відповідні значення F₁, F₂, F₃, то можна визначити коефіцієнти а0, a1, a2 таким чином, що значення квадратичної функції

q(х) = a0 + a1(x-x1) + a2(x-x1)(x-x2) співпадуть зі значенням F(х) в трьох вказаних точках. (див. Табл.1).

Обчислення значень. Таблиця 1

F1 = F(x1) = q(x1) = ao	ao = F1,
F2 = F(x2) = q(x2) = F1 + a1(x2 - x1)	a1 =(F2 - F1)/(x2 - x1),
F3 =q(x3) = F1 + [(F2 - F1) (x3 - x1)]/ /(x2 - x1) + a2(x3 - x1) (x3 - 2)	,
.	.

2.2.2. Метод Пауела

Якщо відомі значення функції f(х) в трьох різних точках  відповідно f_,, f_, f_,, то функція f(х) може бути апроксимована квадратичною функцією

f(х)=Ax²+Bx+C,

де: А, В і C визначаються з рівнянь

A²+B+C=f_ , A²+B+C=f_ , A²+B+C=f_ .

Після перетворень цих рівнянь отримуємо

.

Крок 1. x2 = x1 + D х.

Крок 2. Обчислити F(x1) і F(x2).

Крок 3. Якщо F(x1) > F(x2), то x3 = x1 + 2 D х.

• Якщо F(x1)< F(x2), то x3 = x1 - D х.

Крок 4. Обчислити F(x3) і знайти

• Fmin = min{ F(x1), F(x2), F(x3)},

• Xmin = xi, відповідна Fmin.

Крок 5. По x1, x2, x3 обчислити х*, використовуючи формулу для оцінки з допомогою квадратичної апроксимації (порядок обчислення х* наведено на попередній сторінці).

Крок 6. Перевірка закінчення.

• Якщо |Fmin - F(х*)| < , то закінчити пошук.У іншому випадку перехід до кроку 7.

• Якщо |Xmin - х*| < , то закінчити пошук. У іншому випадку перехід до кроку 7.

Крок 7. Вибрати Xmin або х* і дві точки по обидві сторони від неї. Визначити в природному порядку (тобто розмістити ці точки по зростанню) нові значення x1, x2, x3 і перейти до кроку 4

2.3. Методи з використанням похідних

2.3.1. Метод Ньютона-Рафсона

В рамках схеми Ньютона-Рафсона передбачається, що функція f двічі диференційована. Робота алгоритму починається в точці x_k, яка представляє початкове наближення (чи початкову оцінку) координати стаціонарної точки, або кореня рівняння f'(х)=0. Потім будується лінійна апроксимація функції f'(х) в точці x_k, і точка, в якій апроксимуюча лінійна функція рівна нулю, приймається як наступне наближення.

Рис.1. Метод Ньютона-Рафсона ( збіжність)

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

.

Прирівнявши праву частину рівняння до нуля, отримаємо наступне наближення:

.

Рис.1 ілюструє основні кроки реалізації методу Ньютона. На жаль, в залежності від вибору початкової точки і вигляду функції алгоритм може як збігатися до справжньої стаціонарної точки, так і розбігатися, що відображено на рис. 2. Якщо точка розташована правіше за х₀, то ті x_i, що отримуються внаслідок послідовних наближень точки, віддаляються від стаціонарної точки z.

Рис.2. Метод Ньютона-Рафсона (відсутність збіжності)