Метод половинного деления: решение нелинейного уравнения

Метод половинного деления (он же метод бисекции, или метод дихотомии) - это простейший численный способ найти корень нелинейного уравнения вида $f(x) = 0$, когда аналитической формулы для корня нет. Идея предельно наглядна: если на концах отрезка функция меняет знак, то где-то внутри она обращается в ноль, и достаточно раз за разом делить отрезок пополам, отбрасывая ту половину, где корня нет. Метод медленный, но абсолютно надёжный - он сходится всегда, когда корень отделён. Ниже разберём, при каком условии он работает, как считать середину отрезка, сколько делений нужно для заданной точности и где студенты ошибаются. Чтобы сразу увидеть, как отрезок стягивается к корню, покрутите калькулятор ниже: меняйте уравнение, границы и число делений и следите за оценкой корня и шириной отрезка.

В чём идея метода половинного деления

Пусть нужно решить нелинейное уравнение $f(x) = 0$, где функция $f$ непрерывна на отрезке $[a, b]$. Главное условие, с которого начинается метод половинного деления, - это смена знака на концах отрезка:

$f(a) \cdot f(b) < 0.$

Если произведение значений на концах отрицательно, значит $f(a)$ и $f(b)$ имеют разные знаки. По теореме Больцано-Коши непрерывная функция, меняющая знак, обязательно где-то проходит через ноль - внутри $[a, b]$ есть хотя бы один корень. Этот отрезок называют отрезком отделения корня, а сам процесс его поиска - отделением корня.

Дальше работает простой шаг. Берём середину отрезка

$c = \frac{a + b}{2}$

и смотрим на знак $f(c)$. Возможны три случая. Если $f(c) = 0$, нам повезло - корень найден точно. Если знак $f(c)$ совпадает со знаком $f(a)$, то смена знака сохраняется на правой половине $[c, b]$, и левую половину можно отбросить: заменяем $a$ на $c$. Если же знак $f(c)$ совпадает со знаком $f(b)$, корень лежит в левой половине $[a, c]$, и мы заменяем $b$ на $c$. В любом случае новый отрезок вдвое короче прежнего, а корень по-прежнему гарантированно внутри.

Формула и алгоритм по шагам

Соберём всё в чёткий алгоритм. На каждой итерации метода половинного деления мы:

1. вычисляем середину $c = (a + b)/2$;
2. находим $f(c)$ и определяем его знак;
3. если $f(a)$ и $f(c)$ одного знака - полагаем $a = c$, иначе $b = c$;
4. повторяем, пока ширина отрезка $b - a$ не станет меньше требуемой точности $\varepsilon$.

Рассчитать для своей задачи

Удобно отслеживать не сам корень (мы его точно не знаем), а ширину текущего отрезка - она и есть верхняя граница погрешности. За приближённое значение корня берут середину последнего отрезка: тогда ошибка не превышает половины его длины. Именно поэтому метод половинного деления так предсказуем: после каждого шага неопределённость точно уменьшается вдвое, без всяких допущений о гладкости функции или близости начального приближения.

Сколько итераций нужно для заданной точности

Это любимый вопрос экзаменаторов, и он решается одной формулой. После $n$ делений начальный отрезок длины $b_0 - a_0$ сжимается до

$\frac{b_0 - a_0}{2^{\,n}}.$

Чтобы эта ширина стала не больше точности $\varepsilon$, нужно потребовать $(b_0 - a_0)/2^{\,n} \le \varepsilon$. Логарифмируя, получаем оценку числа итераций:

$n \ge \log_2 \frac{b_0 - a_0}{\varepsilon}.$

Например, для отрезка $[1, 2]$ длиной единица и точности $\varepsilon = 0{,}001$ выходит $n \ge \log_2 1000 \approx 9{,}97$, то есть нужно 10 делений. Для точности $0{,}0001$ - уже 14 делений. Видно главное свойство бисекции: число шагов растёт лишь логарифмически при ужесточении точности, но при этом метод сходится линейно (за каждый шаг погрешность падает строго в 2 раза), что заметно медленнее, чем у метода Ньютона. Зато здесь не нужна производная и нет риска расходимости.

Рассчитать для своей задачи

На рисунке выше - один шаг для кубического уравнения. Слева конец $a = 1$ с $f(a) < 0$, справа $b = 2$ с $f(b) > 0$, середина $c = 1{,}5$ даёт $f(c) < 0$, значит корень правее, и отрезок ужмётся до $[1{,}5;\ 2]$. Скобка внизу показывает, что ширина с единицы упала до половины.

