# Shanks transformation

In numerical analysis, the Shanks transformation is a non-linear series acceleration method to increase the rate of convergence of a sequence. This method is named after Daniel Shanks, who rediscovered this sequence transformation in 1955. It was first derived and published by R. Schmidt in 1941.
   One can calculate only a few terms of a perturbation expansion, usually no more than two or three, and almost never more than seven. The resulting series is often slowly convergent, or even divergent. Yet those few terms contain a remarkable amount of information, which the investigator should do his best to extract. This viewpoint has been persuasively set forth in a delightful paper by Shanks (1955), who displays a number of amazing examples, including several from fluid mechanics.
Milton D. Van Dyke (1975) Perturbation methods in fluid mechanics, p. 202.

## Formulation

For a sequence $\left\{a_{m}\right\}_{m\in \mathbb {N} }$ the series
    $A=\sum _{m=0}^{\infty }a_{m}\,$
is to be determined. First, the partial sum $A_{n}$ is defined as:
    $A_{n}=\sum _{m=0}^{n}a_{m}\,$
and forms a new sequence $\left\{A_{n}\right\}_{n\in \mathbb {N} }$. Provided the series converges, $A_{n}$ will also approach the limit $A$ as $n\to \infty .$ The Shanks transformation $S(A_{n})$ of the sequence $A_{n}$ is the new sequence defined by
    $S(A_{n})={\frac {A_{n+1}\,A_{n-1}\,-\,A_{n}^{2}}{A_{n+1}-2A_{n}+A_{n-1}}}=A_{n+1}-{\frac {(A_{n+1}-A_{n})^{2}}{(A_{n+1}-A_{n})-(A_{n}-A_{n-1})}}$
where this sequence $S(A_{n})$ often converges more rapidly than the sequence $A_{n}.$
Further speed-up may be obtained by repeated use of the Shanks transformation, by computing $S^{2}(A_{n})=S(S(A_{n})),$ $S^{3}(A_{n})=S(S(S(A_{n}))),$ etc.
Note that the non-linear transformation as used in the Shanks transformation is essentially the same as used in Aitken's delta-squared process so that as with Aitken's method, the right-most expression in $S(A_{n})$'s definition (i.e. $S(A_{n})=A_{n+1}-{\frac {(A_{n+1}-A_{n})^{2}}{(A_{n+1}-A_{n})-(A_{n}-A_{n-1})}}$) is more numerically stable than the expression to its left (i.e. $S(A_{n})={\frac {A_{n+1}\,A_{n-1}\,-\,A_{n}^{2}}{A_{n+1}-2A_{n}+A_{n-1}}}$). Both Aitken's method and the Shanks transformation operate on a sequence, but the sequence the Shanks transformation operates on is usually thought of as being a sequence of partial sums, although any sequence may be viewed as a sequence of partial sums.

## Example

As an example, consider the slowly convergent series
    $4\sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{2k+1}}=4\left(1-{\frac {1}{3}}+{\frac {1}{5}}-{\frac {1}{7}}+\cdots \right)$
