numerical-analysis-toolbox

basic numerical analysis algorithms implemented in MATLAB for coursework.

---

algorithms list

1.Linear System

basic

• norm
  • vector norm (p,+inf,-inf)
  • matrix norm (1,2,inf,'fro')
• condition number
• rank
  • QR
  • SVD

direct methods for solving linear system

• Gaussian elimination
  • without pivoting
  • with partial pivoting
  • with complete pivoting
• Thomas method

matrix decomposition

• LU (Doolittle) decomposition
  • with partial pivoting
  • with complete pivoting
• decomposition for symmetric positive definite matrix
  • Cholesky decomposition
  • LDL decomposition
• QR decomposition
  • Gram-Schimidt orthogonalization
  • Givens transformation
  • Householder transformation
  • column pivoting

inverse and pseudo-inverse of matrix

• Newton iteration
• Gauss-Jordan method with complete pivoting
• triangle inverse
• QR decomposition
• SVD (Pseudo Inverse)
• LU decomposition

iterative method for solving linear system

• Jacobi iterative method
• Gauss-Seidel iterative method
• succesise over - relaxation method
  • SOR
  • symmetric SOR
• Krylov methods
  • CG
  • CGNE
  • CGNR
  • GMRES
  • MINRES
  • SYMMLQ
  • QMR
  • BiCG
  • CGS
  • BiCGstab
  • LSQR
  • preconditioning

2.Nonlinear Equation and System

single variable

• bisection method
• Steffensen acceleration for fixed-point iteration
• Newton method
• secant method
• Brent method
• Muller method

multivariable

• Newton method
• Broyden method
• homotopy continuation method
• solving nonlinear LS problem

polynomial

• Horner method
• finding roots using deflation
• finding roots using QR iteration

3.Eigenvalue and Singular Value

reduction

• Hessenberg
• bidiagonal
• tridiagonal

iterative method

• power iteration
• inverse iteration (with shift)
• Rayleigh quotient iteration
• Jacobi method

QR iteration

• single shift
• double shift
• symmetric

pratical methods

• eigenvalue
• eigenpair of symmetric matrix
• deflation method
• matrix balance
• singular value decomposition

4.Interpolation

1D

• polynomial interpolation
  • Lagrange polynomial
  • Newton polynomial
  • Neville algorithm
• Hermite interpolation
  • Lagrange polynomial
  • Newton polynomial
• Chebyshev interpolation
• nearest interpolation
• linear interpolation
• cubic spline interpolation
  • natural end conditions
  • not-a-knot end conditions

2D

• nearest interpolation
• linear interpolation

5.Function Approximation

orthogonal polynomials

• Legendre
• Laguerre
• Hermite
• Chebyshev

least square problem

• full rank least square
  • normal equation
  • QR
  • SVD
• rank deficient least square
  • QR
  • SVD
• weighted least square
• Tikhonov regularization
• polynomial fit

fast Fourier transform

• base 2
• base 3

6.Numerical Integration

1d

• trapezoid
• Simpson
• Gaussian quadrature
  • Gauss-Legendre
  • Gauss-Chebyshev
  • Gauss-Hermite
  • Gauss-Laguerre
• Romberg

2d

7.Numerical Differentiation

differentiation

gradient and jacobian

8.Ordinary Differential Equation

initail value problems

• Runge - Kutta method
  • classic
  • embedded
  • implicit
• Linear multistep method
  • Adams methods
  • implicit Adams methods
  • Adams-Bashforth four-step method with predictor-corrector

boundary value problems

9.Partial Differential Equation

• Poisson equation
• heat equation
• wave equation

10.Optimization

nonlinear least square

• Gauss-Newton
• Levenberg-Marquardt

derivative-free method

• Nelder - Mead

---

Demo

• Runge phenomenon
• minimize error of polynomial interpolation using Chebyshev interpolation
• optimal relaxation factor for SOR
• round-off error in numerical differentiation
• common orthogonal polynomials
• Chebyshev acceleration in linear iteration
• Gershgorin disc theorem

---

Bibliography

• 数值分析基础(第二版),关治,陆金甫. Fundamentals of Numerical Analysis (Second Edition), Zhi Guan, Jinfu Lu.
• Numerical Analysis, Rainer Kress
• An Introduction to Numerical Analysis, Endre suli and David F. Mayers
• Applied Numerical Linear Algebra, James W. Demmel
• Numerical Analysis (2nd edition), Timothy Sauer
• Numerical Analysis (9th edition), Richard L. Burden, J. Douglas Faires
• Matrix Computation (4th edition), Gene H. Golub, Charles F. Van Loan
• Numerical Optimization (2nd edition), Jorge Nocedal, Stephen J. Wright