# Ngô Quốc Anh

## January 11, 2009

### An approximation via Richardson extrapolation

Suppose that  is an approximation to  for every  and that

$M = N(h) + {K_1}{h^2} + {K_2}{h^4} + {K_3}{h^6} + ...$

for some constants , , ,..

Now for given values ,  and  we will produce an  approximation to . Indeed, from

$M = N(h) + {K_1}{h^2} + {K_2}{h^4} + {K_3}{h^6} + ...$

we firstly get

$\begin{gathered} M = N\left( {\frac{h} {2}} \right) + \frac{1} {{{2^2}}}{K_1}{h^2} + \frac{1} {{{2^4}}}{K_2}{h^4} + \frac{1} {{{2^6}}}{K_3}{h^6} + ... \hfill \\ M = N\left( {\frac{h} {4}} \right) + \frac{1} {{{4^2}}}{K_1}{h^2} + \frac{1} {{{4^4}}}{K_2}{h^4} + \frac{1} {{{4^6}}}{K_3}{h^6} + .. \hfill \\ \end{gathered}$

which gives

${2^2}M - M = {2^2}N\left( {\frac{h} {4}} \right) - N\left( {\frac{h} {2}} \right) + \left( {{2^2}\frac{1} {{{4^4}}} - \frac{1} {{{2^2}}}} \right){K_2}{h^4} + \left( {{2^2}\frac{1} {{{4^6}}} - \frac{1} {{{2^6}}}} \right){K_3}{h^6} + ...$

i.e.,

$M = \frac{{{2^2}N\left( {\frac{h} {4}} \right) - N\left( {\frac{h} {2}} \right)}} {{{2^2} - 1}} + \frac{{{2^2}\frac{1} {{{4^4}}} - \frac{1} {{{2^2}}}}} {{{2^2} - 1}}{K_2}{h^4} + \frac{{{2^2}\frac{1} {{{4^6}}} - \frac{1} {{{2^6}}}}} {{{2^2} - 1}}{K_3}{h^6} +...$

Similarly, we obtain

$M = \frac{{{2^2}N\left( {\frac{h} {2}} \right) - N\left( h \right)}} {{{2^2} - 1}} + \frac{{{2^2}\frac{1} {{{2^4}}} - 1}} {{{2^2} - 1}}{K_2}{h^4} + \frac{{{2^2}\frac{1} {{{2^6}}} - 1}} {{{2^2} - 1}}{K_3}{h^6} + ...$

Now we easily get

$\left( {\frac{{{2^2}\frac{1} {{{2^4}}} - 1}} {{{2^2} - 1}} - \frac{{{2^2}\frac{1} {{{4^4}}} - \frac{1} {{{2^2}}}}} {{{2^2} - 1}}} \right)M = \frac{{{2^2}\frac{1} {{{2^4}}} - 1}} {{{2^2} - 1}}\frac{{{2^2}N\left( {\frac{h} {4}} \right) - N\left( {\frac{h} {2}} \right)}} {{{2^2} - 1}} - \frac{{{2^2}\frac{1} {{{4^4}}} - \frac{1} {{{2^2}}}}} {{{2^2} - 1}}\frac{{{2^2}N\left( {\frac{h} {2}} \right) - N\left( h \right)}} {{{2^2} - 1}} + \left( {\frac{{{2^2}\frac{1} {{{2^4}}} - 1}} {{{2^2} - 1}}\frac{{{2^2}\frac{1} {{{4^6}}} - \frac{1} {{{2^6}}}}} {{{2^2} - 1}} - \frac{{{2^2}\frac{1} {{{4^4}}} - \frac{1} {{{2^2}}}}} {{{2^2} - 1}}\frac{{{2^2}\frac{1} {{{2^6}}} - 1}} {{{2^2} - 1}}} \right){K_3}{h^6} + ...$

which implies that

$M = \frac{{ - \frac{1} {{{2^2}}}\frac{{{2^2}N\left( {\frac{h} {4}} \right) - N\left( {\frac{h} {2}} \right)}} {3} + \frac{{1 + {2^2}}} {{{2^6}}}\frac{{{2^2}N\left( {\frac{h} {2}} \right) - N\left( h \right)}} {3}}} {{\frac{{1 + {2^2}}} {{{2^6}}} - \frac{1} {{{2^2}}}}} + \frac{{\frac{{1 + {2^2}}} {{{2^6}}}\frac{{1 + {2^2}}} {{{2^{10}}}} - \frac{{1 + {2^2}}} {{{2^6}}}\frac{{1 + {2^2}}} {{{2^4}}}}} {{\frac{{1 + {2^2}}} {{{2^6}}} - \frac{1} {{{2^2}}}}}{K_3}{h^6} + ...$

For example, for given , $N\left( {\frac{h} {2}} \right) = 1.896119$, $N\left( {\frac{h} {4}} \right) = 1.974232$ one can compute that



In general, Let  be an approximation of  that depends on a positive step size  with an error formula of the form

$A - A(h) = a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots$

where the  are unknown constants and the  are known constants such that . The exact value sought can be given by

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

which can be simplified with Big O notation to be

$A = A(h)+ a_0h^{k_0} + O(h^{k_1}).$

Using the step sizes  and  the two formulas for  are:

$\begin{gathered} A = A(h) + {a_0}{h^{{k_0}}} + O({h^{{k_1}}})\,, \hfill \\ A = A\left( {\frac{h} {2}} \right) + {a_0}{\left( {\frac{h} {2}} \right)^{{k_0}}} + O({h^{{k_1}}}). \hfill \\ \end{gathered}$

Multiplying the second equation by  and subtracting the first equation gives

$({t^{{k_0}}} - 1)A = {t^{{k_0}}}A\left( {\frac{h} {t}} \right) - A(h) + O({h^{{k_1}}}).$

Which can be solved for  to give

$A = \frac{{{t^{{k_0}}}A\left( {\frac{h} {t}} \right) - A(h)}} {{{t^{{k_0}}} - 1}} + O({h^{{k_1}}}).$

By this process, we have achieved a better approximation of  by subtracting the largest term in the error which was . This process can be repeated to remove more error terms to get even better approximations. A general recurrence relation can be defined for the approximations by

${A_{i + 1}}(h) = \frac{{{2^{{k_i}}}{A_i}\left( {\frac{h} {2}} \right) - {A_i}(h)}} {{{2^{{k_i}}} - 1}}$

such that $A = A_{i+1}(h) + O(h^{k_{i+1}})$ with .