\magnification=\magstep1
\centerline{Mathematics 171--Numerical Analysis I}
\centerline{Review Sheet--Final Exam}
\centerline{December 3, 1998}
\bigskip\noindent
{\bf General Information}  
\bigskip
The final examination for this course will be given 
{\it Wednesday, December 16 at 8:30 a.m.}  The exam will be constructed
to take 2 hours to complete if you work at a reasonable steady pace, 
but you will have the entire 3-hour period for the exam if you need the
extra time.  Because there are a relatively
large number of different formulas you will need to use, {\it I will allow you to 
consult one 4" by 6" index card (one side only, please!) during this exam\/}.  
You may include any information you wish.  Choose wisely! 
\bigskip\noindent
{\bf Topics to be Covered}
\bigskip
The final will be a cumulative exam, covering all the major topics we have
studied since the beginning of the semester:
\item{0.}  {\it Maple} --  I might ask you for Maple input commands 
to do some particular calculation -- similar to the question from 
the first midterm.
\item{1.}  {\it Floating Point Number Systems and Arithmetic} -- Roundoff
errors, ``bad situations'' to avoid if possible, and so forth.
\item{2.}  {\it Numerical Root Finding Methods} -- for one-variable equations.
Concentrate here on Newton-Raphson, $x = g(x)$  fixed-point iteration, 
and Steffensen's
Method (fixed point iteration in combination with Aitken Acceleration). 
\item{3.}  {\it Rate of Convergence} -- of a root finding method.  Order of 
convergence.  Know the orders of convergence of the methods above,
both in the general case, and in any relevant special cases, and the
practical implications of this information.
\item{4.}  {\it Polynomial Interpolation} -- Know the Lagrange, divided
difference and Newton forms for the interpolating polynomial
for a given set of points, and know when each is
applicable.  
\item{5.} {\it The Error Formula for Polynomial Interpolation} --
Know the formula for the error of interpolation, and
understand how it is used.
\item{6.}  {\it Cubic Spline Interpolation} -- The calculations needed
to find a spline interpolant are somewhat tedious and time-consuming (i.e.
ill-suited for an exam!).  Know the basic ideas behind this method (the 
definition of a cubic spline, how to determine coefficients to make a 
piecewise cubic polynomial function be a spline, how to use them for various 
jobs, etc.).  Also know {\it why} cubic 
splines might be preferable to interpolating polynomials in some contexts.
\item{7.}  {\it Numerical Differentiation} -- Know the basic forward and
central difference formulas (together with their error terms -- "Big-O" 
notation for describing the rate at which a function $F(h)$ goes to zero as
$h\to 0$).  
Know how to derive other ones by combining appropriate Taylor expansions.
Also know how to analyze the effect of round-off error in these
computations.
\item{8.}  {\it Richardson Extrapolation} -- Know the basic idea and
how to apply it.
\item{9.}  {\it Numerical Integration} -- Trapezoidal and Simpson's Rules
(basic and composite forms) with the error terms.  Romberg integration
(Trapezoidal Rule, combined with Richardson Extrapolation).
\bigskip\noindent
{\bf Proofs to Know}
\bigskip
\item{1.}  If $g$ is a continuously differentiable function with a
fixed point $L$ for which $\vert g^\prime(L)\vert < 1$, then 
fixed point
iteration converges to $L$ for any $x_0$ sufficiently close to $L$.
\item{2.}  Newton's Method converges quadratically to a simple root of
$f(x) = 0$ if $x_0$ is chosen sufficiently close to the root.  (Also
understand how the rate of convergence of Newton's Method changes at
a root of higher multiplicity.)
\item{3.}  State and prove the formula for the error in the centered
difference approximation to $f'(x_0)$.
(Include all relevant hypotheses!)
\item{4.}  Derivation of the Trapezoidal Rule integration formula
and its error term by the Weighted Mean Value Theorem for Integrals.
\bigskip
\noindent
{\bf Suggestions for How to Study}
\bigskip
Start by reviewing the class notes and sections of the text
we have covered (most of Chapters 1 - 4).  For the proofs you 
need to know, {\it understanding the logic of the proof and having
an outline of the argument in mind is better than rote memorization -- you'll
understand the result better and remember it after the exam!}.  Then
look over the Review Problems from the two midterms, the computer labs,
discussions, problem sets.  Try some of the problems in Sections 4.4 and
4.5 also to test your understanding of the composite integration rules
and Romberg Integration.
\bigskip
\noindent
{\bf Review Session}
\bigskip
I will be happy to hold a review session for the final.  We can 
set up a time in class December 3.
\end
