§3.9 Acceleration of Convergence

Keywords:: acceleration of convergence
Referenced by:: §17.18, §2.11(vi)
Permalink:: http://dlmf.nist.gov/3.9

§3.9(i) Sequence Transformations
§3.9(ii) Euler’s Transformation of Series
§3.9(iii) Aitken’s $\Delta^{2}$ -Process
§3.9(iv) Shanks’ Transformation
§3.9(v) Levin’s and Weniger’s Transformations
§3.9(vi) Applications and Further Transformations

§3.9(i) Sequence Transformations

Keywords:: acceleration of convergence
Permalink:: http://dlmf.nist.gov/3.9.i

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

A transformation of a convergent sequence $\{ s_{n}\}$ with limit $\sigma$ into a sequence $\{ t_{n}\}$ is called limit-preserving if $\{ t_{n}\}$ converges to the same limit $\sigma$ .

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

3.9.1 $\lim _{{n\to\infty}}\frac{t_{n}-\sigma}{s_{n}-\sigma}=0.$

Symbols:: $s_{n}$ : sequence, $t_{n}$ : sequence and $\sigma$ : limit
Permalink:: http://dlmf.nist.gov/3.9.E1
Encodings:: TeX, pMML, png

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

Notes:: See Knopp (1964, pp. 253–255).
Keywords:: Euler’s transformation
Referenced by:: §2.11(vi)
Permalink:: http://dlmf.nist.gov/3.9.ii

If $S=\sum _{{k=0}}^{\infty}(-1)^{k}a_{k}$ is a convergent series, then

3.9.2 $S=\sum _{{k=0}}^{\infty}(-1)^{k}2^{{-k-1}}\Delta^{k}a_{0},$

Symbols:: $\Delta$ : forward difference operator and $S$ : a convergent series
Permalink:: http://dlmf.nist.gov/3.9.E2
Encodings:: TeX, pMML, png

provided that the right-hand side converges. Here $\Delta$ is the forward difference operator:

3.9.3 $\Delta^{k}a_{0}=\Delta^{{k-1}}a_{1}-\Delta^{{k-1}}a_{0},$ $k=1,2,\ldots$ .

Symbols:: $\Delta$ : forward difference operator
A&S Ref:: 3.6.27
Permalink:: http://dlmf.nist.gov/3.9.E3
Encodings:: TeX, pMML, png

Thus

3.9.4 $\Delta^{k}a_{0}=\sum _{{m=0}}^{k}(-1)^{m}\binom{k}{m}a_{{k-m}}.$

Symbols:: $\binom{m}{n}$ : binomial coefficient and $\Delta$ : forward difference operator
A&S Ref:: 3.6.27
Permalink:: http://dlmf.nist.gov/3.9.E4
Encodings:: TeX, pMML, png

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 $\mathop{\ln\/}\nolimits 2=1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots=\frac{1}{1\cdot 2^{1}}+\frac{1}{2\cdot 2^{2}}+\frac{1}{3\cdot 2^{3}}+\cdots,$

Symbols:: $\mathop{\ln\/}\nolimits z$ : principal branch of logarithm function
Permalink:: http://dlmf.nist.gov/3.9.E5
Encodings:: TeX, pMML, png

3.9.6 $\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\cdots=\frac{1}{2}\left(1+\frac{1!}{1\cdot 3}+\frac{2!}{3\cdot 5}+\frac{3!}{3\cdot 5\cdot 7}+\cdots\right).$

Symbols:: $!$ : $n!$ : factorial
Permalink:: http://dlmf.nist.gov/3.9.E6
Encodings:: TeX, pMML, png

§3.9(iii) Aitken’s $\Delta^{2}$ -Process

Keywords:: Aitken’s $\Delta^{2}$ -process
Permalink:: http://dlmf.nist.gov/3.9.iii

3.9.7 $t_{n}=s_{n}-\frac{(\Delta s_{n})^{2}}{\Delta^{2}s_{n}}=s_{n}-\frac{(s_{{n+1}}-s_{n})^{2}}{s_{{n+2}}-2s_{{n+1}}+s_{n}}.$

