= Bisection stopping criterion
{title2=$W_k/2\leq\varepsilon$}
For a requested absolute tolerance $\varepsilon>0$, stop when the retained <root bracket> has width at most $2\varepsilon$, and report its <midpoint>. The <bisection error bound> then guarantees $|m_k-x_*|\leq\varepsilon$ in exact arithmetic. Using the <ceiling function> and the base-two <logarithm>, the required number of halvings is
$$
k_{\min}=\max\left\{0,\left\lceil\log_2\frac{b-a}{2\varepsilon}\right\rceil\right\}.
$$
The 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 $\varepsilon=10^{-3}$, $k_{\min}=\lceil\log_2 500\rceil=9$. After nine halvings,
$$
[a_9,b_9]=[1.4140625,1.416015625],\qquad m_9=1.4150390625,\qquad \frac{W_9}{2}=\frac{1}{1024}=0.0009765625.
$$
Thus the reported <midpoint> meets the tolerance; its actual error from the <square root> $\sqrt2$ 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|\leq\mathrm{xtol}+\mathrm{rtol}|x_0|$, and provides a maximum iteration count and convergence status. These differ from the purely absolute width test above.https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.bisect.html[SciPy, scipy.optimize.bisect documentation]{ref}
Back to article page
