everything.study
6.337

Introduction to Numerical Methods

Graduate · Historical course

Spring 2019 · Introduction to Numerical Methods

Topics

  • Course overview, Newton’s method for root-finding
  • Floating-point arithmetic
  • Floating-point summation and backwards stability
  • Norms on vector spaces
  • Condition numbers
  • Numerical methods for ordinary differential equations
  • The SVD, its applications, and condition numbers
  • Linear regression and the generalized SVD
  • Solving the normal equations by QR and Gram-Schmidt
  • Modified Gram-Schmidt and Householder QR
  • Matrix operations, caches, and blocking
  • Cache-oblivious algorithms and spatial locality
  • LU factorization and partial pivoting
  • Cholesky factorization and other specialized solvers. Eigenproblems and Schur factorizations
  • Eigensolver algorithms: Companion matrices, ill-conditioning, and Hessenberg factorization
  • The power method and the QR algorithm
  • Shifted QR and Rayleigh quotients
  • Krylov methods and the Arnoldi algorithm
  • Arnoldi and Lanczos with restarting
  • The GMRES algorithm and convergence of GMRES and Arnoldi
  • Preconditioning techniques. The conjugate-gradient method
  • Convergence of conjugate gradient
  • Biconjugate gradient algorithms
  • Sparse-direct solvers
  • Overview of optimization algorithms
  • Adjoint methods
  • Adjoint methods for eigenproblems and recurrence relations
  • Trust-regions methods and the CCSA algorithm
  • Lagrange dual problems
  • Quasi-Newton methods and the BFGS algorithm
  • Derivation of the BFGS update
  • Derivative-free optimization by linear and quadratic approximations
  • Numerical integration and the convergence of the trapezoidal rule
  • Clenshaw-Curtis quadrature
  • Chebyshev approximation
  • Integration with weight functions, and Gaussian quadrature
  • Adaptive and multidimensional quadrature
  • The discrete Fourier transform (DFT) and FFT algorithms
  • FFT algorithms and FFTW

Readings

Sources