= Interval bisection
<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.https://ocw.mit.edu/courses/18-330-introduction-to-numerical-analysis-spring-2012/5b325bfa56a599794c7196de926844b0_MIT18_330S12_Chapter4.pdf[Laurent Demanet, MIT 18.330, Chapter 4, §4.1, pp. 1–2, 2012]{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)\leq t\leq 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 is
$$
f(x)=x^3+x,\qquad t=10,\qquad [a_0,b_0]=[0,3].
$$
Here $f(0)=0<10<30=f(3)$ and the <derivative> $f'(x)=3x^2+1>0$, so there is exactly one solution. In fact $x_*=2$; knowing this lets us check the computed <absolute error> independently of the guarantee. The first four halvings give the following exact <rational numbers>:
$$
\begin{array}{c|c|r|c}
\text{update }k&\text{tested }m_{k-1}&f(m_{k-1})-10&\text{retained }[a_k,b_k]\\\hline
1&3/2&-41/8&[3/2,3]\\
2&9/4&233/64&[3/2,9/4]\\
3&15/8&-785/512&[15/8,9/4]\\
4&33/16&3425/4096&[15/8,33/16]
\end{array}
$$
\Image[/interval-bisection-cubic-target-brackets.png]
{title=Finding the input for a target output: cubic graph and four retained brackets}
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> are
$$
W_k=b_k-a_k=\frac{3}{2^k},\qquad |m_k-x_*|\leq\frac{W_k}{2}=\frac{3}{2^{k+1}}.
$$
The 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 give
$$
[a_{11},b_{11}]=[4095/2048,2049/1024],\qquad m_{11}=8193/4096,\qquad |m_{11}-2|\leq3/4096<10^{-3}.
$$
The actual <absolute error> is $1/4096$. The new <midpoint> need not be evaluated to obtain this certificate.
The signed \b[output residual] is $r=f(m)-t$; the position <approximation error> is $m-x_*$. 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.https://fncbook.com/rootproblem/[Toby A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation, §4.1.1, Conditioning, error, and residual]{ref} For this particular <polynomial>, direct factorization gives
$$
f(m)-10=(m-2)(m^2+2m+5).
$$
Thus 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\leq f'(x)\leq L$ throughout the bracket, the <mean value theorem> gives the rigorous conversion
$$
\ell|m-x_*|\leq|f(m)-t|\leq L|m-x_*|.
$$
Our 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'(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.
\Image[/interval-bisection-position-output-errors.png]
{title=Certified position error and output residual measure different distances}
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\geq0$, 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.
Back to article page
