List of numerical analysis topics
(Redirected from Outline of numerical analysis)
This is a list of numerical analysis topics.
General
- Validated numerics
- Iterative method
- Rate of convergence — the speed at which a convergent sequence approaches its limit
- Order of accuracy — rate at which numerical solution of differential equation converges to exact solution
- Series acceleration — methods to accelerate the speed of convergence of a series
- Aitken's delta-squared process — most useful for linearly converging sequences
- Minimum polynomial extrapolation — for vector sequences
- Richardson extrapolation
- Shanks transformation — similar to Aitken's delta-squared process, but applied to the partial sums
- Van Wijngaarden transformation — for accelerating the convergence of an alternating series
- Abramowitz and Stegun — book containing formulas and tables of many special functions
- Digital Library of Mathematical Functions — successor of book by Abramowitz and Stegun
- Curse of dimensionality
- Local convergence and global convergence — whether you need a good initial guess to get convergence
- Superconvergence
- Discretization
- Difference quotient
- Complexity:
- Computational complexity of mathematical operations
- Smoothed analysis — measuring the expected performance of algorithms under slight random perturbations of worst-case inputs
- Symbolic-numeric computation — combination of symbolic and numeric methods
- Cultural and historical aspects:
- General classes of methods:
- Collocation method — discretizes a continuous equation by requiring it only to hold at certain points
- Level-set method
- Level set (data structures) — data structures for representing level sets
- Sinc numerical methods — methods based on the sinc function, sinc(x) = sin(x) / x
- ABS methods
Error
- Approximation
- Approximation error
- Catastrophic cancellation
- Condition number
- Discretization error
- Floating point number
- Guard digit — extra precision introduced during a computation to reduce round-off error
- Truncation — rounding a floating-point number by discarding all digits after a certain digit
- Round-off error
- Arbitrary-precision arithmetic
- Interval arithmetic — represent every number by two floating-point numbers guaranteed to have the unknown number between them
- Interval contractor — maps interval to subinterval which still contains the unknown exact answer
- Interval propagation — contracting interval domains without removing any value consistent with the constraints
- Loss of significance
- Numerical error
- Numerical stability
- Error propagation:
- Relative change and difference — the relative difference between x and y is |x − y| / max(|x|, |y|)
- Significant figures
- Artificial precision — when a numerical value or semantic is expressed with more precision than was initially provided from measurement or user input[1]
- False precision — giving more significant figures than appropriate
- Sterbenz lemma
- Truncation error — error committed by doing only a finite numbers of steps
- Well-posed problem
- Affine arithmetic
Elementary and special functions
- Unrestricted algorithm
- Summation:
- Kahan summation algorithm
- Pairwise summation — slightly worse than Kahan summation but cheaper
- Binary splitting
- 2Sum
- 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 very fast
- Fürer's algorithm — asymptotically slightly faster than Schönhage–Strassen
- Division algorithm — for computing quotient and/or remainder of two numbers
- Long division
- Restoring division
- Non-restoring division
- SRT division
- Newton–Raphson division: uses Newton's method to find the reciprocal of D, and multiply that reciprocal by N to find the final quotient Q.
- Goldschmidt division
- Exponentiation:
- Multiplicative inverse Algorithms: for computing a number's multiplicative inverse (reciprocal).
- Polynomials:
- Horner's method
- Estrin's scheme — modification of the Horner scheme with more possibilities for parallelization
- Clenshaw algorithm
- De Casteljau's algorithm
- Square roots and other roots:
- Integer square root
- Methods of computing square roots
- nth root algorithm
- hypot — the function (x2 + y2)1/2
- Alpha max plus beta min algorithm — approximates hypot(x,y)
- Fast inverse square root — calculates 1 / √x using details of the IEEE floating-point system
- Elementary functions (exponential, logarithm, trigonometric functions):
- Trigonometric tables — different methods for generating them
- 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
- AGM method — computes arithmetic–geometric mean; related methods compute special functions
- FEE method (Fast E-function Evaluation) — fast summation of series like the power series for ex
- Gal's accurate tables — table of function values with unequal spacing to reduce round-off error
- Spigot algorithm — algorithms that can compute individual digits of a real number
- Approximations of π:
- Liu Hui's π algorithm — first algorithm that can compute π to arbitrary precision
- Leibniz formula for π — alternating series with very slow convergence
- Wallis product — infinite product converging slowly to π/2
- Viète's formula — more complicated infinite product which converges faster
- Gauss–Legendre algorithm — iteration which converges quadratically to π, based on arithmetic–geometric mean
- Borwein's algorithm — iteration which converges quartically to 1/π, and other algorithms
- Chudnovsky algorithm — fast algorithm that calculates a hypergeometric series
- Bailey–Borwein–Plouffe formula — can be used to compute individual hexadecimal digits of π
- Bellard's formula — faster version of Bailey–Borwein–Plouffe formula
- List of formulae involving π
Numerical linear algebra
Numerical linear algebra — study of numerical algorithms for linear algebra problems
Basic concepts
- Types of matrices appearing in numerical analysis:
- Sparse matrix
- Circulant matrix
- Triangular matrix
- Diagonally dominant matrix
- Block matrix — matrix composed of smaller matrices
- Stieltjes matrix — symmetric positive definite with non-positive off-diagonal entries
- Hilbert matrix — example of a matrix which is extremely ill-conditioned (and thus difficult to handle)
- Wilkinson matrix — example of a symmetric tridiagonal matrix with pairs of nearly, but not exactly, equal eigenvalues
- Convergent matrix — square matrix whose successive powers approach the zero matrix
- Algorithms for matrix multiplication:
- Strassen algorithm
- Coppersmith–Winograd algorithm
- Cannon's algorithm — a distributed algorithm, especially suitable for processors laid out in a 2d grid
- Freivalds' algorithm — a randomized algorithm for checking the result of a multiplication
- Matrix decompositions:
- LU decomposition — lower triangular times upper triangular
- QR decomposition — orthogonal matrix times triangular matrix
- RRQR factorization — rank-revealing QR factorization, can be used to compute rank of a matrix
- Polar decomposition — unitary matrix times positive-semidefinite Hermitian matrix
- Decompositions by similarity:
- Eigendecomposition — decomposition in terms of eigenvectors and eigenvalues
- Jordan normal form — bidiagonal matrix of a certain form; generalizes the eigendecomposition
- Weyr canonical form — permutation of Jordan normal form
- Jordan–Chevalley decomposition — sum of commuting nilpotent matrix and diagonalizable matrix
- Schur decomposition — similarity transform bringing the matrix to a triangular matrix
- Singular value decomposition — unitary matrix times diagonal matrix times unitary matrix
- Matrix splitting — expressing a given matrix as a sum or difference of matrices
Solving systems of linear equations
- Gaussian elimination
- Row echelon form — matrix in which all entries below a nonzero entry are zero
- Bareiss algorithm — variant which ensures that all entries remain integers if the initial matrix has integer entries
- Tridiagonal matrix algorithm — simplified form of Gaussian elimination for tridiagonal matrices
- LU decomposition — write a matrix as a product of an upper- and a lower-triangular matrix
- Crout matrix decomposition
- LU reduction — a special parallelized version of a LU decomposition algorithm
- Block LU decomposition
- Cholesky decomposition — for solving a system with a positive definite matrix
- Iterative refinement — procedure to turn an inaccurate solution in a more accurate one
- Direct methods for sparse matrices:
- Frontal solver — used in finite element methods
- Nested dissection — for symmetric matrices, based on graph partitioning
- Levinson recursion — for Toeplitz matrices
- SPIKE algorithm — hybrid parallel solver for narrow-banded matrices
- Cyclic reduction — eliminate even or odd rows or columns, repeat
- Iterative methods:
- Jacobi method
- Gauss–Seidel method
- Successive over-relaxation (SOR) — a technique to accelerate the Gauss–Seidel method
- Symmetric successive over-relaxation (SSOR) — variant of SOR for symmetric matrices
- Backfitting algorithm — iterative procedure used to fit a generalized additive model, often equivalent to Gauss–Seidel
- Successive over-relaxation (SOR) — a technique to accelerate the Gauss–Seidel method
- Modified Richardson iteration
- Conjugate gradient method (CG) — assumes that the matrix is positive definite
- Derivation of the conjugate gradient method
- Nonlinear conjugate gradient method — generalization for nonlinear optimization problems
- Biconjugate gradient method (BiCG)
- Biconjugate gradient stabilized method (BiCGSTAB) — variant of BiCG with better convergence
- Conjugate residual method — similar to CG but only assumed that the matrix is symmetric
- Generalized minimal residual method (GMRES) — based on the Arnoldi iteration
- Chebyshev iteration — avoids inner products but needs bounds on the spectrum
- Stone's method (SIP — Strongly Implicit Procedure) — uses an incomplete LU decomposition
- Kaczmarz method
- Preconditioner
- Incomplete Cholesky factorization — sparse approximation to the Cholesky factorization
- Incomplete LU factorization — sparse approximation to the LU factorization
- Uzawa iteration — for saddle node problems
- Underdetermined and overdetermined systems (systems that have no or more than one solution):
- Numerical computation of null space — find all solutions of an underdetermined system
- Moore–Penrose pseudoinverse — for finding solution with smallest 2-norm (for underdetermined systems) or smallest residual
- Sparse approximation — for finding the sparsest solution (i.e., the solution with as many zeros as possible)
Eigenvalue algorithms
Eigenvalue algorithm — a numerical algorithm for locating the eigenvalues of a matrix
- Power iteration
- Inverse iteration
- Rayleigh quotient iteration
- Arnoldi iteration — based on Krylov subspaces
- Lanczos algorithm — Arnoldi, specialized for positive-definite matrices
- Block Lanczos algorithm — for when matrix is over a finite field
- 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
- Jacobi method for complex Hermitian matrices
- Divide-and-conquer eigenvalue algorithm
- Folded spectrum method
- LOBPCG — Locally Optimal Block Preconditioned Conjugate Gradient Method
- Eigenvalue perturbation — stability of eigenvalues under perturbations of the matrix
Other concepts and algorithms
- Orthogonalization algorithms:
- Gram–Schmidt process
- Householder transformation
- Householder operator — analogue of Householder transformation for general inner product spaces
- Givens rotation
- Krylov subspace
- Block matrix pseudoinverse
- Bidiagonalization
- Cuthill–McKee algorithm — permutes rows/columns in sparse matrix to yield a narrow band matrix
- In-place matrix transposition — computing the transpose of a matrix without using much additional storage
- Pivot element — entry in a matrix on which the algorithm concentrates
- Matrix-free methods — methods that only access the matrix by evaluating matrix-vector products
Interpolation and approximation
Interpolation — construct a function going through some given data points
- Nearest-neighbor interpolation — takes the value of the nearest neighbor
Polynomial interpolation
Polynomial interpolation — interpolation by polynomials
- Linear interpolation
- Runge's phenomenon
- Vandermonde matrix
- Chebyshev polynomials
- Chebyshev nodes
- Lebesgue constants
- 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 — especially useful for approximation
- Brahmagupta's interpolation formula — seventh-century formula for quadratic interpolation
- Newton polynomial
- Extensions to multiple dimensions:
- Bilinear interpolation
- Trilinear interpolation
- Bicubic interpolation
- Tricubic interpolation
- Padua points — set of points in R2 with unique polynomial interpolant and minimal growth of Lebesgue constant
- Hermite interpolation
- Birkhoff interpolation
- Abel–Goncharov interpolation
Spline interpolation
Spline interpolation — interpolation by piecewise polynomials
- Spline (mathematics) — the piecewise polynomials used as interpolants
- Perfect spline — polynomial spline of degree m whose mth derivate is ±1
- Cubic Hermite spline
- Centripetal Catmull–Rom spline — special case of cubic Hermite splines without self-intersections or cusps
- Monotone cubic interpolation
- Hermite spline
- Bézier curve
- De Casteljau's algorithm
- composite Bézier curve
- Generalizations to more dimensions:
- Bézier triangle — maps a triangle to R3
- Bézier surface — maps a square to R3
- B-spline
- Box spline — multivariate generalization of B-splines
- Truncated power function
- De Boor's algorithm — generalizes De Casteljau's algorithm
- Non-uniform rational B-spline (NURBS)
- T-spline — can be thought of as a NURBS surface for which a row of control points is allowed to terminate
- Kochanek–Bartels spline
- Coons patch — type of manifold parametrization used to smoothly join other surfaces together
- M-spline — a non-negative spline
- I-spline — a monotone spline, defined in terms of M-splines
- Smoothing spline — a spline fitted smoothly to noisy data
- Blossom (functional) — a unique, affine, symmetric map associated to a polynomial or spline
- See also: List of numerical computational geometry topics
Trigonometric interpolation
Trigonometric interpolation — interpolation by trigonometric polynomials
- Discrete Fourier transform — can be viewed as trigonometric interpolation at equidistant points
- Fast Fourier transform (FFT) — a fast method for computing the discrete 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
- Bit-reversal permutation — particular permutation of vectors with 2m entries used in many FFTs.
- Butterfly diagram
- Twiddle factor — the trigonometric constant coefficients that are multiplied by the data
- Cyclotomic fast Fourier transform — for FFT over finite fields
- Methods for computing discrete convolutions with finite impulse response filters using the FFT:
- Sigma approximation
- Dirichlet kernel — convolving any function with the Dirichlet kernel yields its trigonometric interpolant
- Gibbs phenomenon
Other interpolants
- Simple rational approximation
- Polynomial and rational function modeling — comparison of polynomial and rational interpolation
- Wavelet
- Inverse distance weighting
- Radial basis function (RBF) — a function of the form ƒ(x) = φ(|x−x0|)
- Polyharmonic spline — a commonly used radial basis function
- Thin plate spline — a specific polyharmonic spline: r2 log r
- Hierarchical RBF
- Subdivision surface — constructed by recursively subdividing a piecewise linear interpolant
- Slerp (spherical linear interpolation) — interpolation between two points on a sphere
- Generalized quaternion interpolation — generalizes slerp for interpolation between more than two quaternions
- Irrational base discrete weighted transform
- Nevanlinna–Pick interpolation — interpolation by analytic functions in the unit disc subject to a bound
- Pick matrix — the Nevanlinna–Pick interpolation has a solution if this matrix is positive semi-definite
- Multivariate interpolation — the function being interpolated depends on more than one variable
- Barnes interpolation — method for two-dimensional functions using Gaussians common in meteorology
- Coons surface — combination of linear interpolation and bilinear interpolation
- Lanczos resampling — based on convolution with a sinc function
- Natural neighbor interpolation
- PDE surface
- Transfinite interpolation — constructs function on planar domain given its values on the boundary
- Trend surface analysis — based on low-order polynomials of spatial coordinates; uses scattered observations
- Method based on polynomials are listed under Polynomial interpolation
Approximation theory
- Orders of approximation
- Lebesgue's lemma
- Curve fitting
- Modulus of continuity — measures smoothness of a function
- Least squares (function approximation) — minimizes the error in the L2-norm
- Minimax approximation algorithm — minimizes the maximum error over an interval (the L∞-norm)
- Equioscillation theorem — characterizes the best approximation in the L∞-norm
- Unisolvent point set — function from given function space is determined uniquely by values on such a set of points
- Stone–Weierstrass theorem — continuous functions can be approximated uniformly by polynomials, or certain other function spaces
- Approximation by polynomials:
- Linear approximation
- Bernstein polynomial — basis of polynomials useful for approximating a function
- Bernstein's constant — error when approximating |x| by a polynomial
- Remez algorithm — for constructing the best polynomial approximation in the L∞-norm
- Bernstein's inequality (mathematical analysis) — bound on maximum of derivative of polynomial in unit disk
- Mergelyan's theorem — generalization of Stone–Weierstrass theorem for polynomials
- Müntz–Szász theorem — variant of Stone–Weierstrass theorem for polynomials if some coefficients have to be zero
- Bramble–Hilbert lemma — upper bound on Lp error of polynomial approximation in multiple dimensions
- Discrete Chebyshev polynomials — polynomials orthogonal with respect to a discrete measure
- Favard's theorem — polynomials satisfying suitable 3-term recurrence relations are orthogonal polynomials
- Approximation by Fourier series / trigonometric polynomials:
- Jackson's inequality — upper bound for best approximation by a trigonometric polynomial
- Bernstein's theorem (approximation theory) — a converse to Jackson's inequality
- Fejér's theorem — Cesàro means of partial sums of Fourier series converge uniformly for continuous periodic functions
- Erdős–Turán inequality — bounds distance between probability and Lebesgue measure in terms of Fourier coefficients
- Jackson's inequality — upper bound for best approximation by a trigonometric polynomial
- Different approximations:
- Moving least squares
- Padé approximant
- Padé table — table of Padé approximants
- Hartogs–Rosenthal theorem — continuous functions can be approximated uniformly by rational functions on a set of Lebesgue measure zero
- Szász–Mirakyan operator — approximation by e−n xk on a semi-infinite interval
- Szász–Mirakjan–Kantorovich operator
- Baskakov operator — generalize Bernstein polynomials, Szász–Mirakyan operators, and Lupas operators
- Favard operator — approximation by sums of Gaussians
- Surrogate model — application: replacing a function that is hard to evaluate by a simpler function
- Constructive function theory — field that studies connection between degree of approximation and smoothness
- Universal differential equation — differential–algebraic equation whose solutions can approximate any continuous function
- Fekete problem — find N points on a sphere that minimize some kind of energy
- Carleman's condition — condition guaranteeing that a measure is uniquely determined by its moments
- Krein's condition — condition that exponential sums are dense in weighted L2 space
- Lethargy theorem — about distance of points in a metric space from members of a sequence of subspaces
- Wirtinger's representation and projection theorem
- Journals:
Miscellaneous
- Extrapolation
- Linear predictive analysis — linear extrapolation
- Unisolvent functions — functions for which the interpolation problem has a unique solution
- Regression analysis
- Curve-fitting compaction
- Interpolation (computer graphics)
Finding roots of nonlinear equations
- See #Numerical linear algebra for linear equations
Root-finding algorithm — algorithms for solving the equation f(x) = 0
- General methods:
- Bisection method — simple and robust; linear convergence
- Lehmer–Schur algorithm — variant for complex functions
- Fixed-point iteration
- Newton's method — based on linear approximation around the current iterate; quadratic convergence
- Kantorovich theorem — gives a region around solution such that Newton's method converges
- Newton fractal — indicates which initial condition converges to which root under Newton iteration
- Quasi-Newton method — uses an approximation of the Jacobian:
- Broyden's method — uses a rank-one update for the Jacobian
- Symmetric rank-one — a symmetric (but not necessarily positive definite) rank-one update of the Jacobian
- Davidon–Fletcher–Powell formula — update of the Jacobian in which the matrix remains positive definite
- Broyden–Fletcher–Goldfarb–Shanno algorithm — rank-two update of the Jacobian in which the matrix remains positive definite
- Limited-memory BFGS method — truncated, matrix-free variant of BFGS method suitable for large problems
- Steffensen's method — uses divided differences instead of the derivative
- Secant method — based on linear interpolation at last two iterates
- False position method — secant method with ideas from the bisection method
- Muller's method — based on quadratic interpolation at last three iterates
- Sidi's generalized secant method — higher-order variants of secant method
- Inverse quadratic interpolation — similar to Muller's method, but interpolates the inverse
- Brent's method — combines bisection method, secant method and inverse quadratic interpolation
- Ridders' method — fits a linear function times an exponential to last two iterates and their midpoint
- Halley's method — uses f, f' and f''; achieves the cubic convergence
- Householder's method — uses first d derivatives to achieve order d + 1; generalizes Newton's and Halley's method
- Bisection method — simple and robust; linear convergence
- Methods for polynomials:
- Aberth method
- Bairstow's method
- Durand–Kerner method
- Graeffe's method
- Jenkins–Traub algorithm — fast, reliable, and widely used
- Laguerre's method
- Splitting circle method
- Analysis:
- Numerical continuation — tracking a root as one parameter in the equation changes
Optimization
Mathematical optimization — algorithm for finding maxima or minima of a given function
Basic concepts
- Active set
- Candidate solution
- Constraint (mathematics)
- Constrained optimization — studies optimization problems with constraints
- Binary constraint — a constraint that involves exactly two variables
- Corner solution
- Feasible region — contains all solutions that satisfy the constraints but may not be optimal
- Global optimum and Local optimum
- Maxima and minima
- Slack variable
- Continuous optimization
- Discrete optimization
Linear programming
Linear programming (also treats integer programming) — objective function and constraints are linear
- Algorithms for linear programming:
- Simplex algorithm
- Bland's rule — rule to avoid cycling in the simplex method
- Klee–Minty cube — perturbed (hyper)cube; simplex method has exponential complexity on such a domain
- Criss-cross algorithm — similar to the simplex algorithm
- Big M method — variation of simplex algorithm for problems with both "less than" and "greater than" constraints
- Interior point method
- Column generation
- k-approximation of k-hitting set — algorithm for specific LP problems (to find a weighted hitting set)
- Simplex algorithm
- Linear complementarity problem
- Decompositions:
- Basic solution (linear programming) — solution at vertex of feasible region
- Fourier–Motzkin elimination
- Hilbert basis (linear programming) — set of integer vectors in a convex cone which generate all integer vectors in the cone
- LP-type problem
- Linear inequality
- Vertex enumeration problem — list all vertices of the feasible set
Convex optimization
- Quadratic programming
- Linear least squares (mathematics)
- Total least squares
- Frank–Wolfe algorithm
- Sequential minimal optimization — breaks up large QP problems into a series of smallest possible QP problems
- Bilinear program
- Basis pursuit — minimize L1-norm of vector subject to linear constraints
- Basis pursuit denoising (BPDN) — regularized version of basis pursuit
- In-crowd algorithm — algorithm for solving basis pursuit denoising
- Basis pursuit denoising (BPDN) — regularized version of basis pursuit
- Linear matrix inequality
- Conic optimization
- Semidefinite programming
- Second-order cone programming
- Sum-of-squares optimization
- Quadratic programming (see above)
- Bregman method — row-action method for strictly convex optimization problems
- Proximal gradient method — use splitting of objective function in sum of possible non-differentiable pieces
- Subgradient method — extension of steepest descent for problems with a non-differentiable objective function
- Biconvex optimization — generalization where objective function and constraint set can be biconvex
Nonlinear programming
Nonlinear programming — the most general optimization problem in the usual framework
- Special cases of nonlinear programming:
- See Linear programming and Convex optimization above
- Geometric programming — problems involving signomials or posynomials
- Signomial — similar to polynomials, but exponents need not be integers
- Posynomial — a signomial with positive coefficients
- Quadratically constrained quadratic program
- Linear-fractional programming — objective is ratio of linear functions, constraints are linear
- Fractional programming — objective is ratio of nonlinear functions, constraints are linear
- Nonlinear complementarity problem (NCP) — find x such that x ≥ 0, f(x) ≥ 0 and xT f(x) = 0
- Least squares — the objective function is a sum of squares
- Non-linear least squares
- Gauss–Newton algorithm
- BHHH algorithm — variant of Gauss–Newton in econometrics
- Generalized Gauss–Newton method — for constrained nonlinear least-squares problems
- Levenberg–Marquardt algorithm
- Iteratively reweighted least squares (IRLS) — solves a weighted least-squares problem at every iteration
- Partial least squares — statistical techniques similar to principal components analysis
- Mathematical programming with equilibrium constraints — constraints include variational inequalities or complementarities
- Univariate optimization:
- Golden section search
- Successive parabolic interpolation — based on quadratic interpolation through the last three iterates
- General algorithms:
- Concepts:
- Descent direction
- Guess value — the initial guess for a solution with which an algorithm starts
- Line search
- Gradient method — method that uses the gradient as the search direction
- Gradient descent
- Landweber iteration — mainly used for ill-posed problems
- Successive linear programming (SLP) — replace problem by a linear programming problem, solve that, and repeat
- Sequential quadratic programming (SQP) — replace problem by a quadratic programming problem, solve that, and repeat
- Newton's method in optimization
- See also under Newton algorithm in the section Finding roots of nonlinear equations
- Nonlinear conjugate gradient method
- Derivative-free methods
- Coordinate descent — move in one of the coordinate directions
- Adaptive coordinate descent — adapt coordinate directions to objective function
- Random coordinate descent — randomized version
- Nelder–Mead method
- Pattern search (optimization)
- Powell's method — based on conjugate gradient descent
- Rosenbrock methods — derivative-free method, similar to Nelder–Mead but with guaranteed convergence
- Coordinate descent — move in one of the coordinate directions
- Augmented Lagrangian method — replaces constrained problems by unconstrained problems with a term added to the objective function
- Ternary search
- Tabu search
- Guided Local Search — modification of search algorithms which builds up penalties during a search
- Reactive search optimization (RSO) — the algorithm adapts its parameters automatically
- MM algorithm — majorize-minimization, a wide framework of methods
- Least absolute deviations
- Nearest neighbor search
- Space mapping — uses "coarse" (ideal or low-fidelity) and "fine" (practical or high-fidelity) models
- Concepts:
Optimal control and infinite-dimensional optimization
- Pontryagin's minimum principle — infinite-dimensional version of Lagrange multipliers
- Costate equations — equation for the "Lagrange multipliers" in Pontryagin's minimum principle
- Hamiltonian (control theory) — minimum principle says that this function should be minimized
- Types of problems:
- Linear-quadratic regulator — system dynamics is a linear differential equation, objective is quadratic
- Linear-quadratic-Gaussian control (LQG) — system dynamics is a linear SDE with additive noise, objective is quadratic
- Optimal projection equations — method for reducing dimension of LQG control problem
- Algebraic Riccati equation — matrix equation occurring in many optimal control problems
- Bang–bang control — control that switches abruptly between two states
- Covector mapping principle
- Differential dynamic programming — uses locally-quadratic models of the dynamics and cost functions
- DNSS point — initial state for certain optimal control problems with multiple optimal solutions
- Legendre–Clebsch condition — second-order condition for solution of optimal control problem
- Pseudospectral optimal control
- Bellman pseudospectral method — based on Bellman's principle of optimality
- Chebyshev pseudospectral method — uses Chebyshev polynomials (of the first kind)
- Flat pseudospectral method — combines Ross–Fahroo pseudospectral method with differential flatness
- Gauss pseudospectral method — uses collocation at the Legendre–Gauss points
- Legendre pseudospectral method — uses Legendre polynomials
- Pseudospectral knotting method — generalization of pseudospectral methods in optimal control
- Ross–Fahroo pseudospectral method — class of pseudospectral method including Chebyshev, Legendre and knotting
- Ross–Fahroo lemma — condition to make discretization and duality operations commute
- Ross' π lemma — there is fundamental time constant within which a control solution must be computed for controllability and stability
- Sethi model — optimal control problem modelling advertising
Infinite-dimensional optimization
- Semi-infinite programming — infinite number of variables and finite number of constraints, or other way around
- Shape optimization, Topology optimization — optimization over a set of regions
- Topological derivative — derivative with respect to changing in the shape
- Generalized semi-infinite programming — finite number of variables, infinite number of constraints
Uncertainty and randomness
- Approaches to deal with uncertainty:
- Random optimization algorithms:
- Random search — choose a point randomly in ball around current iterate
- Simulated annealing
- Adaptive simulated annealing — variant in which the algorithm parameters are adjusted during the computation.
- Great Deluge algorithm
- Mean field annealing — deterministic variant of simulated annealing
- Bayesian optimization — treats objective function as a random function and places a prior over it
- Evolutionary algorithm
- Differential evolution
- Evolutionary programming
- Genetic algorithm, Genetic programming
- MCACEA (Multiple Coordinated Agents Coevolution Evolutionary Algorithm) — uses an evolutionary algorithm for every agent
- Simultaneous perturbation stochastic approximation (SPSA)
- Luus–Jaakola
- Particle swarm optimization
- Stochastic tunneling
- Harmony search — mimicks the improvisation process of musicians
- see also the section Monte Carlo method
Theoretical aspects
- Convex analysis — function f such that f(tx + (1 − t)y) ≥ tf(x) + (1 − t)f(y) for t ∈ [0,1]
- Pseudoconvex function — function f such that ∇f · (y − x) ≥ 0 implies f(y) ≥ f(x)
- Quasiconvex function — function f such that f(tx + (1 − t)y) ≤ max(f(x), f(y)) for t ∈ [0,1]
- Subderivative
- Geodesic convexity — convexity for functions defined on a Riemannian manifold
- Duality (optimization)
- Weak duality — dual solution gives a bound on the primal solution
- Strong duality — primal and dual solutions are equivalent
- Shadow price
- Dual cone and polar cone
- Duality gap — difference between primal and dual solution
- Fenchel's duality theorem — relates minimization problems with maximization problems of convex conjugates
- Perturbation function — any function which relates to primal and dual problems
- Slater's condition — sufficient condition for strong duality to hold in a convex optimization problem
- Total dual integrality — concept of duality for integer linear programming
- Wolfe duality — for when objective function and constraints are differentiable
- Farkas' lemma
- Karush–Kuhn–Tucker conditions (KKT) — sufficient conditions for a solution to be optimal
- Fritz John conditions — variant of KKT conditions
- Lagrange multiplier
- Semi-continuity
- Complementarity theory — study of problems with constraints of the form ⟨u, v⟩ = 0
- Mixed complementarity problem
- Mixed linear complementarity problem
- Lemke's algorithm — method for solving (mixed) linear complementarity problems
- Mixed complementarity problem
- Danskin's theorem — used in the analysis of minimax problems
- Maximum theorem — the maximum and maximizer are continuous as function of parameters, under some conditions
- No free lunch in search and optimization
- Relaxation (approximation) — approximating a given problem by an easier problem by relaxing some constraints
- Lagrangian relaxation
- Linear programming relaxation — ignoring the integrality constraints in a linear programming problem
- Self-concordant function
- Reduced cost — cost for increasing a variable by a small amount
- Hardness of approximation — computational complexity of getting an approximate solution
Applications
- In geometry:
- Geometric median — the point minimizing the sum of distances to a given set of points
- Chebyshev center — the centre of the smallest ball containing a given set of points
- In statistics:
- Iterated conditional modes — maximizing joint probability of Markov random field
- Response surface methodology — used in the design of experiments
- Automatic label placement
- Compressed sensing — reconstruct a signal from knowledge that it is sparse or compressible
- Cutting stock problem
- Demand optimization
- Destination dispatch — an optimization technique for dispatching elevators
- Energy minimization
- Entropy maximization
- Highly optimized tolerance
- Hyperparameter optimization
- Inventory control problem
- Linear programming decoding
- Linear search problem — find a point on a line by moving along the line
- Low-rank approximation — find best approximation, constraint is that rank of some matrix is smaller than a given number
- Meta-optimization — optimization of the parameters in an optimization method
- Multidisciplinary design optimization
- Optimal computing budget allocation — maximize the overall simulation efficiency for finding an optimal decision
- Paper bag problem
- Process optimization
- Recursive economics — individuals make a series of two-period optimization decisions over time.
- Stigler diet
- Space allocation problem
- Stress majorization
- Trajectory optimization
- Transportation theory
- Wing-shape optimization
Miscellaneous
- Combinatorial optimization
- Dynamic programming
- Bellman equation
- Hamilton–Jacobi–Bellman equation — continuous-time analogue of Bellman equation
- Backward induction — solving dynamic programming problems by reasoning backwards in time
- Optimal stopping — choosing the optimal time to take a particular action
- Global optimization:
- Multi-objective optimization — there are multiple conflicting objectives
- Benson's algorithm — for linear vector optimization problems
- Bilevel optimization — studies problems in which one problem is embedded in another
- Optimal substructure
- Dykstra's projection algorithm — finds a point in intersection of two convex sets
- Algorithmic concepts:
- Test functions for optimization:
- Rosenbrock function — two-dimensional function with a banana-shaped valley
- Himmelblau's function — two-dimensional with four local minima, defined by
- Rastrigin function — two-dimensional function with many local minima
- Shekel function — multimodal and multidimensional
- Mathematical Optimization Society
Numerical quadrature (integration)
Numerical integration — the numerical evaluation of an integral
- Rectangle method — first-order method, based on (piecewise) constant approximation
- Trapezoidal rule — second-order method, based on (piecewise) linear approximation
- Simpson's rule — fourth-order method, based on (piecewise) quadratic approximation
- Boole's rule — sixth-order method, based on the values at five equidistant points
- Newton–Cotes formulas — generalizes the above methods
- Romberg's method — Richardson extrapolation applied to trapezium rule
- Gaussian quadrature — highest possible degree with given number of points
- Chebyshev–Gauss quadrature — extension of Gaussian quadrature for integrals with weight (1 − x2)±1/2 on [−1, 1]
- Gauss–Hermite quadrature — extension of Gaussian quadrature for integrals with weight exp(−x2) on [−∞, ∞]
- Gauss–Jacobi quadrature — extension of Gaussian quadrature for integrals with weight (1 − x)α (1 + x)β on [−1, 1]
- Gauss–Laguerre quadrature — extension of Gaussian quadrature for integrals with weight exp(−x) on [0, ∞]
- Gauss–Kronrod quadrature formula — nested rule based on Gaussian quadrature
- Gauss–Kronrod rules
- Tanh-sinh quadrature — variant of Gaussian quadrature which works well with singularities at the end points
- Clenshaw–Curtis quadrature — based on expanding the integrand in terms of Chebyshev polynomials
- Adaptive quadrature — adapting the subintervals in which the integration interval is divided depending on the integrand
- Monte Carlo integration — takes random samples of the integrand
- See also #Monte Carlo method
- Quantized state systems method (QSS) — based on the idea of state quantization
- Lebedev quadrature — uses a grid on a sphere with octahedral symmetry
- Sparse grid
- Coopmans approximation
- Numerical differentiation — for fractional-order integrals
- Numerical smoothing and differentiation
- Adjoint state method — approximates gradient of a function in an optimization problem
- Euler–Maclaurin formula
Numerical methods for ordinary differential equations
Numerical methods for ordinary differential equations — the numerical solution of ordinary differential equations (ODEs)
- Euler method — the most basic method for solving an ODE
- Explicit and implicit methods — implicit methods need to solve an equation at every step
- Backward Euler method — implicit variant of the Euler method
- Trapezoidal rule — second-order implicit method
- Runge–Kutta methods — one of the two main classes of methods for initial-value problems
- Midpoint method — a second-order method with two stages
- Heun's method — either a second-order method with two stages, or a third-order method with three stages
- Bogacki–Shampine method — a third-order method with four stages (FSAL) and an embedded fourth-order method
- Cash–Karp method — a fifth-order method with six stages and an embedded fourth-order method
- Dormand–Prince method — a fifth-order method with seven stages (FSAL) and an embedded fourth-order method
- Runge–Kutta–Fehlberg method — a fifth-order method with six stages and an embedded fourth-order method
- Gauss–Legendre method — family of A-stable method with optimal order based on Gaussian quadrature
- Butcher group — algebraic formalism involving rooted trees for analysing Runge–Kutta methods
- List of Runge–Kutta methods
- Linear multistep method — the other main class of methods for initial-value problems
- Backward differentiation formula — implicit methods of order 2 to 6; especially suitable for stiff equations
- Numerov's method — fourth-order method for equations of the form
- Predictor–corrector method — uses one method to approximate solution and another one to increase accuracy
- General linear methods — a class of methods encapsulating linear multistep and Runge-Kutta methods
- Bulirsch–Stoer algorithm — combines the midpoint method with Richardson extrapolation to attain arbitrary order
- Exponential integrator — based on splitting ODE in a linear part, which is solved exactly, and a nonlinear part
- 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
- Leapfrog integration — another name for Verlet integration
- Beeman's algorithm — a two-step method extending the Verlet method
- Dynamic relaxation
- 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
- Variational integrator — symplectic integrators derived using the underlying variational principle
- Semi-implicit Euler method — variant of Euler method which is symplectic when applied to separable Hamiltonians
- Energy drift — phenomenon that energy, which should be conserved, drifts away due to numerical errors
- Symplectic integrator — a method for the solution of Hamilton's equations that preserves the symplectic structure
- Other methods for initial value problems (IVPs):
- Methods for solving two-point boundary value problems (BVPs):
- Shooting method
- Direct multiple shooting method — divides interval in several subintervals and applies the shooting method on each subinterval
- Methods for solving differential-algebraic equations (DAEs), i.e., ODEs with constraints:
- Constraint algorithm — for solving Newton's equations with constraints
- Pantelides algorithm — for reducing the index of a DEA
- 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
- Methods for solving integral equations:
- Nyström method — replaces the integral with a quadrature rule
- Analysis:
- Truncation error (numerical integration) — local and global truncation errors, and their relationships
- Lady Windermere's Fan (mathematics) — telescopic identity relating local and global truncation errors
- Truncation error (numerical integration) — local and global truncation errors, and their relationships
- Stiff equation — roughly, an ODE for which unstable methods need a very short step size, but stable methods do not
- L-stability — method is A-stable and stability function vanishes at infinity
- Adaptive stepsize — automatically changing the step size when that seems advantageous
- Parareal -- a parallel-in-time integration algorithm
Numerical methods for partial differential equations
Numerical partial differential equations — the numerical solution of partial differential equations (PDEs)
Finite difference methods
Finite difference method — based on approximating differential operators with difference operators
- Finite difference — the discrete analogue of a differential operator
- Finite difference coefficient — table of coefficients of finite-difference approximations to derivatives
- Discrete Laplace operator — finite-difference approximation of the Laplace operator
- Eigenvalues and eigenvectors of the second derivative — includes eigenvalues of discrete Laplace operator
- Kronecker sum of discrete Laplacians — used for Laplace operator in multiple dimensions
- Discrete Poisson equation — discrete analogue of the Poisson equation using the discrete Laplace operator
- Stencil (numerical analysis) — the geometric arrangements of grid points affected by a basic step of the algorithm
- Compact stencil — stencil which only uses a few grid points, usually only the immediate and diagonal neighbours
- Non-compact stencil — any stencil that is not compact
- Five-point stencil — two-dimensional stencil consisting of a point and its four immediate neighbours on a rectangular grid
- Finite difference methods for heat equation and related PDEs:
- FTCS scheme (forward-time central-space) — first-order explicit
- Crank–Nicolson method — second-order implicit
- Finite difference methods for hyperbolic PDEs like the wave equation:
- Lax–Friedrichs method — first-order explicit
- Lax–Wendroff method — second-order explicit
- MacCormack method — second-order explicit
- Upwind scheme
- Upwind differencing scheme for convection — first-order scheme for convection–diffusion problems
- Lax–Wendroff theorem — conservative scheme for hyperbolic system of conservation laws converges to the weak solution
- Alternating direction implicit method (ADI) — update using the flow in x-direction and then using flow in y-direction
- Nonstandard finite difference scheme
- Specific applications:
- Finite difference methods for option pricing
- Finite-difference time-domain method — a finite-difference method for electrodynamics
Finite element methods, gradient discretisation methods
Finite element method — based on a discretization of the space of solutions gradient discretisation method — based on both the discretization of the solution and of its gradient
- 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
- Discontinuous Galerkin method — a Galerkin method in which the approximate solution is not continuous
- Rayleigh–Ritz method — a finite element method based on variational principles
- Spectral element method — high-order finite element methods
- hp-FEM — variant in which both the size and the order of the elements are automatically adapted
- Examples of finite elements:
- Bilinear quadrilateral element — also known as the Q4 element
- Constant strain triangle element (CST) — also known as the T3 element
- Quadratic quadrilateral element — also known as the Q8 element
- Barsoum elements
- Direct stiffness method — a particular implementation of the finite element method, often used in structural analysis
- Trefftz method
- Finite element updating
- Extended finite element method — puts functions tailored to the problem in the approximation space
- Functionally graded elements — elements for describing functionally graded materials
- Superelement — particular grouping of finite elements, employed as a single element
- Interval finite element method — combination of finite elements with interval arithmetic
- Discrete exterior calculus — discrete form of the exterior calculus of differential geometry
- Modal analysis using FEM — solution of eigenvalue problems to find natural vibrations
- Céa's lemma — solution in the finite-element space is an almost best approximation in that space of the true solution
- Patch test (finite elements) — simple test for the quality of a finite element
- MAFELAP (MAthematics of Finite ELements and APplications) — international conference held at Brunel University
- NAFEMS — not-for-profit organisation that sets and maintains standards in computer-aided engineering analysis
- Multiphase topology optimisation — technique based on finite elements for determining optimal composition of a mixture
- Interval finite element
- Applied element method — for simulation of cracks and structural collapse
- Wood–Armer method — structural analysis method based on finite elements used to design reinforcement for concrete slabs
- Isogeometric analysis — integrates finite elements into conventional NURBS-based CAD design tools
- Loubignac iteration
- Stiffness matrix — finite-dimensional analogue of differential operator
- Combination with meshfree methods:
- Weakened weak form — form of a PDE that is weaker than the standard weak form
- G space — functional space used in formulating the weakened weak form
- Smoothed finite element method
- Variational multiscale method
- List of finite element software packages
Other methods
- Spectral method — based on the Fourier transformation
- Method of lines — reduces the PDE to a large system of ordinary differential equations
- Boundary element method (BEM) — based on transforming the PDE to an integral equation on the boundary of the domain
- Interval boundary element method — a version using interval arithmetics
- 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
- Flux limiter — limits spatial derivatives (fluxes) in order to avoid spurious oscillations
- Riemann solver — a solver for Riemann problems (a conservation law with piecewise constant data)
- Properties of discretization schemes — finite volume methods can be conservative, bounded, etc.
- Discrete element method — a method in which the elements can move freely relative to each other
- Extended discrete element method — adds properties such as strain to each particle
- Movable cellular automaton — combination of cellular automata with discrete elements
- Meshfree methods — does not use a mesh, but uses a particle view of the field
- Discrete least squares meshless method — based on minimization of weighted summation of the squared residual
- Diffuse element method
- Finite pointset method — represent continuum by a point cloud
- Moving Particle Semi-implicit Method
- Method of fundamental solutions (MFS) — represents solution as linear combination of fundamental solutions
- Variants of MFS with source points on the physical boundary:
- Boundary knot method (BKM)
- Boundary particle method (BPM)
- Regularized meshless method (RMM)
- Singular boundary method (SBM)
- Methods designed for problems from electromagnetics:
- Finite-difference time-domain method — a finite-difference method
- Rigorous coupled-wave analysis — semi-analytical Fourier-space method based on Floquet's theorem
- Transmission-line matrix method (TLM) — based on analogy between electromagnetic field and mesh of transmission lines
- Uniform theory of diffraction — specifically designed for scattering problems
- Particle-in-cell — used especially in fluid dynamics
- Multiphase particle-in-cell method — considers solid particles as both numerical particles and fluid
- High-resolution scheme
- Shock capturing method
- Vorticity confinement — for vortex-dominated flows in fluid dynamics, similar to shock capturing
- Split-step method
- Fast marching method
- Orthogonal collocation
- Lattice Boltzmann methods — for the solution of the Navier-Stokes equations
- Roe solver — for the solution of the Euler equation
- Relaxation (iterative method) — a method for solving elliptic PDEs by converting them to evolution equations
- 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
- Immersed boundary method — for simulating elastic structures immersed within fluids
- Multisymplectic integrator — extension of symplectic integrators, which are for ODEs
- Stretched grid method — for problems solution that can be related to an elastic grid behavior.
Techniques for improving these methods
- Multigrid method — uses a hierarchy of nested meshes to speed up the methods
- Domain decomposition methods — divides the domain in a few subdomains and solves the PDE on these subdomains
- Additive Schwarz method
- Abstract additive Schwarz method — abstract version of additive Schwarz without reference to geometric information
- Balancing domain decomposition method (BDD) — preconditioner for symmetric positive definite matrices
- Balancing domain decomposition by constraints (BDDC) — further development of BDD
- Finite element tearing and interconnect (FETI)
- FETI-DP — further development of FETI
- Fictitious domain method — preconditioner constructed with a structured mesh on a fictitious domain of simple shape
- Mortar methods — meshes on subdomain do not mesh
- Neumann–Dirichlet method — combines Neumann problem on one subdomain with Dirichlet problem on other subdomain
- Neumann–Neumann methods — domain decomposition methods that use Neumann problems on the subdomains
- Poincaré–Steklov operator — maps tangential electric field onto the equivalent electric current
- Schur complement method — early and basic method on subdomains that do not overlap
- Schwarz alternating method — early and basic method on subdomains that overlap
- Coarse space — variant of the problem which uses a discretization with fewer degrees of freedom
- Adaptive mesh refinement — uses the computed solution to refine the mesh only where necessary
- Fast multipole method — hierarchical method for evaluating particle-particle interactions
- Perfectly matched layer — artificial absorbing layer for wave equations, used to implement absorbing boundary conditions
Grids and meshes
- Grid classification / Types of mesh:
- Polygon mesh — consists of polygons in 2D or 3D
- Triangle mesh — consists of triangles in 2D or 3D
- Triangulation (geometry) — subdivision of given region in triangles, or higher-dimensional analogue
- Nonobtuse mesh — mesh in which all angles are less than or equal to 90°
- Point-set triangulation — triangle mesh such that given set of point are all a vertex of a triangle
- Polygon triangulation — triangle mesh inside a polygon
- Delaunay triangulation — triangulation such that no vertex is inside the circumcentre of a triangle
- Constrained Delaunay triangulation — generalization of the Delaunay triangulation that forces certain required segments into the triangulation
- Pitteway triangulation — for any point, triangle containing it has nearest neighbour of the point as a vertex
- Minimum-weight triangulation — triangulation of minimum total edge length
- Kinetic triangulation — a triangulation that moves over time
- Triangulated irregular network
- Quasi-triangulation — subdivision into simplices, where vertices are not points but arbitrary sloped line segments
- Volume mesh — consists of three-dimensional shapes
- Regular grid — consists of congruent parallelograms, or higher-dimensional analogue
- Unstructured grid
- Geodesic grid — isotropic grid on a sphere
- Mesh generation
- Image-based meshing — automatic procedure of generating meshes from 3D image data
- Marching cubes — extracts a polygon mesh from a scalar field
- Parallel mesh generation
- Ruppert's algorithm — creates quality Delauney triangularization from piecewise linear data
- Subdivisions:
- Apollonian network — undirected graph formed by recursively subdividing a triangle
- Barycentric subdivision — standard way of dividing arbitrary convex polygons into triangles, or the higher-dimensional analogue
- Improving an existing mesh:
- Chew's second algorithm — improves Delauney triangularization by refining poor-quality triangles
- Laplacian smoothing — improves polynomial meshes by moving the vertices
- Jump-and-Walk algorithm — for finding triangle in a mesh containing a given point
- Spatial twist continuum — dual representation of a mesh consisting of hexahedra
- Pseudotriangle — simply connected region between any three mutually tangent convex sets
- Simplicial complex — all vertices, line segments, triangles, tetrahedra, ..., making up a mesh
Analysis
- Lax equivalence theorem — a consistent method is convergent if and only if it is stable
- Courant–Friedrichs–Lewy condition — stability condition for hyperbolic PDEs
- Von Neumann stability analysis — all Fourier components of the error should be stable
- Numerical diffusion — diffusion introduced by the numerical method, above to that which is naturally present
- Numerical dispersion
- 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
- Motz's problem — benchmark problem for singularity problems
- Variants of the Monte Carlo method:
- Direct simulation Monte Carlo
- Quasi-Monte Carlo method
- Markov chain Monte Carlo
- Metropolis–Hastings algorithm
- Multiple-try Metropolis — modification which allows larger step sizes
- Wang and Landau algorithm — extension of Metropolis Monte Carlo
- Equation of State Calculations by Fast Computing Machines — 1953 article proposing the Metropolis Monte Carlo algorithm
- Multicanonical ensemble — sampling technique that uses Metropolis–Hastings to compute integrals
- Gibbs sampling
- Coupling from the past
- Reversible-jump Markov chain Monte Carlo
- Metropolis–Hastings algorithm
- Dynamic Monte Carlo method
- Particle filter
- Reverse Monte Carlo
- Demon algorithm
- Pseudo-random number sampling
- Inverse transform sampling — general and straightforward method but computationally expensive
- Rejection sampling — sample from a simpler distribution but reject some of the samples
- Ziggurat algorithm — uses a pre-computed table covering the probability distribution with rectangular segments
- For sampling from a normal distribution:
- Convolution random number generator — generates a random variable as a sum of other random variables
- Indexed search
- Variance reduction techniques:
- Low-discrepancy sequence
- Event generator
- Parallel tempering
- Umbrella sampling — improves sampling in physical systems with significant energy barriers
- Hybrid Monte Carlo
- Ensemble Kalman filter — recursive filter suitable for problems with a large number of variables
- Transition path sampling
- Walk-on-spheres method — to generate exit-points of Brownian motion from bounded domains
- Applications:
- Ensemble forecasting — produce multiple numerical predictions from slightly initial conditions or parameters
- Bond fluctuation model — for simulating the conformation and dynamics of polymer systems
- Iterated filtering
- Metropolis light transport
- Monte Carlo localization — estimates the position and orientation of a robot
- Monte Carlo methods for electron transport
- Monte Carlo method for photon transport
- Monte Carlo methods in finance
- Monte Carlo molecular modeling
- Path integral molecular dynamics — incorporates Feynman path integrals
- Quantum Monte Carlo
- Diffusion Monte Carlo — uses a Green function to solve the Schrödinger equation
- Gaussian quantum Monte Carlo
- Path integral Monte Carlo
- Reptation Monte Carlo
- Variational Monte Carlo
- Methods for simulating the Ising model:
- Swendsen–Wang algorithm — entire sample is divided into equal-spin clusters
- Wolff algorithm — improvement of the Swendsen–Wang algorithm
- Metropolis–Hastings algorithm
- 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
Applications
- Computational physics
- Computational electromagnetics
- Computational fluid dynamics (CFD)
- Numerical methods in fluid mechanics
- Large eddy simulation
- Smoothed-particle hydrodynamics
- Aeroacoustic analogy — used in numerical aeroacoustics to reduce sound sources to simple emitter types
- Stochastic Eulerian Lagrangian method — uses Eulerian description for fluids and Lagrangian for structures
- Explicit algebraic stress model
- Computational magnetohydrodynamics (CMHD) — studies electrically conducting fluids
- Climate model
- Numerical weather prediction
- Celestial mechanics
- Quantum jump method — used for simulating open quantum systems, operates on wave function
- Dynamic design analysis method (DDAM) — for evaluating effect of underwater explosions on equipment
- Computational chemistry
- Cell lists
- Coupled cluster
- Density functional theory
- DIIS — direct inversion in (or of) the iterative subspace
- Computational sociology
- Computational statistics
Software
For a large list of software, see the list of numerical-analysis software.
Journals
- Acta Numerica
- Mathematics of Computation (published by the American Mathematical Society)
- Journal of Computational and Applied Mathematics
- BIT Numerical Mathematics
- Numerische Mathematik
- Journals from the Society for Industrial and Applied Mathematics
Researchers
- Cleve Moler
- Gene H. Golub
- James H. Wilkinson
- Margaret H. Wright
- Nicholas J. Higham
- Nick Trefethen
- Peter Lax
- Richard S. Varga
- Ulrich W. Kulisch
- Vladik Kreinovich
- Chi-Wang Shu
References
- ^ Smith, N. J. J. (2008). "Worldly Vagueness and Semantic Indeterminacy". Vagueness and Degrees of Truth. pp. 277–316. doi:10.1093/acprof:oso/9780199233007.003.0007. ISBN 9780199233007.