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

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

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

,

які розміщені симетрично відносно середини відрізку, причому .

Відзначимо також, що точка в свою чергу будує золотий перетин відрізку , так як = .

Аналогічно точка будує золотий перетин відрізка . Спираючись на цю властивість золотого перетину, опишемо відповідний метод.

Покладемо , . На відрізку візьмемо точки , , які будують золотий перетин, і обчислимо значення , . Далі, якщо , то покладемо , , ; якщо ж , то покладемо , , . Так як функція унімодальна на , то відрізок має хоча б одну спільну точку з множиною точок мінімуму на [a, b]. Крім того, , а та-кож належить відрізку . В цій точці відоме значення

і вона будує золотий перетин відрізка .

Припустимо, що все відомі точки , , , обчислені значення , , , знайдено відрізок такий, що

,

,

і відома точка , яка будує золотий перетин відрізка і така що

.

Тоді в якості наступної точки візьмемо точку

,

яка також будує золотий перетин відрізка , обчислимо значення .

Нехай для визначенності (випадок < u розглядається аналогічно). Якщо , то покладемо

, ,

якщо ж , то покладемо

, , .

Новий відрізок такий, що

,

точка будує золотий перетин відрізка і

.

Якщо кількість обчислень значень наперед не обмежена, то цей процес можна продовжувати, наприклад, до тієї пори, поки не виконається нерівність , де - задана точність. Якщо ж кількість обчислень значень наперед чітко задана і дорівнює n, по процес на цьому закінчується і в якості розв’язку задачі другого типу можна вважати пару , де є наближенням для , а також служить наближенням для множини з похибкою

.

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

;

Методом математичної індукції легко показати ще n-е число Фібоначчі можна записати в вигляді:

(4)

Використовуючи числа побудуємо n -точковий послідовний метод, який називається методом Фібоначчі. Цей метод відноситься до класу симетричних методів і визначається заданням на відрізку симетричних точок

,

.

Методом математичної індукції неважко довести, що коли проведені обчислення значень функції в точках , то мінімум буде локалізовано на відрізку , який має довжину

причому точка з обчисленним значенням співпадає однією з точок

(5)

які розміщені на відрізку симетрично відносно його середини.

Як видно з (5), при точки співпадають. Це означає, що при перша частина процесу закінчується обчисленням значення функції в точці та визначенням відрізка локалізації мінімуму довжини _, причому точка співпадає з серединою відрізка ,

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

Цей метод будемо позначати через .

Мінімізація функцій однієї змінної. (Z=20)

Номер варіанту обчислюється як ((N_сп-1) mod Z) + 1, де N_сп - Ваш номер у журнальному списку.

1. Виберіть функцію з наведеної нижче таблиці, побудуйте її графік засобами MatLab'а (або Excel) в розумному діапазоні для пошуку точок її екстремумів (найбільшого й найменшого значень) із заданою точністю.

2. Для обраної функції знайдіть оптимальне значення методом половинного поділу, методом золотого перетину та методом чисел Фібоначі, попередньо визначивши відрізок локалізації мінімуму. Для кожного методу слід визначити: - кількість виконаних ітерацій, - кількісь обчислень значень цільвої функції, -наближене значення точки оптимуму, - наближене значення оптимуму цільової функції. Одержані результати подати у вигляді таблиці і порівняти їх:

№	Назва методу
	Половинного поділу
	Золотого перерізу
	Фібоначчі

№	Функція

Дата добавления: 2015-07-02