Метод дихотомії (поділу навпіл)

В даному випадку загальна кількість обчислень f (x) парна, тобто N = 2 l, l = 1, 2, …, на j -му кроці (j -й ітерації) проводиться пара обчислень  та  віддалених на відстань ε / 2 по обидві сторони від середини поточного відрізка локалізації . Якщо  то відкидається частина відрізку, справа від . Якщо  то відкидається частина відрізку, справа від .

Використовують дві умови завершення обчислень:

а) виконання заданої кількості обчислень N;

б) досягнення заданої величини δ зменшення відрізку локалізації.

Алгоритм пошуку мінімуму методом дихотомії полягає в наступному.

1. Задаються N (або δ) та ε, приймається j =1.

2. На j -й ітерації обчислюються

, .

Якщо , то , .

Якщо , то , .

3. Перевіряється умова завершення обчислень:

а)   або б) .

Якщо вона виконується, то визначається результуючий відрізок локалізації, оцінки точки мінімуму x * та величини мінімуму         f *= f (x *), та обчислення завершуються.

Якщо умова не виконується, то приймається j = j +1 та перехід до п.2.

Для визначення оцінки точки мінімуму необхідно розглянути всі досліджені точки результуючого відрізку локалізації та обрати одну з них, для якої значення функції буде мінімальним.

 

Метод Фібоначчі

Найкращий з точки зору зменшення відрізку локалізації.

На першому кроці проводять два обчислення значень f (x) в точках  та  (причому ), розташованих симетрично відносно середини відрізку Δ₀ = [ a, b ]. За результатами обчислень одна з частин відрізку ([ a, ] або [ , b ]) відкидається, при цьому одна з точок (відповідно  або ) вже перевірених обчислень залишається всередині відрізку Δ₂ ≡ Δ⁽¹⁾. На кожному наступному кроці (наступній ітерації) точка чергового обчислення обирається симетрично точки, що залишилась. Таким чином, на першій ітерації проводяться два обчислення значень f (x), на кожній наступній − одне обчислення. Тому при заданій кількості обчислень N буде виконано N −1 кроків (ітерацій).

При обчисленні  та , , використовуються числа Фібоначчі, які визначаються наступним чином:

F ₀ = F ₁ =1, F_k = F_k −1 + F_k −2, k = 2, 3,....

Умовою завершення обчислень є виконання заданої кількості обчислень N.

Алгоритм пошуку мінімуму унімодальної функції методом Фібоначчі полягає в наступному.

1. Задається N, визначаються числа Фібоначчі F_k, , обирається ε з умови .

Приймається j =1.

2. На j -й ітерації обчислюються

,

,

, .

Якщо , то , , .

Якщо , то , , .

3. Перевіряється умова завершення обчислень j = N −1.

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

Якщо умова не виконується, то приймається j = j +1 та перехід до п.2.

Примітка. На j -й, j > 1, ітерації обчислюється тільки та точка x_i ^(j), i =1, 2, яка не була визначена на попередній ітерації.

Оцінкою точки мінімуму x * є та з точок x_i ^(N-1), i =1, 2, яка залишилась всередині результуючого відрізку локалізації Δ N.

Приклад. Визначити методом Фібоначчі мінімум функції f (x) = x ⁴ − 6 x ² +10, заданої на відрізку Δ=[1,3], при N =4.

Рішення. В даному випадку будуть виконані N −1 = 3 ітерації. Визначаємо числа Фібоначчі F_k, : 

F ₀ = F ₁ =1, F₂ = 2, F₃ = 3, F₄ = 5, F₅ = 8.

.

Обираємо e=0,1.Результати обчислень записуємо в табл. 2.3.

Перша ітерація.

Друга ітерація.

Третя ітерація.

Таблиця 2. 3

