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.Weniger (2003).

Formulation

For a sequence $\left\_$ the series

:$A = \sum_^\infty a_m\,$

is to be determined. First, the partial sum $A_n$ is defined as:

:$A_n = \sum_^n a_m\,$

and forms a new sequence $\left\_$. 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 byBender & Orszag (1999), pp. 368–375.Van Dyke (1975), pp. 202–205.

:$S(A_n) = \frac = A_ - \frac$

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_ - \frac$) is more numerically stable than the expression to its left (i.e. $S(A_n) = \frac$). 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_^\infty (-1)^k \frac = 4 \left( 1 - \frac + \frac - \frac + \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.

The Shanks transformation $S(A_1)$ already has two-digit accuracy, while the original partial sums only establish the same accuracy at $A_.$ 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 said before, $A_n$ only obtains 6-digit accuracy after about summing 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_ = A + \alpha q^ \quad , \qquad A_n = A + \alpha q^n \qquad \text \qquad A_ = A + \alpha q^.$

These three equations contain three unknowns: $A,$ $\alpha$ and $q.$ Solving for $A$ gives

:$A = \frac.$

In the (exceptional) case that the denominator is equal to zero: then $A_n=A$ for all $n.$

Generalized Shanks transformation

The generalized ''k''th-order Shanks transformation is given as the ratio of the determinants:Bender & Orszag (1999), pp. 389–392.
:$S_k(A_n) = \frac,$
with $\Delta A_p = A_ - 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_^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_, A_, \ldots, A_$ and solving for $A,$ the above expression for the ''k''th-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 to calculate the determinants.

See also

* Aitken's delta-squared process
*Anderson acceleration
*Rate of convergence
*Richardson extrapolation
*Sequence transformation

Notes

References

*
*
*
*
*
*
*
* {{ citation , first=P. , last=Wynn , title=Acceleration techniques for iterated vector and matrix problems , journal=Math. Comp. , volume=16 , year=1962 , pages=301–322

Numerical analysis
Asymptotic analysis
Iterative methods