Метод Дихотомії: Як Шукати Мінімум

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

Метод Дихотомії: Умови Застосування та Основна Ідея

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

Далі задають точність пошуку \( \varepsilon \). Вона показує, якої ширини має бути кінцевий інтервал, у межах якого міститься точка мінімуму. Тут також корисно розрізняти два поняття. По-перше, є точка мінімуму \( x^* \). По-друге, є мінімальне значення функції \( f(x^*) \). Метод дихотомії насамперед допомагає наближено знайти саме точку \( x^* \), а вже після цього, за потреби, обчислюють і значення функції в цій точці. Отже, мова йде не про точне знаходження розв’язку у готовому вигляді, а про його наближене значення із заданою точністю.

На початковому відрізку \( [a_0,b_0] \) будують дві внутрішні точки:

\[
x_1^{(0)}=\frac{a_0+b_0-\delta}{2}, \qquad x_2^{(0)}=\frac{a_0+b_0+\delta}{2},
\]

де \( \delta \) — мале додатне число, для якого виконується умова

\[
0<\delta<\varepsilon.
\]

Навіщо потрібні саме дві точки? Тому що одного значення посередині недостатньо, щоб зрозуміти, у який бік слід звужувати інтервал. А от порівняння значень функції у двох близьких внутрішніх точках уже дає потрібну інформацію. При цьому параметр \( \delta \) вводять для того, щоб точки \( x_1^{(0)} \) і \( x_2^{(0)} \) не збігалися з серединою відрізка, а лежали дуже близько по обидва боки від неї. Саме на цьому і будується подальша процедура пошуку.

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

Послідовне Звуження Інтервалу: Як Отримують Нові Наближення

Тепер переходимо до наступного етапу. Після побудови точок \( x_1^{(0)} \) і \( x_2^{(0)} \) обчислюють значення функції в цих точках \( f \left(x_1^{(0)}\right) \) та \( f \left(x_2^{(0)}\right) \).

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

Якщо \( f \left(x_1^{(0)}\right)<f \left(x_2^{(0)}\right) \), то мінімум слід шукати на відрізку \( [a_1,b_1]=[a_0,x_2^{(0)}] \).
Якщо ж \( f \left(x_1^{(0)}\right)>f \left(x_2^{(0)}\right) \), то новим інтервалом пошуку стає \( [a_1,b_1]=[x_1^{(0)},b_0] \).
Якщо ж значення однакові, тобто \( f \left(x_1^{(0)}\right)=f \left(x_2^{(0)}\right) \), то точка мінімуму міститься між цими точками, а тому беруть інтервал \( [a_1,b_1]=[x_1^{(0)},x_2^{(0)}] \).

Отже, після першого порівняння ми вже отримуємо новий, вужчий інтервал пошуку. Саме в цьому і полягає практична мета кожної ітерації: не знайти точку мінімуму одразу, а крок за кроком звужувати область, у межах якої вона міститься. До речі, випадок рівності \( f \left(x_1^{(0)}\right)=f \left(x_2^{(0)}\right) \) на практиці трапляється рідше, проте його важливо враховувати як частину повного опису алгоритму.

Після цього процес повторюється вже для нового відрізка \( [a_1,b_1] \). Для нього знову будують дві внутрішні точки:

\[
x_1^{(1)}=\frac{a_1+b_1-\delta}{2}, \qquad x_2^{(1)}=\frac{a_1+b_1+\delta}{2},
\]

потім знаходять значення \( f \left(x_1^{(1)}\right) \) та \( f \left(x_2^{(1)}\right) \), і ще раз звужують інтервал.

Аналогічно на довільній \( k \)-й ітерації, коли вже маємо інтервал \( [a_k,b_k] \), внутрішні точки обчислюють за формулами

\[
x_1^{(k)}=\frac{a_k+b_k-\delta}{2}, \qquad x_2^{(k)}=\frac{a_k+b_k+\delta}{2}.
\]

Після порівняння значень \( f \left(x_1^{(k)}\right) \) та \( f \left(x_2^{(k)}\right) \) одержують новий інтервал \( [a_{k+1},b_{k+1}] \). Таким чином, з кожною ітерацією область пошуку стає меншою. Хіба не зручно, коли складна задача зводиться до повторення кількох зрозумілих дій?

Процес продовжують доти, доки довжина поточного інтервалу не стане меншою за задану точність:

\[
b_k-a_k<\varepsilon.
\]

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

\[
x^*\approx \frac{a_k+b_k}{2}.
\]

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

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

Практична Частина: Як Метод Дихотомії Працює на Конкретній Задачі

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

Приклад 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].
\]

Візьмемо \( \delta=0.05 \), оскільки це число менше за задану точність \( \varepsilon=0.1 \).

Для першої ітерації обчислюємо дві внутрішні точки:

\[
\begin{gathered}
x_1^{(0)}=\frac{a_0+b_0-\delta}{2}=\frac{1+4-0.05}{2}=2.475,
\\[6pt]
x_2^{(0)}=\frac{a_0+b_0+\delta}{2}=\frac{1+4+0.05}{2}=2.525.
\end{gathered}
\]

Тепер знайдемо значення функції в цих точках:

\[
\begin{gathered}
f\left(x_1^{(0)}\right)=f(2.475)=(2.475-2)^2+1=1.226,
\\[6pt]
f\left(x_2^{(0)}\right)=f(2.525)=(2.525-2)^2+1=1.276.
\end{gathered}
\]

Оскільки \( f\left(x_1^{(0)}\right)<f\left(x_2^{(0)}\right) \), беремо новий інтервал пошуку

\[
[a_1,b_1]=[a_0,x_2^{(0)}]=[1,2.525].
\]

Переходимо до другої ітерації. Для інтервалу \( [a_1,b_1]=[1,2.525] \) маємо

