Richardson extrapolation

Let $A\_0(h)$ be an approximation of $A^*$(exact value) that depends on a step size {{mvar|h}} (where ) with an error formula of the form

$$A^*\; =\; A\_0(h)+a\_0h^\{k\_0\}\; +\; a\_1h^\{k\_1\}\; +\; a\_2h^\{k\_2\}\; +\; \backslash cdots$$

where the $a\_i$ are unknown constants and the $k\_i$ are known constants such that $h^\{k\_i\}\; >\; h^\{k\_\{i+1\}\}$. Furthermore, $O(h^\{k\_i\})$ represents the truncation error of the $A\_i(h)$ approximation such that $A^*\; =\; A\_i(h)+O(h^\{k\_i\}).$ Similarly, in $A^*=A\_i(h)+O(h^\{k\_i\}),$ the approximation $A\_i(h)$ is said to be an $O(h^\{k\_i\})$ approximation.

Note that by simplifying with Big O notation, the following formulae are equivalent:

$$\backslash begin\{align\}$$

A^* &= A_0(h) + a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots \\

A^* &= A_0(h)+ a_0h^{k_0} + O(h^{k_1}) \\

A^* &= A_0(h)+O(h^{k_0})

\end{align}

Richardson extrapolation is a process that finds a better approximation of $A^*$ by changing the error formula from $A^*=A\_0(h)+O(h^\{k\_0\})$ to $A^*\; =\; A\_1(h)\; +\; O(h^\{k\_1\}).$ Therefore, by replacing $A\_0(h)$ with $A\_1(h)$ the truncation error has reduced from $O(h^\{k\_0\})$ to $O(h^\{k\_1\})$ for the same step size $h$. The general pattern occurs in which $A\_i(h)$ is a more accurate estimate than $A\_j(h)$ when $i>j$. By this process, we have achieved a better approximation of $A^*$ by subtracting the largest term in the error which was $O(h^\{k\_0\})$. This process can be repeated to remove more error terms to get even better approximations.

Using the step sizes $h$ and $h\; /\; t$ for some constant $t$, the two formulas for $A^*$ are:

{{NumBlk||$$A^*\; =\; A\_0(h)+\; a\_0h^\{k\_0\}\; +\; a\_1h^\{k\_1\}\; +\; a\_2h^\{k\_2\}\; +\; O(h^\{k\_3\})$$|{{EquationRef|1}}}}

{{NumBlk||$$A^*\; =\; A\_0\backslash !\backslash left(\backslash frac\{h\}\{t\}\backslash right)\; +\; a\_0\backslash left(\backslash frac\{h\}\{t\}\backslash right)^\{k\_0\}\; +\; a\_1\backslash left(\backslash frac\{h\}\{t\}\backslash right)^\{k\_1\}\; +\; a\_2\backslash left(\backslash frac\{h\}\{t\}\backslash right)^\{k\_2\}\; +\; O(h^\{k\_3\})$$|{{EquationRef|2}}}}

To improve our approximation from $O(h^\{k\_0\})$ to $O(h^\{k\_1\})$ by removing the first error term, we multiply {{EquationNote|2|equation 2}} by $t^\{k\_0\}$ and subtract {{EquationNote|1|equation 1}} to give us

$$(t^\{k\_0\}-1)A^*\; =\; \backslash bigg[t^\{k\_0\}A\_0\backslash left(\backslash frac\{h\}\{t\}\backslash right)\; -\; A\_0(h)\backslash bigg]\; +\; \backslash bigg(t^\{k\_0\}a\_1\backslash bigg(\backslash frac\{h\}\{t\}\backslash bigg)^\{k\_1\}-a\_1h^\{k\_1\}\backslash bigg)+\; \backslash bigg(t^\{k\_0\}a\_2\backslash bigg(\backslash frac\{h\}\{t\}\backslash bigg)^\{k\_2\}-a\_2h^\{k\_2\}\backslash bigg)\; +\; O(h^\{k\_3\}).$$

This multiplication and subtraction was performed because $\backslash big[t^\{k\_0\}A\_0\backslash left(\backslash frac\{h\}\{t\}\backslash right)\; -\; A\_0(h)\backslash big]$ is an $O(h^\{k\_1\})$ approximation of $(t^\{k\_0\}-1)A^*$. We can solve our current formula for $A^*$ to give

