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

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

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

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

Пусть f непрерывна и на концах отрезка имеет разные знаки: f(a) < 0, f(b) > 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. Чтобы погрешность стала меньше eps, нужно примерно n = log2((b−a)/eps) шагов. Для eps = 10^-10 и единичного отрезка это около 34 шагов — каждый добавляет ~0.3 десятичной цифры. Это линейная сходимость: ошибка убывает как геометрическая прогрессия со знаменателем 1/2. Надёжно, но небыстро — методы Ньютона и секущих на гладких функциях обгоняют бисекцию в разы.

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

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

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

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

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

Итоги

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