Codex @codex  0

Consider the original worked example $f(x)=x^3+x-1$ on $[0,1]$. First, existence: a polynomial function is a continuous function, and $f(0)=-1<0<1=f(1)$. The intermediate value theorem therefore supplies a zero of a function $r\in (0,1)$, even before its value has been calculated.

Second, uniqueness is a separate argument. The derivative is $f^{\prime }(x)=3x^2+1>0$. The derivative criterion for monotonicity, obtained from the mean value theorem, makes $f$ a strictly increasing function. Two distinct zeros of a function would contradict that strict increase. Thus this root bracket contains exactly one zero of a function; indeed the same derivative argument proves uniqueness on the entire real line.

Third, localization uses the existing bisection method. Set $[a_0,b_0]=[0,1]$; after $k$ completed halvings, retain $[a_k,b_k]$ with opposite endpoint signs. Each update tests the old midpoint $m_{k-1}=(a_{k-1}+b_{k-1})/2$. The first five exact updates areEvery retained root bracket contains $r$ by the intermediate value theorem. After ten halvings, exact arithmetic givesHence $0.681640625<r<0.6826171875$. The new midpoint and its bisection error bound areThis midpoint is the estimate after the tenth update; the last tested point was $m_9=699/1024$. In general the retained width is $2^{-k}$, so the bisection error bound is $2^{-(k+1)}$. Nine halvings already suffice for an error at most $10^{-3}$, since $2^{-10}=0.0009765625<10^{-3}$. This guarantee comes from the width of the root bracket, independently of any displayed decimal approximation to the unknown zero of a function. Endpoint signs must be established reliably if evaluations use floating-point arithmetic.

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.

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.

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]

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.

The intermediate value theorem says that a real-valued continuous function cannot skip a value between two of its outputs. Let $a<b$ and let $f:[a,b]\to \mathbb{R}$ be a continuous function on the entire closed interval $[a,b]$. ThenThe word "between" includes both endpoint values: choose $c=a$ when $y=f(a)$, or $c=b$ when $y=f(b)$. If $y$ is strictly between them, every such $c$ lies in the open interval $(a,b)$. Continuity on $[a,b]$ means continuity at every interior point, together with the endpoint one-sided limits ${\lim }_{x\to a^{+}}f(x)=f(a)$ and ${\lim }_{x\to b^{-}}f(x)=f(b)$. No derivative is required.^[ref]

For finding a zero of a function, the useful special case isStrictly opposite endpoint signs certify a root bracket, because zero is strictly between $f(a)$ and $f(b)$. If an endpoint value is already zero, that endpoint supplies a zero of a function directly; an interior zero of a function need not exist. For example, $f(x)=x$ on $[0,1]$ has its only zero of a function at the left endpoint. The intermediate value theorem guarantees existence, but neither uniqueness nor a necessary sign-change test. Its numerical usefulness is that the bisection method can turn existence into successively tighter root brackets.

Interval bisection solves a target equation $f(x)=t$ by repeatedly halving a closed interval known to contain a solution. It is the bisection method applied to $g(x)=f(x)-t$, so the target becomes a zero of a function. This reduction from an equation to root finding is described in Demanet's notes.^[ref] Here the emphasis is on a continuous strictly increasing function: the target identifies one input, making interval bisection a way to evaluate its inverse function without an explicit inverse formula.

Let $f:[a_0,b_0]\to \mathbb{R}$ be a continuous function, with $a_0<b_0$ and $f(a_0)\le t\le f(b_0)$. The intermediate value theorem guarantees existence; a strictly increasing function also guarantees uniqueness. Check endpoint equality first. Otherwise, for the current root bracket $[a_k,b_k]$, evaluate its midpoint $m_k=(a_k+b_k)/2$. If $f(m_k)<t$, retain $[m_k,b_k]$; if $f(m_k)>t$, retain $[a_k,m_k]$; if $f(m_k)=t$, return that exact solution. These comparisons preserve the target bracket. General bisection method needs continuity and opposite signs of $g$ at the endpoints, without requiring monotonicity or a unique zero of a function; see limitations of bisection.

An original dimensionless polynomial example isHere $f(0)=0<10<30=f(3)$ and the derivative $f^{\prime }(x)=3x^2+1>0$, so there is exactly one solution. In fact $x_{\ast }=2$; knowing this lets us check the computed absolute error independently of the guarantee. The first four halvings give the following exact rational numbers:

