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 &pi;]]: **[[Liu Hui's π algorithm]] — first algorithm that can compute &pi; to arbitrary precision **[[Gauss–Legendre algorithm]] — iteration which converges quadratically to &pi;, based on arithmetic-geometric mean **[[Bailey-Borwein-Plouffe formula]] — can be used to compute individual hexadecimal digits of &pi; **[[Borwein's algorithm]] — iteration which converges quartically to 1/&pi;, 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 &pm;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>&infin;</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>&infin;</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]]