Номер ітерації	x 1^(j)	x 2^(j)	f 1^(j)	£ >	f 2^(j)	a ^(j)	b ^(j)
0	–	–	–		–	1	3
1	1,78*	2,22*	1,028	<	4,719	1	2,22
2	1,44*	1,78	1,858	>	1,028	1,44	2,22
3	1,78	1,88*	1,028	<	1,286	1,44	1,88

Примітка. Знаком * відмічаємо точки x_i ^(j), i =1, 2, що обчислюються на j -й ітерації.

Оскільки j = N −1=3, то обчислення завершуються. Точка мінімуму локалізована на відрізку Δ₄ = [1,44; 1,88], x *» x ₁⁽³⁾= 1,028.

Метод золотого перетину

Недоліком найбільш ефективного методу Фібоначчі є то, що необхідно задавати кількість обчислень N. Метод золотого перетину близький за ефективністю, до методу Фібоначчі, але при цьому не залежить від N. Алгоритм пошуку за методом золотого перетину   визначається тем же правилом симетрії, що і алгоритм за методом Фібоначчі: на першій ітерації обираються дві точки, розташовані симетрично відносно середини відрізку; на кожній наступній ітерації обирається одна точка, розташована симетрично до точки, що залишилась. Різниця полягає у виборі точок. Метод золотого перетину  заснований на поділі відрізку локалізації «золотим перерізом», тобто коли відношення більшої частини відрізку до всього відрізку дорівнює відношенню меншої частини до більшої.

.

При такому поділі використовують два дроби Фібоначчі

, ,

які задовольняють умовам , .

При оптимізації методом золотого перетину використовуються дві умови завершення обчислень:

а) виконання заданої кількості обчислень N,

б) досягнення заданої величини δ зменшення відрізку локалізації.

Алгоритм пошуку мінімуму унімодальної функції методом золотого перетину полягає в наступному.

1. Задається N (або δ), приймається j =1.

2. На j -й ітерації обчислюються

, ,

, .

Якщо , то , , .

Якщо , то , , .

3. Перевіряється умова завершення обчислень:

а)     або б) .

Якщо вона виконується, то визначається результуючий відрізок локалізації точки мінімуму x ∗ та величини мінімуму f * і обчислення завершуються.

Якщо умова не виконується, то приймається j = j +1 та перехід       до п.2.

Порядок виконання роботи

2.1. Відповідно до варіанту за П. 1.1–1.3 знайти мінімум функції одним з чисельних методів оптимізації. Дані взяти з табл. 2.4.

2.2. Побудувати графік функції з табл. 2.4 поблизу точки екстремуму.

3. Звіт має містити результати розрахунків по П. 2.1, графіки функції поблизу точки екстремуму, висновки по роботі.

Варіанти

Таблиця 2. 4

№ вар.	Функція f (x)	Значення x	N	e	Метод оптимізації
1.	x ^2– 3 x + 2	[0;4]	8	0,1	метод дихотомії
2.	x ^2– 3 x + 2	[0;4]	4	0,1	метод золотого перетину
3.	x ^2– 3 x + 2	[0;4]	4	0,2	метод Фібоначчі
4.	x ^2– 4 x + 3	[0;3]	12	0,1	метод дихотомії
5.	x ^2– 4 x + 3	[1;5]	4	0,1	метод золотого перетину
6.	x ^2– 4 x + 3	[0;4]	4	0,2	метод Фібоначчі
7.	x ^4– 6 x ^2+ 10	[1;3]	8	0,1	метод дихотомії
8.	x ^4– 6 x ^2+ 10	[1;3]	4	0,1	метод Фібоначчі
9.	x ^4– 6 x ^2+ 10	[1;3]	4	0,1	метод золотого перетину
10.	x ^2– 4 x + 3	[0;4]	8	0,1	метод дихотомії

Контрольні питання

1.Пояснить суть оптимізації методом дихотомії.

2.Розкрити суть оптимізації методом Фібоначчі.

3.Розкрити суть оптимізації методом золотого перетину.

4.Назвати умови застосування розглянутих методів оптимізації.

Лабораторна робота № 2.3