Метод Дихотомии: Алгоритм, Формулы и Практическое Применение

Метод дихотомии относится к базовым численным методам, которые применяют для поиска минимума функции одной переменной на заданном отрезке. Почему этот подход стоит рассматривать отдельно? Прежде всего потому, что он задаёт чёткую последовательность действий и показывает, как задачу минимизации можно решать шаг за шагом. Кроме того, этот метод хорошо подходит для обучения, так как позволяет проследить, как постепенно сужается область поиска. Именно поэтому далее мы рассмотрим основные условия применения метода и принцип построения последовательных приближений к точке минимума.

Метод Дихотомии: Условия Применения и Основная Идея

Пусть задана функция \( 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 \). Таким образом, практический пример наглядно показывает, как метод дихотомии через последовательное сужение интервала позволяет приближённо определить минимальное значение функции.

Дополнительные Темы: Что Изучать Дальше

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

1. Метод Ньютона: Как учитывать поведение функции — В этой статье речь пойдёт о поиске минимума с помощью производных и о том, почему этот подход часто даёт быстрый результат.
2. Покоординатный спуск: Как искать минимум по отдельным переменным — В этой статье будет показано, как находят минимум функции многих переменных, последовательно изменяя каждую координату.
3. Градиентный спуск: Как двигаться в сторону уменьшения функции — В этой статье будет рассмотрен один из самых известных методов минимизации для функций нескольких переменных и его основная идея.

Метод Дихотомии в Коде: Создайте Собственную Программу для Поиска Минимума

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