List of numerical analysis topics
444250
222652405
2008-06-30T13:12:12Z
Epbr123
1395162
Reverted edits by [[Special:Contributions/194.80.187.10|194.80.187.10]] to last version by Chamal N (using [[WP:HG|Huggle]])
This is a '''list of [[numerical analysis]] topics''', by Wikipedia page.
==General==
*[[Iterative method]]
*[[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]]
**[[Van Wijngaarden transformation]] — for accelerating the convergence of an alternating series
*[[Level set method]]
**[[Level set (data structures)]] — data structures for representing level sets
*[[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]]
**[[Collocation method]] — discretizes a continuous equation by requiring it only to hold at certain points
*[[Difference quotient]]
*[[Computational complexity of mathematical operations]]
*[[International Workshops on Lattice QCD and Numerical Analysis]]
*[[ABS methods]]
==Error==
[[Error analysis]]
*[[Approximation]]
*[[Approximation error]]
*[[Arithmetic precision]]
*[[Condition number]]
*[[Discretization error]]
*[[Floating point]] number
**[[Guard digit]] — extra precision introduced during a computation to reduce round-off error
**[[Arbitrary-precision arithmetic]]
**[[Truncation]] — rounding a floating-point number by discarding all digits after a certain digit
*[[Interval arithmetic]] — represent every number by two floating-point numbers guaranteed to have the unknown number between them
*[[Loss of significance]]
*[[Numerical error]]
*[[Numerical stability]]
*Error propagation:
**[[Propagation of uncertainty]]
**[[Significance arithmetic]]
** [[Residual (numerical analysis)]]
*[[Relative difference]] — the relative difference between ''x'' and ''y'' is |''x'' − ''y''| / max(|''x''|, |''y''|)
*[[Round-off error]]
**[[Stochastic rounding]]
*[[Significant figures]]
**[[False precision]] — giving more significant figures than appropriate
*[[Truncation error]] — error committed by doing only a finite numbers of steps
*[[Well-posed problem]]
*[[Affine arithmetic]]
==Elementary and special functions==
*Summation:
**[[Kahan summation algorithm]]
**[[Binary splitting]]
*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
*Exponentiation:
**[[Exponentiation by squaring]]
**[[Addition-chain exponentiation]]
*Polynomials:
**[[Horner scheme]]
**[[Estrin's scheme]] — modification of the Horner scheme with more possibilities for parallellization
**[[Clenshaw algorithm]]
**[[De Casteljau's algorithm]]
*Square roots and other roots:
**[[Integer square root]]
**[[Methods of computing square roots]]
**[[Nth root algorithm|''n''th root algorithm]]
**[[Alpha max plus beta min algorithm]] — approximates <math>\sqrt{x^2+y^2}</math>
*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
*[[Spigot algorithm]] — algorithms that can compute individual digits of a real number
*[[Computing π|Computation of π]]:
**[[Liu Hui's π algorithm]] — first algorithm that can compute π to arbitrary precision
**[[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/π, and other algorithms
**[[Chudnovsky algorithm]] — fast algorithm that calculates a hypergeometric series
==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]]
***[[Band matrix]]
***[[Tridiagonal matrix]]
***[[Pentadiagonal matrix]]
***[[Skyline matrix]]
**[[Circulant matrix]]
**[[Triangular matrix]]
**[[Diagonally dominant matrix]]
**[[Hilbert matrix]] — example of a matrix which is extremely ill-conditioned (and thus difficult to handle)
*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
**[[Freivald's algorithm]] — a randomized algorithm for checking the result of a multiplication
=== Solving systems of linear equations ===
*[[Gaussian elimination]]
**[[Row echelon form]] — matrix in which all entries below a nonzero entry are zero
**[[Gauss–Jordan elimination]] — variant in which the entries below the pivot are also zeroed
**[[Montante's method]] — 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
***[[Tridiagonal matrix algorithm/Derivation]]
*[[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
**[[Minimum degree algorithm]]
**[[Symbolic Cholesky decomposition]]
*[[Frontal solver]] — for sparse matrices; used in finite element methods
*[[Levinson recursion]] — for Toeplitz matrices
*Iterative methods:
**[[Jacobi method]]
**[[Gauss–Seidel method]]
***[[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
***[[Preconditioned conjugate gradient method]] (PCG)
***[[Nonlinear conjugate gradient method]] — generalization for nonlinear optimization problems
**[[Biconjugate gradient method]] (BiCG)
**[[Generalized minimal residual method]] (GMRES) — based on the Arnoldi iteration
**[[Stone method|Stone's method]] (SIP - Srongly Implicit Procedure) — uses an incomplete LU decomposition
**[[Kaczmarz method]]
**[[Preconditioner]]
*Underdetermined and overdetermined systems (systems that have no or more than one solution):
**[[Kernel (matrix)#Numerical computation of null space|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
*[[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]]
*[[Folded spectrum method]]
=== Other concepts and algorithms ===
*[[Orthogonalization]] algorithms:
**[[Gram–Schmidt process]]
**[[Householder transformation]]
**[[Givens rotation]]
*[[QR decomposition]]
*[[Krylov subspace]]
*[[Block matrix pseudoinverse]]
*[[Bidiagonalization]]
*[[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
==[[Interpolation]]==
*[[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 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]] — especially useful for approximation
*Extensions to multiple dimensions:
**[[Bilinear interpolation]]
**[[Trilinear interpolation]]
**[[Bicubic interpolation]]
**[[Tricubic interpolation]]
**[[Padua points]] — set of points in '''R'''<sup>2</sup> with unique polynomial interpolant and minimal growth of Lebesgue constant
*[[Hermite interpolation]]
*[[Birkhoff 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 ''m''th derivate is ±1
*[[Cubic Hermite spline]]
*[[Monotone cubic interpolation]]
*[[Hermite spline]]
*[[Cardinal spline]]
*[[Bézier spline]]
**[[Bézier curve]]
**[[De Casteljau's algorithm]]
**Generalizations to more dimensions:
***[[Bézier triangle]] — maps a triangle to '''R'''<sup>3</sup>
***[[Bézier surface]] — maps a square to '''R'''<sup>3</sup>
*[[B-spline]]
**[[Truncated power function]]
**[[De Boor's algorithm]] — generalizes De Casteljau's algorithm
*[[Nonuniform rational B-spline]] (NURBS)
*[[Kochanek–Bartels spline]]
*[[Catmull–Rom spline]]
*[[Blossom (mathematics)]] — 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
**[[Relations between Fourier transforms and Fourier series]]
*[[Fast Fourier transform]] — 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]]
**[[Butterfly diagram]]
**[[Twiddle factor]] — the trigonometric constant coefficients that are multiplied by the data
**[[Fast cosine transform]] — fast methods for computing the discrete cosine transform
**Methods for computing discrete convolutions with finite impulse response filters using the FFT:
***[[Overlap-add method]]
***[[Overlap-save method]]
*[[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]]
**[[Continuous wavelet]]
***[[Continuous wavelet transform]]
**[[Transfer matrix]]
*[[Inverse distance weighting]]
**[[Cascade algorithm]] — iterative algorithm to compute wavelets
*[[Radial basis function]]
**[[Polyharmonic spline]] — a commonly used radial basis function
**[[Thin plate spline]] — a specific polyharmonic spline: ''r''<sup>2</sup> log ''r''
**[[Radial basis function network]] — neural network using radial basis functions as activation functions
*[[Subdivision surface]] — constructed by recursively subdividing a piecewise linear interpolant
**[[Catmull–Clark subdivision surface]]
**[[Doo–Sabin subdivision surface]]
**[[Loop subdivision surface]]
*[[Slerp]]
*[[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
*[[Pareto interpolation]]
*[[Multivariate interpolation]] — the function being interpolated depends on more than one variable
**[[Lanczos resampling]] — based on convolution with a sinc function
**[[Natural neighbor]] interpolation
**[[PDE surface]]
**Method based on polynomials are listed under ''Polynomial interpolation''
=== Approximation theory ===
[[Approximation theory]]
*[[Orders of approximation]]
*[[Lebesgue's lemma]]
*[[Curve fitting]]
*[[Modulus of continuity]] — measures smoothness of a function
*[[Minimax approximation algorithm]] — minimizes the maximum error over an interval (the L<sup>∞</sup>-norm)
*Approximation by polynomials:
**[[Linear approximation]]
**[[Bernstein polynomial]] — basis of polynomials useful for approximating a function
**[[Remez algorithm]] — for constructing the best polynomial approximation in the L<sup>∞</sup>-norm
**[[Bramble-Hilbert lemma]] — upper bound on L<sup>p</sup> error of polynomial approximation in multiple dimensions
**[[Bernstein's constant]] — error when approximating |''x''| by a polynomial
*[[Surrogate model]] — application: replacing a function that is hard to evaluate by a simpler function
*[[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
**[[Szász-Mirakyan operator]] — approximation by e<sup>−''n''</sup> ''x''<sup>''k''</sup> on a semi-infinite interval
**[[Szász-Mirakyan-Kantorovich operator]]
**[[Baskakov operator]] — generalize Bernstein polynomials, Szász-Mirakyan operators, and Lupas operators
**[[Favard operator]] — approximation by sums of Gaussians
=== Miscellaneous ===
*[[Extrapolation]]
**[[Linear predictive analysis]] — linear extrapolation
*[[Regression analysis]]
**[[Isotonic regression]]
*[[Curve-fitting compaction]]
*[[Interpolation (computer programming)]] — interpolation in the context of 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
***[[Newton fractal]]
***[[Quasi-Newton method]] — uses an approximation of the Jacobian:
****[[Broyden's method]] — uses a rank-one update for the Jacobian
****[[SR1 formula]] — 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
****[[BFGS method]] — rank-two update of the Jacobian in which the matrix remains positive definite
***[[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
**[[Müller's method]] — based on quadratic interpolation at last three iterates
**[[Inverse quadratic interpolation]] — similar to Müller'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''<nowiki>'</nowiki> and ''f''<nowiki>''</nowiki>; achieves the cubic convergence
**[[Householder's method]] — uses first ''d'' derivatives to achieve order ''d'' + 1; generalizes Newton's and Halley's method
*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]]
*Methods for other special cases:
**[[Shifting nth-root algorithm]]
*Analysis:
**[[Wilkinson's polynomial]]
*[[Numerical continuation]] — tracking a root as one parameters in the equation changes
**[[Piecewise linear continuation]]
== Optimization ==
[[Optimization (mathematics)]] — algorithm for finding maxima or minima of a given function
=== Basic concepts ===
*[[Active set]]
*[[Candidate solution]]
*[[Constraint (mathematics)]]
*[[Corner solution]]
*[[Fitness function]] — (esp. in genetic algorithms) an approximation to the objective function that is easier to evaluate
*[[Global optimum]] and [[Local optimum]]
*[[Maxima and minima]]
*[[Slack variable]]
*[[Surplus 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
**[[Interior point method]]
***[[Karmarkar's algorithm]]
***[[Mehrotra predictor-corrector method]]
**[[Delayed column generation]]
**[[k-approximation of k-hitting set]] — algorithm for specific LP problems (to find a weighted hitting set)
*[[Linear complementarity problem]]
*[[Dantzig-Wolfe decomposition]]
*[[Fourier–Motzkin elimination]]
=== Nonlinear programming ===
[[Nonlinear programming]] — the most general optimization problem in the usual framework
*Special cases of nonlinear programming:
**[[Quadratic programming]]
***[[Linear least squares]]
***[[Frank–Wolfe algorithm]]
***[[Bilinear program]]
**[[Convex optimization]]
***[[Linear matrix inequality]]
***[[Conic optimization]]
****[[Semidefinite programming]]
****[[Second-order cone programming]]
****Quadratic programming (see above)
***[[Subgradient method]] — extension of steepest descent for problems with a nondifferentiable objective function
**[[Geometric programming]] — problems involving posynomials
***[[Posynomial]] — similar to polynomials, but coefficients have to be positive while exponents need not be integers
**[[Quadratically constrained quadratic program]]
**[[Least squares]] — the objective function is a sum of squares
***[[Non-linear least squares]]
***[[Gauss–Newton algorithm]]
****[[Generalized Gauss–Newton method]] — for constrained nonlinear least-squares problems
***[[Levenberg–Marquardt algorithm]]
**Univariate optimization:
***[[Golden section search]]
***[[Successive parabolic interpolation]] — based on quadratic interpolation through the last three iterates
*General algorithms:
**Concepts:
***[[Descent direction]]
***[[Line search]]
****[[Backtracking line search]]
****[[Wolfe conditions]]
**[[Gradient descent]]
***[[Stochastic gradient descent]]
**[[Successive linear programming]] (SLP) — replace problem by a linear programming problem, solve that, and repeat
**[[Newton's method in optimization]]
***See also under ''Newton algorithm'' in the [[#Finding roots of nonlinear equations|section ''Finding roots of nonlinear equations'']]
**[[Nonlinear conjugate gradient method]]
**[[Nelder-Mead method]]
**[[Ternary search]]
**[[Tabu search]]
**[[Guided Local Search]] — modification of search algorithms which builds up penalties during a search
**[[Least absolute deviations]]
***[[Expectation-maximization algorithm]]
****[[Ordered subset expectation maximization]]
**[[Nearest neighbor search]]
*[[Mixed complementarity problem]]
=== Uncertainty and randomness ===
*Approaches to deal with uncertainty:
**[[Markov decision process]]
**[[Partially observable Markov decision process]]
**[[Robust optimization]]
**[[Stochastic approximation]]
**[[Stochastic optimization]]
**[[Stochastic programming]]
**[[Stochastic gradient descent]]
*[[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]]
***[[Differential evolution]]
***[[Evolutionary programming]]
***[[Evolution window]]
***[[Genetic algorithm]], [[Genetic programming]]
****[[Genetic algorithm in economics]]
****[[Speciation (genetic algorithm)]]
***[[Genetic representation]]
***[[Gaussian adaptation]]
**[[Memetic algorithm]]
**[[Particle swarm optimization]]
**[[Cooperative optimization]]
***[[Repulsive particle swarm optimization]]
**[[Stochastic tunneling]]
**[[Harmony search]] - mimicks the improvisation process of musicians
**see also the section ''Monte Carlo method''
=== Theoretical aspects ===
*[[Convex analysis]]
**[[Quasiconvex function]]
**[[Subderivative]]
*Duality:
**[[Dual problem]], [[Shadow price]]
**[[Dual cone and polar cone]]
*[[Farkas' lemma]]
*[[Karush–Kuhn–Tucker conditions]]
*[[Lagrange multipliers]]
**[[Lagrange multipliers on Banach spaces]]
**[[Constrained optimization and Lagrange multipliers]]
*[[Danskin's theorem]] — used in the analysis of minimax problems
*[[No free lunch in search and optimization]]
*[[Relaxation technique (mathematics)]]
**[[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
=== 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
*[[Automatic label placement]]
*[[Cutting stock problem]]
*[[Demand optimization]]
*[[Energy minimization]]
*[[Entropy maximization]]
*[[Expenditure minimization problem]]
*[[Inventory control problem]]
**[[Newsvendor]]
**[[Extended Newsvendor models]]
*[[Job-shop problem]]
*[[Multidisciplinary design optimization]]
*[[Optimal classification]]
*[[Paper bag problem]]
*[[Process optimization]]
*[[Stigler diet]]
*[[Stress majorization]]
*[[Trajectory optimization]]
*[[Utility maximization problem]]
*[[Wing shape optimization]]
=== Miscellaneous ===
*[[Combinatorial optimization]]
*[[Dynamic programming]]
**[[Bellman equation]]
**[[Hamilton-Jacobi-Bellman equation]] — continuous-time analoge 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]]:
**[[BRST algorithm]]
**[[MCS algorithm]]
*[[Infinite-dimensional optimization]]
**[[Optimal control]]
***[[Pontryagin's minimum principle]] — infinite-dimensional version of Lagrange multipliers
**[[Shape optimization]], [[Topology optimization]] — optimization over a set of regions
***[[Topological derivative]] — derivative with respect to changing in the shape
*[[Optimal substructure]]
*Algorithmic concepts:
**[[Barrier function]]
**[[Penalty method]]
**[[Trust region]]
*Famous 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 <math>f(x, y) = (x^2+y-11)^2 + (x+y^2-7)^2</math>
**[[Shekel function]] — multimodal and multidimensional
*[[Mathematical Programming Society]]
==Numerical quadrature==
[[Numerical integration]] — the numerical evaluation of an integral
*[[Rectangle method]]
*[[Trapezium rule]]
*[[Simpson's rule]]
**[[Adaptive Simpson's method]]
*[[Newton–Cotes formulas]]
*[[Romberg's method]] - Richardson extrapolation applied to Trapezium rule
*[[Gaussian quadrature]] - highest possible degree with given number of points
*[[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]]''
*[[T-integration]] — a non-standard method
*[[Lebedev grid]] — grid on a sphere with octahedral symmetry
*[[Sparse grid]]
*[[Numerical differentiation]]
*[[Euler–Maclaurin formula]]
==Numerical ordinary differential equations==
[[Numerical 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
*[[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
**[[Cash–Karp method]] — a fifth-order method with six stages and an embedded fourth-order method
**[[Dormand–Prince method]] — another fifth-order method with six stages and an embedded fourth-order method
**[[Runge–Kutta–Fehlberg method]] — another fifth-order method with six stages and an embedded fourth-order method
**[[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 <math>y'' = f(t,y)</math>
*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
*[[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
***[[Semi-implicit Euler]] — variant of Euler method which is symplectic when applied to separable Hamiltonians
*[[Adaptive stepsize]] — automatically changing the step size when that seems advantageous
*[[Stiff equation]] — roughly, an ODE for which the unstable methods needs a very short step size, but stable methods do not.
*Methods for solving two-point boundary value problems (BVPs):
**[[Shooting method]]
*Methods for solving differential-algebraic equations (DAEs), i.e., ODEs with constraints:
**[[Constraint algorithm]] — for solving Newton's equations with constraints
*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
*[[Bi-directional delay line]]
*[[History of numerical solution of differential equations using computers]]
==Numerical 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
**[[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 implicit method for heat equation and related PDEs
*[[Alternating direction implicit]] — second-order method for heat equation and related PDEs
*[[Lax–Wendroff method]] — second-order explicit method for hyperbolic PDEs
*[[MacCormack method]] — second-order explicit method for hyperbolic PDEs
*[[Upwind scheme]] — method for hyperbolic PDEs
*[[Finite-difference time-domain method]] — a finite-difference method for electrodynamics
=== Finite element methods ===
[[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
**[[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
*[[Direct stiffness method]] — a particular implementation of the finite element method, often used in structural analysis
*[[Trefftz method]]
*[[Finite element updating]]
*[[XFEM]] — extended finite element methods, which put functions tailored to the problem in the approximation space
*[[Functionally graded elements]] — elements for describing functionally graded materials
*[[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
*[[NAFEMS]] — not-for-profit organisation that sets and maintains standards in computer-aided engineering analysis
=== Other methods ===
*[[Spectral method]] — based on the Fourier transformation
**[[Pseudo-spectral method]]
*[[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
**[[Diffuse element method]] —
*[[Uniform theory of diffraction]] — specifically designed for scattering problems in electromagnetics
*[[Particle-in-cell]] — used especially in fluid dynamics
*[[High-resolution scheme]]
*[[Shock capturing methods]]
*[[Split-step method]]
*[[Fast marching method]]
*[[Lattice Boltzmann methods]] — for the solution of the Navier-Stokes equations
*[[Roe solver]] — for the solution of the Euler equation
*[[Relaxation method]] — a method for solving elliptic PDEs by converting them to evolution equations
*Broad classes of methods:
**[[Mimetic (mathematics)|Mimetic]] methods — methods that respect in some sense the structure of the original problem
**[[Multiphysics]] — models consisting of various submodels with different physics
=== 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]] (BDD) — preconditioner for symmetric positive definite matrices
**[[BDDC|Balancing domain decomposition by constraints]] (BDDC) — further development of BDD
**[[FETI|Finite element tearing and interconnect]] (FETI)
**[[FETI-DP]] — further development of FETI
**[[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
**[[Schur complement method]] — early and basic method on subdomains that do not overlap
**[[Schwarz alternating method]] — early and basic method on subdomains that overlap
*[[Adaptive mesh refinement]] — uses the computed solution to refine the mesh only where necessary
*[[Fast Multipole Method]] — hierarchical method for evaluating particle-particle interactions
=== Miscellaneous ===
*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
**[[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
*Grids and meshes:
**[[Geodesic grid]] — isotropic grid on a sphere
**[[Parallel mesh generation]]
**[[Spatial twist continuum]] — dual representation of a mesh consisting of hexahedra
*[[Perfectly matched layer]] — artificial absorbing layer for wave equations, used to implement absorbing boundary conditions
==[[Monte Carlo method]]==
*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
***[[Gibbs sampling]]
***[[Coupling from the past]]
**[[Dynamic Monte Carlo method]]
***[[Kinetic Monte Carlo]]
***[[Gillespie algorithm]]
**[[Particle filter]]
**[[Reverse Monte Carlo]]
*Sampling methods:
**[[Inverse transform sampling]] — general and straightforward method but computationally expensive
**[[Rejection sampling]] — sample from a simpler distribution but reject some of the samples
**For sampling from a normal distribution:
***[[Box-Muller transform]]
***[[Marsaglia polar method]]
*[[Low-discrepancy sequence]]
**[[Constructions of low-discrepancy sequences]]
**[[Illustration of a low-discrepancy sequence]]
*[[Event generator]]
*[[Parallel tempering]]
*[[Umbrella sampling]] — improves sampling in physical systems with significant energy barriers
*[[Variance reduction]] techniques:
**[[Control variate]]
**[[Importance sampling]]
**[[Stratified sampling]]
**[[VEGAS algorithm]]
*[[Ensemble Kalman filter]] — recursive filter suitable for problems with a large number of variables
*Applications:
**[[Metropolis light transport]]
**[[Monte Carlo method for photon transport]]
**[[Monte Carlo methods in finance]]
***[[Monte Carlo option model]]
***[[Quasi-Monte Carlo methods in finance]]
**[[Monte Carlo project]] — research project modelling of human exposure to food chemicals and nutrients
**[[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]]
**[[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==
*[[Climate model]]
*[[Numerical weather prediction]]
**[[Geodesic grid]]
*[[Computational chemistry]]
**[[Cell lists]]
**[[Coupled cluster]]
**[[Density functional theory]]
**[[Self-consistent field method]]
*[[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]]
*[[Computational statistics]]
*[[Celestial mechanics]]
**[[Numerical model of solar system]]
==Software==
For software, see the [[list of numerical analysis software]].
[[Category:Numerical analysis|*Topics]]
[[Category:Mathematics-related lists|Numerical analysis topics]]
[[de:Liste numerischer Verfahren]]