Symbols:: $s_{n}$ : sequence and $t_{n}$ : sequence
A&S Ref:: 3.9.7
Permalink:: http://dlmf.nist.gov/3.9.E7
Encodings:: TeX, pMML, png

This transformation is accelerating if $\{ s_{n}\}$ is a linearly convergent sequence, i.e., a sequence for which

3.9.8 $\lim _{{n\to\infty}}\frac{s_{{n+1}}-\sigma}{s_{n}-\sigma}=\rho,$ $\left|\rho\right|<1$ .

Symbols:: $s_{n}$ : sequence
Permalink:: http://dlmf.nist.gov/3.9.E8
Encodings:: TeX, pMML, png

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

§3.9(iv) Shanks’ Transformation

Keywords:: Shanks’ transformation, Wynn’s epsilon algorithm, determinants
Permalink:: http://dlmf.nist.gov/3.9.iv

Shanks’ transformation is a generalization of Aitken’s $\Delta^{2}$ -process. Let $k$ be a fixed positive integer. Then the transformation of the sequence $\{ s_{n}\}$ into a sequence $\{ t_{{n,2k}}\}$ is given by

3.9.9 $t_{{n,2k}}=\frac{H_{{k+1}}(s_{n})}{H_{k}(\Delta^{2}s_{n})},$ $n=0,1,2,\dots$ ,

Symbols:: $s_{n}$ : sequence, $t_{n}$ : sequence and $H_{m}(u)$ : Hankel determinant
Referenced by:: §3.9(iv)
Permalink:: http://dlmf.nist.gov/3.9.E9
Encodings:: TeX, pMML, png

where $H_{m}$ is the Hankel determinant

3.9.10 $H_{m}(u_{n})=\begin{vmatrix}u_{n}&u_{{n+1}}&\cdots&u_{{n+m-1}}\\ u_{{n+1}}&u_{{n+2}}&\cdots&u_{{n+m}}\\ \vdots&\vdots&\ddots&\vdots\\ u_{{n+m-1}}&u_{{n+m}}&\cdots&u_{{n+2m-2}}\end{vmatrix}.$

Symbols:: $H_{m}(u)$ : Hankel determinant
Permalink:: http://dlmf.nist.gov/3.9.E10
Encodings:: TeX, pMML, png

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

3.9.11

$\varepsilon _{{-1}}^{{(n)}}=0,$

$\varepsilon _{0}^{{(n)}}=s_{n},$ $n=0,1,2,\dots$ ,

$\varepsilon _{{m+1}}^{{(n)}}=\varepsilon _{{m-1}}^{{(n+1)}}+\frac{1}{\varepsilon _{m}^{{(n+1)}}-\varepsilon _{m}^{{(n)}}},$ $n,m=0,1,2,\dots$ .

Symbols:: $s_{n}$ : sequence
Referenced by:: §3.11(iv)
Permalink:: http://dlmf.nist.gov/3.9.E11
Encodings:: TeX, TeX, TeX, pMML, pMML, pMML, png, png, png

Then $t_{{n,2k}}=\varepsilon _{{2k}}^{{(n)}}$ . Aitken’s $\Delta^{2}$ -process is the case $k=1$ .

