Richardson extrapolation
In numerical analysis, Richardson extrapolation is a sequence acceleration method used to improve the rate of convergence of a sequence of estimates of some value formula_1. In essence, given the value of formula_2 for several values of formula_3, we can estimate formula_4 by extrapolating the estimates to formula_5. It is named after Lewis Fry Richardson, who introduced the technique in the early 20th century, though the idea was already known to Christiaan Huygens in his calculation of π. In the words of Birkhoff and Rota, "its usefulness for practical computations can hardly be overestimated." Practical applications of Richardson  extrapolation include Romberg integration, which applies Richardson extrapolation to the trapezoid rule, and the Bulirsch–Stoer algorithm for solving ordinary differential equations. Example of Richardson extrapolation. Suppose that we wish to approximate formula_6, and we have a method formula_2 that depends on a small parameter formula_3 in such a way that formula_9 Let us define a new function formula_10 where formula_3 and formula_12 are two distinct step sizes. Then formula_13 formula_14 is called the Richardson extrapolation of "A"("h"), and has a higher-order error estimate formula_15 compared to formula_16. Very often, it is much easier to obtain a given precision  by using "R(h)" rather than "A(h')" with a much smaller " h' ". Where "A(h')" can cause problems due to limited precision (rounding errors) and/or due to the increasing number of calculations needed (see examples below). General formula. Let "formula_2" be an approximation of "formula_6"(exact value) that depends on a positive step size "h" with an error formula of the form where the "a" are unknown constants and the "k" are known constants such that "h" > "h". Further "k" is the leading order step size behavior of the truncation error as formula_20 The exact value sought can be given by which  can be simplified with Big O notation to be Using the step sizes "h" and "formula_23" for some constant "t", the two formulas for "A" are: Multiplying the second equation by "t" and subtracting the first equation gives which can be solved for formula_6 to give Therefore, using formula_29 the truncation error has been reduced to formula_30. This is in contrast to formula_2 where the truncation error is formula_32 for the same step size formula_3 By this process, we have achieved a better approximation of "A" by subtracting the largest term in the error which was "O"("h"). This process can  be repeated to remove more error terms to get even better approximations. A general recurrence relation beginning with formula_34 can be defined for the approximations by where formula_36 satisfies The Richardson extrapolation can be considered as a linear sequence transformation. Additionally, the general formula can be used to estimate "k" (leading order step size behavior of Truncation error) when neither its value nor "A" (exact value) is known "a priori". Such a technique can be useful for quantifying an unknown rate of convergence. Given approximations of "A" from three distinct step sizes "h", "h / t", and "h / s", the exact  relationship yields an approximate relationship (please note that the notation here may cause a bit of confusion, the two O appearing in the equation above only indicates the leading order step size behavior but their explicit forms are different and hence cancelling out of the two O terms is approximately valid) which can be solved numerically to estimate "k" for some arbitrary choices of "h", "s" and "t". Example pseudocode code for Richardson extrapolation. The following pseudocode in MATLAB style demonstrates Richardson extrapolation to help solve the ODE formula_40, formula_41 with the Trapezoidal method. In this example we halve the  step size formula_3 each iteration and so in the discussion above we'd have that formula_43. The error of the Trapezoidal method can be expressed in terms of odd powers so that the error over multiple steps can be expressed in even powers; this leads us to raise formula_44 to the second power and to take powers of formula_45 in the pseudocode. We want to find the value of formula_46, which has the exact solution of formula_47 since the exact solution of the ODE is formula_48. This pseudocode assumes that a function called codice_1 exists which attempts to compute codice_2  by performing the trapezoidal method on the function codice_3, with starting point codice_4 and codice_5 and step size codice_6. Note that starting with too small an initial step size can potentially introduce error into the final solution. Although there are methods designed to help pick the best initial step size, one option is to start with a large step size and then to allow the Richardson extrapolation to reduce the step size each iteration until the error reaches the desired tolerance. tStart = 0 % Starting time tEnd = 5 % Ending time f = -y^2 % The derivative of y, so y ' = f(t, y(t)) = -y^2 y0 = 1 % The initial position (i.e. y0 = y(tStart) = y(0) = 1) tolerance = 10^-11 % 10 digit accuracy is desired maxRows = 20 % Don't allow the iteration to continue indefinitely initialH = tStart - tEnd % Pick an initial step size haveWeFoundSolution = false % Were we able to find the solution to within the desired tolerance? not yet. h = initialH % Create a 2D matrix of size maxRows by maxRows to hold the Richardson extrapolates % Note that this will be a lower triangular matrix and that at most two rows are actually  % needed at any time in the computation. A = zeroMatrix(maxRows, maxRows) %Compute the top left element of the matrix. The first row of this (lower triangular) matrix has now been filled. A(1, 1) = Trapezoidal(f, tStart, tEnd, h, y0) % Each row of the matrix requires one call to Trapezoidal % This loops starts by filling the second row of the matrix, since the first row was computed above for i = 1 : maxRows - 1 % Starting at i = 1, iterate at most maxRows - 1 times end if (haveWeFoundSolution == false) % If we were not able to find a solution to  within the desired tolerance end