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 (2-point 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

1. Alfio Quarteroni, Riccardo Sacco, and Fausto Saleri. Numerical mathematics, volume 37 of Texts in Applied Mathematics. Springer-Verlag, Berlin, second edition, 2007.
2. Ake Björck and Germund Dahlquist. Numerical methods. Prentice-Hall Inc., Englewood Cliffs, N.J., 1974. Translated from the Swedish by Ned Anderson, Prentice-Hall Series in Automatic Computation.
3. 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.
4. Kendall E. Atkinson. An introduction to numerical analysis. John Wiley & Sons Inc., New York, second edition, 1989.
5. 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

1. Gaussian Elimination: Condition number and stability of linear systems of equations, LU factorization and its variants, pivoting, iterative refinement, roundoff error analysis, complexity.
2. Linear Least Squares Problems: basic theory (projection, best approximation), over and under-determined systems, Gram-Schmidt and its variants, Householder and Givens transformations, QR factorization, singular value decomposition (SVD), stability and conditioning of least squares problems.
3. 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

1. Sparse Gaussian Elimination: sparse matrix data structures, graph model for Gaussian Elimination, computing the fill-in, ordering (minimum degree, nested dissection), complexity, band matrices.
2. Iterative Methods for Linear Equations: convergence theory, basic iterative methods (Jacobi, Gauss-Seidel, SOR, SSOR, ILU), complexity, orderings, convergence criteria.
3. Krylov Subspace Methods: Conjugate gradients, preconditioning, generalized condition number, Lanczos method, GMRES, Biconjugate gradients.

Specialized References for Mathematics 270A

1. 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.
2. G. W. Stewart. Matrix algorithms. Vol. I. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998. Basic decompositions.
3. G. W. Stewart. Matrix algorithms. Vol. II. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001. Eigensystems.
4. J. H. Wilkinson. The algebraic eigenvalue problem. Monographs on Numerical Analysis. The Clarendon Press Oxford University Press, New York, 1988. Oxford Science Publications.
5. Richard S. Varga. Matrix iterative analysis, volume 27 of Springer Series in Computational Mathematics. Springer-Verlag, Berlin, expanded edition, 2000.
6. Alan George and Joseph W. H. Liu. Computer solution of large sparse positive definite systems. Prentice-Hall Inc., Englewood Cliffs, N.J., 1981. Prentice-Hall Series in Computational Mathematics.

270B: Numerical Approximation and Nonlinear Equations

Nonlinear Equations and Optimization

1. Scalar Equations: Fixed point iteration, bisection, Newton's method, secant method, order of convergence.
2. Nonlinear Systems: Steepest descent, Approximate Newton Methods, Kantorovich Theorem, Quasi Newton Methods, line search, trust region.
3. 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

1. Polynomial Interpolation: Lagrange Interpolation, divided differences, Aiken-Neville and Barycentric formulas, error estimates, Runge's example, Chebyshev approximation, orthogonal polynomials, least squares approximation.
2. Piecewise Polynomial Approximation: C^0 approximation spaces, error estimates for interpolation and least squares, Peano Kernel Theorem, Hermite and spline approximation.
3. Numerical Quadrature: Newton-Cotes and Gaussian Quadrature, basic and composite formulas, error estimates, singular integrals, Richardson extrapolation, Euler-Maclaurin Formula, Romberg integration, adaptive quadrature.

Specialized References for Mathematics 270B

1. Philip E. Gill, Walter Murray, and Margaret H. Wright. Practical optimization. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1981.
2. 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.
3. 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.
4. Carl de Boor. A practical guide to splines, volume 27 of Applied Mathematical Sciences. Springer-Verlag, New York, revised edition, 2001.
5. 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

1. 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).
2. Single-Step Methods: explicit and diagonally implicit Runge-Kutta and Runge-Kutta-Fehlberg methods, error estimates and order of convergence, absolute stability, A and L stability, stiff equations, adaptive time stepping.
3. Multi-Step 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

1. Theoretical Background: existence, uniqueness and stability for the 2-point BVP, Ritz and Galerkin variational formulations, Lax-Milgram Theorem.
2. Finite Difference Methods: derivation of finite difference equations, consistency, stability and error estimates, convection dominated problems.
3. Finite Element Methods: basic formulation, stability and error estimates, duality and Nitsche's trick, reference elements, streamline diffusion Petrov-Galerkin method for convection dominated problems.

Specialized References for Mathematics 270C

