MA005: Calculus I

(i) Find two values of $x$, say a and $b$, so that $f(a)$ and $f(b)$ have opposite signs (then $\mathrm{f}(\mathrm{x})$ has a root between a and $\mathrm{b}$, a root in the interval $[\mathrm{a}, \mathrm{b}]$).

(ii) Calculate the midpoint (bisection point) of the interval $[a, b], m=(a+b) / 2$, and evaluate $\mathrm{f}(\mathrm{m})$.

(iii) (a) If $\mathrm{f}(\mathrm{m})=0$, then $\mathrm{m}$ is a root of $\mathrm{f}$, and we are done.

(b) If $f(m) \neq 0$, then $f(m)$ has the sign opposite one of $f(a)$ or $f(b)$ :

if $\mathrm{f}(\mathrm{a})$ and $\mathrm{f}(\mathrm{m})$ have opposite signs, then $\mathrm{f}$ has a root in $[\mathrm{a}, \mathrm{m}]$ so put $\mathrm{b}=\mathrm{m}$

if $\mathrm{f}(\mathrm{b})$ and $\mathrm{f}(\mathrm{m})$ have opposite signs, then $\mathrm{f}$ has a root in $[\mathrm{m}, \mathrm{b}]$ so put $\mathrm{a}=\mathrm{m}$

(iv) Repeat steps (ii) and (iii) until a root is found exactly or is approximated closely enough.

The length of the interval known to contain a root is cut in half each time through steps (ii) and (iii) so the Bisection Algorithm quickly "squeezes" in on a root (Fig. 10).

The steps of the Bisection Algorithm can be done "by hand", but it is tedious to do very many of them that way. Computers are very good with this type of tedious repetition, and the algorithm is simple to program.

Example 7: Find a root of $f(x)=x-x^{3}+1$.

Solution: $\mathrm{f}(0)=1$ and $\mathrm{f}(1)=1$ so we cannot conclude that $\mathrm{f}$ has a root between 0 and 1. $f(1)=1$ and $f(2)=-5$ have opposite signs, so by the Intermediate Value Property of continuous functions (this function is a polynomial so it is continuous everywhere) we know that there is a number $c$ between 1 and 2 such that $\mathrm{f}(\mathrm{c})=0$ (Fig. 11). The midpoint of the interval $[1,2]$ is $m=(1+2) / 2=3 / 2=1.5$, and $f(3 / 2)=-7 / 8$ so $\mathrm{f}$ changes sign between 1 and $1.5$ and we can be sure that there is a root between 1 and $1.5$. If we repeat the operation for the interval $[1,1.5]$, the midpoint is $\mathrm{m}=(1+1.5) / 2=1.25$, and $\mathrm{f}(1.25)=19 / 64>0$  so $\mathrm{f}$ changes sign between $1.25$ and $1.5$ and we know $\mathrm{f}$ has a root between $1.25$ and $1.5$.

Repeating this procedure a few more times, we get that

If we continue the table, the interval containing the root will squeeze around the value $\mathrm{1.324718}$.

The Bisection Algorithm has one major drawback - there are some roots it does not find. The algorithm requires that the function be both positive and negative near the root so that the graph actually crosses the $x$-axis. The function $f(x)=x^{2}-6 x+9=(x-3)^{2}$ has the root $x=3$ but is never negative (Fig. 12).

We cannot find two starting points a and $b$ so that $f(a)$ and $f(b)$ have opposite signs, and we cannot use the Bisection Algorithm to find the root $\mathrm{x}=3$. In Chapter 2 we will see another method, Newton's Method, which does find roots of this type.

The Bisection Algorithm requires that we supply two starting points $\mathrm{a}$ and $\mathrm{b}$, two $\mathrm{x}$-values at which the function has opposite signs. These values can often be found with a little "trial and error", or we can examine the graph of the function and use it to help pick the two values.

Finally, the Bisection Algorithm can also be used to solve equations because the solution of any equation can always be transformed into an equivalent problem of finding roots by moving everything to one side of the equal sign. For example, the problem of solving the equation $x^{3}=x+1$ can be transformed into the equivalent problem of solving $x+1-x^{3}=0$ or of finding the roots of $f(x)=x+1-x^{3}$ which we did in the previous example.

Example 8: $\quad$ Find all of the solutions of $\sin (x)=\frac{2 x+1}{x-2}$. ($x$ is in radians).

Solution: We can convert this problem of solving an equation to the problem of finding the roots of $\mathrm{f}(\mathrm{x})=\sin (\mathrm{x})-\frac{2 \mathrm{x}+1}{\mathrm{x}-2}=0$. The function $\mathrm{f}(\mathrm{x})$ is continuous everywhere except at $\mathrm{x}=2$, and the graph of $\mathrm{f}(\mathrm{x})$ in Fig. 13 can help us find two starting values for the Bisection Algorithm. The graph shows that $\mathrm{f}(-1)$ is negative and $\mathrm{f}(0)$ is positive, and we know $\mathrm{f}(\mathrm{x})$ is continuous on the interval $[-1,0]$. Using the algorithm with the starting interval $[-1,0]$, we get that the root is contained in the shrinking intervals:

$\begin{aligned} &{[-.5,0],[-.25,0],[-.25,-.125], \ldots} \\ &{[-.238281,-.236328], \ldots,[-.237176,-.237177]} \end{aligned}$

so the root is approximately $-.237177$.

We might also notice that $\mathrm{f}(0)=0.5$ is positive and $\mathrm{f}(\pi)=0-\frac{2 \pi+1}{\pi-2} \approx-6.38$ is negative. Why is it wrong to conclude that $\mathrm{f}(\mathrm{x})$ has another root between $x=0$ and $x=\pi?$