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 .

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: