Метод половинного поділу відрізка

Мінімізація функцій однієї змінної.

Визначення 5. Функція називається унімодальною на відрізку , якщо вона неперервна на та існують числа (a ≤ ≤ ≤ b) такі, що:

1) строго монотонно спадає при a ≤u ≤ , якщо a< ;

2) строго монотонно зростає при ≤u ≤ b, якщо < b;

3) при ≤ u ≤ , так що .

У випадку коли = , функція називається строго унімодальною на відрізку .

Слід відзначити, що якщо функція унімодальна на , то вона буде унімодальною і на будь-якому відрізку .

Цей метод є найпростішим методом мінімізації функції однієї змінної, який не потребує обчислення похідної. Будемо припускати, що мінімізуєма функція є унімодальною на відрізку . Пошук мінімума починається з вибору двох точок та , де – константа, яка є параметром методу, . Величина вибирається самостійно і може визначитися значимою кількістю вірних десяткових знаків при заданні аргументу u. Зокрема, зрозуміло, що не може бути менше машинної похибки ЕОМ, яка використовується для розв’язання задачі. Точки , розміщені симетрично на відрізку відносимо його середини та при малих б ділять його майже пополам (це і пояснює назву методу).

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

.

Нехай відрізок , який має непустий перетин з , вже відомий, і

.

Тоді виберемо точки

,

,

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

і .

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

.

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

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

при

або

при ,

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

При такому виборі наближення для буде допущена похибка .

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

,

тут k = n/2 і – достатньо мале.

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

Зі сказаного вище слідує, що методом половинного поділу за допомогою n=2k обчислень значення функції можна визначити точку мінімуму унімодальної функції на відрізку в кращому випадку з точністю . Виникає питання про існування методів, які дозволяють за допомогою такої ж кількості обчислень значень функції розв’язати задачу мінімізації унімодальної функції точніше. Такі методи існують і один з них буде розглянуто в наступному пункті.

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

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