 Bisection error bound

In exact arithmetic, after $k$ completed halvings the retained root bracket has width $W_k=b_k-a_k$ and midpoint $m_k$, whereThe absolute value bound holds for every zero of a function $x_{\ast }$ 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\ge 1$, 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)$.

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-\sqrt{2}|\approx 0.000151062$ to $|m_7-\sqrt{2}|\approx 0.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 $\sqrt{2}$ 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.