Поиск корней: бисекция

Где функция пересекает ноль? Самый надёжный способ найти корень — делить отрезок пополам.

Корень уравнения $f(x) = 0$ — это значение $x$, при котором функция обращается в ноль (график пересекает ось абсцисс).

Зачем искать корни

К уравнению $f(x) = 0$ сводится масса задач: «при какой температуре реакция остановится», «при какой ставке кредит окупится», «где траектория пересечёт землю». Часто аналитически решить нельзя (например, $x = \cos(x)$), и тогда корень ищут численно.

Идея бисекции

Если функция непрерывна и на концах отрезка $[a, b]$ имеет разные знаки ($f(a) \cdot f(b) \lt 0$), то по теореме о промежуточном значении где-то внутри есть корень. Делим отрезок пополам, смотрим знак в середине — и оставляем ту половину, где смена знака сохраняется. Отрезок сжимается вдвое за шаг, корень зажимается всё точнее.

a────────●────────b      f(a)<0, f(b)>0
         mid
проверяем знак f(mid), оставляем половину со сменой знака
a───●────b               и снова делим

Реализация на чистом Python

Найдём корень уравнения $x^3 - x - 2 = 0$ на отрезке $[1, 2]$:

def f(x):
    return x**3 - x - 2

a, b = 1.0, 2.0
assert f(a) * f(b) < 0          # знаки разные — корень внутри

for _ in range(40):
    mid = (a + b) / 2
    if f(a) * f(mid) <= 0:
        b = mid                 # корень в левой половине
    else:
        a = mid                 # корень в правой половине

root = (a + b) / 2
print("Корень  :", round(root, 8))
print("Проверка: f(корня) =", round(f(root), 8))

Вывод:

Корень  : 1.52137971
Проверка: f(корня) = 0.0

А в SciPy — одна строка

from scipy.optimize import brentq

root = brentq(lambda x: x**3 - x - 2, 1, 2)
print(root)   # 1.5213797068045676

brentq — это метод Брента: он сочетает надёжность бисекции со скоростью более умных методов. Гарантированно сходится, если на концах разные знаки.

Как работает под капотом

Бисекция надёжна как скала: она не может разойтись, потому что отрезок с корнем всегда сжимается. Цена надёжности — скорость: за каждый шаг точность улучшается ровно в 2 раза (линейная сходимость). Чтобы зажать корень до $10^{-10}$ на единичном отрезке, нужно около 34 шагов ($\log_2(10^{10}) \approx 33$). Метод Брента в brentq хитрее: пока всё хорошо, он использует быструю обратную квадратичную интерполяцию, а если та «капризничает» — откатывается к надёжной бисекции. Так он получает и скорость, и гарантию.

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

Одинаковые знаки на концах. Если $f(a) \cdot f(b) \gt 0$, бисекция неприменима — корня в отрезке может не быть (или быть чётное число).
Разрыв функции. Метод предполагает непрерывность; на разрыве «смена знака» обманет — найдётся полюс, а не корень.
Слишком широкий отрезок с несколькими корнями. Бисекция найдёт какой-то один; чтобы найти все, отрезок дробят.

Итог

Бисекция ищет корень, зажимая отрезок со сменой знака.
Требует $f(a) \cdot f(b) \lt 0$ и непрерывности; зато не расходится никогда.
Сходится линейно (точность ×2 за шаг) — надёжно, но небыстро.
В SciPy надёжный выбор — brentq (метод Брента: скорость + гарантия).