Accelerate convergence (Shanks Transformation)

Written by

in

Summation techniques

Imagine you’ve solved a problem using a Taylor series expansion of the solution, and the resulting series converges very slowly. The Shanks transformation is one way of improving the speed of convergence of a convergent series.
Given the partial sum:

$\displaystyle S_N = a_0 + a_1 + a_2 + \dots + a_N$

Suppose that this partial sum converges to:

$\displaystyle S = a_0 + a_1 + a_2 + \dots$

$\displaystyle S = \lim_{N \to \infty} \sum_{k=0}^{N} a_k$

We can model the difference between S and S_N as follows:

$\displaystyle S_N = S + \alpha \beta^{N}$

Where $|\beta| < 1$ :

$\displaystyle S_{N+1} = S + \alpha \beta^{N+1}$

$\displaystyle S_N = S + \alpha \beta^{N}$

$\displaystyle S_{N-1} = S + \alpha \beta^{N-1}$

and

$\displaystyle S_{N+1} - S = \alpha \beta^{N+1}$

$\displaystyle S_N - S = \alpha \beta^{N}$

$\displaystyle S_{N-1} - S = \alpha \beta^{N-1}$

Therefore:

$\displaystyle \frac{S_N - S}{S_{N-1}-S} = \frac{\alpha \beta^{N}}{\alpha \beta^{N-1}} = \beta$

$\displaystyle \frac{S_{N+1} - S}{S_{N}-S} = \frac{\alpha \beta^{N+1}}{\alpha \beta^{N}} = \beta$

$\displaystyle \frac{S_N - S}{S_{N-1}-S} = \frac{S_{N+1} - S}{S_{N}-S}$

$\displaystyle (S_N - S)(S_{N}-S) = (S_{N+1} - S)(S_{N-1}-S)$

$\displaystyle S_N^2 - 2S_NS + S^2 = S_{N+1}S_{N-1}- SS_{N+1} - SS_{N-1} + S^2$

$\displaystyle S_N^2 - 2S_NS + S^2= S_{N+1}S_{N-1} + S^{2}- S(S_{N+1}+ S_{N-1})$

$\displaystyle S_N^2 - 2S_NS = S_{N+1}S_{N-1}- S(S_{N+1}+ S_{N-1})$

$\displaystyle S_N^2 - S_{N+1}S_{N-1} = - S(S_{N+1}+ S_{N-1}) - 2S_NS$

$\displaystyle S_N^2 - S_{N+1}S_{N-1} = S(-S_{N+1}- S_{N-1})+ 2S_N$

$\displaystyle S = \frac{S_N^2 - S_{N+1}S_{N-1}}{2S_N -S_{N+1}- S_{N-1}}$

According to this result, the Shanks transformation is defined as:

$\displaystyle \mathcal{S} := \frac{S_N^2 - S_{N+1}S_{N-1}}{2S_N -S_{N+1}- S_{N-1}}$

Comments

Leave a comment Cancel reply

More posts