 Bisection stopping criterion

For a requested absolute tolerance $\epsilon >0$, stop when the retained root bracket has width at most $2\epsilon$, and report its midpoint. The bisection error bound then guarantees $|m_k-x_{\ast }|\le \epsilon$ in exact arithmetic. Using the ceiling function and the base-two logarithm, the required number of halvings isThe zero allows stopping before any update when the initial root bracket is already sufficiently narrow. For the polynomial $f(x)=x^2-2$ on $[1,2]$ with $\epsilon =10^{-3}$, $k_{\min }=\lceil {\log }_{2}500\rceil =9$. After nine halvings,Thus the reported midpoint meets the tolerance; its actual error from the square root $\sqrt{2}$ is approximately $0.000825500126905$. After eight halvings the bound is $1/512>10^{-3}$, so eight do not give this worst-case guarantee.

Cache the endpoint values. Each update of the bisection method needs just one new function evaluation, at the old midpoint. With no early zero of a function, $k$ updates therefore cost $k+2$ function evaluations, including the two initial endpoints. Returning the new midpoint requires no additional function evaluation; requesting its value would add one. The nine-update example needs eleven evaluations for the guarantee.

A small function value $|f(m_k)|$ alone does not guarantee a small position error: rescaling $f$ changes those values without changing its zeros of a function. In a practical implementation, use an explicit width test and an iteration limit. With floating-point arithmetic, also stop if the computed midpoint equals either endpoint: the root bracket can no longer shrink, so repeating the update would loop forever. Report this precision limit separately if the requested tolerance remains unmet. Reliable sign evaluations are needed to preserve the root bracket; compare signs directly rather than multiplying endpoint values, which can suffer overflow or underflow in floating-point arithmetic.

For a rounded midpoint $m$ still inside a valid root bracket, the geometric error bound is $\max \{m-a_k,b_k-m\}$; it need not equal $W_k/2$ because of roundoff error. A rigorous computed enclosure also needs conservative arithmetic for that bound and reliable endpoint signs. The exact-arithmetic bisection error bound should not be claimed unchanged after precision prevents further halving.

For practical tolerance conventions, SciPy's bisect combines absolute and relative tolerances through $|x-x_0|\le \mathrm{xtol}+\mathrm{rtol}|x_0|$, and provides a maximum iteration count and convergence status. These differ from the purely absolute width test above.^[ref]