Numerical Analysis Preliminary Exam Syllabus

The exam is based on APPM 5600-5610

Texts

  • K. Atkinson, Introduction to Numerical Analysis (except Chapter 1).
  • G. Golub and C. Van Loan, Matrix Computations, Chapters 2-5, 7, 10.
  • K. W. Morton and D. F. Mayers, Numerical Solution of Partial Differential Equations,Chapters 2.2,  2.4,  2.6-2.9,  3.1,  3.2,  4.2,  5.1-5.5.

Recommended Supplemental Text

  • J. Stoer and R. Bulirsch, Introduction to Numerical Analysis.

Topics

The following topics are covered in APPM 5600-5610.
The prelim does NOT cover any additional APPM 6610 topics.

Interpolation Theory

  • General aspects of polynomial interpolation theory.
  • Formulations in different basis, e.g. Lagrange, Newton etc. and their approximation and computational properties (convergence, error bounds, conditioning, complexity, forward and backward error analysis etc.).
  • Hermite interpolation and its properties.
  • Piecewise polynomial interpolation and spline interpolation.
  • Trigonometric interpolation, Fourier series, DFT and FFT.

Approximation of Functions

  • The Weierstrass Theorem and Taylor's Theorem
  • The minimax approximation problem
  • The least squares approximation problem
  • Orthogonal polynomials and their properties

Rootfinding for Nonlinear Equations

  • Properties and formulations of basic rootfinding methods, e.g. the bisectionmethod, Newton's method and the secant method.
  • Existence, uniqueness and convergence of one-step iteration methods.
  • Aitken extrapolation for linearly convergent sequences.
  • Systems of nonlinear equations.
  • Newton's method for nonlinear systems.
  • Basic unconstrained optimization.

Numerical Integration

  • Properties and formulation of Newton-Cotes integration formulae, e.g. the trapezoidal rule and Simpson's rule.
  • Properties and construction of Gaussian quadrature.
  • Asymptotic error formulae for quadrature and their applications.

Linear Algebra

  • Eigenvalues and canonical forms / factorizations of matrices.
  • Vector and matrix norms, condition numbers.
  • Sherman-Morrison type formulas.

Numerical Solution of Systems of Linear Equations, Direct methods

  • Gaussian elimination, formulations, analysis and variations (pivoting strategies etc.).
  • Forward and backward error analysis.
  • Solution techniques for least squares problems.

Numerical Solution of Systems of Linear Equations, Iterative Methods

  • Formulation and analysis of basic stationary methods e.g. Gauss-Jacobi, Gauss-Seidel.
  • The numerical solution of Poisson's equation.
  • The conjugate gradient method.

The Matrix Eigenvalue Problem

  • Eigenvalue location, error, perturbation, and stability results.
  • Formulation and analysis of the power method and its variations.
  • Orthogonal transformations of Householder and Givens type.
  • Properties of the eigenvalues of a symmetric tridiagonal matrix.
  • The QR Method for eigenvalues and eigenvectors.

Numerical Methods for Ordinary Differential Equations

  • Existence, uniqueness, and stability theory.
  • Derivation and stability and convergence analysis of linear multistep methods (e.g. Euler’s, midpoint and trapezoidal method).
  • Derivation and analysis of single-step and Runge-Kutta methods.
  • Formulation of predictor corrector methods.
  • Discretization of boundary value problems.

Introduction to Linear Parabolic and Hyperbolic PDEs

  • Understanding of convergence, stability and consistency and their connection through the Lax Equivalence Theorem.
  • Techniques for analyzing periodic finite difference methods including von Neumann, energy and CFL / domain of dependence techniques.
  • Finite difference methods for parabolic problems in one space dimension: analysis of stability, convergence and consistency of explicit and implicit formulations.
  • Methods and analysis techniques for Hyperbolic problems in one space dimension.