Shanks transformation explained

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.^[1]

Formulation

For a sequence

\left\{a _{m\right\}} _{m\inN} the seriesA = \sum ^{inf ty} _{m =0} a _{m}

is to be determined. First, the partial sum

A _{n} is defined as:A _{n} = \sum ^{n} _{m =0} a _{m}

and forms a new sequence

\left\{A _{n\right\}} _{n\inN} . Provided the series converges, A _{n} will also approach the limit A as n\to inf ty. The Shanks transformation S(A _{n)} of the sequence A _{n} is the new sequence defined by^{[2] [3]} S(A _{n)} = (A _{n +1} A _{n-1} - A ^{2} _{n})/(A _{n+1} -2 A _{n+A} _{n-1}) = A _{n+1} - ((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} - ((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)} = (A _{n +1} A _{n-1} - A ^{2} _{n})/(A _{n+1} -2 A _{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^[3]

4 \sum ^{inf ty} _{k =0} ( -1 ) ^{k} (1)/(2 k +1) = 4 \left( 1 - (1)/(3) + (1)/(5) - (1)/(7) + … \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^[2] A _{n} = A + \alpha q ^{n,}

with

|q|< 1 so that the sequence converges transiently to the series result A for n\to inf ty. So for n -1 , n and n +1 the respective partial sums are:A _{n-1} = A + \alpha q ^{n-1} , A _{n} = A + \alpha q ^{n} and A _{n+1} = A + \alpha q ^{n+1} .

These three equations contain three unknowns:

A, \alpha and q. Solving for A gives^[2] A = (A _{n +1} A _{n-1} - A ^{2} _{n})/(A _{n+1} -2 A _{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:^[4]

S _{k(A} _{n)} = (\begin{vmatrix)/(A) _{n-k} & … & A _{n-1} & A _{n} \\ \Delta A _{n-k} & … & \Delta A _{n-1} & \Delta A _{n} \\ \Delta A _{n-k+1} & … & \Delta A _{n} & \Delta A _{n+1} \\ \vdots & & \vdots & \vdots \\ \Delta A _{n-1} & … & \Delta A _{n+k-2} & \Delta A _{n+k-1} \\ \end{vmatrix} }{ \begin{vmatrix} 1 & … & 1 & 1 \\ \Delta A _{n-k} & … & \Delta A _{n-1} & \Delta A _{n} \\ \Delta A _{n-k+1} & … & \Delta A _{n} & \Delta A _{n+1} \\ \vdots & & \vdots & \vdots \\ \Delta A _{n-1} & … & \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 ^{k} _{p =1} \alpha _{p} q ^{n.} _{p}

This model for the convergence behaviour contains

2 k +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.^[4]

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.^{[5] [6]}

See also

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

References

• • • • • Weniger . E.J. . Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series. Computer Physics Reports . 10 . 5–6 . 189–371 . math.NA/0306302 . 1989 . 1989CoPhR..10..189W . 10.1016/0167-7977(89)90011-7 .

Notes and References

1. Weniger (2003).
2. Bender & Orszag (1999), pp. 368–375.
3. Van Dyke (1975), pp. 202–205.
4. Bender & Orszag (1999), pp. 389–392.
5. Wynn (1956)
6. Wynn (1962)