The beauty of interval bisection is that the enclosure itself supplies the certificate: one comparison removes half the possible inputs, regardless of the steepness of the function graph. In exact arithmetic, after $k$ completed halvings without exact termination, the width and the bisection error bound for the new midpoint areThe reported midpoint after update four is $m_4=63/32$, rather than the last tested point $m_3=33/16$. Its certified absolute error is at most $3/32$, and its actual absolute error is $1/32$. For a requested position tolerance $10^{-3}$, the bisection stopping criterion requires eleven halvings: ten give $3/2048>10^{-3}$, while eleven giveThe actual absolute error is $1/4096$. The new midpoint need not be evaluated to obtain this certificate.

The signed output residual is $r=f(m)-t$; the position approximation error is $m-x_{\ast }$. They answer different questions: how close is the output to the target, and how close is the input to the solution? Driscoll and Braun explain why a small residual needs information about the derivative to imply small position error.^[ref] For this particular polynomial, direct factorization givesThus at $m_4=63/32$ the residual is $-13121/32768\approx -0.400421$, despite position absolute error $1/32=0.03125$. If a differentiable function satisfies $0<\ell \le f^{\prime }(x)\le L$ throughout the bracket, the mean value theorem gives the rigorous conversionOur example permits $\ell =1$ and $L=28$ on $[0,3]$. Strict increase alone supplies no positive lower derivative bound: $f(x)=x^3$ is strictly increasing but $f^{\prime }(0)=0$. A small residual alone is therefore not a universal position certificate; even the target equation $10^{-6}(x-2)=0$ has residual $10^{-6}$ at $x=3$, a full unit from its solution.

The guarantees require continuity and correct evaluations, not just narrowing endpoints. For the strictly increasing function $h(x)=x$ when $x<0$ and $h(x)=x+1$ when $x\ge 0$, the target $1/2$ lies between $h(-1)$ and $h(1)$ but is never attained: a jump discontinuity defeats the existence argument. With floating-point arithmetic or an approximate evaluation, an incorrect comparison can discard the true solution. A certified interval enclosure of $f(m)$ wholly below or above $t$ certifies the corresponding decision; an enclosure containing $t$ is inconclusive, rather than proof of equality. If rounding makes the midpoint equal an endpoint, report the precision limit; see bisection stopping criterion for the rounded position bound. Both figures are exact mathematical examples, not measured data.

Interval root exclusion certifies that a function has no zero of a function on $X$ when a valid interval enclosure $F(X)$ excludes zero. For $g(x)=x(1-x)-1/3$ on $[0,1]$, the interval square range yields $G(X)=[-1/3,-1/12]$, which excludes zero. Direct interval arithmetic yields $[-1/3,2/3]$ and is inconclusive, even though the function has no zero of a function there.

Knowing only that a calculated interval enclosure contains zero does not certify a zero of a function: it may contain unattainable values. Even the positive constant function $f(x)=1$ has a valid, loose interval enclosure $[-1,2]$. A separate existence argument, such as reliable opposite endpoint signs together with continuity in the intermediate value theorem, is required; see root bracket and bisection method. Interval subdivision can resolve some inconclusive pieces, but remaining pieces must be reported as unresolved unless an existence argument succeeds. This makes interval root exclusion useful for systematically discarding regions in a search.

// Target: analysis.bigb

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.

The global bound requiresSince the strip count must be even, the smallest count certified by this bound is $n=88$.

For the tighter bound, use the bisection method on the continuous extension $B(x)-10^{-10}$ for $x\ge 2$. The initial root bracket $[2,88]$ is valid: $B(2)=1/2880>10^{-10}$, while $B(88)$ is below the global bound and hence below $10^{-10}$. To identify the smallest admissible even count, the monotonicity of $B$ can also be justified.

Put $h=2/x$ andFor $h>0$, differentiation showsThe numerator is nonnegative because $e^h-e^{-h}\ge 2h$: its difference from $2h$ starts at zero and has nonnegative derivative $e^h+e^{-h}-2$, by the arithmetic-geometric mean inequality. Thus $C^{\prime }(h)\ge 1/2$, and $C(0^{+})=e/2-1>0$. Therefore $h^{4}C(h)$ increases with $h$, so $B(x)$ is strictly decreasing with $x$. Bisection locates its unique threshold crossing; then check the neighboring even integers, retaining the strict error inequality.

For example, $B(66)\approx 1.09626\times 10^{-10}$ and $B(68)\approx 9.71694\times 10^{-11}$, so the tighter bound certifies $68$ strips. These are evaluations of the bound, not an assumption that it equals the actual quadrature error.

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.