Interval bisection and linear interpolationEdexcel International A Level Further Maths: Revision notes

To solve $f(x)=0$ numerically, first show that a root exists in an interval $[a,b]$. If $f$ is continuous on $[a,b]$ and $f(a)$ and $f(b)$ have opposite signs, then $f(x)=0$ has at least one root in $[a,b]$. Example: $f(x)=x^3+2x-7$ has $f(1)=-4$ and $f(2)=5$, so there is a root in $[1,2]$. In an answer, state the two values, the sign change and continuity. The test can fail:

• if $f$ is not continuous, e.g. $f(x)=\frac{1}{x-2}$ on $[1,3]$ changes sign but never equals zero;
• if a root is a repeated root, e.g. $(x-2)^2$ touches the axis without a sign change, so a root can be missed.

Interval bisection repeatedly halves an interval that contains a root.

1. Find the midpoint $m=\frac{a+b}{2}$ and evaluate $f(m)$.
2. If $f(m)$ has the same sign as $f(a)$, the root is in $[m,b]$; otherwise it is in $[a,m]$.
3. Repeat.

Example: $f(x)=x^3+2x-7$, root in $[1,2]$. $f(1.5)=-0.625<0$, so the root is in $[1.5,2]$. $f(1.75)=1.859>0$, so the root is in $[1.5,1.75]$. After $n$ bisections the interval has width $\frac{b-a}{2^n}$. It is reliable, but slow: roughly three or four bisections for each extra decimal place.

Linear interpolation replaces the curve on $[a,b]$ by the straight line through $(a,f(a))$ and $(b,f(b))$, and takes where it meets the $x$-axis as the next estimate. By similar triangles, with $f(a)<0<f(b)$: $\frac{x-a}{|f(a)|}=\frac{b-x}{|f(b)|}\quad\Rightarrow\quad x=a+\frac{|f(a)|}{|f(a)|+|f(b)|}(b-a).$ Example: $f(x)=x^3+x-5$ with $f(1)=-3$ and $f(2)=5$: $x=1+\frac{3}{8}=1.375$. Then $f(1.375)=-1.025<0$, so use $[1.375,2]$: $x=1.375+\frac{1.0254}{1.0254+5}(0.625)=1.481.$ Each time, use the sign of $f$ at the new estimate to choose the next interval.

Linear interpolation is usually faster than bisection when the curve is nearly straight on the interval, but its estimate can lie on one side of the root. To check that a root is correct to a stated accuracy, find the interval of half the final unit either side, e.g. to prove $\alpha=2.208$ to 3 d.p., show $f(2.2075)$ and $f(2.2085)$ have opposite signs. Remember that these methods find a root in an interval, not all roots: choose intervals with one sign change, and work in radians if $f$ involves trigonometry.