Numerical Analysis Qualifying Exam
The Numerical Analysis Qualifying Exam is based in the syllabus for
Mathematics 270ABC. The course is divided in to six segments,
each approximately five weeks in length, that survey major topics in
Numerical Analysis and Scientific Computation. These basic topics are:
 Numerical Linear Algebra for Dense Matrices (270A)
 Numerical Linear Algebra for Sparse Matrices (270A)
 Nonlinear Equations and Optimization (270B)
 Approximation Theory (270B)
 Initial Value Problems for Ordinary Differential Equations (270C)
 Two Point Boundary Value Problems for Ordinary Differential Equations
(270C)
Because of the timing of the qualifying exam, questions on the last topic
(2point BVP) are not included in the exam.
In five weeks time, none of these topics can be addressed very deeply.
However, those choosing to specialize in
some area of numerical analysis or scientific computation need to have
some understanding of the issues, both theoretical and algorithmic,
in all of these areas. There exist more specialized and advanced courses
(e.g., Mathematics 271ABC and Mathematics 272ABC) that address some
of these topics in a more comprehensive fashion.
The textbook for Mathematics 270ABC,
Numerical Mathematics, by Quarteroni, Sacco, and
Saleri ([1] below)
has chapters that cover most of the material in the syllabus.
This textbook is also available online through SpringerLink at
http://www.springerlink.com/content/q67046/.
Other texts that provide a survey of many of the topics
covered in this course
include Dalquist and Björck [2,3],
Atkinson [4],
and Isaacson and Keller [5].
General References for Mathematics 270ABC

Alfio Quarteroni, Riccardo Sacco, and Fausto Saleri.
Numerical mathematics, volume 37 of Texts in Applied
Mathematics.
SpringerVerlag, Berlin, second edition, 2007.

Ake Björck and Germund Dahlquist.
Numerical methods.
PrenticeHall Inc., Englewood Cliffs, N.J., 1974.
Translated from the Swedish by Ned Anderson, PrenticeHall Series in
Automatic Computation.

Germund Dahlquist and Åke Björck.
Numerical methods.
Dover Publications Inc., Mineola, NY, 2003.
Translated from the Swedish by Ned Anderson, Reprint of the 1974
English translation.

Kendall E. Atkinson.
An introduction to numerical analysis.
John Wiley & Sons Inc., New York, second edition, 1989.