which has the exact sum π ≈ 3.14159265. The partial sum $A_{6}$ has only one digit accuracy, while six-figure accuracy requires summing about 400,000 terms.
In the table below, the partial sums $A_{n}$, the Shanks transformation $S(A_{n})$ on them, as well as the repeated Shanks transformations $S^{2}(A_{n})$ and $S^{3}(A_{n})$ are given for $n$ up to 12. The figure to the right shows the absolute error for the partial sums and Shanks transformation results, clearly showing the improved accuracy and convergence rate.
| $n$ | $A_{n}$ | $S(A_{n})$ | $S^{2}(A_{n})$ | $S^{3}(A_{n})$ |
| 0 | 4.00000000 | — | — | — |
| 1 | 2.66666667 | 3.16666667 | — | — |
| 2 | 3.46666667 | 3.13333333 | 3.14210526 | — |
| 3 | 2.89523810 | 3.14523810 | 3.14145022 | 3.14159936 |
| 4 | 3.33968254 | 3.13968254 | 3.14164332 | 3.14159086 |
| 5 | 2.97604618 | 3.14271284 | 3.14157129 | 3.14159323 |
| 6 | 3.28373848 | 3.14088134 | 3.14160284 | 3.14159244 |
| 7 | 3.01707182 | 3.14207182 | 3.14158732 | 3.14159274 |
| 8 | 3.25236593 | 3.14125482 | 3.14159566 | 3.14159261 |
| 9 | 3.04183962 | 3.14183962 | 3.14159086 | 3.14159267 |
| 10 | 3.23231581 | 3.14140672 | 3.14159377 | 3.14159264 |
| 11 | 3.05840277 | 3.14173610 | 3.14159192 | 3.14159266 |
| 12 | 3.21840277 | 3.14147969 | 3.14159314 | 3.14159265 |
The Shanks transformation $S(A_{1})$ already has two-digit accuracy, while the original partial sums only establish the same accuracy at $A_{24}.$ Remarkably, $S^{3}(A_{3})$ has six digits accuracy, obtained from repeated Shank transformations applied to the first seven terms $A_{0},\ldots ,A_{6}.$ As mentioned before, $A_{n}$ only obtains 6-digit accuracy after summing about 400,000 terms.

## Motivation

The Shanks transformation is motivated by the observation that — for larger $n$ — the partial sum $A_{n}$ quite often behaves approximately as
    $A_{n}=A+\alpha q^{n},\,$
with $|q|<1$ so that the sequence converges transiently to the series result $A$ for $n\to \infty .$ So for $n-1,$ $n$ and $n+1$ the respective partial sums are:
    $A_{n-1}=A+\alpha q^{n-1}\quad ,\qquad A_{n}=A+\alpha q^{n}\qquad {\text{and}}\qquad A_{n+1}=A+\alpha q^{n+1}.$
These three equations contain three unknowns: $A,$ $\alpha$ and $q.$ Solving for $A$ gives
    $A={\frac {A_{n+1}\,A_{n-1}\,-\,A_{n}^{2}}{A_{n+1}-2A_{n}+A_{n-1}}}.$
In the (exceptional) case that the denominator is equal to zero: then $A_{n}=A$ for all $n.$

## Generalized Shanks transformation

The generalized kth-order Shanks transformation is given as the ratio of the determinants:
    $S_{k}(A_{n})={\frac {\begin{vmatrix}A_{n-k}&\cdots &A_{n-1}&A_{n}\\\Delta A_{n-k}&\cdots &\Delta A_{n-1}&\Delta A_{n}\\\Delta A_{n-k+1}&\cdots &\Delta A_{n}&\Delta A_{n+1}\\\vdots &&\vdots &\vdots \\\Delta A_{n-1}&\cdots &\Delta A_{n+k-2}&\Delta A_{n+k-1}\\\end{vmatrix}}{\begin{vmatrix}1&\cdots &1&1\\\Delta A_{n-k}&\cdots &\Delta A_{n-1}&\Delta A_{n}\\\Delta A_{n-k+1}&\cdots &\Delta A_{n}&\Delta A_{n+1}\\\vdots &&\vdots &\vdots \\\Delta A_{n-1}&\cdots &\Delta A_{n+k-2}&\Delta A_{n+k-1}\\\end{vmatrix}}},$
with $\Delta A_{p}=A_{p+1}-A_{p}.$ It is the solution of a model for the convergence behaviour of the partial sums $A_{n}$ with $k$ distinct transients:
    $A_{n}=A+\sum _{p=1}^{k}\alpha _{p}q_{p}^{n}.$
This model for the convergence behaviour contains $2k+1$ unknowns. By evaluating the above equation at the elements $A_{n-k},A_{n-k+1},\ldots ,A_{n+k}$ and solving for $A,$ the above expression for the kth-order Shanks transformation is obtained. The first-order generalized Shanks transformation is equal to the ordinary Shanks transformation: $S_{1}(A_{n})=S(A_{n}).$
The generalized Shanks transformation is closely related to Padé approximants and Padé tables.
Note: The calculation of determinants requires many arithmetic operations to make, however Peter Wynn discovered a recursive evaluation procedure called epsilon-algorithm which avoids calculating the determinants.