If $s_{n}$ is the $n$ th partial sum of a power series $f$ , then $t_{{n,2k}}=\varepsilon _{{2k}}^{{(n)}}$ is the Padé approximant $[(n+k)/k]_{f}$ (§3.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 $t_{{n,2k}}$ are supplied for

3.9.12 $s_{n}=\sum _{{j=1}}^{n}\frac{(-1)^{{j+1}}}{j^{2}},$

Symbols:: $s_{n}$ : sequence
Permalink:: http://dlmf.nist.gov/3.9.E12
Encodings:: TeX, pMML, png

with $s_{\infty}=\frac{1}{12}\pi^{2}=0.82246\; 70334\; 24\ldots$ .

Table 3.9.1: Shanks’ transformation for $s_{n}=\sum _{{j=1}}^{n}(-1)^{{j+1}}j^{{-2}}$ .

$n$	$t_{{n,2}}$	$t_{{n,4}}$	$t_{{n,6}}$	$t_{{n,8}}$	$t_{{n,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

Symbols:: $s_{n}$ : sequence and $t_{n}$ : sequence
Referenced by:: ¶ ‣ §3.9(iv)
Permalink:: http://dlmf.nist.gov/3.9.T1

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

Keywords:: Levin’s transformations, Weniger’s transformation, convergence, iterative methods
Referenced by:: §3.5(vii)
Permalink:: http://dlmf.nist.gov/3.9.v

We give a special form of Levin’s transformation in which the sequence $s=\{ s_{n}\}$ of partial sums $s_{n}=\sum _{{j=0}}^{n}a_{j}$ is transformed into:

3.9.13 ${\cal L}_{k}^{{(n)}}(s)=\frac{\sum _{{j=0}}^{k}(-1)^{j}\binomial{k}{j}c_{{j,k,n}}\ifrac{s_{{n+j}}}{a_{{n+j+1}}}}{\sum _{{j=0}}^{k}(-1)^{j}\binomial{k}{j}c_{{j,k,n}}/a_{{n+j+1}}},$

Symbols:: $\binom{m}{n}$ : binomial coefficient, $s_{n}$ : sequence and $c_{{j,k,n}}$ : coefficient
Referenced by:: §3.9(v)
Permalink:: http://dlmf.nist.gov/3.9.E13
Encodings:: TeX, pMML, png

where $k$ is a fixed nonnegative integer, and

3.9.14 $c_{{j,k,n}}=\frac{(n+j+1)^{{k-1}}}{(n+k+1)^{{k-1}}}.$

Symbols:: $c_{{j,k,n}}$ : coefficient
Permalink:: http://dlmf.nist.gov/3.9.E14
Encodings:: TeX, pMML, png

Sequences that are accelerated by Levin’s transformation include logarithmically convergent sequences, i.e., sequences $s_{n}$ converging to $\sigma$ such that

3.9.15 $\lim _{{n\to\infty}}\frac{s_{{n+1}}-\sigma}{s_{n}-\sigma}=1.$

Symbols:: $s_{n}$ : sequence and $\sigma$ : limit
Permalink:: http://dlmf.nist.gov/3.9.E15
Encodings:: TeX, pMML, png

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

In Weniger’s transformations the numbers $c_{{j,k,n}}$ in (3.9.13) are chosen as follows:

3.9.16 $c_{{j,k,n}}=\frac{\left(\beta+n+j\right)_{{k-1}}}{\left(\beta+n+k\right)_{{k-1}}},$

Symbols:: $\left(a\right)_{{n}}$ : Pochhammer’s symbol, $c_{{j,k,n}}$ : coefficient and $\beta$ : arbitrary constant
Permalink:: http://dlmf.nist.gov/3.9.E16
Encodings:: TeX, pMML, png

3.9.17 $c_{{j,k,n}}=\frac{\left(-\gamma-n-j\right)_{{k-1}}}{\left(-\gamma-n-k\right)_{{k-1}}},$

Symbols:: $\left(a\right)_{{n}}$ : Pochhammer’s symbol, $\gamma$ : arbitrary constant and $c_{{j,k,n}}$ : coefficient
Permalink:: http://dlmf.nist.gov/3.9.E17
Encodings:: TeX, pMML, png

where $\left(a\right)_{{0}}=1$ and $\left(a\right)_{{j}}=a(a+1)\cdots(a+j-1)$ are Pochhammer symbols (§5.2(iii)), and the constants $\beta$ and $\gamma$ are chosen arbitrarily subject to certain conditions. See Weniger (1989).

§3.9(vi) Applications and Further Transformations

Keywords:: acceleration of convergence
Permalink:: http://dlmf.nist.gov/3.9.vi

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).