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.

Formulation

For a sequence the series is to be determined. First, the partial sum A_n is defined as: and forms a new sequence. 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 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 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. ) is more numerically stable than the expression to its left (i.e. ). 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 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_{24}. Remarkably, S^3(A_3) has six digits accuracy, obtained from repeated Shank transformations applied to the first seven terms 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 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: These three equations contain three unknowns: A, \alpha and q. Solving for A gives 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: with It is the solution of a model for the convergence behaviour of the partial sums A_n with k distinct transients: This model for the convergence behaviour contains 2k+1 unknowns. By evaluating the above equation at the elements 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: 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.