Метод Рівномірного Пошуку: Теоретичні Основи та Практичне Застосування

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

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

Метод Рівномірного Пошуку: Постановка Задачі та Зміст Мінімізації

Нехай потрібно знайти найменше значення функції однієї змінної на заданому відрізку. Інакше кажучи, розглядаємо функцію \( f(x) \) на інтервалі \( [a_0,b_0] \) і шукаємо таку точку \( x^* \), у якій функція набуває мінімального значення. Це записують так:

\[
f(x^*)=\min_{x\in[a_0,b_0]} f(x).
\]

Що означає цей запис? Він означає, що серед усіх точок відрізка \( [a_0,b_0] \) існує така точка \( x^* \), у якій значення функції є найменшим.

У задачах чисельної оптимізації дуже часто припускають, що функція є унімодальною на розглядуваному інтервалі. Це важливо, адже тоді пошук мінімуму дає надійний результат. Нагадаємо, що функція називається унімодальною на відрізку \( [a_0,b_0] \), якщо вона має на цьому відрізку лише одну точку мінімуму \( x^* \), причому ліворуч від неї функція строго спадає, а праворуч — строго зростає.

Отже, якщо функція поводиться саме так, то можна впевнено звужувати область пошуку. Чому це настільки важливо? Тому що чисельні методи не завжди знаходять точне значення \( x^* \) одразу. Найчастіше вони будують наближений розв’язок, який з кожним кроком стає точнішим.

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

• Похідна функції невідома.
• Функція задана таблично.
• Аналітичний вираз є занадто складним.
• Обчислення похідної є незручним або недоцільним.

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

Прямі Методи Мінімізації: Чому Метод Рівномірного Пошуку є Таким Простим

Тепер перейдемо до самої ідеї методу. Вона справді дуже проста. Початковий інтервал невизначеності \( [a_0,b_0] \), на якому шукається мінімум, ділять на кілька рівних частин. Після цього в точках поділу обчислюють значення функції й порівнюють їх між собою.

Нехай інтервал \( [a_0,b_0] \) розбитий на \( n \) однакових частин. Тоді величина кроку задається формулою

\[
h=\frac{b_0-a_0}{n}.
\]

Після цього будують послідовність точок

\[
x_i=a_0+i\cdot h, \qquad i=0,1,2,\dots,n.
\]

Що відбувається далі? У кожній із цих точок обчислюють значення функції:

\[
f(x_0), f(x_1), f(x_2), \dots, f(x_n).
\]

Потім серед усіх отриманих значень знаходять найменше. Припустімо, що воно досягається в точці \( x_k \). Тоді маємо

\[
f(x_k)=\min_{0\leq i\leq n} f(x_i).
\]

Саме цей результат дає важливу інформацію для подальшого пошуку. Якщо функція є унімодальною, то істинна точка мінімуму \( x^* \) повинна лежати поблизу точки \( x_k \). Тому в межах даного підходу роблять висновок, що шукана точка мінімуму належить інтервалу

\[
x^* \in [x_{k-1},x_{k+1}].
\]

Інакше кажучи, після одного проходу ми вже не шукаємо мінімум на всьому початковому відрізку. Натомість переходимо до значно вужчого інтервалу, у якому міститься точка мінімуму.

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

Разом із тим потрібно пам’ятати і про важливу особливість. Якщо обрати занадто малий крок, доведеться виконати багато обчислень. Якщо ж крок буде надто великим, то точність пошуку виявиться недостатньою. Отже, ефективність методу безпосередньо пов’язана з вибором числа поділів \( n \).

Звуження Інтервалу: Як Формується Наближений Розв’язок

Тепер розгляньмо, як саме формується наближене рішення. Після порівняння значень функції в точках \( x_0,x_1,\dots,x_n \) знаходять точку \( x_k \), у якій функція приймає найменше значення серед усіх перевірених. Тоді цю точку можна взяти як перше наближення до шуканої точки мінімуму:

\[
x^* \approx x_k.
\]

Проте на цьому процес, як правило, не зупиняється. Навпаки, далі беруть новий інтервал невизначеності

\[
[a_1,b_1]=[x_{k-1},x_{k+1}],
\]

а потім повторюють ту саму процедуру вже на цьому вужчому відрізку.

