\magnification=\magstep1
\centerline{Mathematics 172 -- Numerical Analysis 2}
\centerline{Review Sheet -- Final Exam}
\centerline{April 29, 1999}
\bigskip
\noindent
{\bf General Information}
\bigskip
The final exam for this
course will be given at 8:30 am on Thursday, May 13.  You will have
the full 3-hour period to work on the exam, although I will try to 
construct the exam so that all the problems could be completed in 2 hours
if you worked steadily.  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
\noindent
The exam will cover the following material:
\bigskip
\item{1)}  Adaptive Quadrature (know the error estimate
that is the basis of the algorithm and how to 
apply the algorithm in relatively simple cases like integrals in problems
1,2 from section 4.6).
\item{2)}  Gaussian Quadrature (know the theory behind the Gaussian
Quadrature method -- see the Theorems to Know A below -- 
and how to apply it to approximate a definite integral if you 
are given a table of the roots $x_{n,i}$ and the weights $c_{n,i}$.
I will not ask you to compute roots or weights as we did in Lab 1, though.)
\item{3)}  Methods for ODE initial value problems: Euler's Method,
the Modified Euler and Midpoint Methods, the Classical 4th order 
Runge-Kutta method.  Be prepared to carry out several steps of 
each of these methods by hand on a reasonably simple equation.
Also know how to estimate their one-step or local truncation errors.
\item{4)}  Gaussian Elimination for linear systems $Ax = b$ (be able
to carry out the algorithm on a $3\times 3$ or $4 \times 4$ system, 
with or without maximal column pivoting using floating point
or rational arithmetic.)  "Gaussian Elimination = $LU$-factorization".
\item{5)}  Vector and matrix norms.  Know the definition of 
the matrix norm induced by a vector norm and its consequences.
Also be able to compute the matrix $1-, 2-, or \infty-$ norm 
of a $3\times 3$ matrix.
\item{6)}  Iterative techniques for systems of linear equations --
the Jacobi, Gauss-Seidel, and SOR methods; analysis of their convergence
via vector and matrix norms and the spectral radius of the "G-matrix".
Be prepared to carry two or three iterations of either Jacobi or
Gauss-Seidel on a $3\times 3$ or $4 \times 4$ system of equations.
\item{7)}  Eigenvalues, the Gershgorin Circle Theorem.
\item{8)}  The Power and Inverse Power methods for eigenvalues.
Be prepared to carry out two or three iterations of either of these
on a $3\times 3$ example.   
\vfill\eject
\noindent
{\bf Theorems and Proofs to Know}
\bigskip
\item{A)}  Show that if $\{p_0(x), \ldots ,p_n(x)\}$ are polynomials
orthogonal with respect to the inner product
$$\langle f,g\rangle = \int_a^b f(x)g(x)\ dx,$$
with $\deg(p_i) = i$ all $i$, and such that $p_n(x) = 0$ has $n$ real roots
$x_1, \ldots, x_n$,  then with weights
$$c_i = \int_a^b {\prod_{k\ne i} (x - x_k) \over \prod_{k\ne i} (x_i - x_k)}\ dx,$$
the approximate integration rule
$$\int_a^b f(x)\ dx \doteq c_1f(x_1) + \cdots + c_n f(x_n)$$
has degree of precision (at least) $2n - 1$.
\item{B)}  The Midpoint Method for the ODE IVP 
$$\cases{y' = f(t,y) & \cr
         y(t_0) = \alpha &\cr}$$
has one-step error $O(h^3)$ (or local truncation error $O(h^2)$).
\item{C)}  Iteration $x^{(k)} = G x^{(k-1)} + c$ converges
if $\|G\| < 1$ for some induced matrix norm.
\item{D)}  The Gershgorin Circle Theorem.
\bigskip
\noindent
{\bf Review Problems}
\bigskip
\item{} Section 4.6/1,2
\item{} Section 4.7/1,2,3,4 (given the information in 
the table on page 227), 6,8
\item{} (possible Extra Credit problem) section 5.1/7 (Picard iteration)
\item{} Section 5.2/3,4, 5 a,b
\item{} Section 5.4/1,3,10, 13
\item{} Section 6.2/Problems like 5, 7 ("partial pivoting" = "maximal
column pivoting")
\item{} Section 6.5/2,3
\item{} Section 7.1/2,8,10,11
\item{} Section 7.3/problems like 1,2 a-d,10 ($T_j$ is the Jacobi
"G-matrix")
\item{} Section 9.1/1,2,3,10 a,c
\item{} Section 9.2/1,2 (use several different values of $s$ (= $q$ in 
text)),10
\bigskip
\noindent
{\bf Review Session}
\bigskip
I will be happy to hold an evening review session for the 
exam either Monday or Tuesday, May 10, or 11.
\bye