\[
\begin{gathered}
x_1^{(1)}=\frac{a_1+b_1-\delta}{2}=\frac{1+2.525-0.05}{2}=1.738,
\\[6pt]
x_2^{(1)}=\frac{a_1+b_1+\delta}{2}=\frac{1+2.525+0.05}{2}=1.788.
\end{gathered}
\]

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

\[
\begin{gathered}
f\left(x_1^{(1)}\right)=f(1.738)=(1.738-2)^2+1=1.069,
\\[6pt]
f\left(x_2^{(1)}\right)=f(1.788)=(1.788-2)^2+1=1.045.
\end{gathered}
\]

Тут уже отримуємо \( f\left(x_1^{(1)}\right)>f\left(x_2^{(1)}\right) \), тому новий інтервал матиме вигляд

\[
[a_2,b_2]=[x_1^{(1)},b_1]=[1.738,2.525].
\]

На третій ітерації знаходимо

\[
\begin{gathered}
x_1^{(2)}=\frac{a_2+b_2-\delta}{2}=\frac{1.738+2.525-0.05}{2}=2.107,
\\[6pt]
x_2^{(2)}=\frac{a_2+b_2+\delta}{2}=\frac{1.738+2.525+0.05}{2}=2.157.
\end{gathered}
\]

Тоді

\[
\begin{gathered}
f\left(x_1^{(2)}\right)=f(2.107)=(2.107-2)^2+1=1.011,
\\[6pt]
f\left(x_2^{(2)}\right)=f(2.157)=(2.157-2)^2+1=1.025.
\end{gathered}
\]

Оскільки \( f\left(x_1^{(2)}\right)<f\left(x_2^{(2)}\right) \), звужуємо інтервал до

\[
[a_3,b_3]=[a_2,x_2^{(2)}]=[1.738,2.157].
\]

Далі знову повторюємо ту саму процедуру. Для інтервалу \( [a_3,b_3]=[1.738,2.157] \) маємо

\[
\begin{gathered}
x_1^{(3)}=\frac{a_3+b_3-\delta}{2}=\frac{1.738+2.157-0.05}{2}=1.923,
\\[6pt]
x_2^{(3)}=\frac{a_3+b_3+\delta}{2}=\frac{1.738+2.157+0.05}{2}=1.973.
\end{gathered}
\]

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

\[
\begin{gathered}
f\left(x_1^{(3)}\right)=f(1.923)=(1.923-2)^2+1=1.006,
\\[6pt]
f\left(x_2^{(3)}\right)=f(1.973)=(1.973-2)^2+1=1.001.
\end{gathered}
\]

Тепер \( f\left(x_1^{(3)}\right)>f\left(x_2^{(3)}\right) \), а отже, новий інтервал пошуку такий:

\[
[a_4,b_4]=[x_1^{(3)},b_3]=[1.923,2.157].
\]

Ще раз виконаємо обчислення. Для інтервалу \( [a_4,b_4]=[1.923,2.157] \) одержуємо

\[
\begin{gathered}
x_1^{(4)}=\frac{a_4+b_4-\delta}{2}=\frac{1.923+2.157-0.05}{2}=2.015,
\\[6pt]
x_2^{(4)}=\frac{a_4+b_4+\delta}{2}=\frac{1.923+2.157+0.05}{2}=2.04.
\end{gathered}
\]

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

\[
\begin{gathered}
f\left(x_1^{(4)}\right)=f(2.015)=(2.015-2)^2+1=1,
\\[6pt]
f\left(x_2^{(4)}\right)=f(2.04)=(2.04-2)^2+1=1.002.
\end{gathered}
\]

Оскільки \( f\left(x_1^{(4)}\right)<f\left(x_2^{(4)}\right) \), одержуємо новий інтервал

\[
[a_5,b_5]=[a_4,x_2^{(4)}]=[1.923,2.04].
\]

Його довжина дорівнює

\[
b_5-a_5=2.04-1.923=0.117,
\]

тому умова точності ще не виконана, і потрібно зробити ще один крок.

Для інтервалу \( [a_5,b_5]=[1.923,2.04] \) маємо

\[
\begin{gathered}
x_1^{(5)}=\frac{a_5+b_5-\delta}{2}=\frac{1.923+2.04-0.05}{2}=1.957,
\\[6pt]
x_2^{(5)}=\frac{a_5+b_5+\delta}{2}=\frac{1.923+2.04+0.05}{2}=2.007.
\end{gathered}
\]

Тоді

\[
\begin{gathered}
f\left(x_1^{(5)}\right)=f(1.957)=(1.957-2)^2+1=1.002,
\\[6pt]
f\left(x_2^{(5)}\right)=f(2.007)=(2.007-2)^2+1=1.
\end{gathered}
\]

Бачимо, що \( f\left(x_1^{(5)}\right)>f\left(x_2^{(5)}\right) \), тому новий інтервал пошуку дорівнює

\[
[a_6,b_6]=[x_1^{(5)},b_5]=[1.957,2.04].
\]

Тепер перевіряємо його довжину:

\[
b_6-a_6=2.04-1.957=0.083<0.1.
\]

Отже, умова точності виконана. За наближене значення точки мінімуму беремо середину останнього інтервалу:

\[
x^*\approx \frac{a_6+b_6}{2}=\frac{1.957+2.04}{2}=1.999.
\]

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

\[
f_{\min}\approx f(x^*)=f(1.999)=(1.999-2)^2+1=1.
\]

Отже, методом дихотомії ми отримали

\[
x^*\approx 1.999,
\qquad
f_{\min}\approx 1.
\]

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

Додаткові Теми: Куди Рухатися Далі

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

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

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

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

Метод Дихотомії: Алгоритм, Формули та Практичне Застосування