Recall that we encountered the Bisection method in Chapter 5. This was another way to do rootfinding. If we reenter the bisection procedure:

```
bisect := proc (f::procedure, interval::range,{eps:=10^(-4)})::numeric;
description "This procedure performs the bisection method on the function f with given range. The parameter eps will determine the halting condition."
local mid := .5*(lhs(interval)+rhs(interval));
local inter := interval;
if f(rhs(inter))*f(lhs(inter))>0 then
error "A root is not guaranteed to be in this interval.":
end if:
while rhs(inter)-lhs(inter) > eps do
if f(lhs(inter))*f(mid) < 0 then
inter := lhs(inter) .. mid
else
inter := mid .. rhs(inter)
end if;
mid := .5*(lhs(inter)+rhs(inter));
end do;
return mid:
end proc:
```

We can find roots, like $\sqrt{2}$ using this instead.

`bisect(x->x^2-2,1..2)`

Find the solution to $\cos x = x$ using the bisection method.

Earlier, we have seen a few cases of iteration, in particular recursive iteration. For example, the sequence:

$$a_{n} = \frac{1}{a_{n-1}+1}$$

with $a_0=1$ generates a sequence. In Chapter 10 we found the first few terms and then found the limit of this. Recall that if we define:

```
a:=n->1/(1+a(n-1))
a(0):=1
```

then `seq(a(n),n=1..10)`

generates the first 10 terms or

$$1,\frac{1}{2},\frac{2}{3},\frac{3}{5},\frac{5}{8},{\frac {8}{13}},{\frac {13}{21}},{\frac {21}{34}},{\frac {34}{55}},{\frac {55}{89}},{\frac {89}{144}}$$

and as we discovered above, this sequence converges to the golden mean (or golden ratio)

$$\frac{1+\sqrt{5}}{2}$$

Another useful iterative sequence is the following:

$$x_{n+1} = \frac{x_n^{2}+a}{2x_n}\qquad x_0=a$$

for a positive number $a$. We will show that this converges to $\sqrt{a}$. For example, if $a=2$, then

```
x:=n->(x(n)^{2}+2)/(2*x(n-1))
x(0):=2
```

(and again make sure that the $x_0$ is entered after the general formula.) If we find the first few terms of this we get:

$$\frac{3}{2},\frac{17}{12},\frac{577}{408},\frac{665857}{470832},\frac{886731088897}{627013566048},\ldots$$

and then the fraction gets quite large because $x_0$ is an integer and Maple is trying to keep everything as exact numbers (so returns a rational). If instead, we use $x(0):=2.0$, the rerun the first few terms:

$$2.0,1.500000000,1.416666666,1.414215686,1.414213562,

\ldots$$

Use the above to find $\sqrt{5}$.

(First, before trying any of these, you’ll probably want to `unassign('x')`

to get everything to work correctly.)

The above formula is a specific case of Newton’s method for finding roots. Here’s a geometric view of Newton’s method.

We intend to find the point $x^{\star}$ such that $f(x)=0$. We don’t know how to find $x^{\star}$, but have an approximate solution, call it $x_0$. Draw the tangent line to the curve $y=f(x)$ at $x_0$. The following plot is an example with $f(x)=x^{2}-2$ and $x_0=0.4$:

The point on the left is $x_0=0.4$ and the blue line is the tangent line there. Instead of using the function, we use the tangent line, which is easy to solve. That value is $x_1=2.7$. At this point (no pun intended), we find the tangent line at $x_1$ and find where it crosses the $x$-axis.

This process continues indefinitely and (for this example), it converges to $\sqrt{2}$.

Recall that the tangent line to the curve $y=f(x)$ at $x=a$ is

$$y=f'(a)(x-a)+f(a)$$

and if we set $y=0$ in the tangent line because we are seeking the root (where the function is 0)

$$0=f'(a)(x-a)+f(a)$$

and then we solve for $x$. (Either by hand or let Maple do it).

$$x=a+\frac{f(a)}{f'(a)}$$

Next, if we let $a=x_0$, our initial point and $x$ be $x_1$, the next point:

$$x_1=x_0+\frac{f(x_0)}{f'(x_0)}$$

or in general:

$$x_{n+1}=x_n+\frac{f(x_n)}{f'(x_n)}$$

and this last equation is called *Newton’s rootfinding method* (or just *Newton’s method*)

Use Newton’s method to find the solution to $\cos x = x$.

If we let $f(x)=x-\cos x$ and perform Newton’s method. Since, $f'(x)=1+\sin x$, this means that

$$x_{n+1} = x_n - \frac{x_n-\cos x_n}{1+\sin x_n}$$

and let’s use $x_0=0$ as an initial guess.

In Maple, if we enter:

```
x:=n->x(n-1)-(x(n-1)-cos(x(n-1)))/(1+sin(x(n-1)))
x(0):=0.0
```

and then `seq(x(n),n=0..5)`

results in

$$0., 1.000000000, 0.7503638679, 0.7391128909, 0.7390851334, 0.7390851332$$

As you can see from the sequence, the last two numbers are the same for the first 9 digits.

And looking at a plot of $x$ and $\cos x$,

The solution looks like about 0.73.

There are two $x$ values such that $1-x^{2}=\sin x$. Find the solution that satisfies $x\lt 0$. Plot the two function to see if your answer is reasonable.

`NewtonsMethod`

commandThere is a command called `NewtonsMethod`

in the `Student[Calculus1]`

package. Look at the Help Browser for the command and explore the options. Reproduce the problems above.