= A cubic root from existence to a quantitative bracket
{title2=$f(x)=x^3+x-1$}
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'(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 are
$$
\begin{array}{c|c|r|c}
k&\text{tested }m_{k-1}&f(m_{k-1})&\text{retained }[a_k,b_k]\\\hline
1&1/2&-3/8&[1/2,1]\\
2&3/4&11/64&[1/2,3/4]\\
3&5/8&-67/512&[5/8,3/4]\\
4&11/16&51/4096&[5/8,11/16]\\
5&21/32&-2003/32768&[21/32,11/16]
\end{array}
$$
Every retained <root bracket> contains $r$ by the <intermediate value theorem>. After ten halvings, exact arithmetic gives
$$
a_{10}=\frac{349}{512},\qquad b_{10}=\frac{699}{1024},\qquad
f(a_{10})=-\frac{220923}{134217728}<0,
\qquad f(b_{10})=\frac{744899}{1073741824}>0.
$$
Hence $0.681640625<r<0.6826171875$. The new <midpoint> and its <bisection error bound> are
$$
m_{10}=\frac{1397}{2048}=0.68212890625,\qquad
|m_{10}-r|\leq\frac{1}{2048}=0.00048828125.
$$
This <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>.
\Image[/intermediate-value-cubic-nested-root-brackets.png]
{title=The cubic x cubed plus x minus one: its unique root and the first five nested bisection brackets}
Back to article page
