Метод загального пошуку

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

Рисунок 13.6 – Метод загального пошуку

В результаті інтервал невизначеності звужується до двох кроків сітки. Звичайно говорять про дроблення інтервалу невизначеності, яке характеризується коефіцієнтом f. Розділивши інтервал невизначеності на N частин, отримаємо N+1 вузол, і тоді

.

Щоб отримати значення f = 0,01, необхідно обчислити цільову функцію в 199 точках, а при f = 0,001 N=1999. Звідси видно, що ефективність цього методу при зменшенні інтервалу невизначеності швидко падає. Напрошується інший варіант: щоб отримати f=0,01, необхідно обчислити спочатку функцію в 19 точках і отримати f = 0,1, а потім обчислити ще 19 значень функції на скороченому інтервалі невизначеності, отримати f = 0,01, зробивши при цьому всього 38, а не 199 обчислень. Таким чином, при деякій винахідливості ефективність пошуку можна різко збільшити.

Метод дихотомії

Найпростішим з методів уточнення коренів є метод половинного ділення, або метод дихотомії, призначений для знаходження коренів рівнянь, представлених у вигляді f(x)=0.

Нехай безперервна функція f(x) на кінцях відрізка [a,b] має значення різних знаків, тобто f(a)´f(b)£0 (рис.1), тоді на відрізку є хоча б один корінь.

Візьмемо середину відрізка с=(a+b)/2. Якщо f(a)´f(c)£0, то корінь явно належить відрізку від a до(a+b)/2 і в іншому випадку від (a+b)/2 до b.

Рис. 1. Графік функції f(x)

Тому беремо відповідний з цих відрізків, обчислюємо значення функції в його середині і т.д. до тих пір, поки довжина чергового відрізка не виявиться менше заданої граничної абсолютної похибки (b-a)<e.

Так як кожне чергове обчислення середини відрізка c та значення функції f(c) звужує інтервал пошуку вдвічі, то при вихідному відрізку [a,b] та граничної похибки e кількість обчислень n визначається умовою
(b-a)/2ⁿ<e,абоn~log₂((b-a)/e).

З точки зору машинної реалізації (рис.2) цей метод найбільш простий і використовується в багатьох стандартних програмних засобах.

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

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

Рисунок 13.11 – Позначення, які використовуються в методі золотого перетину

Суть цього методу полягає в наступному. Інтервал невизначеності ділиться на дві нерівні частини, відношення довжини більшого відрізку до довжини всього інтервалу дорівнює відношенню довжини меншого відрізку до довжини більшого відрізку. На рис. 13.11 показаний інтервал невизначеності Z, який складається з відрізків z₁ i z₂, відношення довжин яких визначається правилом золотого перетину.

Крім того, z₁ + z₂ = Z. Із першого рівняння витікає . Підставивши значення Z з другого рівняння і поділивши обидві частини на , отримаємо

Розв’язуючи це квадратне рівняння, знаходимо для додатнього кореня значення

На рис. 13.12 показано ділення інтервалу невизначеності в цьому відношенні і нанесені відповідні значення цільової функції, які дозволяють зменшити інтервал невизначеності в 1/ 0,618 раз.

Рисунок 13.12 – Метод золотого перетину

На цій стадії ще не видно переваг методу золотого перетину в порівнянні з методом дихотомії, однак їх добре видно при подальшому діленні інтервалу, так як виявляється, що одне із значень цільової функції, яке необхідно обчислити на наступному кроці, вже відомо. Тому, щоб зменшити невизначеність ще в 1/ 0,618 раз, потрібно додатково обчислити тільки одне значення цільової функції в точці, яка визначається правилом золотого перетину.

При n > 2 ефективність методу золотого перетину вища, ніж у метода дихотомії, так як при кожному наступному обчисленні цільової функції інтервал невизначеності скорочується в 1/ 0,618 раз. Після обчислення N значень цільової функції коефіцієнт дроблення інтервалу невизначеності складає

f = 0,618 N-1.

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

Z_J-2 = Z_J-1 + Z_J, 1 < <>

де Z_J довжина інтервалу невизначеності після обчислення J-го значення цільової функції.0