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

Очевидно, найбільш природнім способом звуження інтервалу невизначеності для одновимірної унімодальної функції є ділення його на декілька рівних частин з наступним обчисленням значень цільової функції в вузлах отриманої сітки (рис. 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 обчислень. Таким чином, при деякій винахідливості ефективність пошуку можна різко збільшити.

13.2 Метод половинного ділення (розділення відрізка навпіл)

Суть метода полягає в постійному діленні відрізка дослідження цільової функції [a, b] навпіл і визначенні на ньому координат трьох точок х1, х2, хm. При чому значення їх визначаються як:

, L=b-a, , .

Рисунок 13.7 - Геометрична інтерпретація методу половинного ділення

Точки , поділяють відрізок [a,b] на чотири рівні частини (рис. 13.6), обчислюємо значення цільової функції Потім порівнюємо значення і , якщо , то виключаємо з дослідження відрізок та покладемо . Тоді середньою точкою нового відрізка [a, b] стає . Але якщо , то порівнюємо значення цільової функції і ; якщо , то виключаємо відрізок , покладемо ; якщо , то виключаємо відрізок та , покладемо , тобто формуємо новий відрізок дослідження. Обчислюємо L = b - a, якщо , якщо немає, то знову повертаємося до початку.

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

Рисунок 13.8 – Схема алгоритму метода половинного ділення

Цей метод відрізняється великою ефективністю.