Syllabus

1. Numerical Computation
   1. General error analysis: problems vs. algorithms, data vs. computational error, error propagation, condition of a problem, stability of an algorithm, cancellation, ill-posed problems.
   2. Finite-precision computation: floating-point numbers, rounding rules, floating-point arithmetic.
   3. Operation counts.
2. Direct Methods for Dense Systems
   1. Linear spaces including geometric interpretation: subspaces, linear independence, span, dimension, rank, basis, range space, null space, determinants, Cramer's rule.
   2. Gaussian elimination, proof that it computes an LU factorization, existence and uniqueness of an LU factorization, partitioned matrices.
   3. Normed linear spaces including geometric interpretation: unit ball, vector and matrix norms, Frobenius norm, condition number of a matrix.
   4. Growth factor, diagonally dominant and positive definete matrices, partial pivoting, residual vs. error.
3. Least Squares Problems
   1. Inner product spaces including geometric interpretation.
   2. Linear least squares including geometric interpretation: normal equations, orthogonal projection.
   3. Orthogonal matrices, Householder reflections and Givens rotations, incl. geometric interpretation: use of Householder reflections for a QR factorization; derivation of the solution given a QR factorization.
   4. Gram-Schmidt orthogonalization (classical and modified).
   5. Singular Value Decomposition (SVD).
4. Eigenvalue problems
   1. Eigenvalues: similarity transformation, Gershgorin discs.
   2. Power method, inverse iteration, rate of convergence.
   3. Reduction to Hessenberg form via Householder reflections, special case of a symmetric matrix.
   4. Shifted QR iteration (single real or imaginary shift), special case of a Hessenberg and a symmetric tridiagonal matrix.
   5. Jacobi iteration.
5. Iterative Methods
   1. Stationary methods: point Jacobi, Gauss-Seidel, and successive overrelaxation (SOR), spectral radius and convergence, strictly diagonal and s.p.d. matrices.
   2. Gradient methods for s.p.d. systems: steepest descent, convergence, finite convergence property of conjugate gradient method.
6. Approximation of functions
   1. Polynomial interpolation: Hermite interpolation, Taylor expansion, remainder term as a divided difference, mean value theorem, Runge phenomenon for high order interpolation, Lagrange and Newton form, divided differences and their relationship to derivatives.
   2. Spline functions: natural cubic spline interpolation.
7. Initial Value Problems in ODE
   1. Euler and backward Euler discretization: nonstiff and stiff problems, truncation error, local and global error, error propagation.
   2. Taylor and Runge-Kutta methods.
   3. Stability analysis: test problem $y\prime = \lambda y$; solution of difference equations.
8. Boundary Value Problems for a Second Order ODE
   1. Shooting method.
   2. Collocation.
   3. Finite differences; order of accuracy.
9. Solution of Nonlinear Equations
   1. Single equation: bisection, secant, Newton-Raphson, order of convergence, multiple roots, hybrid methods with guaranteed convergence.
   2. Systems of equations: Newton's method.
10. Elliptic Partial Differential Equations
    1. Laplace and Poisson equation, essential and natural boundary conditions, trial and test functions, integration by parts.
    2. Linear and quadratic finite elements: stiffness matrix, load vectors, shape functions, basis functions, assembly from element matrices and element load vectors.
    3. Finite difference methods: 5-point start
    4. Solution of discrete elliptic equations: Direct methods: band and sparse solvers, re-ordering; nested dissection.
11. Time dependent Partial Differential Equations
    1. Parabolic PDE: Heat equation in 1 and 2 space dimensions.
    2. Hyperbolic PDE: wave equation in 1 and 2 space dimensions.
    3. von Neumann stability analysis; Courant-Fredrichs-Lewy (CFL) condition