readme

This note is outcome of Spring 25 CS 450. Numerical Analysis in UIUC taught by instructor Paul Fischer.
The book is Scientific Computing: An Introductory Survey, Revised Second Edition.

Topics by type

Recap

Types of Matrix

Factorization:

• LU factorization
  • Cholesky factorization w/ SPD
• QR factorization based on orthogonal
• Singular value decomposition (SVD)

Solving:

• Forward-backward substitution w/ LU factorization
• normal equation w/ Vandermonde matrix to solve polynomial

Eigenvalue and Eigenvector problem:

• Eigenvalue and Eigenvector
• Find Eigenvectors by iterations:
  • power iteration and it’s variants normalized power iteration and power iteration with shift
  • inverse iteration
  • Rayleigh quotient iteration and Rayleigh quotient
  • deflation
  --- multi eign-solver ---
  • orthogonal iteration and QR iteration

Nonlinear equations:

• convergence rate: how fast is a method finding solutions
• multiplicity
• bisection method
• Aitken’s method
• Newton’s method and it’s variants Secant’s method, Muller’s method
• Newton’s method - multi for system of nonlinear equations and it’s variants Broyden’s Method
• inverse quadratic interpolation

Optimization:

• some terms: coercive, convex, level set, unimodal, critical points, gradient, Hessian matrix
• Golden Section Search, Newton’s method, Successive Parabolic Interpolation for single variable (1-D)
• Newton’s method, BFGS Method, Steepest Descent Method, Conjugate Gradient Method for system of variables(n-D)
• Gauss Newton Method, Levenberg-Marquardt method and Nonlinear Least Squares
• Constrained Optimality: Lagrangian function

Polynomial Interpolation:

• there are mainly two types:
  • global, like using basis function, Lagrange Interpolation or orthogonal polynomial interpolation (with Legendre Polynomials or Chebyshev Polynomials), Chebyshev interpolation (basically interpolation used Chebyshev nodes)
  • piece-wise linear or piece-wise polynomial (more stable than global) like Splines
• The error analysis for global interpolation: interpolation error

Numerical Integration and Differentiation:

• Richardson Extrapolation
• basic difference
• Quadrature, Newton-Cotes Quadrature and Gaussian Quadrature

Ordinary Differential Equations:

• Forward Euler and Backward Euler
• Trapezoidal Rule and Runge-Kutta method

Topics by Chapter

Chapter 1 Introduction

Chapter 2 System of linear equations

Chapter 3 Linear Least Squares

Chapter 4 Eigenvalue problems

Chapter 5 Nonlinear equations

Chapter 6 Optimization

Chapter 7 Interpolation

Chapter 8 Numerical Integration and Differentiation

Chapter 9 Ordinary Differential Equations