Bracketing method

A bracketing method finds a zero of a function by maintaining a root bracket and shrinking it as new values of the function become available. The bisection method always tries the midpoint; its special attraction is a predictable bisection error bound without any derivative evaluations.

A root bracket is a closed interval known to contain at least one zero of a function. For a real-valued continuous function on $[a,b]$, a strict change of sign between $f(a)$ and $f(b)$ certifies such an enclosure by the intermediate value theorem. An endpoint with value zero already supplies a zero of a function. For example, $[1,2]$ is a root bracket for the polynomial $f(x)=x^2-2$, since $f(1)=-1$ and $f(2)=2$. A root bracket need not contain a unique zero of a function.

The bisection method finds a zero of a function by repeatedly halving a root bracket. Let $f$ be a real-valued continuous function on the closed interval $[a,b]$, with $a<b$. First check for endpoint zeros of a function; otherwise require strictly opposite signs at the endpoints. Evaluate the midpoint and retain the half with strictly opposite endpoint signs, stopping immediately if the midpoint is a zero of a function. The intermediate value theorem ensures that every retained root bracket still contains a zero of a function. This is the construction in MIT's root-finding notes.^[ref]

For a worked square root calculation, use the polynomial $f(x)=x^2-2$ on $[1,2]$. Write $[a_k,b_k]$ for the root bracket after $k$ halvings, with $[a_0,b_0]=[1,2]$. The candidate evaluated during update $k$ is the old midpoint $m_{k-1}$:The initial midpoint is $m_0=1.5$. After four halvings the new midpoint is $m_4=1.40625$, and the bisection error bound is $|m_4-\sqrt{2}|\le 0.03125$. Its actual error is approximately $0.00796356237310$. The last tested candidate $m_3=1.4375$ and the reported midpoint $m_4$ are different points.

The useful feature of the bisection method is that the retained width halves on every update, independently of the shape of the function graph. The bisection error bound therefore supplies an accuracy guarantee before the zero of a function is known. No derivative is needed, and a valid initial root bracket gives convergence without a close initial guess. This makes the bisection method a dependable fallback for the faster Newton root-finding iteration.

The bisection method preserves some root in a sign-changing bracket but does not select a fixed root when several are present. For the displayed polynomial, endpoint and midpoint roots are returned immediately. If $2<b<3$, the first midpoint lies in $(1/2,1)$ with negative function value, so the retained bracket contains only zero. If $b=3$, the first midpoint is exactly one. If $3<b\le 4$, that midpoint lies in $(1,3/2]$ with positive function value, so the retained bracket contains only two. At $b=2$ the right endpoint itself is the root two.

Thus arbitrarily small changes of the initial endpoint across $b=3$ change the limiting root from zero to two, with one selected exactly at the transition. The guarantee concerns distance to a root inside the retained interval, rather than continuous dependence of that root's identity on the starting data.

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.

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]

Several zeros of a function can lie in one initial root bracket: the bisection method seeks one, rather than enumerating them. For instance, the polynomial $(x-1)(x-2)(x-3)$ has opposite endpoint signs on $[0,4]$, but its first midpoint evaluation returns only the polynomial root $2$. The initial zero of a function need not be unique for the bisection error bound to apply to a retained zero of a function.

A zero of a function without a sign change cannot be located by the strict sign-change test alone. The polynomial $(x-1{)}^2$ touches zero at $1$ but is positive on either side. On $[0,3]$ both endpoint values are positive: although the closed interval contains a polynomial root, it fails the usual starting test for the bisection method. An endpoint or evaluated midpoint zero of a function can still be recognized directly.

Opposite signs certify a root bracket only with the required continuity. For $f(x)=1/x$, the values at $-1$ and $1$ have opposite signs, but $f$ is undefined at the midpoint $0$ and has no zero of a function. Hence $[-1,1]$ is invalid input for the bisection method; the intermediate value theorem does not apply across the gap.