everything.study
18.335

Introduction to Numerical Methods

3-0-9 units · Graduate

Advanced introduction to numerical analysis: accuracy and efficiency of numerical algorithms. In-depth coverage of sparse-matrix/iterative and dense-matrix algorithms in numerical linear algebra (for linear systems and eigenproblems). Floating-point arithmetic, backwards error analysis, conditioning, and stability. Other computational topics (e.g., numerical integration or nonlinear optimization) may also be surveyed. Final project involves some programming.

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

Prerequisites & course information

Same subject as 6.7310J Prereq: 18.06 , 18.700 , or 18.701 Acad Year 2027-2028: Not offered Acad Year 2028-2029: G (Fall) 3-0-9 units

Sources