\nopagenumbers
\magnification=1200
\baselineskip=12pt
\def \d{\displaystyle}
\def \h{\hfill}
\def \v{\vfill}
\def \title#1{\line{\h{\bf Math 151  #1}\h}}
\def \namdat#1{\line {Name and Section \vrule height .4pt width2in depth0pt
\h#1\par}}
\def \frac #1#2{{\d #1\over \d #2}}
\parindent=0pt
\font \bigbf = cmr10 scaled 1200
\def \i{\item}
\def \vs{\vskip 5pt}
\def \vss{\vskip 10pt}
\def \hs{\hskip 10pt}
\def \c{\circ}
\def \t{\theta}
\def \vc#1{ {\bf\vec#1} }
\def \q{\quad}


\baselineskip = 13pt
\line{\h  Spring 1998}
\line{\h \bigbf Maple Lab, Week 18 \h}
\vss
\line{\h \bigbf Newton's Method and Maple Programming\h}
\vss
{\bf Background:}  The objective of this lab is to use Maple to illustrate
Newton's method,
 an interative method for finding approximate solutions to the equation 
$f(x) = 0 :$
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\,,\q n=1,2,\ldots.$$
In addition, this will be an excellent opportunity to introduce some 
commands useful for programming with Maple, such as {\tt for .. do .. od;} for
writing loops of commands 
(REMARK: {\tt od} is {\tt do} spelled backwards, and ends the loop), 
the {\tt if .. then .. fi;} command 
(REMARK: {\tt fi} is {\tt if} spelled backwards, 
and ends the {\tt if} command), and the {\tt proc() .. end;} command for
writing procedures.  
The exercises below will be based on Exercise 11 in Chapter 3 of your 
CalcLabs Manual, solving $f(x) = x^3 + x -2 = 0$. 

In preparation for the exercises, execute the following Maple commands:
\vs
$>$ {\tt f := x -> x**3 + x - 2;  fp := D(f);}

$>$ {\tt Newton := x -> evalf(x - f(x)/fp(x));}

$>$ {\tt Digits := 20:  tol := 10.**(-Digits + 2);}


Make a plot of {\tt f} to locate all the roots. 
(It is easy to see that, in this case, the only root is $x = 1$. 
This will make it easy to see how accurate the approximations are.)
\vss
{\bf Exercises:  1.}  
Execute the command {\tt Newton(0);}, and then {\tt Newton(");} a few times, 
until the output converges to 1.  
Retype the command each time so that all iterations are left on the screen. 
What is the number of digits of accuracy of each approximation?
\vss
{\bf 2.}  The {\tt for .. do .. od;} command.

The above sequence of commands can easily be executed in a loop as follows:
\vs
$>$ {\tt x := 0:}

$>$ {\tt for i from 1 to 8 do} 

$>$ {\tt x := Newton(x);}

$>$ {\tt od;} 
\vs
Now repeat the above commands, but replace {\tt Newton(x)} by 
{\tt x - f(x)/fp(x)}. Explain the result.
\vss 
{\bf 3.} The {\tt if .. then .. fi;} command.

Execute the following version of the first loop in Exercise 2, 
in order to halt the computation when  successive iterates are 
sufficiently close, i.e., when $|x_{n+1} - x_x|$ is sufficiently small: 
 Replace the line {\tt x := Newton(x);} by the following 
three commands: 
{\tt x1 := Newton(x); if abs(x1-x)<.0001 then break fi; x := x1;}.
 Explain the result.
\vss
{\bf 4.}  The {\tt proc() .. end;} command.

A Maple {\bf procedure} is a group of Maple commands which form what's usually
referred to in programming languages as a {\bf subprogram}. 
It would be called a {\bf subroutine} in FORTRAN, or a {\bf function} in
C. 
It typically has input variables,  one or more outputs, 
and possibly some internal variables that are known as {\bf local}
variables. 
As an example, the following is a procedure to calculate the circumference 
and area of a circle of radius {\tt r}.
\vs
$>$ {\tt Circle := proc(r)}

$>$ {\tt local C,A;}

$>$ {\tt C := evalf(2*Pi*r);}

$>$ {\tt A := evalf(Pi*r**2);}

$>$ {\tt RETURN(C,A);}

$>$ {\tt end;}
\vs

To use the procedure, 
say to find the circumference and radius of a circle of radius 10, 
the user enters
\vs
$>$ {\tt Circle(10);}
\vs
Your lab task is to write a procedure named {\tt Newt} that implements
Newton's method. 
Have as input the function {\tt Newton}, as defined above, 
the starting value {\tt xstart}, and the tolerance, {\tt tol}. 
Use a {\tt for .. do .. od}; loop as in Exercise 4, with a maximum of 
10 iterations, and stop when successive iterates are within {\tt tol}. 
Return the value {\tt x1} of the last iteration.  
Test your procedure with the command
\vs
$>$ {\tt Newt(Newton,0,tol);}
\vss
{\bf Do either Exercise 5 or Exercise 6; extra credit for doing both.}
\vss
{\bf 5.}  Apply the software you have developed, to find all the real
roots of $10x^4 + 4x^3 -0.4x^2 -0.01x + 0.007 = 0$.
Comment on the importance of a good starting value.
\vss 
{\bf 6.}  You might be asking, why bother learning about Newton's method,
when
Maple has a command for solving equations, {\tt fsolve}?
  Of course, the
easy answer is that you may not always have Maple available to you. 
Another answer
is that Newton's method might be faster than {\tt fsolve}, and if so, 
this could be significant if you have a lot of equations to solve.  
This exercise will be
to use Maple's {\tt time} command to find out which is faster, 
{\tt fsolve} or {\tt Newt}, in solving the equation $f(x) = 0$.  

Use the on-line help for the {\tt time} command. 
Next, find out how long it takes to execute the command 
{\tt Newt(Newton,0,tol):} 100 times. 
(Remark: You should use a loop, and end all statements with a colon, 
to suppress the output).  Then, find out how
 long it takes to execute the command {\tt fsolve(f(x)=0,x):} 100 times. 
 NOTE: You might have to unassign {\tt x} before using {\tt fsolve}.


 
\bye