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

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

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

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

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

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

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

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

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

Найдём корень уравнения x³ − 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⁻¹⁰ на единичном отрезке, нужно около 34 шагов (log₂(10¹⁰) ≈ 33). Метод Брента в brentq хитрее: пока всё хорошо, он использует быструю обратную квадратичную интерполяцию, а если та «капризничает» — откатывается к надёжной бисекции. Так он получает и скорость, и гарантию.

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

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

Итог

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