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: History of numerical solution of differential equations using computers Hundred-dollar, Hundred-digit Challenge problems — list of ten problems proposed by Nick Trefethen in 2002 Timeline of numerical analysis after 1945 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 Error analysis (mathematics) 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 Numeric precision in Microsoft Excel 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 See also: Interval boundary element method, Interval finite element Loss of significance Numerical error Numerical stability Error propagation: Propagation of uncertainty Residual (numerical analysis) 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 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: Exponentiation by squaring Addition-chain exponentiation Multiplicative inverse Algorithms: for computing a number's multiplicative inverse (reciprocal). Newton's method 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 / 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 Band matrix Bidiagonal matrix Tridiagonal matrix Pentadiagonal matrix Skyline 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 Minimum degree algorithm Symbolic Cholesky decomposition 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 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