Numerical Analysis Comprehensive Exam Syllabus

This document gives the list of topics for the PhD comprehensive exam in Numerical Analysis. It was created based on the MATH 640ABC sequence taught by Martin J. Mohlenkamp in the 2003-4 academic year. Check with the professor who will create your exam for current information.

Prerequisites

The foundation of Numerical Analysis is the study of how to do operations numerically that are discribed in theory in other branches of mathematics. To even begin to talk of the numerical aspects, one must have a solid understanding of the background mathematics. In particular, linear algebra, calculus, and differential equations are essential. The prerequisites for 640A are 211, 560A, and (544 or 546). It is recommended that you also have 560BC and 541.

References

The main text is

[KC]: Numerical Analysis: Mathematics of Scientific Computing, 3rd edition, by David Kincaid and Ward Cheney, Brooks/Cole, 2002.

A lower-level text that sometimes has clearer explanations is

[BF]: Numerical Analysis, 7th edition, by Richard L. Burden and J. Douglas Faires, Brooks/Cole, 2001.

Some other supplementary references are:

Introduction to Numerical Analysis, K. Atkinson
Matrix Computations, G. Golub and C. Van Loan
Numerical Solution of Partial Differential Equations, K. W. Morton and D. F. Mayers
Introduction to Numerical Analysis, J. Stoer and R. Bulirsch

Topics

The topics listed here are the most central. They are given priorities:

Core material to be understood thoroughly. Be able to derive the method and its properties from scratch.
Be able to apply the theorem or perform the algorithm, explain why it works, state its properties, discuss its advantages and disadvantages, decide when it is appropriate, and compare it with other methods.
Be able to explain the method, state its properties, determine when it is appropriate, and discuss alternatives.

In principle any topic within Numerical Analysis could be part of this exam. In particular you may be given an unfamiliar problem or algorithm and asked to analyse it, using the tools of the field.

Computer Arithmetic

floating point errors; 1 [KC 2.1] [BF 1.2]
loss of significance; 1 [KC 2.2] [BF 1.2]
stability and conditioning; 1 [KC 2.3]

Linear Algebra

vector spaces, matrices, linear systems, vector and matrix norms, eigenvectors, condition numbers; 1 [KC 4.1,4.4] [BF 6.3,7.1,7.2,9.1]
Gaussian elimination (LU decomposition), pivoting, scaling; 1 [KC 4.2,4.3] [BF 6.1,6.2,6.5,6.6]
Gaussian error analysis; 2 [KC 4.4,4.8] [BF 6.1,6.2,6.5,6.6]
Neumann Series and Schulz iteration; 1 [KC 4.5]
Residual correction; 1 [KC 4.5] [BF 7.4]
Iterative methods framework; 1 [KC 4.6]
Gauss-Jacobi, Gauss-Seidel; 1 [KC 4.6] [BF 7.3]
Steepest descent methods; 1 [KC 4.7]
the conjugate gradient method; 3 [KC 4.7] [BF 7.5]
eigenvalue location, error, and stability results; 1 [KC 5.2]
the power method and inverse power method; 1 [KC 5.1] [BF 9.2]
orthogonal transformations using Householder matrices; 1 [KC 5.2,5.3] [BF 9.3]
the QR decomposition; 1 [KC 5.3]
the singular value decomposition; 1 [KC 5.4]
determinants and Schur's factorization; 1 [KC 5.2]
least squares solution of linear systems; 1 [KC 5.3,5.4]
Sherman-Morrison formula; 2 [BF 10.3]
the QR Method for finding eigenvalues; 2 [KC 5.5] [BF 9.4]

Nonlinear equations and systems

the bisection method; 1 [KC 3.1] [BF 2.1]
Newton's method; 1 [KC 3.2] [BF 2.3,10.2]
the secant method (single equation); 1 [KC 3.3]
fixed points and iteration; 1 [KC 3.4] [BF 2.2,2.4,10.1]
roots of polynomials; 2 [KC 3.5]
Newton's method for nonlinear systems; 2 [KC 3.2]
Aitken acceleration for linearly convergent sequences; 3 [KC 5.1] [BF 2.5]
descent methods; 1 [KC 4.7,11.2] [BF 10.4]
homotopy methods; 3 [KC 3.6] [BF 10.5]

Approximation of Functions

polynomial interpolation theory; 1 [KC 6.1] [BF 3.1]
Newton divided differences; 1 [KC 6.2] [BF 3.2]
Hermite interpolation; 2 [KC 6.3] [BF 3.3]
piecewise polynomial interpolation; 1 [KC 6.4] [BF 3.4]
B-splines; 2 [KC 6.5,6.6]
trigonometric interpolation, discrete Fourier Transform; 1 [KC 6.12] [BF 8.5]
Fast Fourier Transform; 3 [KC 6.13] [BF 8.6]
least squares approximation; 1 [KC 6.8] [BF 8.1]
orthogonal polynomials; 2 [KC 6.8] [BF 8.2,8.3]
the Weierstrass Theorem and Taylor's Theorem; 2 [KC 1.1,6.1]
the minimax (Chebyshev) approximation problem; 3 [KC 6.9]

Integration and Differentiation

numerical differentiation; 1 [KC 7.1] [BF 4.1]
the trapezoidal rule and Simpson's rule; 1 [KC 7.2] [BF 4.4]
Newton-Cotes integration formulae; 1 [KC 7.2] [BF 4.3]
Gaussian quadrature; 1 [KC 7.3] [BF 4.7]
asymptotic error formulae, Richardson extrapolation, and Rohmberg integration; 1 [KC 7.1,7.4] [BF 4.2,4.5]
adaptive quadrature; 2 [KC 7.5] [BF 4.6]
improper integrals; 2 [BF 4.9]

Ordinary Differential Equations

existence, uniqueness, and stability theory; 2 [KC 8.1,8.7] [BF 5.1]
Taylor-series methods; 1 [KC 8.2] [BF 5.3]
Euler's method, midpoint method, trapezoidal method, and Runge-Kutta methods; 1 [KC 8.3] [BF 5.2,5.4]
multistep methods; 1 [KC 8.4] [BF 5.6]
convergence, consistency, stability; 1 [KC 8.5] [BF 5.10]
stiffness and stability domains; 1 [KC 8.12] [BF 5.11]
predictor-corrector algorithms; 2 [KC 8.4]
boundary value problems via shooting, finite differences, and collocation; 1 [KC 8.8,8.9,8.10] [BF 11.1,11.2,11.3,11.4]
Adaptive methods, Runge-Kutta-Fehlberg; 2 [KC 8.3] [BF 5.5,5.7]

Partial Differential Equations

parabolic problems via explicit and implicit methods; 1 [KC 9.1,9.2] [BF 12.2]
elliptic problems via finite differences and Galerkin methods; 1 [KC 9.3,9.4] [BF 12.1]
Rayleigh-Ritz and finite element methods; 3 [KC 9.4] [BF 12.4]
hyperbolic problems in one space dimension; 1 [KC 9.7][BF 12.3]
the Lax Equivalence Theorem; 3

See the computational math exam at the University of Colorado for ample practice problems. The syllabus here was adapted from their syllabus.

Martin J. Mohlenkamp

Last modified: Thu Jun 2 16:58:27 EDT 2005