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

Недоліком найбільш ефективного методу Фібоначчі є то, що необхідно задавати кількість обчислень 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.4 поблизу точки екстремуму.

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

4. Варіанти

Таблиця 2.4

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

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

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

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

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

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