1. K. Eriksson, D. Estep, P. Hansbo, and C. Johnson. Computational differential equations. Cambridge University Press, Cambridge, 1996.
2. C. William Gear. Numerical initial value problems in ordinary differential equations. Prentice-Hall Inc., Englewood Cliffs, N.J., 1971.
3. E. Hairer, S. P. Nørsett, and G. Wanner. Solving ordinary differential equations. I, volume 8 of Springer Series in Computational Mathematics. Springer-Verlag, Berlin, second edition, 1993. Nonstiff problems.
4. E. Hairer and G. Wanner. Solving ordinary differential equations. II, volume 14 of Springer Series in Computational Mathematics. Springer-Verlag, Berlin, 1991. Stiff and differential-algebraic problems.
5. Kendall Atkinson and Weimin Han. Theoretical numerical analysis, volume 39 of Texts in Applied Mathematics. Springer, Dordrecht, third edition, 2009. A functional analysis framework.
6. Gilbert Strang and George J. Fix. An analysis of the finite element method. Prentice-Hall Inc., Englewood Cliffs, N. J., 1973. Prentice-Hall Series in Automatic Computation.

Math 273ABC Syllabus (2009-2010 version)

273A: Ordinary Differential Equations and Dynamical Systems

1. Linear operator theory [1,2]: Linear systems and exponentials of operators. Canonical forms of operators (nilpotent, Jordan, and real canonical forms).
2. Existence and Uniqueness [3,4]: Existence and uniqueness of solutions to initial value problems. Continuous dependence on initial conditions. Gronwall's inequality, Cauchy-Peano theorem, Picard-Lindelöf theorem.
3. Flow Maps [5,6]: Time-t maps, phase space and flow maps, first integrals, phase volume and the connection to the divergence of a vector field.
4. Dynamical Systems [7,2]: Qualitative analysis for nonlinear systems, phase portraits, classification of equilibria, Hartman-Grobman Theorem, Lyapunov stability theorem, Poincaré-Bendixson theorem. Brouwer fixed point theorem and its proof via the no-retraction theorem and the determinant lemma [8].
5. Classical mechanics [6,9]: Lagrangian and Hamiltonian systems with one degree of freedom. Hamilton's and Hamilton's phase space principle, Euler-Lagrange and Hamilton's equations. Generating functions and Hamilton-Jacobi theory.

References for Mathematics 273A

1. Morris W. Hirsch and Stephen Smale. Differential equations, dynamical systems, and linear algebra. Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974. Pure and Applied Mathematics, Vol. 60.
2. Lawrence Perko. Differential equations and dynamical systems, volume 7 of Texts in Applied Mathematics. Springer-Verlag, New York, third edition, 2001.
3. Jack K. Hale. Ordinary differential equations. Robert E. Krieger Publishing Co. Inc., Huntington, N.Y., second edition, 1980.
4. Earl A. Coddington and Norman Levinson. Theory of ordinary differential equations. McGraw-Hill Book Company, Inc., New York-Toronto-London, 1955.
5. Vladimir I. Arnol'd. Ordinary differential equations. Springer Textbook. Springer-Verlag, Berlin, 1992. Translated from the third Russian edition by Roger Cooke.
6. Ralph Abraham and Jerrold E. Marsden. Foundations of mechanics. Benjamin/Cummings Publishing Co. Inc. Advanced Book Program, Reading, Mass., 1978. Second edition, revised and enlarged, With the assistance of Tudor Ratiu and Richard Cushman.
7. John Guckenheimer and Philip Holmes. Nonlinear oscillations, dynamical systems, and bifurcations of vector fields, volume 42 of Applied Mathematical Sciences. Springer-Verlag, New York, 1990. Revised and corrected reprint of the 1983 original.
8. Yakar Kannai. An elementary proof of the no-retraction theorem. Amer. Math. Monthly, 88(4):264-268, 1981.
9. V. I. Arnol'd. Mathematical methods of classical mechanics, volume 60 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1989. Translated from the Russian by K. Vogtmann and A. Weinstein.

273B: Partial Differential Equations and Nonlinear Analysis

1. Linear Analysis [1,2]: Banach and Hilbert spaces. Linear operators, adjoints, four fundamental subspaces. Operator norms. Bounded, unbounded, closed, compact, projection operators. Fredholm alternative. Semi-groups. Linear functionals, dual space, reflexive and separable spaces. Strong, weak, weak-* topologies. Riesz, Hahn-Banach, Banach-Schauder, and Banach-Steinhaus Theorems.
2. Hyperbolic Partial Differential Equations [3,4]: First order systems and characteristics. Classification and well-posedness. Cauchy problem for hyperbolic equations, wave equation, conservation laws. Weak solutions, jump conditions, shocks. Weak, strong, symmetric hyperbolicity. Local and global existence.
3. Elliptic and Parabolic Partial Differential Equations [2,4]: Dirichlet and Neumann problems for elliptic and parabolic equations. Classical, strong, weak solutions. Distributions and fundamental solutions. Definition of Sobolev spaces. Ellipticity, inf-sup conditions, energy estimates, Lax-Milgram Theorem, existence, uniqueness. Maximum principles, a priori L^oo estimates, Harnack inequality.
4. Nonlinear Analysis [2,5,6]: Nonlinear maps in Banach spaces, variations, Gateaux and Frechet derivatives. Taylor expansion, Newton's Method. Inverse and Implicit Function Theorems, Bifurcation. Stationarity of functionals. Weakly closed sets, weak-lower-semi-continuity, reflexive Banach spaces, weak convergence. Existence of minimizers. Applications to nonlinear PDE.
5. Fixed-Point Techniques [2,5,7]: Fixed-point iteration, rates of convergence. Banach Fixed-Point Theorem. Ordered Banach spaces, maximum principle, monotone increasing maps. Method of sub- and super-solutions, compatible barriers. Extension of the Brouwer Theorem to the Schauder Fixed-Point Theorem. Homotopy and continuation methods. Applications to nonlinear PDE.

