і чергового наближення x k + 1 вибирають точку перетину з віссю абсцис січною до графіка функції f (x).
Цей метод має сверхлінейную швидкість збіжності. Модифікації методу Ньютона володіють тільки локальної збіжністю, тобто сходяться, якщо початкова точка обрана в деякій околиці точки мінімуму функції. Якщо ж початкова точка розташована занадто далеко від точки мінімуму, то подібний метод може розходитися або «зациклюватися». На відміну від методу середньої точки метод січних використовує інформацію не тільки про знак похідної, а й про значеннях у пробних точках.
Метод кубічної апроксимації
У методах поліноміальної апроксимації при побудові многочлена, аппроксимирующего мінімізіруемую функцію в околиці шуканої точки х * мінімуму, крім значень функції в окремих точках можуть бути використані і значення її похідних.
Нехай для безперервно диференціюється функції f (x), строго опуклою на відрізку [x 1, x 2], відомі значення y 1=f (x 1), y 2=f (x 2) функції і значення її похідної y 11=f (x 1), y 12=f (x 2). Якщо y 11 * y 12 lt; 0, то розглянута функція строго унімодального на цьому відрізку.
За умови y 11 * y 12 lt; 0 на відрізку [х 1, х 2] можна побудувати єдиний многочлен третього ступеня, розташовуючи значеннями функції і похідних на кінцях цього відрізка. Цей многочлен називається кубічним інтерполяційним многочленом Ерміта.
2. Детальний опис використовуваних методів
2.1 Метод золотого перетину
перетин апроксимація ньютон похідна
Розглянемо наступну задачу умовної оптимізації: знайти мінімум одновимірної унімодальної функції f (x), визначеної в замкнутій області допустимих значень D=[a, b],
Властивості золотого перетину:
Розглянемо інтервал [a, b] (рис. 2). Кажуть, що точка c виконує золотий перетин інтервалу [a, b], якщо:
(1)
де 0,618- рішення квадратного рівняння:
2 + - 1=0 (2)
Рис. 2. Золотий перетин відрізка.
З визначення золотого перетину випливає, що.
Дійсно,
Алгоритм золотого перетину.
Алгоритм золотого перетину відноситься до класу послідовних методів пошуку.
. Виконуємо присвоювання:
r=1, a 1=a, b 1=b,
ТІН 1=[a 1, b 1].
. Обчислюємо величини (Рис. 3)
, (3)
3. Обчислюємо значення f (), f () функції f (x).
. Якщо f () lt; f (), то виконуємо присвоювання:
a r + 1=a r, b r + 1 =,
ТІН r + 1=[a r + 1, b r + 1]
Інакше - виконуємо присвоювання
a r + 1 =, b r + 1=r,
ТІН r + 1=[a r + 1, b r + 1].
5. Якщо, то закінчуємо обчислення. Інакше - виконуємо присвоювання r=r + 1 і переходимо на п.2. Тут - необхідна точність рішення
.
Рис. 3. Визначення величин,
В якості наближеного значення точки мінімуму x * з рівними підставами може бути прийнята будь-яка точка останнього поточного інтервалу невизначеності.
Деякі властивості алгоритму золотого перетину:
Твердження 1.
Точки, розташовані симетрично щодо решт поточного інтервалу невизначеності.
Дійсно, з (3) випливає, що точка відстоїть від точки br на величину (br -ar); точка відстоїть від точки ar на ту ж величину.
Твердження 2.
Для будь-якого r? 1 алгоритм золотого перетину має наступну властивість: одна з точок, збігається з однією з точок,.
Доказ.
Нехай на r-й ітерації f () lt; f (). Відповідно до алгоритму золотого перетину ТІН r + 1=[ar,] причому, очевидно, ТІН r + 1. Для того, щоб довести справедливість твердження досить показати, що вірно ставлення:
(4)
Зі співвідношень (3) випливає, що
(br -)=(br - ar)
br - - ar + ar=(br - ar)
(br - ar) - (-ar)=(br - ar)
- ar=(br - ar) (1)
- a r=(b r - a r)
Розділивши перший з цих результатів на другий, отримаємо
