= Bisection error bound
{title2=$|m_k-x_*|\leq(b-a)/2^{k+1}$}
In exact arithmetic, after $k$ completed halvings the retained <root bracket> has width $W_k=b_k-a_k$ and <midpoint> $m_k$, where
$$
W_k=\frac{b-a}{2^k},\qquad m_k=\frac{a_k+b_k}{2},\qquad |m_k-x_*|\leq\frac{W_k}{2}=\frac{b-a}{2^{k+1}}.
$$
The <absolute value> bound holds for every <zero of a function> $x_*$ in the current <root bracket>, including the one approached by continued <bisection method> updates. A <zero of a function> discarded with an earlier half need not satisfy later bounds. Before update $k\geq1$, the evaluated candidate is $m_{k-1}$, whose corresponding guarantee is $(b-a)/2^k$. After update $k$, the new <midpoint> $m_k$ has the smaller guarantee $(b-a)/2^{k+1}$, even without evaluating $f(m_k)$.
\Image[/bisection-error-halving.png]
{title=Bisection widths, midpoint error bounds, and actual square-root errors after zero to fifteen halvings}
The guaranteed error halves at every step; the actual <absolute value> error need not decrease at every step or have successive ratio $1/2$. In the <square root> example it increases from $|m_6-\sqrt2|\approx0.000151062$ to $|m_7-\sqrt2|\approx0.003755188$, while both errors remain below their guarantees. An exact <midpoint> <zero of a function> instead gives zero error and immediate termination. For this example $\sqrt2$ is an <irrational number>, so no finite exact halving can produce it as a <midpoint>.
For a brief proof outline, each retained half has half the previous width and contains a <zero of a function> by the <intermediate value theorem>. Every point in the retained <root bracket> is at most half its width from its <midpoint>. If the process does not stop at a <zero of a function>, the <nested interval theorem> gives one common point as the widths tend to zero; <continuity> and the opposite endpoint signs force its <function> value to be zero. Uniqueness in the initial <root bracket> is unnecessary.
Back to article page
