GuideNonlinear equationsbasic

Bisection method

The most robust method: halve the interval bracketing the root and keep the half where the sign changes. Explicit error bound and guaranteed convergence.

The idea: bracket the root

Bisection algorithm

Compute the midpoint $m_k=\frac{a_k+b_k}{2}$ of the current interval.
If $f(a_k)\,f(m_k)<0$ , the root is in the left half: the new interval is $[a_k,m_k]$ . Otherwise it is in $[m_k,b_k]$ . (If $f(m_k)=0$ , the exact root has been found.)
Repeat until the interval length (or $|f(m_k)|$ ) drops below the tolerance. The approximation is the last midpoint.

Error bound and speed

DerivationDerivation: bisection error boundView as its own page →

After $k$ bisections, the interval $[a_k,b_k]$ still contains the root and is half the size of the previous one:
$b_k-a_k=\frac{b-a}{2^k}$
The approximation is the midpoint $m_k$ , and the root lies in one of the two halves, at distance at most half the interval:
$|m_k-\alpha|\le\frac{b_k-a_k}{2}=\frac{b-a}{2^{k+1}}$
To guarantee $|m_k-\alpha|<\varepsilon$ , solve for $k$ in $\frac{b-a}{2^{k+1}}<\varepsilon$ : the number of iterations is known before starting, something no other method in this area offers.
$k>\log_2\!\left(\frac{b-a}{\varepsilon}\right)-1$

Each iteration gains one bit of precision (halves the error), which amounts to one decimal digit every $\log_2 10\approx 3.3$ iterations. It is slow compared with Newton, but it requires no derivatives, only continuity and a sign change, and it does not diverge. Use it to locate the root and hand a reliable initial estimate to a fast method.