\magnification=\magstep1
\centerline{Mathematics 371 -- Numerical Analysis}
\centerline{Lab 2/Midterm Problem Set 1}
\centerline{\it September 28, 2001}
\bigskip
\noindent
{\it Ground Rules}
\bigskip
The lab problems below and the additional theoretical questions 
form the first midterm problem set announced in the course syllabus.
This is an open book, open notes, open Swords 335 assignment.
You must work {\it independently} on these problems, and you
may not consult with other faculty members, etc.  You may 
consult other sources in the library, on the Internet, etc.
but if you find something relevant there, please {\it footnote
it}.  When you have finished your solutions, please write
out a short statement that you have abided by these ground
rules, sign it, and return it with your solutions.
\bigskip
\noindent
This assignment is due no later than {\it 5:00pm on Friday, 
October 5}.
\bigskip
\noindent
{\it Lab Problems}
\bigskip
\noindent
In class on Friday, September 21 we wrote a rudimentary
Maple procedure implementing Newton-Raphson iteration.  Last time
we also introduced Steffensen's iteration.  There are two files 
containing Maple source code for these methods available from 
the course homepage.  Download and save them to your directory
to start.  (Use the same procedure as in the previous lab.)
Insert {\tt print} or {\tt lprint} statements to 
display all the terms in the iteration sequences for the 
Maple output you submit.
\bigskip
\item{A)}  Use Newton-Raphson to solve $0 = \tan(\pi x) - 6$ starting
from $x_0 = 0.4$ until an accuracy of $10^{-7}$ is obtained.
Explain why your sequence of approximations 
to the root is converging quadratically, and estimate the 
asymptotic constant $K_2$ in the equation 
$$\lim_{n\to \infty} {|x_n - p|\over |x_{n-1} - p|^2} = K_2.$$ 
\bigskip
\item{B)}  If you apply Newton-Raphson to solve
$$0 = {1\over 2} + {1\over 4}x^2 - x\sin(x) - {1\over 2}\cos(2x)$$
starting from $x_0 = {\pi\over 2}$, in theory you 
should generate a sequence of approximations converging to 
$p \doteq 1.895494267$ (exact value to 10 decimal digits).
What happens if you use our NewtonRaphson procedure
in Maple's default floating point number system and
iterate until an accuracy of $10^{-6}$ is obtained? 
Alter the procedure to print out $x_n$ and $|x_n - x_{n-1}|$ for each $n$,
and explain what is happening here.  What happens if you use
fewer (say 5) or more (say 20) decimal digits in the floating point
computation?
\bigskip
\item{C)}  Now, solve the same equation as in B using Steffensen's 
iteration, and floating point number systems with 5,10,20 digits.  
Compare the results from Newton-Raphson and Steffensen.  What additional 
lesson about root-finding in floating point arithmetic do you see
by considering this equation?
\bigskip
\item{D)}  Do Problem 30 from Section 2.3 in the text.
\bigskip
\noindent
{\it Additional Theoretical Problems}
\bigskip
\noindent
\item{E)}  Suppose that $p$ is a root of $f(x) = 0$ of multiplicity $m \ge 2$.  
Show that if Newton-Raphson iteration converges to $p$ from some $x_0$, then 
the convergence is {\it linear}, and determine (with proof) 
the asymptotic constant $K_1$ in the equation 
$$\lim_{n\to \infty} {|x_n - p|\over |x_{n-1}-p|} = K_1.$$
If you had two equations, one with a root of multiplicity 2, and one
of multiplicity 3, and you used Newton-Raphson on both, which 
sequence of approximations would converge faster?  Explain.  
\bigskip
\item{F)}  Suppose that $p$ is a root of $f(x) = 0$ of multiplicity $m$.
Show that if $f'''$ is continuous on some interval containing $p$, then
the iteration 
$$x_n = x_{n-1} - {m f(x_{n-1})\over f'(x_{n-1})}$$
will give a {\it quadratically convergent} sequence of approximations
to $p$, starting from $x_0$ in a suitable interval.  This rate of
convergence is as good as that for Steffensen's iteration.  But which 
method is better, and why?
\bigskip
\item{G)}  Show that the following iteration method
$$x_n = x_{n-1} - {f(x_{n-1})\over f'(x_{n-1})} - 
{1\over 2}{f''(x_{n-1})\over f'(x_{n-1})}\left({f(x_{n-1})\over f'(x_{n-1})}\right)^2$$
will yield {\it cubic} convergence under suitable hypotheses (say what these are).
Even though cubic convergence is ``super-fast'' convergence (much faster even
than quadratic convergence), this kind of method is almost never used in 
practice.  Why do you suppose that is the case?
\bye