Отже, метод працює крок за кроком:

\[
[a_0,b_0]\rightarrow [a_1,b_1]\rightarrow [a_2,b_2]\rightarrow \dots \rightarrow [a_m,b_m].
\]

На кожному новому кроці інтервал стає коротшим, а наближення до точки мінімуму — точнішим. У результаті отримують настільки малий інтервал, що його довжина задовольняє потрібну точність. Це записують умовою

\[
b_m-a_m<\varepsilon,
\]

де \( \varepsilon \) — заздалегідь задана точність.

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

\[
x^* \approx x_k
\]

або

\[
x^* \approx \frac{a_m+b_m}{2}.
\]

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

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

Практична Частина: Як Метод Рівномірного Пошуку Працює на Конкретній Задачі

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

Приклад 1. Знайти мінімальне значення функції \( f(x)=(x-2)^2+1 \) на відрізку \( [1,4] \) з точністю \( \varepsilon=0.1 \), використовуючи метод рівномірного пошуку

Розглянемо функцію \( f(x)=(x-2)^2+1 \) на відрізку \( [1,4] \). На цьому відрізку вона є унімодальною, оскільки має лише одну точку мінімуму при \( x=2 \). Отже, метод рівномірного пошуку тут можна використовувати коректно.

Починаємо з інтервалу

\[
[a_0,b_0]=[1,4].
\]

Для простоти на кожному кроці будемо ділити поточний інтервал на чотири рівні частини. Тоді для першого кроку маємо

\[
h_0=\frac{b_0-a_0}{4}=\frac{4-1}{4}=0.75.
\]

Будуємо точки поділу:

\[
\begin{gathered}
x_0=1,\qquad x_1=1.75,\qquad x_2=2.5,\qquad x_3=3.25,\qquad x_4=4.
\end{gathered}
\]

Обчислюємо значення функції в цих точках:

\[
\begin{gathered}
f(x_0)=(1-2)^2+1=2,
\\[6pt]
f(x_1)=(1.75-2)^2+1=1.063,
\\[6pt]
f(x_2)=(2.5-2)^2+1=1.25,
\\[6pt]
f(x_3)=(3.25-2)^2+1=2.563,
\\[6pt]
f(x_4)=(4-2)^2+1=5.
\end{gathered}
\]

Найменше значення отримано в точці \( x_1=1.75 \). Отже, новий інтервал невизначеності беремо у вигляді

\[
[a_1,b_1]=[x_0,x_2]=[1,2.5].
\]

Тепер повторюємо ту саму процедуру для нового інтервалу. Його довжина дорівнює \( 2.5-1=1.5 \), тому крок буде

\[
h_1=\frac{b_1-a_1}{4}=\frac{2.5-1}{4}=0.375.
\]

Будуємо точки:

\[
\begin{gathered}
x_0=1,\qquad x_1=1.375,\qquad x_2=1.75,\qquad x_3=2.125,\qquad x_4=2.5.
\end{gathered}
\]

Обчислюємо значення функції:

\[
\begin{gathered}
f(x_0)=(1-2)^2+1=2,
\\[6pt]
f(x_1)=(1.375-2)^2+1=1.391,
\\[6pt]
f(x_2)=(1.75-2)^2+1=1.063,
\\[6pt]
f(x_3)=(2.125-2)^2+1=1.016,
\\[6pt]
f(x_4)=(2.5-2)^2+1=1.25.
\end{gathered}
\]

Тепер найменше значення досягається в точці \( x_3=2.125 \). Тому звужуємо інтервал:

\[
[a_2,b_2]=[x_2,x_4]=[1.75,2.5].
\]

Далі

\[
h_2=\frac{b_2-a_2}{4}=\frac{2.5-1.75}{4}=0.188.
\]

Отже, точки поділу мають вигляд

\[
\begin{gathered}
x_0=1.75,\qquad x_1=1.938,\qquad x_2=2.125,\qquad x_3=2.313,\qquad x_4=2.5.
\end{gathered}
\]

Обчислюємо значення функції:

