Mathematics 172 – Numerical Analysis 2 Review Sheet – Final Exam April 29, 1999

General Information

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, 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!

Topics To Be Covered

The exam will cover the following material:

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).

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.)

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.

4) Gaussian Elimination for linear systems Ax = b (be able to carry out the algorithm on a 3 × 3 or 4 × 4 system, with or without maximal column pivoting using floating point or rational arithmetic.) ”Gaussian Elimination = LU-factorization”.

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∞− norm of a 3 × 3 matrix.

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 × 3 or 4 × 4 system of equations.

7) Eigenvalues, the Gershgorin Circle Theorem.

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 × 3 example.

Theorems and Proofs to Know

A) Show that if {p_{0}(x), …, p_{n}(x)} are polynomials orthogonal with respect to the inner product

⟨f, g⟩ = ∫_{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}, …, x_{n}, then with weights

c_{i} = ∫_{a}^{b} \frac{∏_{k≠i}(x − x_{k})}{∏_{k≠i}(x_{i} − x_{k})} dx,

the approximate integration rule

∫_{a}^{b} f(x) dx ≐ c_{1}f(x_{1}) + ⋯ + c_{n}f(x_{n})

has degree of precision (at least) 2n − 1. B) The Midpoint Method for the ODE IVP

\{ \begin{matrix}y′ = f(t, y) \\ y(t_{0}) = α \end{matrix}

has one-step error O(h^{3}) (or local truncation error O(h^{2})). C) Iteration x^{(k)} = Gx^{(k−1)} + c converges if ∥G∥ < 1 for some induced matrix norm. D) The Gershgorin Circle Theorem.

Review Problems

Section 4.6/1,2 Section 4.7/1,2,3,4 (given the information in the table on page 227), 6,8 (possible Extra Credit problem) section 5.1/7 (Picard iteration) Section 5.2/3,4, 5 a,b Section 5.4/1,3,10, 13 Section 6.2/Problems like 5, 7 (”partial pivoting” = ”maximal column pivoting”) Section 6.5/2,3 Section 7.1/2,8,10,11 Section 7.3/problems like 1,2 a-d,10 (T_{j} is the Jacobi ”G-matrix”) Section 9.1/1,2,3,10 a,c Section 9.2/1,2 (use several different values of s (= q in text)),10

Review Session

I will be happy to hold an evening review session for the exam either Monday or Tuesday, May 10, or 11.