Покроковий метод оптимізації.

Розглянемо покроковий метод на прикладі мінімізації функції однієї змінної. Нехай потрібно мінімізувати функцію , задану на [a,b]. Суть покрокового методу покажемо на рисунку 5. Вона заключається в знаходженні всіх значень функції на [a,b] з кроком h і визначення мінімуму шляхів їх порівняння між собою. Очевидно, що в ролі оптимального значення функції , приведеної на рисунку 5, буде її значення в точці , оскільки тут функція має найменше значення.

Основні плюси методу

Порівняно простота алгоритму.

Не потрібно великого об’єму пам’яті ЕОМ.

Основні недоліки методу

Можливість пропуску точки екстремуму.

Різке зростання об’єму обчислень при підвищення точності.

Розглянемо покроковий метод, при якому задана область досліджується на початку з більш великим кроком. Потім вона зменшується до значеня 2h. Обчислення продовжуються до тих пір, поки не буде досягнута задана погрешность Е.

Для визначення мінімуму функції немає необхідності запам’ятовувати всі її значення. Для цього достатньо прийняти яку-небудь допоміжну змінну (в нашому випадку ), а потім в циклі відбувається її порівняння з натупним значенням функції. Якщо y < P, то воно запам’ятовується, тобто P = y. Одночасно запам’ятовується ордината цієї точки – змінна С.

В блок-схемі початковий крок h не задається, а обчислюється по формулі: h=z(b-a).

Даний алгоритм представляє собою два вкладених цикла з розгалуженням у внутрішньому циклі. Зовнішній цикл – ітераційний, внутрішній – з рівномірним нарощуванням параметру циклу. В алгоритмі використовуються допоміжні змінні a i b, що дало можливість побудувати однотипний по способу виконання циклічний алгоритм зменшення інтервалу [a,b].

Блок-схема підпрограми для оптимізації функції

“Покроковим методом”