Метод половинного деления

Детская игра «угадай число от одного до ста» решается за семь вопросов, если после каждого ответа вычёркивать половину оставшегося: $2^7=128>100$. Метод половинного деления играет ту же игру с уравнением. Если $f$ непрерывна и на концах отрезка $[a,b]$ имеет разные знаки, внутри лежит корень; берём середину $c=(a+b)/2$, смотрим знак $f(c)$ и оставляем ту половину, где знак меняется. Корень зажат, интервал сжимается вдвое, гарантия абсолютная — не нужно ничего, кроме непрерывности и смены знака.

Пример: $f(x)=x^3-x-2$ на $[1,2]$, значения $-2$ и $4$. Середина $1.5$: $f(1.5)=-0.125$ — корень справа. Середина $1.75$: $f(1.75)=1.609$ — корень слева. После $n$ делений корень сидит в отрезке длины $(b-a)/2^n$; для точности $0.01$ здесь хватит семи шагов, ведь $1/128\approx 0.0078<0.01$. Настоящий корень $\approx 1.5214$. Медленно? Да: линейная сходимость с $q=1/2$. Зато непробиваемо — поэтому бисекцией часто надёжно подготавливают старт для быстрых методов; сборка методов — в уроке решение нелинейных уравнений, рамка — в терминах итерационный метод, цена ошибок — в источниках погрешностей.