Numerical Analysis Preliminary Exam Syllabus

Texts

  • A. J. Salgado and S. M. Wise, Classical Numerical Analysis, Chapters 3, 5-20, 23, 24, 28, 29
  • 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.

Scope and Expectations

The preliminary examination tests understanding of the numerical methods and analysis listed below.

Unless otherwise stated, students should be able to:

  • formulate and apply the methods listed;
  • derive standard forms of the methods in simple settings;
  • analyze their convergence, stability, accuracy, or sensitivity as appropriate; and
  • apply relevant theorems and error estimates.

Some topics listed below are identified as prerequisite background. Students are expected to know and use this material, but no exam question will be devoted solely to it.

In general students are expected to know the statement, application, and proof of theorems listed below, except in some cases noted explicitly below, where students are only expected to know the statement and application of a theorem, but not its proof.

1. Numerical Linear Algebra

1.1 Nonsingular Systems of Linear Equations

Background and Sensitivity

  • Existence and uniqueness of solutions (prerequisite background)
  • Sensitivity of solutions to perturbations
    • Forward error
    • Backward error
    • Condition numbers
  • Roundoff-error analysis is not included.

Direct Methods

  • Gaussian elimination with pivoting
  • Permuted LU factorization

Stationary Iterative Methods

  • General theory of stationary iterations
  • Richardson iteration
  • Jacobi iteration
  • Gauss-Seidel iteration

Nonstationary Iterative Methods

  • Steepest descent
  • MINRES
  • Conjugate gradients

1.2 Full-Rank Linear Least-Squares Problems

Background

  • Existence and uniqueness of least-squares solutions (prerequisite background)

Direct Methods

  • Solution through the normal equations using Gaussian elimination
  • Gram-Schmidt and modified Gram-Schmidt
  • QR factorization arising from Gram-Schmidt and modified Gram-Schmidt

Other methods for computing QR factorizations are not included.

1.3 Linear Eigenvalue Problems

Background

  • Diagonalization and Jordan form (prerequisite background)

Localization and Sensitivity

  • Gershgorin disks
  • Bauer-Fike theorem

Iterative Methods

  • Power method
  • Shifted power method
  • Inverse iteration

2. Nonlinear Equations and Optimization

2.1 Scalar Nonlinear Equations

  • Bisection method
  • Fixed-point iteration
  • Newton's method
  • Secant method
  • Convergence and error analysis for these methods, except for the proof of the rate of convergence for the secant method

2.2 Systems of Nonlinear Equations

  • Fixed-point methods
  • Newton's method
  • Convergence and error analysis

2.3 Unconstrained Optimization

Existence and Optimality

  • Existence of minimizers for continuous coercive functions on $\mathbb{R}^n$
  • Necessary optimality conditions for local extrema of smooth functions

Convexity

  • Basic properties of convex sets
  • Basic properties of convex functions on $\mathbb{R}^n$

Gradient Descent

  • Gradient descent with fixed step size
  • Convergence for convex functions
  • Convergence under assumptions involving Lipschitz continuity of the gradient

Line-search methods are not included.

3. Approximation, Interpolation, and Quadrature

3.1 Polynomial Interpolation in One Dimension

  • Lagrange interpolation
  • Newton divided differences
  • Hermite interpolation
  • Interpolation error analysis
  • Piecewise polynomial interpolation

3.2 Polynomial Approximation in One Dimension

Minimax Approximation

  • Weierstrass approximation theorem
  • Chebyshev equioscillation theorem

Least-Squares Approximation

  • Existence and uniqueness
  • Orthogonal polynomials
    • Roots
    • Three-term recurrence relations
  • L2 convergence

3.3 Quadrature

  • Derivation, construction, and error analysis of quadrature rules based on polynomial interpolation
  • Euler-Maclaurin formula
  • Richardson extrapolation
  • Romberg quadrature
  • Gaussian quadrature

4. Discrete Fourier Analysis

4.1 Trigonometric Approximation

Minimax Approximation

  • Density of trigonometric polynomials in the space of continuous periodic functions

Least-Squares Approximation

  • Existence and uniqueness
  • L2 convergence

4.2 Fourier Series and the Discrete Fourier Transform

  • Trapezoidal rule for periodic functions
  • Use of the discrete Fourier transform to compute Fourier-series coefficients

4.3 Trigonometric Interpolation

  • One-dimensional trigonometric interpolation
  • Discrete Fourier transform
  • Aliasing

5. Numerical Methods for Ordinary Differential Equations

5.1 Initial-Value Problems

Background

  • Existence and uniqueness of solutions (prerequisite background)

One-Step Methods

  • Local truncation error
  • Convergence analysis
  • Discrete Gronwall inequality

Runge-Kutta Methods

  • Definition of Runge-Kutta methods
  • Butcher tableau notation

Runge-Kutta order conditions are not included.

Linear Multistep Methods

  • Local truncation error
  • Consistency
  • Order conditions
  • Zero stability
  • Root condition
  • Dahlquist equivalence theorem
  • Dahlquist first barrier

Linear Stability

For both Runge-Kutta and linear multistep methods:

  • Linear stability
  • Absolute stability
  • A-stability

For linear multistep methods:

  • Dahlquist second barrier

Students should know the statements and applications of the Dahlquist equivalence theorem and the first and second Dahlquist barriers, but are not expected to know their proofs.

Boundary-value problems are treated as a special one-dimensional case of elliptic partial differential equations.

6. Finite Difference Methods for Linear Partial Differential Equations

The examination is concerned with equispaced finite-difference methods for standard linear PDE model problems.

6.1 Consistency and Accuracy

  • Construction of finite-difference approximations on uniform grids
  • Consistency
  • Local truncation error

6.2 Stability

For discretizations of parabolic and hyperbolic PDEs:

  • Von Neumann stability analysis
  • Conditional stability
  • Unconditional stability

6.3 Convergence

For discretizations of parabolic and hyperbolic PDEs:

  • Convergence of finite-difference schemes
  • Relationship among consistency, stability, and convergence