\[
\begin{gathered}
f(x_0)=(1.75-2)^2+1=1.063,
\\[6pt]
f(x_1)=(1.938-2)^2+1=1.004,
\\[6pt]
f(x_2)=(2.125-2)^2+1=1.016,
\\[6pt]
f(x_3)=(2.313-2)^2+1=1.098,
\\[6pt]
f(x_4)=(2.5-2)^2+1=1.25.
\end{gathered}
\]

Найменше значення серед знайдених тепер досягається в точці \( x_1=1.938 \). Тому беремо новий інтервал

\[
[a_3,b_3]=[x_0,x_2]=[1.75,2.125].
\]

Тепер його довжина дорівнює \( 2.125-1.75=0.375 \), а крок становить

\[
h_3=\frac{b_3-a_3}{4}=\frac{0.375}{4}=0.094.
\]

Будуємо точки:

\[
\begin{gathered}
x_0=1.75,\qquad x_1=1.844,\qquad x_2=1.938,\qquad x_3=2.031,\qquad x_4=2.125.
\end{gathered}
\]

Значення функції дорівнюють:

\[
\begin{gathered}
f(x_0)=(1.75-2)^2+1=1.063,
\\[6pt]
f(x_1)=(1.844-2)^2+1=1.024,
\\[6pt]
f(x_2)=(1.938-2)^2+1=1.004,
\\[6pt]
f(x_3)=(2.031-2)^2+1=1.001,
\\[6pt]
f(x_4)=(2.125-2)^2+1=1.016.
\end{gathered}
\]

І тут найменше значення досягається в точці \( x_3=2.031 \). Тоді новий інтервал буде таким:

\[
[a_4,b_4]=[x_2,x_4]=[1.938,2.125].
\]

Його довжина дорівнює \( b_4-a_4=2.125-1.938=0.187 \). Оскільки це значення ще не менше за задану точність \( \varepsilon=0.1 \), виконуємо ще один крок. Маємо

\[
h_4=\frac{b_4-a_4}{4}=\frac{0.187}{4}=0.047.
\]

Будуємо точки:

\[
\begin{gathered}
x_0=1.938,\qquad x_1=1.985,\qquad x_2=2.032,\qquad x_3=2.079,\qquad x_4=2.125.
\end{gathered}
\]

Тепер обчислюємо значення функції:

\[
\begin{gathered}
f(x_0)=(1.938-2)^2+1=1.004,
\\[6pt]
f(x_1)=(1.985-2)^2+1=1,
\\[6pt]
f(x_2)=(2.032-2)^2+1=1.001,
\\[6pt]
f(x_3)=(2.079-2)^2+1=1.006,
\\[6pt]
f(x_4)=(2.125-2)^2+1=1.016.
\end{gathered}
\]

Найменше значення тепер отримуємо в точці \( x_1=1.985 \). Тому новий інтервал невизначеності має вигляд

\[
[a_5,b_5]=[x_0,x_2]=[1.938,2.032].
\]

Тепер перевіряємо точність: \( b_5-a_5=2.032-1.938=0.094<0.1 \). Отже, умова точності виконана. За наближене значення точки мінімуму можна взяти точку

\[
x^*\approx 1.985,
\]

а відповідне мінімальне значення функції дорівнює

\[
f_{\min}\approx f(1.985)=1.
\]

Цей результат узгоджується з точною відповіддю, адже для функції \( f(x)=(x-2)^2+1 \) мінімум справді досягається при \( x=2 \), а найменше значення дорівнює \( 1 \). Отже, метод рівномірного пошуку дав близький результат і наочно показав, як через послідовне звуження інтервалу можна наблизитися до точки мінімуму.

Додаткові Теми: Що Варто Розглянути Далі

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

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

Метод Рівномірного Пошуку в Коді: Створіть Власну Програму для Пошуку Мінімуму

Тепер подивіться на блок-схему нижче не лише як на ілюстрацію, а як на готову основу для невеликого навчального проєкту. Чому б не використати її та не написати на улюбленій мові програмування невеликий код, який визначає мінімальне значення унімодальної функції методом рівномірного пошуку? Така робота добре показує, як математична ідея переходить у зрозумілий алгоритм, а потім — у програмний код, який можна перевіряти на різних прикладах. Крім того, це гарна нагода переконатися, що ви добре розумієте метод не лише теоретично, а й під час практичного програмування.