Мінімізація функції однієї змінної методом рівномірного пошуку

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

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

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

Графічне представлення методу рівномірного пошуку

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

1. Вибравши деякий крок , розбиваємо інтервал невизаченості  на  частин .
2. Обчислюємо значення функції в  знайдених точках .
3. Серед отриманих точок знаходимо точку , в якій функція приймає найменшого значення .
4. Точка мінімуму  належить інтервалу , на якому, в якості наближеного розв’язку може бути обрана точка , тобто .

Мінімізація функції однієї змінної методом рівномірного пошуку – приклад:

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

Графік заданої функції на заданому інтервалі

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

Ріновіддалені точки інтервалу невизначеності та значення функції в них

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

Зауваження: для отримання більш точного значення, на практиці доволі часто проробляють аналогічну процедуру декілька разів. Тобто, в результаті виконання першого кроку отримують деякий новий інтервал невизначеності . Його, знову-таки ділимо на декілька части, в результаті чого приходимо до нового інтервалу . Продовжуючи даний процес далі, отримуємо як завгодно малий інтервал (довжина якого, як правило, менший від заданого числа ), який міститиме більш точне значення точки мінімуму.

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