List of numerical analysis topics
From Wikipedia, the free encyclopedia
This is a list of numerical analysis topics, by Wikipedia page.
[edit] General
- Iterative method
- Sequence transformations — methods to accelerate the speed of convergence
- Level set method
- Level set (data structures) — data structures for representing level sets
- Abramowitz and Stegun
- Curse of dimensionality
- Superconvergence
- Termination
- Discretization
- Collocation method — discretizes a continuous equation by requiring it only to hold at certain points
- Difference quotient
- Computational complexity of mathematical operations
[edit] Error
- Approximation
- Approximation error
- Condition number
- Discretization error
- Floating point number
- Guard digits — extra precision introduced during a computation to reduce round-off error
- Arbitrary-precision arithmetic
- Hilbert matrix
- Loss of significance
- Numerical stability
- Precision (arithmetic)
- Propagation of uncertainty
- Round-off error
- Significant figures
- Truncation
- Well-posed problem
- Affine arithmetic
[edit] Elementary and special functions
- Summation:
- Multiplication:
- Multiplication algorithm — general discussion, simple methods
- Karatsuba algorithm — the first algorithm which is faster than straightforward multiplication
- Toom-Cook multiplication — generalization of Karatsuba multiplication
- Schönhage-Strassen algorithm — based on Fourier transform, asymptotically fastest
- Exponentiation:
- Polynomials:
- Square roots and other roots:
- Elementary functions (exponential, logarithm, trigonometric functions):
- Generating trigonometric tables
- CORDIC — shift-and-add algorithm using a table of arc tangents
- BKM algorithm — shift-and-add algorithm using a table of logarithms and complex numbers
- Gamma function:
- Lanczos approximation
- Spouge's approximation — modification of Stirling's approximation; easier to apply than Lanczos
- Computation of π:
- Gauss-Legendre algorithm — iteration which converges quadratically to π, based on arithmetic-geometric mean
- Bailey-Borwein-Plouffe formula — can be used to compute individual hexadecimal digits of π
- Borwein's algorithm — iteration which converges quartically to 1/π
- Borwein's algorithm (others)
[edit] Numerical linear algebra
Numerical linear algebra — study of numerical algorithms for linear algebra problems
- Types of matrices appearing in numerical analysis:
- Algorithms for matrix multiplication:
- Strassen algorithm
- Coppersmith–Winograd algorithm
- Freivald's algorithm — a randomized algorithm for checking the result of a multiplication
- Solving a system of linear equations:
- Gaussian elimination
- Row echelon form — matrix in which all entries below a nonzero entry are zero
- Reduced row echelon form — matrix in row echelon form, in which the leading coefficients are one and have only zeros above them
- Gauss–Jordan elimination — variant in which the entries below the pivot are also zeroed
- Tridiagonal matrix algorithm — simplified form of Gaussian elimination for tridiagonal matrices
- LU decomposition
- Block LU decomposition
- Cholesky decomposition — for solving a system with a positive definite matrix
- Levinson recursion — for solving a system with a Toeplitz matrix
- Iterative methods:
- Jacobi method
- Gauss-Seidel method
- Successive over-relaxation (SOR) — a technique to accelerate the Gauss-Seidel method
- Conjugate gradient method — assumes that the matrix is positive definite
- Biconjugate gradient method (BiCG)
- Generalized minimal residual method (GMRES) — based on the Arnoldi iteration
- Stone method — uses an incomplete LU decomposition
- Preconditioner
- Gaussian elimination
- Eigenvalue algorithms:
- Power iteration
- Inverse iteration
- Rayleigh quotient iteration
- Arnoldi iteration — based on Krylov subspaces
- Lanczos algorithm — Arnoldi, specialized for positive-definite matrices
- QR algorithm
- Jacobi eigenvalue algorithm — select a small submatrix which can be diagonalized exactly, and repeat
- Jacobi rotation — the building block, almost a Givens rotation
- Divide-and-conquer eigenvalue algorithm
- Orthogonalization algorithms:
- QR decomposition
- Krylov subspace
- Block matrix pseudoinverse
- Bidiagonalization
[edit] Interpolation
- Nearest neighbor interpolation
- Polynomial interpolation
- Linear interpolation
- Runge's phenomenon
- Vandermonde matrix
- Chebyshev polynomials
- Chebyshev nodes
- Lebesgue constant (interpolation)
- Different forms for the interpolant:
- Newton polynomial
- Divided differences
- Neville's algorithm — for evaluating the interpolant; based on the Newton form
- Lagrange polynomial
- Bernstein polynomial
- Newton polynomial
- Extensions to multiple dimensions:
- Hermite interpolation
- Birkhoff interpolation
- Spline interpolation
- Spline (mathematics)
- Cubic Hermite spline
- Hermite spline
- Cardinal spline
- Kochanek-Bartels spline
- Catmull-Rom spline
- Bézier spline
- B-spline
- Truncated power function
- De Boor's algorithm — generalizes De Casteljau's algorithm
- Nonuniform rational B-spline (NURBS)
- Blossom (mathematics) — a unique, affine, symmetric map associated to a polynomial or spline
- See also: List of numerical computational geometry topics
- Simple rational approximation
- Slerp
- Wavelet
- Inverse distance weighting
- Trigonometric interpolation
- Fast Fourier transform
- Bluestein's FFT algorithm
- Bruun's FFT algorithm
- Cooley-Tukey FFT algorithm
- Split-radix FFT algorithm — variant of Cooley-Tukey that uses a blend of radices 2 and 4
- Goertzel algorithm
- Prime-factor FFT algorithm
- Rader's FFT algorithm
- Butterfly diagram
- Twiddle factor — the trigonometric constant coefficients that are multiplied by the data
- Sigma approximation
- Fast Fourier transform
- Radial basis function
- Polyharmonic spline — a commonly used radial basis function
- Irrational base discrete weighted transform
- Pick matrix — appears when interpolating by analytic functions which must be bounded in the unit disc
- Pareto interpolation
- Extrapolation
- Regression analysis
- Approximation theory
- Orders of approximation
- Lebesgue's lemma
- Curve fitting
- Remez algorithm — for constructing the best polynomial approximation
- Surrogate model — application: replacing a function that is hard to evaluate by a simpler function
- Different approximations:
- Curve-fitting compaction
[edit] Finding roots of nonlinear equations
- See #Numerical linear algebra for linear equations
- General methods:
- Methods for polynomials:
- Methods for other special cases:
- Analysis:
[edit] Optimization
- Concepts:
- Continuous optimization
- Discrete optimization is not a part of numerical analysis
- Linear programming (also treats integer programming)
- Quadratic programming
- Convex optimization
- Semidefinite programming
- Second order cone programming
- Nonlinear programming
- Descent direction
- Linesearch
- Gradient descent
- Newton's method in optimization
- BFGS method
- Nelder-Mead method
- Golden section search
- Tabu search
- Nonlinear least squares
- Gauss-Newton algorithm
- Levenberg-Marquardt algorithm
- Expectation-maximization algorithm
- Osem (mathematics) — ordered subset expectation maximization
- Nearest neighbor search
- Mixed complementarity problem
- Combinatorial optimization
- Stochastic programming
- Dynamic programming
- Global optimization:
- Random optimization algorithms:
- Simulated annealing
- Adaptive simulated annealing — variant in which the algorithm parameters are adjusted during the computation.
- Great Deluge algorithm
- Evolutionary algorithm, Evolution strategy
- Memetic algorithm
- Particle swarm optimization
- Cooperative optimization
- Stochastic tunneling
- see also the section Monte Carlo method
- Simulated annealing
- Infinite-dimensional optimization
- Optimal substructure
- Algorithmic concepts:
- Theoretical aspects:
- Applications:
- Mathematical Programming Society
[edit] Numerical integration
- Rectangle method
- Trapezium rule
- Simpson's rule
- Newton-Cotes formulas
- Gaussian quadrature
- Romberg's method
- Clenshaw-Curtis quadrature — based on expanding the integrand in terms of Chebyshev polynomials
- Monte Carlo integration — takes random samples of the integrand
- See also #Monte Carlo method
- T-integration — a non-standard method
- Lebedev grid — grid on a sphere with octahedral symmetry
- Sparse grid
- Numerical differentiation
- Euler-Maclaurin formula
[edit] Numerical ordinary differential equations
Numerical ordinary differential equations — the numerical solution of ordinary differential equations (ODEs)
- Euler integration — the most basic method for solving an ODE
- Explicit and implicit methods — implicit methods need to solve an equation at every step
- Runge–Kutta methods — one of the two main classes of methods for initial-value problems
- Midpoint method — a second-order method with two stages
- Multistep method — the other main class of methods for initial-value problems
- Methods designed for the solution of ODEs from classical physics:
- Newmark-beta method — based on the extended mean-value theorem
- Verlet integration — a popular second-order method
- Beeman's algorithm — a two-step method extending the Verlet method
- Geometric integrator — a method that preserves some geometric structure of the equation
- Symplectic integrator — a method for the solution of Hamilton's equations that preserves the symplectic structure
- Stiff equation — roughly, an ODE for which the unstable methods needs a very short step size, but stable methods do not.
- Shooting method — a method for the solution of boundary-value problems
- Methods for solving stochastic differential equations (SDEs):
- Euler-Maruyama method — generalization of the Euler method for SDEs
- Milstein method — a method with strong order one
- Runge–Kutta method (SDE) — generalization of the family of Runge–Kutta methods for SDEs
- Bi-directional delay line
[edit] Numerical partial differential equations
Numerical partial differential equations — the numerical solution of partial differential equations (PDEs)
- Methods for the solution of PDEs:
- Finite difference method — based on approximating differential operators with difference operators
- Finite difference — the discrete analogue of a differential operator
- Difference operator — the numerator of a finite difference
- Discrete Laplace operator — finite-difference approximation of the Laplace operator
- Discrete Poisson equation — discrete analogue of the Poisson equation using the discrete Laplace operator
- Five-point stencil — standard finite-difference approximation of the Laplace operator in two dimensions
- Crank-Nicolson method — second-order method for heat and related PDEs
- Finite-difference time-domain method — a finite-difference method for electrodynamics
- Finite difference — the discrete analogue of a differential operator
- Finite element method, finite element analysis — based on a discretization of the space of solutions
- Finite element method in structural mechanics — a physical approach to finite element methods
- Galerkin method — a finite element method in which the residual is orthogonal to the finite element space
- Rayleigh-Ritz method — a finite element method based on variational principles
- Direct stiffness method — a particular implementation of the finite element method, often used in structural analysis
- Spectral method — based on the Fourier transformation
- Numerical method of lines — reduces the PDE to a large system of ordinary differential equations
- Boundary element method — based on transforming the PDE to an integral equation on the boundary of the domain
- Analytic element method — similar to the boundary element method, but the integral equation is evaluated analytically
- Finite volume method — based on dividing the domain in many small domains; popular in computational fluid dynamics
- Godunov's scheme — first-order conservative scheme for fluid flow, based on piecewise constant approximation
- MUSCL scheme — second-order variant of Godunov's scheme
- AUSM — advection upstream splitting method
- Discrete element method — a method in which the elements can move freely relative to each other
- Meshfree methods — does not use a mesh, but uses a particle view of the field
- Uniform theory of diffraction — specifically designed for scattering problems in electromagnetics
- High resolution scheme
- Split-step method
- Finite difference method — based on approximating differential operators with difference operators
- Techniques for improving these methods:
- Multigrid, multigrid method — uses a hierarchy of nested meshes to speed up the methods
- Domain decomposition method — divides the domain in a few subdomains and solves the PDE on these subdomains
- Adaptive mesh refinement — uses the computed solution to refine the mesh only where necessary
- Broad classes of methods:
- Mimetic methods — methods that respect in some sense the structure of the original problem
- Multiphysics — models consisting of various submodels with different physics
- Analysis:
- Courant–Friedrichs–Lewy condition — stability condition for hyperbolic PDEs
- Numerical diffusion — diffusion introduced by the numerical method, above to that which is naturally present
- Numerical resistivity — the same, with resistivity instead of diffusion
- Weak formulation — a functional-analytic reformulation of the PDE necessary for some methods
- Total variation diminishing — property of schemes that do not introduce spurious oscillations
- Godunov's theorem — linear monotone schemes can only be of first order
- Boundary conditions:
[edit] Monte Carlo method
- Variants of the Monte Carlo method:
- Box-Muller transform
- Low-discrepancy sequence
- Event generator
- Parallel tempering
- Variance reduction techniques:
- Applications:
- Metropolis light transport
- Monte Carlo methods in finance
- Quantum Monte Carlo
- Auxiliary field Monte Carlo — computes averages of operators in many-body quantum mechanical problems
- Cross-entropy method — for multi-extremal optimization and importance sampling
- Also see the list of statistics topics
[edit] Applications
- Climate model
- Computational chemistry
- Computational electromagnetics
- Computational fluid dynamics
- Large eddy simulation
- Smoothed particle hydrodynamics
- Acoustic analogy — used in numerical aeroacoustics to reduce sound sources to simple emitter types
- Computational physics
- Numerical model of solar system
[edit] Software
For software, see the list of numerical analysis software
