Scientific Computing Group
	Department of Computer Science
	University of Illinois at Urbana-Champaign

Numerical Analysis PhD Qualifying Examination

Examination Syllabus

Numerical Computation

• General error analysis: well-posed problems, problems vs. algorithms, data error vs. computational error, forward error vs. backward error, conditioning of a problem, stability of an algorithm.
• Finite-precision computation: floating-point numbers, rounding rules, machine precision, floating-point arithmetic, cancellation.
• Operation counts, "big O" notation.

Systems of Linear Equations

• Mathematical background: vector spaces, subspaces, linear independence, rank, dimension, span, basis, null space, determinant, existence and uniqueness of solutions to linear systems, permutation matrices, transpose, conjugate transpose, symmetric matrices, Hermitian matrices, partitioned matrices.
• Norms and conditioning: vector norm, matrix norm, condition number of a matrix, error bounds for solutions to linear systems, residual vs. error.
• Gaussian elimination: LU factorization, permutations, partial pivoting, complete pivoting, growth factor, scaling, diagonal dominance, iterative refinement, Gauss-Jordan elimination, rank-one updating.
• Symmetric matrices: symmetric positive definite matrices, Cholesky factorization, symmetric indefinite systems.
• Sparse linear systems: band matrices, sparse storage schemes, graph of a matrix, graph interpretation of elimination, fill, reordering for sparsity, nested dissection, minimum degree.
• Stationary iterative methods: spectral radius, convergence rate, Jacobi, Gauss-Seidel, and SOR methods.
• Conjugate gradient method: finite convergence, optimality, conjugacy of search directions.

Linear Least Squares Problems

• Mathematical background: orthogonality, idempotence, orthogonal projectors, existence and uniqueness of least squares solutions to (not necessarily square) linear systems, normal equations.
• Orthogonalization methods: orthogonal matrices, Householder reflections, Givens rotations, QR factorization, classical and modified Gram-Schmidt orthogonalization.
• Singular value decomposition: rank, Euclidean norm, condition number, and pseudoinverse of a matrix in terms of its SVD; orthonormal bases, lower-rank approximation.

Algebraic Eigenvalue Problems

• Mathematical background: eigenvalues, characteristic polynomial, Cayley-Hamilton Theorem, algebraic and geometric multiplicity, defective matrix, diagonalizable matrices, normal matrices, invariant subspaces, block triangular matrices, Schur form, real Schur form, Jordan form, Gershgorin Theorem.
• Power method, inverse iteration, Raleigh quotient iteration, deflation.
• QR iteration: simultaneous iteration, orthogonal iteration, QR iteration, reduction to Hessenberg or tridiagonal form, shifts.
• Krylov subspace methods: Lanczos iteration, Arnoldi iteration
• Jacobi iteration

Nonlinear Equations and Optimization

• Mathematical background: Intermediate Value Theorem, Inverse Function Theorem, Contraction Mapping Theorem, coerciveness, convexity, gradient vector, Hessian matrix, optimality conditions.
• Convergence rates, order of convergence, simple vs. multiple root.
• Single equations: bisection, fixed-point iteration, Newton's method, secant method, inverse interpolation, safeguarded methods.
• Systems of equations: fixed-point iteration, Jacobian matrix, Newton's method, Broyden's method, robust (damped or trust-region) Newton-like methods.
• One-dimensional optimization: golden section search, successive parabolic interpolation, Newton's method, safeguarded methods.
• Multidimensional unconstrained optimization: steepest descent method, Newton's method, quasi-Newton methods, conjugate gradient method, line search, trust-region methods.

Interpolation and Approximation

• Mathematical background: existence and uniqueness of interpolant.
• Polynomial interpolation: Vandermonde matrix, Lagrange and Newton forms, divided differences, Hermite interpolation, convergence and error bound for polynomial interpolation of a continuous function, Runge phenomenon, Chebyshev points, Taylor polynomial.
• Piecewise polynomial interpolation: Hermite cubic interpolation, splines, cubic spline interpolation, natural cubic spline.
• Trigonometric interpolation: discrete Fourier transform, FFT algorithm
• Orthogonal polynomials: function spaces, inner products, orthogonality, Gram-Schmidt orthogonalization, three-term recurrence, Legendre polynomials, Chebyshev polynomials.
• Polynomial approximation: Weierstass Approximation Theorem, best uniform approximation, least squares approximation.

Numerical Integration and Differentiation

• Mathematical background: Riemann sums, existence of Riemann integral, ill-posedness of differentiation.
• Numerical quadrature: interpolatory quadrature, method of undetermined coefficients, moment equations, Newton-Cotes quadrature, midpoint rule, trapezoid rule, Simpson's rule, Gaussian quadrature, composite quadrature, adaptive quadrature.
• Extrapolation methods: Richardson extrapolation, Romberg integration
• Numerical differentiation: conditioning, interpolation, smoothing, finite difference approximations.

Initial Value Problems for ODEs

• Mathematical background: order, reduction to first order, autonomous systems, stability of solutions, linear homogeneous systems with constant coefficients, Jacobian matrix for a nonlinear system.
• Basic numerical methods: Euler's method, backward Euler method, trapezoid method.
• Accuracy and stability: truncation error, local error, global error, order of accuracy, stability of numerical method, scalar test problem, convergence, difference equations, root condition, local error estimation, step size control.
• Multistep methods: explicit and implicit Adams methods, predictor-corrector methods, backward differentiation formulas, solution of implicit equations.
• Taylor series, Runge-Kutta, and extrapolation methods.

Boundary Value Problems for ODEs

• Mathematical background: fundamental matrix, Green's function, dichotomy.
• Shooting method
• Finite difference method
• Collocation method
• Galerkin method

Numerical Solution of Elliptic PDEs

• Mathematical background: Laplace, Poisson, and Helmholtz equations; essential (Dirichlet) and natural (Neumann) boundary conditions.
• Weighted residual methods: weak form, trial and test functions; Divergence Theorem and integration by parts, Rayleigh-Ritz-Galerkin method, stiffness matrix and load vector.
• Finite element methods: linear and quadratic finite elements, shape functions, basis functions, quadrature, assembly.
• Finite difference methods: five-point stencil, symmetry and positive definiteness, fast direct solvers (e.g., cyclic reduction).

Numerical Solution of Parabolic PDEs

• Mathematical background: heat equation in one and two space dimensions, boundary conditions, advection-diffusion equation, Burgers' equation, ill-posedness of backward heat equation.
• Numerical methods: theta method, Crank-Nicolson method, method of lines, ADI.
• Accuracy and stability: local and global truncation error, Fourier (von Neumann) stability analysis.
• Linearization of nonlinear discrete equations by Newton's method.

Numerical Solution of Hyperbolic PDEs

• Mathematical background: classification of first-order systems and second-order single equations, characteristics, domain of dependence.
• Conservation laws: advection equation, wave equation, inviscid Burgers' equation.
• Finite difference methods: consistency, stability, convergence, Lax Equivalence Theorem, Fourier (von Neumann) stability analysis.

Scientific Computing Group, Department of Computer Science, University of Illinois at Urbana-Champaign, 201 N. Goodwin Ave., Urbana, IL 61801, USA.