$$A^*\; =\; \backslash frac\{\backslash bigg[t^\{k\_0\}A\_0\backslash left(\backslash frac\{h\}\{t\}\backslash right)\; -\; A\_0(h)\backslash bigg]\}\{t^\{k\_0\}-1\}$$

+ \frac{\bigg(t^{k_0}a_1\bigg(\frac{h}{t}\bigg)^{k_1}-a_1h^{k_1}\bigg)}{t^{k_0}-1}

+ \frac{\bigg(t^{k_0}a_2\bigg(\frac{h}{t}\bigg)^{k_2}-a_2h^{k_2}\bigg)}{t^{k_0}-1}

+O(h^{k_3})

which can be written as $A^*\; =\; A\_1(h)+O(h^\{k\_1\})$ by setting

$$A\_1(h)\; =\; \backslash frac\{t^\{k\_0\}A\_0\backslash left(\backslash frac\{h\}\{t\}\backslash right)\; -\; A\_0(h)\}\{t^\{k\_0\}-1\}\; .$$

A general recurrence relation can be defined for the approximations by

$$A\_\{i+1\}(h)\; =\; \backslash frac\{t^\{k\_i\}A\_i\backslash left(\backslash frac\{h\}\{t\}\backslash right)\; -\; A\_i(h)\}\{t^\{k\_i\}-1\}$$

where $k\_\{i+1\}$ satisfies

$$A^*\; =\; A\_\{i+1\}(h)\; +\; O(h^\{k\_\{i+1\}\})\; .$$

The Richardson extrapolation can be considered as a linear sequence transformation.

Additionally, the general formula can be used to estimate $k\_0$ (leading order step size behavior of Truncation error) when neither its value nor $A^*$ 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$$A^*=\backslash frac\{t^\{k\_0\}A\_i\backslash left(\backslash frac\{h\}\{t\}\backslash right)\; -\; A\_i(h)\}\{t^\{k\_0\}-1\}\; +\; O(h^\{k\_1\})\; =\; \backslash frac\{s^\{k\_0\}A\_i\backslash left(\backslash frac\{h\}\{s\}\backslash right)\; -\; A\_i(h)\}\{s^\{k\_0\}-1\}\; +\; O(h^\{k\_1\})$$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 {{math|O}} terms is only approximately valid)

$$A\_i\backslash left(\backslash frac\{h\}\{t\}\backslash right)\; +\; \backslash frac\{A\_i\backslash left(\backslash frac\{h\}\{t\}\backslash right)\; -\; A\_i(h)\}\{t^\{k\_0\}-1\}\; \backslash approx\; A\_i\backslash left(\backslash frac\{h\}\{s\}\backslash right)\; +\backslash frac\{A\_i\backslash left(\backslash frac\{h\}\{s\}\backslash right)\; -\; A\_i(h)\}\{s^\{k\_0\}-1\}$$

which can be solved numerically to estimate $k\_0$ for some arbitrary valid choices of $h$, $s$, and $t$.

As $t\; \backslash neq\; 1$, if $t>0$ and $s$ is chosen so that $s\; =\; t^2$, this approximate relation reduces to a quadratic equation in $t^\{k\_0\}$, which is readily solved for $k\_0$ in terms of $h$ and $t$.

Suppose that we wish to approximate $A^*$, and we have a method $A(h)$ that depends on a small parameter $h$ in such a way that

$$A(h)\; =\; A^\backslash ast\; +\; C\; h^n\; +\; O(h^\{n+1\}).$$

Let us define a new function$$R(h,t)\; :=\; \backslash frac\{\; t^n\; A(h/t)\; -\; A(h)\}\{t^n-1\}$$where $h$ and $\backslash frac\{h\}\{t\}$ are two distinct step sizes.

Then

$$R(h,\; t)\; =\; \backslash frac\{\; t^n\; (\; A^*\; +\; C\; \backslash left(\backslash frac\{h\}\{t\}\backslash right)^n\; +\; O(h^\{n+1\})\; )\; -\; (\; A^*\; +\; C\; h^n\; +\; O(h^\{n+1\})\; )\; \}\{\; t^n\; -\; 1\}\; =\; A^*\; +\; O(h^\{n+1\}).$$

