Approximaths

Richardson interpolation

Written by

approximaths

in

Another method for accelerating convergence is Richardson interpolation. This method is similar to the Shanks transformation. Let’s model the partial sum as:

\displaystyle S_N = \sum_{n=0}^{N} a_n = S + \frac{a}{N} + \frac{b}{N^2} + \frac{c}{N^3} + \dots

where S = \lim_{N \to \infty} S_N.

\displaystyle S_N = S + \frac{a}{N} + \frac{b}{N^2} + \frac{c}{N^3} + \dots
\displaystyle S_{N+1} = S + \frac{a}{N+1} + \frac{b}{(N+1)^2} + \frac{c}{(N+1)^3} + \dots
\displaystyle S_{N+2} = S + \frac{a}{N+2} + \frac{b}{(N+2)^2} + \frac{c}{(N+2)^3} + \dots

equivalently:

\displaystyle N^2 S_N = N^2 S + N a + b + \frac{c}{N} + \dots
\displaystyle (N+1)^2 S_{N+1} = (N+1)^2 S + (N+1) a + b + \frac{c}{N+1} + \dots
\displaystyle (N+2)^2 S_{N+2} = (N+2)^2 S + (N+2) a + b + \frac{c}{N+2} + \dots

and

\displaystyle N^2 S_N = N^2 S + N a + b + \frac{c}{N} + \dots
\displaystyle -2 (N+1)^2 S_{N+1} = -2 (N+1)^2 S - 2 (N+1) a - 2 b - 2 \frac{c}{N+1} + \dots
\displaystyle (N+2)^2 S_{N+2} = (N+2)^2 S + (N+2) a + b + \frac{c}{N+2} + \dots

Summing up the system above:

\displaystyle N^2 S_N - 2 (N+1)^2 S_{N+1} + (N+2)^2 S_{N+2} = N^2 S + N a + b + \frac{c}{N} + \dots
\displaystyle -2 (N+1)^2 S - 2 (N+1) a - 2 b - 2 \frac{c}{N+1} + \dots
\displaystyle + (N+2)^2 S + (N+2) a + b + \frac{c}{N+2} + \dots

Simplifying and taking the limit N \to \infty:

\displaystyle N^2 S_N - 2 (N+1)^2 S_{N+1} + (N+2)^2 S_{N+2} = N^2 S + a N + b
\displaystyle - 2 N^2 S - 4 N S - 2 S - 2 a N - 2 a - 2 b
\displaystyle + N^2 S + 4 N S + 4 S + a N + 2 a + b
\displaystyle = 2 S
\displaystyle \implies S = \frac{N^2 S_N - 2 (N+1)^2 S_{N+1} + (N+2)^2 S_{N+2}}{2} \quad \text{(as } N \to \infty\text{)}

On this basis, we define the Richardson interpolation as:

\boxed{\displaystyle \mathcal{R}_N := \frac{N^2 S_N - 2 (N+1)^2 S_{N+1} + (N+2)^2 S_{N+2}}{2}}

Comments

Leave a comment

More posts