Разбор типовой задачи

Решим классическое уравнение $x^3 - x - 2 = 0$ методом половинного деления с точностью до $0{,}1$. Сначала отделяем корень: $f(1) = 1 - 1 - 2 = -2 < 0$, а $f(2) = 8 - 2 - 2 = 4 > 0$. Знаки разные, значит на $[1, 2]$ есть корень - отрезок отделения найден.

Теперь делим:

• Шаг 1. $c = 1{,}5$, $f(1{,}5) = 3{,}375 - 1{,}5 - 2 = -0{,}125 < 0$. Знак совпал с $f(a)$, корень правее: новый отрезок $[1{,}5;\ 2]$.
• Шаг 2. $c = 1{,}75$, $f(1{,}75) \approx 1{,}61 > 0$. Знак совпал с $f(b)$, корень левее: отрезок $[1{,}5;\ 1{,}75]$.
• Шаг 3. $c = 1{,}625$, $f(1{,}625) \approx 0{,}666 > 0$. Корень левее: отрезок $[1{,}5;\ 1{,}625]$.
• Шаг 4. $c = 1{,}5625$, $f(1{,}5625) \approx 0{,}252 > 0$. Корень левее: отрезок $[1{,}5;\ 1{,}5625]$ шириной $0{,}0625 < 0{,}1$.

Точность достигнута, за приближённый корень берём середину последнего отрезка: $x \approx 1{,}53$. Точное численное значение корня $x^* \approx 1{,}5214$, и наша оценка отличается от него меньше чем на $0{,}1$, как и требовалось. Метод бисекции хорош тем, что эта таблица механична: ни на одном шаге не нужно угадывать, куда двигаться - знак $f(c)$ всё решает сам.

Связь с другими численными методами

Метод половинного деления - самый медленный, но самый устойчивый из методов уточнения корня. Его линейная сходимость уступает квадратичной сходимости метода касательных Ньютона и сверхлинейной у метода секущих, зато он не требует ни производной, ни хорошего начального приближения и никогда не расходится, если корень отделён. Поэтому бисекцию часто используют как «страховку»: ей грубо локализуют корень, а затем переключаются на быстрый метод касательных, который уже опирается на производную и потому стартует только из достаточно близкой точки.

Частые ошибки

• Отрезок без смены знака. Если $f(a)$ и $f(b)$ одного знака, теорема Больцано-Коши ничего не гарантирует: корня на отрезке может не быть, и метод половинного деления применять нельзя. Всегда сначала проверяйте $f(a)\cdot f(b) < 0$.
• Чётное число корней внутри отрезка. Если корней два (или любое чётное число), знаки на концах совпадают, и бисекция их «не видит». Сначала разбейте область на отрезки, где корень ровно один.
• Сравнение значений вместо знаков. Решение о выборе половины принимается по знаку $f(c)$, а не по тому, какое значение больше по модулю. Сравнивать нужно именно знаки $f(a)$ и $f(c)$.
• Точность по корню, а не по отрезку. Останавливаться надо по ширине отрезка $b - a$ (она и есть граница погрешности), а не по близости $f(c)$ к нулю - около пологого корня $f(c)$ мало даже вдали от него.
• Деление в градусах для тригонометрических уравнений. В выражениях вроде $\cos x = x$ аргумент берётся в радианах. Подстановка градусов даст неверные знаки и сорвёт сходимость.

FAQ

При каком условии можно применять метод половинного деления? Функция должна быть непрерывна на отрезке $[a, b]$, и на его концах должна быть смена знака: $f(a)\cdot f(b) < 0$. Тогда корень гарантированно лежит внутри, и метод обязательно к нему сойдётся.

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

Сколько шагов нужно для точности 0,001 на отрезке длины 1? По формуле $n \ge \log_2(1/0{,}001) = \log_2 1000 \approx 9{,}97$, то есть 10 делений. Для точности $0{,}0001$ на том же отрезке потребуется уже 14 итераций.

Коротко

Метод половинного деления решает нелинейное уравнение $f(x) = 0$, многократно деля пополам отрезок, на концах которого функция меняет знак. Условие применимости - $f(a)\cdot f(b) < 0$; на каждом шаге считают середину $c = (a+b)/2$, по знаку $f(c)$ отбрасывают половину без корня, и ширина отрезка падает вдвое. Число итераций для точности $\varepsilon$ оценивается формулой $n \ge \log_2\big((b-a)/\varepsilon\big)$. Метод медленный, но надёжный: он сходится всегда, когда корень отделён, и потому служит базовым инструментом численного решения уравнений.