="justify"> (5)
З рівняння (2) випливає, що 1=2. Звідси і з (5) випливає справедливість (4). Аналогічно проводиться доказ для випадку f () gt; f ().
Зазначене властивість алгоритму золотого перетину дозволяє на кожній ітерації (крім першої) виробляти випробування тільки в одній точці.
Затвердження 3.
В результаті однієї ітерації алгоритму золотого перетину довжина поточного інтервалу невизначеності скорочується в раз.
Тому кількість ітерацій N, необхідних для знаходження мінімуму функції з точністю x, знаходиться з умови x? (b - a) N
2.2 Метод квадратичної параболи
Метод квадратичної апроксимації відноситься до сімейства методів поліноміальної апроксимації. Ідея методу поліноміальної апроксимації полягає в тому, що в деякій околиці мінімуму функції f (x) вона апроксимується поліномом досить високого порядку і в якості точки мінімуму функції f (x) (або в якості чергового наближення до цієї точки) приймається точка мінімуму аппроксимирующего полінома. В силу того, що апроксимуюча функція є поліномом, цей мінімум знаходиться легко. Як апроксимуючі поліномів найчастіше використовуються поліноми другого і третього порядків, тобто квадратична і кубічна апроксимації.
Розглянемо квадратичну апроксимацію (рис. 4). Нехай у процесі вирішення задачі пошуку мінімуму функції f (x) тим чи іншим чином отримані попарно що не збігаються точки x 1, x 2, x 3, що належать області допустимих значень D (не обов'язково впорядковані зліва направо).
Рис. 4. Квадратична апроксимація
Побудуємо квадратичну функцію
y=ax 2 + bx + c, (6)
проходить через точки (xi, fi), i=1,2,3, де fi=f (xi).
Коефіцієнти a, b, c функції (6) задовольняють системі лінійних алгебраїчних рівнянь (СЛАР)
(7)
Визначник СЛАР (7) є визначником Вандермонда, який відмінний від нуля, якщо величини x 1, x 2, x 3 попарно різні.
Таким чином, в зроблених припущеннях СЛАР (7) має рішення і притому єдине. Оскільки визначник СЛАР (7) дорівнює), це рішення має вигляд:
Підставами знайдені значення коефіцієнтів a, b, c в необхідна умова y=2ax + b=0 мінімуму квадратичної функції (6), отримаємо стаціонарну точку цієї функції:
(8)
де.
Метод квадратичної апроксимації.
Розглянемо наступну задачу умовної оптимізації: знайти мінімум одновимірної унімодальної функції f (x), визначеної в замкнутій області допустимих значень D=[a, b],
(9)
Метод квадратичної апроксимації відноситься до класу методів скорочення поточного інтервалу невизначеності. Нехай при вирішенні задачі (8) будь-яким методом отримані три точки x 1 lt; x 2 lt; x 3, що належать області допустимих значень, такі, що f (x 1) gt; f (x 2) lt; f (x 3).
Схема методу квадратичної апроксимації:
. Виконуємо присвоювання
r=1
x 1
2
3
ТІН r=[,]
. Обчислюємо значення функції f (x) в точках,, відповідно.
. За формулою (8) обчислюємо величину r і знаходимо значення функції f (x) в цій точці r=f (r)
. Знаходимо наступні три точки:
випадок (а) - якщо r [,], то =,=r,=(рис. 5а);
випадок (б) - якщо r [,], то =,=r,=(рис. 5б).
. В якості наступного поточного інтервалу невизначеності приймаємо
ТІН r + 1=[,].
. Якщо, то закінчуємо обчислення. Інакше - виконуємо присвоювання r=r + 1 і переходимо на п.2. Тут - необхідна точність рішення.
Рис. 5. Метод квадратичної апроксимації:
В якості наближеного значення точки мінімуму x * з рівними підставами може бути прийнята будь-яка точка останнього поточного інтервалу невизначеності.
Зауваження.
У силу умов, точка r завжди належить поточним інтервалу невизначеності ТІН r=[].
Текст програми методу квадратичної параболи розміщений в Додатку 1. Блок-схема алгоритму представлена ??в Додатку 2.
3. Отримані результати
