\magnification=\magstep1
\centerline{MATH 131, section 1 -- Calculus for Physical and Life Sciences, 1}
\centerline{Lab Day 3 -- Newton's Method}
\centerline{November 20, 2007}
\bigskip
\noindent
{\it Goals}
\bigskip
The goal for this lab is to use and investigate the numerical root-finding
method known as Newton's Method (sometimes also called the Newton-Raphson
method).  Using Maple, you will apply Newton's Method to find numerical 
approximations to solutions of various 
equations $f(x) = 0$.  In the process you will see cases where the method
succeeds and others where it fails quite badly.  You should work in pairs
for this assignment (the previous lab pairs, or other pairings of your
choice are OK).  
\bigskip
\noindent
{\it The Mathematical Background}
\bigskip
As we saw in class yesterday, the idea behind Newton's Method is that
we can use the linear functions defining the tangent lines to a graph 
$y = f(x)$ to approximate that function and approximate where the graph
crosses the $x$-axis.  If we start at some ``seed'' value $x = x_0$,
then Newton's Method essentially determines where the tangent line
to the graph $y = f(x)$ at $x_0$ crosses the $x$-axis.  This number
is called $x_1$.  Then the method finds where the tangent line at $x = x_1$
crosses the $x$-axis and calls that number $x_2$.  Repeating the process
gives a {\it sequence} of $x$-values,
$$x_0, x_1, x_2, \ldots, x_n, \ldots$$
that should get closer and closer to a root of $f$, that is, a 
solution of the equation $f(x) = 0$.
We say that the sequence {\it converges} to a root $r$ if 
$$\lim_{n\to\infty} x_n = r.$$
We will study convergence of sequences in the course next semester when 
we study infinite series.

Ideally, the iterative process above will eventually head toward a
root of $f(x) = 0$.  Different ``seeds'' $x_0$ may produce different
sequences of approximations, though, and those different sequences
of approximations may converge to {\it different roots of the equation(!)}.  
There are also cases where Newton's Method can fail to converge.

In terms of equations, Newton's Method reduces to performing the 
following computations:
$$x_n = x_{n-1} - {f(x_{n-1})\over f'(x_{n-1})}$$
for $n = 1, 2, 3, \ldots $ one after the other.  We need a seed $x_0$
to produce $x_1$, but then $x_1$ produces $x_2$, $x_2$ produces $x_3$, and 
so on.  This process is an example of {\it iteration}, an important
topic in numerical mathematics and applications.  It is also {\it something
for which computers are ideally suited}.
\bigskip
\noindent
{\it A Worked Example -- Newton's Method in Maple}
\bigskip
Maple has a ``built-in'' Newton's Method procedure that we will use in 
today's lab.  To use it, you first enter the command
\medskip
\centerline{\tt with(Student[Calculus1]):}
\medskip
\noindent
(note capitalization!)  Then to apply Newton's Method to try to find approximations
to a solution of $f(x) = 0$, you would proceed as follows.  For instance,
say we want to look at what happens for the equation $f(x) = x^2 - 1 = 0$
(where we know what the solutions are so we can see how well the process is working!).
The command
\medskip
\centerline{\tt NewtonsMethod(x\^{}2-1, x=2, iterations=3);}
\medskip
\noindent
will do three iterations (finding $x_3$ in the sequence of approximations) starting
from the seed $x_0 = 2$.  The output is the value $x_3$.  Of course, we might
also want to see all the terms in the sequence of approximations starting
from the seed.  This can be shown by putting in an option as follows:
\medskip
\centerline{\tt NewtonsMethod(x\^{}2-1, x=2, iterations=3, output=sequence);}
\medskip
\noindent
Other nice features that can help us visualize what is happening are to 
have Maple actually draw the graph and the tangent lines used to produce
the sequence $x_n$.  The way to do this is to use different options in the 
{\tt NewtonsMethod} command.  For instance,
\medskip
\centerline{\tt NewtonsMethod(x\^{}2-1, x=2, iterations=3, output= plot);}
\medskip
\noindent
generates a single plot showing all the tangent lines, while
\medskip
\centerline{\tt NewtonsMethod(x\^{}2-1, x=2, iterations=3, output= animation);}
\medskip
\noindent
adds them in one at a time so you can see the order in which they are generated.
(You ``play'' the animation here in a fashion similar to some of the other
animated plots we saw in previous labs.)
You should enter all of these and compare what they do so that you understand
exactly what is happening here.  Also try increasing the number of iterations
to $5$, then $10$ and see what happens.
\bigskip
\noindent
{\it Lab Questions}
\bigskip
\noindent
A)  
\item{1)}  Continuing with the worked example above, using $f(x) = x^2 - 1$, what
happens if you start with the seed $x_0 = -2$ rather than $x_0 = +2$?  What
root of the equation $x^2 - 1 = 0$ are we approaching now?  
\item{2)}  What if we start with $x_0 = 0$?  Could we have predicted this?
What does this say about the choice of the seed for Newton's Method?
\item{3)}  By looking at the graph $y = x^2 - 1$, try to guess which 
initial seeds will produce sequences converging to the root $r = -1$ 
and which will produce sequences converging to the root $r = 1$. Confirm
your guess by testing several different seeds.
\bigskip
\noindent
B)  {\it Effectiveness of Newton's Method.}  Let's explore how well Newton's
Method converges to a root by computing the error at each step of the 
process.  First enter the command 
\medskip
\centerline{\tt Digits := 20;}
\medskip
\item{}
which tells Maple to do all numerical computations using 20 decimal digits
in its numbers.  Then use Newton's Method to compute the 
first 6 iterations applied to $x^2 - 1 = 0$ starting from $x_0 = 2$.  
What is the error at each step (how far is the approximate root $x_n$
from the true root $r = 1$ for each $n = 0,1,2,3,4,5,6$)?  Give your
numbers in ``scientific notation,'' for example $2.3\times 10^{-3}$.
How much does the approximation improve at each step?  How many decimal
places accuracy are gained at each step?
\bigskip
\noindent
C)  {\it Computing $\pi$}.  One equation that has the number $\pi$
as a solution is $\tan(x/4) - 1 = 0$ (do you see why?)  Set {\tt Digits:=50;} now.
Use Newton's Method to compute the first 40 decimal digits of $\pi$.  How
can you be sure those first 40 digits are correct?
\bigskip
\noindent
D)  Use Newton's Method to compute the first 20 digits of the (real)
fifth root of 2.  (What equation has this number as a root?)  
\bigskip
\noindent
E)  Use Newton's Method to approximate all real solutions of the equation 
$$3\cos(x^2 + 2) - x = 0$$
to 10 decimal places.
{\it Hint: Start by plotting this function to get an idea how many
roots there are and to get some possible seeds to use}.
\bigskip
\noindent
F)  {\it Complete Success.}  Explain why Newton's Method finds the solution
to a linear equation $mx + b = 0$ in exactly one step, with no error, for
all choices of seed $x_0$(!)
\bigskip
\noindent
G)  {\it Failure of Newton's Method.}  What happens if you apply Newton's Method
to find roots of $x^4 - 6x^2 - 11 = 0$ starting from the seed $x_0 = 1$?  Try 10 iterations, first show
the sequence of iterations, then the plot to explain what happens.  
What if you try changing the seed slightly to $x_0 = 0.8$ or $x_0 = 1.25$?
Does this help?  By making better choices of  seed, find all the real roots
of this equation, to 10 decimal places.
\bye


