Digital Library of Mathematical Functions
About the Project
NIST
3 Numerical MethodsAreas

§3.9 Acceleration of Convergence

Contents

§3.9(i) Sequence Transformations

All sequences (series) in this section are sequences (series) of real or complex numbers.

A transformation of a convergent sequence {sn} with limit σ into a sequence {tn} is called limit-preserving if {tn} converges to the same limit σ.

The transformation is accelerating if it is limit-preserving and if

3.9.1 limntn-σsn-σ=0.

Similarly for convergent series if we regard the sum as the limit of the sequence of partial sums.

It should be borne in mind that a sequence (series) transformation can be effective for one type of sequence (series) but may not accelerate convergence for another type. It may even fail altogether by not being limit-preserving.

§3.9(ii) Euler’s Transformation of Series

If S=k=0(-1)kak is a convergent series, then

3.9.2 S=k=0(-1)k2-k-1Δka0,

provided that the right-hand side converges. Here Δ is the forward difference operator:

3.9.3 Δka0=Δk-1a1-Δk-1a0,
k=1,2,.

Thus

3.9.4 Δka0=m=0k(-1)m(km)ak-m.

Euler’s transformation is usually applied to alternating series. Examples are provided by the following analytic transformations of slowly-convergent series into rapidly convergent ones:

3.9.5 ln2=1-12+13-14+=1121+1222+1323+,
3.9.6 π4=1-13+15-17+=12(1+1!13+2!35+3!357+).

§3.9(iii) Aitken’s Δ2-Process

3.9.7 tn=sn-(Δsn)2Δ2sn=sn-(sn+1-sn)2sn+2-2sn+1+sn.

This transformation is accelerating if {sn} is a linearly convergent sequence, i.e., a sequence for which

3.9.8 limnsn+1-σsn-σ=ρ,
|ρ|<1.

When applied repeatedly, Aitken’s process is known as the iterated Δ2-process. See Brezinski and Redivo Zaglia (1991, pp. 39–42).

§3.9(iv) Shanks’ Transformation

Shanks’ transformation is a generalization of Aitken’s Δ2-process. Let k be a fixed positive integer. Then the transformation of the sequence {sn} into a sequence {tn,2k} is given by

3.9.9 tn,2k=Hk+1(sn)Hk(Δ2sn),
n=0,1,2,,

where Hm is the Hankel determinant

3.9.10 Hm(un)=|unun+1un+m-1un+1un+2un+mun+m-1un+mun+2m-2|.

The ratio of the Hankel determinants in (3.9.9) can be computed recursively by Wynn’s epsilon algorithm:

3.9.11 ε-1(n) =0,
ε0(n) =sn,
n=0,1,2,,
εm+1(n) =εm-1(n+1)+1εm(n+1)-εm(n),
n,m=0,1,2,.

Then tn,2k=ε2k(n). Aitken’s Δ2-process is the case k=1.

If sn is the nth partial sum of a power series f, then tn,2k=ε2k(n) is the Padé approximant [(n+k)/k]f3.11(iv)).

For further information on the epsilon algorithm see Brezinski and Redivo Zaglia (1991, pp. 78–95).

Example

In Table 3.9.1 values of the transforms tn,2k are supplied for

3.9.12 sn=j=1n(-1)j+1j2,

with s=112π2=0.82246 70334 24.

Table 3.9.1: Shanks’ transformation for sn=j=1n(-1)j+1j-2.
n tn,2 tn,4 tn,6 tn,8 tn,10
0 0.80000 00000 00 0.82182 62806 24 0.82244 84501 47 0.82246 64909 60 0.82246 70175 41
1 0.82692 30769 23 0.82259 02017 65 0.82247 05346 57 0.82246 71342 06 0.82246 70363 45
2 0.82111 11111 11 0.82243 44785 14 0.82246 61821 45 0.82246 70102 48 0.82246 70327 79
3 0.82300 13550 14 0.82247 78118 35 0.82246 72851 83 0.82246 70397 56 0.82246 70335 90
4 0.82221 76684 88 0.82246 28314 41 0.82246 69467 93 0.82246 70314 36 0.82246 70333 75
5 0.82259 80392 16 0.82246 88857 22 0.82246 70670 21 0.82246 70341 24 0.82246 70334 40
6 0.82239 19390 77 0.82246 61352 37 0.82246 70190 76 0.82246 70331 54 0.82246 70334 18
7 0.82251 30483 23 0.82246 75033 13 0.82246 70400 56 0.82246 70335 37 0.82246 70334 26
8 0.82243 73137 33 0.82246 67719 32 0.82246 70301 49 0.82246 70333 73 0.82246 70334 23
9 0.82248 70624 89 0.82246 71865 91 0.82246 70351 34 0.82246 70334 48 0.82246 70334 24
10 0.82245 30535 15 0.82246 69397 57 0.82246 70324 88 0.82246 70334 12 0.82246 70334 24

§3.9(v) Levin’s and Weniger’s Transformations

We give a special form of Levin’s transformation in which the sequence s={sn} of partial sums sn=j=0naj is transformed into:

3.9.13 k(n)(s)=j=0k(-1)j(kj)cj,k,nsn+j/an+j+1j=0k(-1)j(kj)cj,k,n/an+j+1,

where k is a fixed nonnegative integer, and

3.9.14 cj,k,n=(n+j+1)k-1(n+k+1)k-1.

Sequences that are accelerated by Levin’s transformation include logarithmically convergent sequences, i.e., sequences sn converging to σ such that

3.9.15 limnsn+1-σsn-σ=1.

For further information see Brezinski and Redivo Zaglia (1991, pp. 39–42).

In Weniger’s transformations the numbers cj,k,n in (3.9.13) are chosen as follows:

3.9.16 cj,k,n=(β+n+j)k-1(β+n+k)k-1,

or

3.9.17 cj,k,n=(-γ-n-j)k-1(-γ-n-k)k-1,

where (a)0=1 and (a)j=a(a+1)(a+j-1) are Pochhammer symbols (§5.2(iii)), and the constants β and γ are chosen arbitrarily subject to certain conditions. See Weniger (1989).

§3.9(vi) Applications and Further Transformations

For examples and other transformations for convergent sequences and series, see Wimp (1981, pp. 156–199), Brezinski and Redivo Zaglia (1991, pp. 55–72), and Sidi (2003, Chapters 6, 12–13, 15–16, 19–24, and pp. 483–492).

For applications to asymptotic expansions, see §2.11(vi), Olver (1997b, pp. 540–543), and Weniger (1989, 2003).