Eugene Isaacson and Herbert Bishop Keller.
Analysis of numerical methods.
Dover Publications Inc., New York, 1994.
Corrected reprint of the 1966 original [Wiley, New York; MR0201039
(34 #924)].
270A: Numerical Linear Algebra
Numerical Linear Algebra for Dense Matrices
 Gaussian Elimination: Condition number and stability
of linear systems of equations, LU factorization and its
variants, pivoting, iterative refinement, roundoff error
analysis, complexity.
 Linear Least Squares Problems: basic theory
(projection, best approximation),
over and underdetermined systems,
GramSchmidt and its variants,
Householder and Givens transformations, QR factorization,
singular value decomposition (SVD), stability and conditioning
of least squares problems.
 Algebraic Eigenvalue Problem: Schur Decomposition,
power method, inverse iteration, Rayleigh Quotient iteration,
Hessenberg form, QR method for eigenvalues, Sturm sequences,
Gerschgorin estimates, conditioning of eigenvalues and eigenvectors.
Numerical Linear Algebra for Sparse Matrices
 Sparse Gaussian Elimination: sparse matrix data structures,
graph model for Gaussian Elimination, computing the fillin,
ordering (minimum degree, nested dissection), complexity,
band matrices.
 Iterative Methods for Linear Equations: convergence theory,
basic iterative methods (Jacobi, GaussSeidel, SOR, SSOR, ILU),
complexity, orderings, convergence criteria.
 Krylov Subspace Methods: Conjugate gradients, preconditioning,
generalized condition number, Lanczos method, GMRES, Biconjugate
gradients.
Specialized References for Mathematics 270A

Gene H. Golub and Charles F. Van Loan.
Matrix computations.
Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins
University Press, Baltimore, MD, third edition, 1996.

G. W. Stewart.
Matrix algorithms. Vol. I.
Society for Industrial and Applied Mathematics, Philadelphia, PA,
1998.
Basic decompositions.

G. W. Stewart.
Matrix algorithms. Vol. II.
Society for Industrial and Applied Mathematics (SIAM), Philadelphia,
PA, 2001.
Eigensystems.

J. H. Wilkinson.
The algebraic eigenvalue problem.
Monographs on Numerical Analysis. The Clarendon Press Oxford
University Press, New York, 1988.
Oxford Science Publications.

Richard S. Varga.
Matrix iterative analysis, volume 27 of Springer Series in
Computational Mathematics.
SpringerVerlag, Berlin, expanded edition, 2000.

Alan George and Joseph W. H. Liu.
Computer solution of large sparse positive definite systems.
PrenticeHall Inc., Englewood Cliffs, N.J., 1981.
PrenticeHall Series in Computational Mathematics.
270B: Numerical Approximation
and Nonlinear Equations
Nonlinear Equations and Optimization
 Scalar Equations:
Fixed point iteration, bisection, Newton's method,
secant method, order of convergence.
 Nonlinear Systems: Steepest descent, Approximate Newton Methods,
Kantorovich Theorem, Quasi Newton Methods, line search, trust region.
 Optimization: unconstrained, equality and inequality constraints,
necessary and sufficient conditions,
penalty and barrier methods,
active set methods, interior point methods,
KKT systems, linear and quadratic programming.
Approximation Theory
 Polynomial Interpolation: Lagrange Interpolation,
divided differences, AikenNeville and
Barycentric formulas, error estimates, Runge's example,
Chebyshev approximation, orthogonal polynomials, least squares
approximation.
 Piecewise Polynomial Approximation: C^0 approximation
spaces, error estimates for interpolation and least squares,
Peano Kernel Theorem,
Hermite and spline approximation.
 Numerical Quadrature: NewtonCotes and Gaussian Quadrature,
basic and composite formulas, error estimates, singular
integrals, Richardson extrapolation, EulerMaclaurin Formula,
Romberg integration, adaptive quadrature.
Specialized References for Mathematics 270B

Philip E. Gill, Walter Murray, and Margaret H. Wright.
Practical optimization.
Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London,
1981.

J. M. Ortega and W. C. Rheinboldt.
Iterative solution of nonlinear equations in several variables,
volume 30 of Classics in Applied Mathematics.
Society for Industrial and Applied Mathematics (SIAM), Philadelphia,
PA, 2000.
Reprint of the 1970 original.

Philip J. Davis.
Interpolation and approximation.
Dover Publications Inc., New York, 1975.
Republication, with minor corrections, of the 1963 original, with a
new preface and bibliography.

Carl de Boor.
A practical guide to splines, volume 27 of Applied
Mathematical Sciences.
SpringerVerlag, New York, revised edition, 2001.

Kendall Atkinson and Weimin Han.
Theoretical numerical analysis, volume 39 of Texts in
Applied Mathematics.
Springer, Dordrecht, third edition, 2009.
A functional analysis framework.
270C: Numerical Ordinary Differential Equations
Initial Value Problems for Ordinary Differential Equations
 Theoretical Background: existence, uniqueness and stability for
first order IVP systems, Lipschitz continuity, Gronwall's Lemma,
converting IVP's to standard form (first order systems).
 SingleStep Methods: explicit and diagonally implicit RungeKutta and
RungeKuttaFehlberg methods, error estimates and order of convergence,
absolute stability, A and L stability, stiff equations, adaptive
time stepping.
 MultiStep Methods: solution of linear difference equations,
Adams methods, predictor corrector, backward difference formulas,
weak and strong stability, error analysis and orders of convergence.
Two Point Boundary Value Problems for
Ordinary Differential Equations
 Theoretical Background: existence, uniqueness and stability
for the 2point BVP, Ritz and Galerkin variational formulations,
LaxMilgram Theorem.
 Finite Difference Methods: derivation of finite difference
equations, consistency, stability and error estimates,
convection dominated problems.
 Finite Element Methods: basic formulation, stability and error estimates,
duality and Nitsche's trick, reference elements, streamline diffusion
PetrovGalerkin method for convection dominated problems.
Specialized References for Mathematics 270C

K. Eriksson, D. Estep, P. Hansbo, and C. Johnson.
Computational differential equations.
Cambridge University Press, Cambridge, 1996.

C. William Gear.
Numerical initial value problems in ordinary differential
equations.
PrenticeHall Inc., Englewood Cliffs, N.J., 1971.

E. Hairer, S. P. Nørsett, and G. Wanner.
Solving ordinary differential equations. I, volume 8 of Springer Series in Computational Mathematics.
SpringerVerlag, Berlin, second edition, 1993.
Nonstiff problems.

E. Hairer and G. Wanner.
Solving ordinary differential equations. II, volume 14 of
Springer Series in Computational Mathematics.
SpringerVerlag, Berlin, 1991.
Stiff and differentialalgebraic problems.

Kendall Atkinson and Weimin Han.
Theoretical numerical analysis, volume 39 of Texts in
Applied Mathematics.
Springer, Dordrecht, third edition, 2009.
A functional analysis framework.

Gilbert Strang and George J. Fix.
An analysis of the finite element method.
PrenticeHall Inc., Englewood Cliffs, N. J., 1973.
PrenticeHall Series in Automatic Computation.