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 .