References for Mathematics 273B

1. E. Kreyszig. Introductory Functional Analysis with Applications. John Wiley & Sons, Inc., New York, NY, 1990.
2. I. Stakgold and M. Holst. Green's Functions and Boundary Value Problems. John Wiley & Sons, Inc., New York, NY, third edition, 2010.
3. M. Renardy and R. C. Rogers. An Introduction to Partial Differential Equations. Springer-Verlag, New York, NY, 1993.
4. L. C. Evans. Partial Differential Equations, volume 19 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 1998.
5. E. Zeidler. Nonlinear Functional Analysis and its Applications, volume I: Fixed Point Theorems. Springer-Verlag, New York, NY, 1991.
6. S. Fucik and A. Kufner. Nonlinear Differential Equations. Elsevier Scientific Publishing Company, New York, NY, 1980.
7. S. Kesavan. Topics in Functional Analysis and Applications. John Wiley & Sons, Inc., New York, NY, 1989.

273C: Applied Harmonic Analysis and Approximation Theory

1. Sobolev spaces [1,2] Classification of open bounded domains in R^n. Banach spaces C_k and L_p. Weak derivatives, W[k,p] norm, L_p-based Sobolev spaces W[k,p]. H[k,p] via completion of C_oo. Meyers-Serin Theorem (W=H). Embedding, compactness, density, extension, trace theorems. Poincare inequality. Hilbert spaces H[k]=W[k,2}. Fractional spaces W[s,p] via fractional norm or Fourier transform.
2. Besov spaces [3,4]: Holder spaces C[k,alpha]. Modulus of continuity, L_p modulus of smoothness. The B[s;p,q] norm and Besov space B[s;,p,q]. K-functionals. Norm, operator, and space interpolation. Relation to Sobolev and Potential spaces, third distinct construction of fractional order Sobolev spaces. The DeVore diagram. Approximation spaces. Interpolation and quasi-interpolation.
3. Wavelet Decomposition [5,6]: Haar system, piecewise linear systems, detail spaces. B-splines. Refinable functions, scaling function, multiresolution analysis. Orthogonal and biorthogonal wavelets. Jackson and Bernstein inequalities, Riesz stable bases. Interpolatory wavelets, semi-orthogonal wavelets, curvelets, ridglets, Fast wavelet transform. Vanishing moments and compression.
4. Approximation Theory [2,3,7]: Bernstein polynomials, Weierstrass Theorem. Best linear approximation in Banach Spaces, the Hilbert Space Projection Theorem. Petrov-Galerkin methods, inf-sup conditions, a priori and a posteriori error estimates. Nonlinear approximation and N-widths. Convergence and optimality of adaptive methods. Applications to linear and nonlinear PDE.
5. Applications to Operator Equations [2,6,8]: Iterative methods for linear operator equations. Integral equations, boundary integral methods. Sparse representation of integral operators. Optimal preconditioners for elliptic operators. Littlewood-Paley decomposition. Compression, compressed sensing, L_1-approximation.

References for Mathematics 273C

1. R. A. Adams and J. F. Fornier. Sobolev Spaces. Academic Press, San Diego, CA, second edition, 2003.
2. I. Stakgold and M. Holst. Green's Functions and Boundary Value Problems. John Wiley & Sons, Inc., New York, NY, third edition, 2010.
3. R. A. DeVore and G. G. Lorentz. Constructive Approximation. Springer-Verlag, New York, NY, 1993.
4. H. Triebel. Interpolation Theory, Function Spaces, and Differential Operators. North-Holland, Amsterdam, 1978.
5. I. Daubechies. Ten Lectures on Wavelets. SIAM, Philadelphia, PA, 1992.
6. Karstan Urban. Wavelet Methods for Elliptic Partial Differential Equations. Oxford University Press, New York, 2009.
7. D. Braess. Nonlinear Approximation Theory. Springer-Verlag, Berlin, Germany, 1980.
8. P. Oswald. Multilevel Approximation. B. G. Teubner, Stuttgart, Germany, 1994.