Главная | Обратная связь | Поможем написать вашу работу!

Метод золотого перерізу.

Р О З Д І Л 1

МЕТОДИ МІНІМІЗАЦІЇ ФУНКЦІЇ ОДНІЄЇ ЗМІННОЇ.

Постановка задачі.

Нехай - числова вісь, – деяка множина з , – функція, визначена на . Розглянемо задачу мінімізації функції на множині . Спочатку нагадаємо деякі означення з класичного математичного аналізу.

Означення 1. Точку називають точкою мінімуму функції на множині , якщо для будь-яких . Величину називають найменшим або мінімальним значенням на і позначають . Множину всіх точок мінімуму на позначатимемо . Так визначена точка мінімуму є, більш точно, точкою глобального мінімуму або точкою абсолютного мінімуму

Означення 2. Точка називається точкою локального мінімуму функції на множині , якщо існує число таке, що для будь-яких

В залежності від властивостей множини і функції множина може містити одну, декілька, нескінченно багато точок, а також можливі випадки, коли .

Приклад 1.. Функція на приймає своє найменше значення рівне нулю, в усіх точках відрізка . Якщо , то містить одну точку ; якщо , то .

Рис 1.

У тих випадках, коли , природним узагальненням поняття найменшого значення функції є поняття нижньої грані функції.

Означення 3. Функція називається обмеженою знизу на множині , якщо існує число таке, що для будь-яких . Функція не обмежена знизу на , якщо існує послідовність , для якої .

Означення 4. Нехай функція обмежена знизу на множині . Тоді число називають нижньою гранню на , якщо

1) при будь-яких ;

2) для довільного як завгодно малого числа знайдеться точка , для якої .

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

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

Означення 5. Послідовність називається мінімізаційною для функції на , якщо .

Означення 6. Під задачею мінімізації функції на розумітимемо наступне:

1. визначити величину ;

2. якщо , то знайти хоча б одну точку ;

3. якщо , то побудувати мінімізаційну послідовність .

Коротко задачу мінімізації функції на множині будемо записувати наступним чином:

Виділимо спеціальний клас функцій, для яких .

Означення 7. Функція називається унімодальною на відрізку , якщо вона неперервна на і існують числа , такі, що

1. монотонно спадає при ;

2. монотонно зростає при ;

3. , при , так що .

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

Клас функцій , унімодальних на відрізку позначимо через . Для перевірки унімодальності функції на на практиці використовують такі достатні умови:

1) якщо і не спадає на , то – унімодальна на ;

2) якщо і для будь яких , то –унімодальна на .

Рис 2. Рис 3.

Рис 4. Рис 5.

Рис 6.

Приклад 2. Дослідимо на унімодальність функцію

Розв’язування. Оскільки і, як легко бачити , при , то – унімодальна функція на .

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

Класичний метод.

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

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

1) має розрив першого роду;

2) неперервна, однак, похідна не існує;

3) ;

4) або , тобто – кінці відрізка.

Ці точки прийнято називати точками підозрілими на екстремум. Пошук точок екстремуму функції починають з находження всіх точок, підозрілих на екстремум. Після того як таки точки знайдені, проводять додаткові дослідження і відбирають серед них ті, які є точками локального мінімуму або максимуму. Для цього зазвичай досліджують знак першої похідної в околі (або відповідному півоколі граничних точок або ) підозрілої точки.

В тих випадках, коли вдається обчислити в підозрілій точці похідні другого і більш високих порядків, то їх також можна використовувати для дослідження поведінки функції в околі цієї точки. А саме, нехай відомі похідні причому при а Якщо – парне число, то у випадку в точці реалізується локальний мінімум, а у випадку – локальний максимум. Якщо – непарне, то при в точці не може бути локального мінімуму або максимуму, при (або при ) у випадку в точці маємо локальний мінімум (максимум), а у випадку – локальний максимум (мінімум).

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

На жаль, класичний метод має досить обмежене застосування і не завжди зручний для реалізації на ЕОМ. Так, обчислення похідної в окремих випадках може бути трудомістким, або взагалі неможливо обчисліти. Крім того, задача розв'язування рівняння може бути не менш складна ніж вихідна задача. Це, звичайно, не означає, що класичний метод не застосовується на практиці, однак важливо мати методи пошуку екстремуму, що не потребують обчислення похідних, більш зручних для реалізації на сучасних ЕОМ.

Розглянемо деякі з таких методів мінімізації унімодальних функцій.

Метод золотого перерізу.

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

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

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

Вірні такі твердження:

1. Точки і розташовані симетрично відносно середини відрізка, тобто .

2. Точка здійснює золотий переріз відрізка , оскільки і . Аналогічно, точка здійснює золотий переріз відрізка .

Спираючись на ці властивості золотого перерізу, можна запропонувати наступний метод мінімізації унімодальної функції на відрізку .

Покладемо . На відрізку візьмемо точки , які здійснюють золотий переріз, і обчислимо значення . Далі, якщо , то приймемо ; якщо ж , то . Оскільки функція унімодальна на , то відрізок має хоча б одну спільну точку з множиною точок мінімуму на . Крім того, і дуже важливо те, що всередині міститься точка з обчисленим значенням , яка здійснює золотий переріз відрізка . Нехай уже визначені точки , обчислені значення , знайдено відрізок такий, що , і відома точка , яка здійснює золотий переріз відрізка і така, що . Тоді в якості наступної точки візьмемо точку , яка також здійснює золотий переріз відрізка , і обчислимо значення . Нехай для визначеності (випадок розглядається аналогічно). Якщо , то покладаємо ; якщо ж , то . Новий відрізок такий, що , , точка здійснює золотий переріз і

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

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

12 Следующая ⇒