$R(h,t)$ is called the Richardson extrapolation of A(h), and has a higher-order error estimate $O(h^\{n+1\})$ compared to $A(h)$.

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).

The following pseudocode in MATLAB style demonstrates Richardson extrapolation to help solve the ODE $y\text{'}(t)\; =\; -y^2$, $y(0)\; =\; 1$ with the Trapezoidal method. In this example we halve the step size $h$ each iteration and so in the discussion above we'd have that $t\; =\; 2$. 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 $t$ to the second power and to take powers of $4\; =\; 2^2\; =\; t^2$ in the pseudocode. We want to find the value of $y(5)$, which has the exact solution of $\backslash frac\{1\}\{5\; +\; 1\}\; =\; \backslash frac\{1\}\{6\}\; =\; 0.1666...$ since the exact solution of the ODE is $y(t)\; =\; \backslash frac\{1\}\{1\; +\; t\}$. This pseudocode assumes that a function called Trapezoidal(f, tStart, tEnd, h, y0) exists which attempts to compute y(tEnd) by performing the trapezoidal method on the function f, with starting point y0 and tStart and step size h.

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

% The solution to this ODE is y = 1/(1 + t)

y0 = 1 % The initial position (i.e. y0 = y(tStart) = y(0) = 1)

tolerance = 10^-11 % 10 digit accuracy is desired

% Don't allow the iteration to continue indefinitely

maxRows = 20

% Pick an initial step size

initialH = tStart - tEnd

% Were we able to find the solution to within the desired tolerance? not yet.

haveWeFoundSolution = false

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

% Halve the previous value of h since this is the start of a new row.

h = h/2

% Starting filling row i+1 from the left by calling

% the Trapezoidal function with this new smaller step size

A(i + 1, 1) = Trapezoidal(f, tStart, tEnd, h, y0)

% Go across this current (i+1)-th row until the diagonal is reached

for j = 1 : i

% To compute A(i + 1, j + 1), which is the next Richardson extrapolate,

% use the most recently computed value (i.e. A(i + 1, j))

% and the value from the row above it (i.e. A(i, j)).

A(i + 1, j + 1) = ((4^j).*A(i + 1, j) - A(i, j))/(4^j - 1);

end

% After leaving the above inner loop, the diagonal element of row i + 1 has been computed

% This diagonal element is the latest Richardson extrapolate to be computed.

% The difference between this extrapolate and the last extrapolate of row i is a good

% indication of the error.

if (absoluteValue(A(i + 1, i + 1) - A(i, i)) < tolerance) % If the result is within tolerance

% Display the result of the Richardson extrapolation

print("y = ", A(i + 1, i + 1))

haveWeFoundSolution = true

% Done, so leave the loop

break

end

end

% If we were not able to find a solution to within the desired tolerance

if (not haveWeFoundSolution)

print("Warning: Not able to find solution to within the desired tolerance of ", tolerance);

print("The last computed extrapolate was ", A(maxRows, maxRows))

end

• Aitken's delta-squared process
• Takebe Kenko
• Richardson iteration

{{Reflist}}

{{refbegin}}

• Extrapolation Methods. Theory and Practice by C. Brezinski and M. Redivo Zaglia, North-Holland, 1991.
• Ivan Dimov, Zahari Zlatev, Istvan Farago, Agnes Havasi: Richardson Extrapolation: Practical Aspects and Applications, Walter de Gruyter GmbH & Co KG, {{ISBN|9783110533002}} (2017).

{{refend}}

• {{cite web|url=http://www.math.ubc.ca/~feldman/m256/richard.pdf|first1=Joel|last1=Feldman|title= Richardson-Extrapolation|year=2000}}
• {{cite web|url=http://www.math.ubc.ca/~israel/m215/rich/rich.html|title= Richardson extrapolation|first1=Robert|last1=Israel}}
• [https://www.mathworks.com/matlabcentral/fileexchange/24388-richardson-extrapolation Matlab code] for generic Richardson extrapolation.
• [https://github.com/JuliaMath/Richardson.jl Julia code] for generic Richardson extrapolation.

Category:Series acceleration methods

Category:Extrapolation

Category:Articles with example MATLAB/Octave code