Notation

Let ${\displaystyle A_{0}(h)}$ be an approximation of ${\displaystyle A^{*}}$(exact value) that depends on a positive step size h with an error formula of the form

$${\displaystyle A^{*}=A_{0}(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots }$$

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

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

$${\displaystyle {\begin{aligned}A^{*}&=A_{0}(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots \\A^{*}&=A_{0}(h)+a_{0}h^{k_{0}}+O(h^{k_{1}})\\A^{*}&=A_{0}(h)+O(h^{k_{0}})\end{aligned}}}$$

Purpose

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

Process

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

$${\displaystyle A^{*}=A_{0}(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+O(h^{k_{3}})}$$

(1)

$${\displaystyle A^{*}=A_{0}\!\left({\frac {h}{t}}\right)+a_{0}\left({\frac {h}{t}}\right)^{k_{0}}+a_{1}\left({\frac {h}{t}}\right)^{k_{1}}+a_{2}\left({\frac {h}{t}}\right)^{k_{2}}+O(h^{k_{3}})}$$

(2)

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

$${\displaystyle (t^{k_{0}}-1)A^{*}={\bigg [}t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h){\bigg ]}+{\bigg (}t^{k_{0}}a_{1}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{1}}-a_{1}h^{k_{1}}{\bigg )}+{\bigg (}t^{k_{0}}a_{2}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{2}}-a_{2}h^{k_{2}}{\bigg )}+O(h^{k_{3}}).}$$

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

$${\displaystyle A^{*}={\frac {{\bigg [}t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h){\bigg ]}}{t^{k_{0}}-1}}+{\frac {{\bigg (}t^{k_{0}}a_{1}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{1}}-a_{1}h^{k_{1}}{\bigg )}}{t^{k_{0}}-1}}+{\frac {{\bigg (}t^{k_{0}}a_{2}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{2}}-a_{2}h^{k_{2}}{\bigg )}}{t^{k_{0}}-1}}+O(h^{k_{3}})}$$

which can be written as ${\displaystyle A^{*}=A_{1}(h)+O(h^{k_{1}})}$ by setting

$${\displaystyle A_{1}(h)={\frac {t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h)}{t^{k_{0}}-1}}.}$$

Recurrence relation

A general recurrence relation can be defined for the approximations by

$${\displaystyle A_{i+1}(h)={\frac {t^{k_{i}}A_{i}\left({\frac {h}{t}}\right)-A_{i}(h)}{t^{k_{i}}-1}}}$$

where ${\displaystyle k_{i+1}}$ satisfies

$${\displaystyle A^{*}=A_{i+1}(h)+O(h^{k_{i+1}}).}$$

Properties

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

Additionally, the general formula can be used to estimate ${\displaystyle k_{0}}$ (leading order step size behavior of Truncation error) when neither its value nor ${\displaystyle A^{*}}$ is known a priori. Such a technique can be useful for quantifying an unknown rate of convergence. Given approximations of ${\displaystyle A^{*}}$ from three distinct step sizes ${\displaystyle h}$, ${\displaystyle h/t}$, and ${\displaystyle h/s}$, the exact relationship

$${\displaystyle A^{*}={\frac {t^{k_{0}}A_{i}\left({\frac {h}{t}}\right)-A_{i}(h)}{t^{k_{0}}-1}}+O(h^{k_{1}})={\frac {s^{k_{0}}A_{i}\left({\frac {h}{s}}\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 O terms is only approximately valid)

$${\displaystyle A_{i}\left({\frac {h}{t}}\right)+{\frac {A_{i}\left({\frac {h}{t}}\right)-A_{i}(h)}{t^{k_{0}}-1}}\approx A_{i}\left({\frac {h}{s}}\right)+{\frac {A_{i}\left({\frac {h}{s}}\right)-A_{i}(h)}{s^{k_{0}}-1}}}$$

which can be solved numerically to estimate ${\displaystyle k_{0}}$ for some arbitrary valid choices of ${\displaystyle h}$, ${\displaystyle s}$, and ${\displaystyle t}$.

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