Метод бисекции (половинного деления): как это работает

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

Идея и условие применимости

Пусть функция $f$ непрерывна на отрезке $[a, b]$ и на его концах принимает значения разных знаков: $f(a)\cdot f(b) < 0$. По теореме Больцано–Коши (теореме о промежуточном значении) внутри отрезка обязательно найдётся хотя бы одна точка $x^{*}$, в которой $f(x^{*}) = 0$. Это и есть корень, который ищет метод половинного деления.

Алгоритм на каждом шаге сокращает отрезок локализации корня вдвое. Берём середину $c = \frac{a + b}{2}$ и смотрим на знак $f(c)$. Если $f(a)\cdot f(c) < 0$, корень лежит в левой половине $[a, c]$ - заменяем $b$ на $c$. Иначе корень в правой половине $[c, b]$ - заменяем $a$ на $c$. В обоих случаях новый отрезок вдвое короче и по-прежнему содержит корень. Условие смены знака на концах - единственное требование метода бисекции, и именно оно делает его таким устойчивым.

Пошаговый расчёт корня

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

После того как видно, как отрезок схлопывается к корню, разберём, что именно гарантирует сходимость и сколько шагов она требует.

Алгоритм половинного деления по шагам

Формально метод бисекции записывается так:

1. Проверить, что $f(a)\cdot f(b) < 0$. Если нет - метод неприменим, нужен другой отрезок.
2. Вычислить середину $c = \dfrac{a + b}{2}$ и значение $f(c)$.
3. Если $|f(c)| < \delta$ или длина отрезка $b - a < \varepsilon$ - принять $c$ за корень и остановиться.
4. Если $f(a)\cdot f(c) < 0$, положить $b := c$, иначе $a := c$.
5. Вернуться к шагу 2.

Каждая итерация требует ровно одного нового вычисления функции - в точке $c$. Знаки $f(a)$ и $f(b)$ уже известны с предыдущего шага, пересчитывать их не нужно. Это делает половинное деление дешёвым по числу обращений к $f$, что важно, когда вычисление функции дорогое.

Скорость сходимости и оценка числа итераций

После $n$ итераций длина отрезка локализации равна

$b_n - a_n = \frac{b - a}{2^{n}}.$

Если в качестве приближения корня брать середину текущего отрезка $c_n = \frac{a_n + b_n}{2}$, то погрешность ограничена половиной его длины:

$|c_n - x^{*}| \le \frac{b - a}{2^{n+1}}.$

Отсюда сразу следует оценка числа итераций для заданной точности $\varepsilon$. Потребовав $\frac{b - a}{2^{n+1}} \le \varepsilon$ и прологарифмировав, получаем

$n \ge \log_2\frac{b - a}{\varepsilon} - 1.$

Например, чтобы уточнить корень на отрезке единичной длины до $\varepsilon = 10^{-6}$, нужно около $\log_2(10^{6}) \approx 20$ итераций. Это линейная сходимость с множителем $\frac{1}{2}$: каждый шаг добавляет примерно $\log_{10} 2 \approx 0{,}3$ верного десятичного знака, то есть один новый знак - за каждые три-четыре итерации. Метод бисекции медленнее метода Ньютона (квадратичная сходимость) и метода секущих, но в отличие от них он сходится всегда, как бы плохо ни вело себя начальное приближение. Тесно связан с ним и метод простой итерации, где скорость, наоборот, целиком зависит от свойств итерационной функции.

Критерий остановки

Остановку метода половинного деления задают одним из трёх условий или их комбинацией:

• По длине отрезка: $b_n - a_n < \varepsilon$ - гарантирует, что корень локализован с точностью $\varepsilon$.
• По значению функции: $|f(c_n)| < \delta$ - приближение достаточно близко к нулю по вертикали.
• По числу итераций: жёсткий лимит $n_{\max}$ как страховка от зацикливания при численных артефактах.

Самый надёжный - критерий по длине отрезка: он не зависит от того, насколько круто или полого функция пересекает ось. Критерий $|f(c_n)| < \delta$ обманчив для пологих функций: значение $f$ может быть малым далеко от корня. Поэтому на практике комбинируют первый критерий с лимитом числа шагов.

Достоинства, недостатки и где применять

Сильные стороны метода бисекции - безусловная сходимость при выполнении $f(a)\cdot f(b) < 0$, отсутствие требований к производной и предсказуемое число шагов, которое известно заранее по формуле через $\log_2$. Слабые стороны - медленная линейная скорость, неспособность находить корни чётной кратности (где функция касается оси, но не меняет знак) и работа только с одним корнем на отрезке за раз.

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

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

• Запуск без проверки смены знака. Если $f(a)\cdot f(b) > 0$, теорема Больцано–Коши неприменима и метод бисекции работать не обязан - корня на отрезке может не быть либо их чётное число.
• Попытка найти корень чётной кратности. Там, где функция касается оси ($f$ не меняет знак, например $f(x) = (x-1)^2$), половинное деление бессильно - знаки на концах одинаковы.
• Критерий остановки только по $|f(c)|$. Для пологой функции малое $|f(c)|$ не означает близость к корню; надёжнее контролировать длину отрезка.
• Вычисление произведения $f(a)\cdot f(c)$ напрямую. При больших значениях функции возможно переполнение - сравнивайте знаки.
• Несколько корней на отрезке. Метод сойдётся лишь к одному из них (или к границе между парами), остальные потеряются - отрезок нужно дробить заранее.

FAQ

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

Сколько итераций нужно для заданной точности? Число шагов оценивается заранее: $n \ge \log_2\frac{b-a}{\varepsilon} - 1$. Для отрезка длины 1 и точности $10^{-6}$ это около 20 итераций - независимо от вида функции.

Можно ли применять метод к разрывной функции? Формально теорема о промежуточном значении требует непрерывности. У разрывной функции смена знака может означать не корень, а скачок через ось - метод выдаст точку разрыва вместо нуля. Перед применением проверяйте непрерывность на отрезке.

Коротко

Метод бисекции (половинного деления) находит корень уравнения $f(x) = 0$ на отрезке $[a, b]$, где функция меняет знак ($f(a)\cdot f(b) < 0$): отрезок последовательно делится пополам, и оставляется половина со сменой знака. Погрешность убывает как $\frac{b-a}{2^{n+1}}$, число итераций для точности $\varepsilon$ известно заранее из $n \ge \log_2\frac{b-a}{\varepsilon}-1$. Метод медленный (линейная сходимость), но абсолютно надёжный и не требует производной - поэтому его ценят как устойчивый старт перед быстрыми методами Ньютона или секущих.