шук полягає у виборі точок, рівномірно розташованих на відрізку [a, b], координати яких:
При цьому довжина інтервалу, що містить мінімум дає оцінку швидкості збіжності пасивного пошуку із зростанням числа N точок, так як швидкість збіжності будь-якого методу прямого пошуку можна характеризувати швидкістю зменшення інтервалу невизначеності зі зростанням N. Обчислюючи значення цільової функції в кожній точці fk=f (xk), знайдемо найменше значення fj, і тоді точка оптимуму x * (xj - 1, x j + 1), і можна вважати, що x * xj ± е з точністю е.
1. Огляд існуючих методів рішення задачі
1.1 Методи послідовного пошуку
Припущення про унімодального функції дозволяє розробити адаптивні (або послідовні) алгоритми пошуку оптимального значення. При цьому використовується поняття інтервалу невизначеності, як інтервалу містить точку мінімуму, хоча її точне положення невідомо. Важливою характеристикою даних методів є кількість обчислень значень оптимизируемой функції для отримання кінцевої величини інтервалу невизначеності, що не перевищує заданої величини. Методи орієнтовані на знаходження точки оптимуму всередині заданого інтервалу, засновані на властивості унімодального функції, не використовують інформацію про похідної функції.
Метод ділення відрізка навпіл
Здається інтервал [a, b] і похибка. В алгоритмі розподілу навпіл або алгоритмі рівномірного дихотомічного пошуку випробування проводяться парами. Координати кожної наступної пари випробувань рознесені між собою на величину. Випробування проводяться в середині поточного інтервалу невизначеності (ТІН). За значеннями f (x), отриманим в цих точках, одна половина ТІН чинності унімодального функції f (x) виключається з подальшого розгляду. Величина визначається необхідною точністю рішення. Алгоритм відноситься до класу методів послідовного пошуку.
Розрахунок відбувається до тих пір, поки довжина інтервалу не стане менше заданої похибки. В середньому за одне обчислення функції відрізок, на якому знаходиться x, зменшується приблизно в 1.33 рази. Цей метод простий у реалізації, дозволяє знаходити мінімум розривної функції, однак вимагає великого числа обчислень функції для забезпечення заданої точності.
Метод золотого перетину
Золотий перетин - це таке поділ відрізка [a, b] на дві нерівні частини [a, x] і [x, b], при якому має місце наступне співвідношення:
xb/ab=ax/xb=1-,
=2/(3+) 0.381966011.
Алгоритм пошуку мінімуму аналогічний вищеописаному методу ділення відрізка навпіл і відрізняється тим, що на початку точки x 1 і x 2 вибираються так, щоб виконувалася золоте ставлення, і обчислюються значення функції в цих точках.
За одне обчислення функції відрізок, на якому знаходиться xm, зменшується в 1 1.61 рази, тобто швидше, ніж метод поділу відрізка навпіл.
Метод Фібоначчі
Метод аналогічний методу золотого перетину. Відмінність полягає в тому, що коефіцієнт стиснення інтервалу невизначеності змінюється від ітерації до ітерації згідно послідовності Фібоначчі. Послідовність чисел визначається наступним чином:
F 0=F 1=1,
F k + 1=F k + F k - 1,
k=1, 2, ...
Пробні точки k і м k обчислюють за формулами:
При цьому число ітерацій вибирається до початку обчислень і обумовлено необхідною точністю:
1.2 Методи апроксимації
У методах прямого пошуку ми не мали жодної інформації про функції, що мінімізується за винятком її значень в обраних нами точках і припущення, що вона неперервна і є унімодальної функцією на розглянутому відрізку. Якщо функцію в деякій околиці точки її мінімуму можна досить точно замінити (апроксимувати) многочленом, то для її мінімізації доцільно використовувати так звані методи поліноміальної апроксимації. Їх загальна особливість полягає в обчисленні коефіцієнтів многочлена по відомим значенням функції в окремих точках і наступному знаходженні мінімуму цього многочлена з використанням необхідних і достатніх умов екстремуму. Основна ідея методу: можливість апроксимації гладкої функції поліномом досить високого порядку і використання цього полінома для оцінювання точки оптимуму. Якість цієї оцінки може бути підвищити двома способами:
. збільшенням ступеня полінома;
. зменшенням інтервалу апроксимації.
Другий спосіб краще, тому що побудова пол...
