Метод бисекции: медленно, но надёжно

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

Метод бисекции ищет корень $f(x)=0$ на отрезке $[a,b]$, где $f(a)$ и $f(b)$ разных знаков, многократно деля отрезок пополам и оставляя половину, на концах которой знаки по-прежнему разные.

Идея: ловушка для корня

Пусть f непрерывна и на концах отрезка имеет разные знаки: $f(a) \lt 0$, $f(b) \gt 0$. По теореме о промежуточном значении где-то внутри есть точка, где $f = 0$ — корень пойман в «ловушку» $[a,b]$. Берём середину $c = (a+b)/2$. Если знак $f(c)$ совпал с $f(a)$ — корень в правой половине, сдвигаем $a = c$. Иначе — в левой, $b = c$. Ловушка сжалась вдвое, корень по-прежнему внутри. Повторяем, пока отрезок не станет короче нужной точности.

Главное достоинство: гарантия. Если условие разных знаков выполнено, метод обязательно сойдётся к корню — никаких «а вдруг разойдётся». Цена — скорость: за шаг добавляется ровно один двоичный разряд точности.

def бисекция(f, a, b, eps=1e-10):
    fa = f(a)
    if fa * f(b) > 0:
        raise ValueError("на концах одинаковые знаки — корень не пойман")
    шаг = 0
    while (b - a) / 2 > eps:
        c = (a + b) / 2
        fc = f(c)
        шаг += 1
        if шаг <= 6:
            print(f"шаг {шаг}: [{a:.6f}, {b:.6f}]  c={c:.6f}  f(c)={fc:+.6f}")
        if fa * fc < 0:
            b = c                 # корень слева от c
        else:
            a, fa = c, fc         # корень справа от c
    return (a + b) / 2

import math
# Ищем sqrt(2): корень x^2 - 2 = 0 на [1, 2]
корень = бисекция(lambda x: x * x - 2, 1.0, 2.0)
print(f"\nкорень = {корень:.10f}")
print(f"sqrt(2) = {math.sqrt(2):.10f}")

Вывод:

шаг 1: [1.000000, 2.000000]  c=1.500000  f(c)=+0.250000
шаг 2: [1.000000, 1.500000]  c=1.250000  f(c)=-0.437500
шаг 3: [1.250000, 1.500000]  c=1.375000  f(c)=-0.109375
шаг 4: [1.375000, 1.500000]  c=1.437500  f(c)=+0.066406
шаг 5: [1.375000, 1.437500]  c=1.406250  f(c)=-0.022461
шаг 6: [1.406250, 1.437500]  c=1.421875  f(c)=+0.021729

корень = 1.4142135623
sqrt(2) = 1.4142135624

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

После $n$ шагов длина отрезка равна $(b-a)/2^n$. Чтобы погрешность стала меньше $\varepsilon$, нужно примерно $n = \log_2((b-a)/\varepsilon)$ шагов. Для $\varepsilon = 10^{-10}$ и единичного отрезка это около 34 шагов — каждый добавляет ~0.3 десятичной цифры. Это линейная сходимость: ошибка убывает как геометрическая прогрессия со знаменателем $1/2$. Надёжно, но небыстро — методы Ньютона и секущих на гладких функциях обгоняют бисекцию в разы.

[a========================b]   корень где-то внутри (разные знаки)
[a===========c]                делим пополам, смотрим знак f(c)
[a=====c]                      оставляем половину с разными знаками
[a==c]                         и снова...
 каждый шаг = +1 двоичный разряд точности (надёжно, но медленно)

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

Важная тонкость — критерий остановки. Останавливаться нужно по длине отрезка $(b-a)/2 \lt \varepsilon$, а не по $|f(c)| \lt \varepsilon$: у пологих функций f может быть мала далеко от корня, а у крутых — велика рядом с ним. Ещё одна тонкость — проверка знака: вместо $f(a) \cdot f(c) \lt 0$ в промышленном коде используют сравнение знаков (через math.copysign), чтобы произведение двух больших значений не переполнилось. Наконец, бисекция требует, чтобы корень был нечётной кратности (функция реально пересекала ось, а не касалась её) — иначе знаки на концах не различаются.

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

Запуск без проверки знаков. Если $f(a)$ и $f(b)$ одного знака, корень не пойман — метод не имеет смысла. Всегда проверяйте $f(a) \cdot f(b) \lt 0$.
Остановка по $|f(c)|$. Для устойчивости останавливайтесь по длине отрезка — она напрямую ограничивает ошибку корня.
Ожидать корень чётной кратности. У $(x-1)^2 = 0$ знаки на концах одинаковые — бисекция бессильна, нужны другие методы.

Итоги

Бисекция гарантированно находит корень непрерывной функции при разных знаках на концах отрезка.
Сходимость линейная: +1 двоичный разряд за шаг, $n \approx \log_2((b-a)/\varepsilon)$.
Останавливаться нужно по длине отрезка, а не по значению $|f(c)|$.
Метод надёжен, но медленнее Ньютона/секущих; часто его берут как страховку или старт.