# §3.9 Acceleration of Convergence

## §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 $\{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 See also: Annotations for 3.9(i), 3.9 and 3

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=\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 See also: Annotations for 3.9(ii), 3.9 and 3

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 See also: Annotations for 3.9(ii), 3.9 and 3

Thus

 3.9.4 $\Delta^{k}a_{0}=\sum_{m=0}^{k}(-1)^{m}\genfrac{(}{)}{0.0pt}{}{k}{m}a_{k-m}.$ ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{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 See also: Annotations for 3.9(ii), 3.9 and 3

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 $\ln 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: $\ln\NVar{z}$: principal branch of logarithm function Permalink: http://dlmf.nist.gov/3.9.E5 Encodings: TeX, pMML, png See also: Annotations for 3.9(ii), 3.9 and 3
 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: $\pi$: the ratio of the circumference of a circle to its diameter and $!$: factorial (as in $n!$) Permalink: http://dlmf.nist.gov/3.9.E6 Encodings: TeX, pMML, png See also: Annotations for 3.9(ii), 3.9 and 3

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

 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 See also: Annotations for 3.9(iii), 3.9 and 3

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 See also: Annotations for 3.9(iii), 3.9 and 3

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

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 See also: Annotations for 3.9(iv), 3.9 and 3

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}.$ ⓘ Defines: $H_{m}(u)$: Hankel determinant (locally) Symbols: $\det$: determinant Permalink: http://dlmf.nist.gov/3.9.E10 Encodings: TeX, pMML, png See also: Annotations for 3.9(iv), 3.9 and 3

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

 3.9.11 $\displaystyle\varepsilon_{-1}^{(n)}$ $\displaystyle=0,$ $\displaystyle\varepsilon_{0}^{(n)}$ $\displaystyle=s_{n},$ $n=0,1,2,\dots$, $\displaystyle\varepsilon_{m+1}^{(n)}$ $\displaystyle=\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 See also: Annotations for 3.9(iv), 3.9 and 3

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 See also: Annotations for 3.9(iv), 3.9(iv), 3.9 and 3

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

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

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}\genfrac{(}{)}{0.0pt}{}{k}{j% }c_{j,k,n}\ifrac{s_{n+j}}{a_{n+j+1}}}{\sum_{j=0}^{k}(-1)^{j}\genfrac{(}{)}{0.0% pt}{}{k}{j}c_{j,k,n}/a_{n+j+1}},$ ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{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 See also: Annotations for 3.9(v), 3.9 and 3

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}}.$ ⓘ Defines: $c_{j,k,n}$: coefficient (locally) Permalink: http://dlmf.nist.gov/3.9.E14 Encodings: TeX, pMML, png See also: Annotations for 3.9(v), 3.9 and 3

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 See also: Annotations for 3.9(v), 3.9 and 3

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(\NVar{a}\right)_{\NVar{n}}}$: Pochhammer’s symbol (or shifted factorial), $c_{j,k,n}$: coefficient and $\beta$: arbitrary constant Permalink: http://dlmf.nist.gov/3.9.E16 Encodings: TeX, pMML, png See also: Annotations for 3.9(v), 3.9 and 3

or

 3.9.17 $c_{j,k,n}=\frac{{\left(-\gamma-n-j\right)_{k-1}}}{{\left(-\gamma-n-k\right)_{k% -1}}},$ ⓘ Symbols: ${\left(\NVar{a}\right)_{\NVar{n}}}$: Pochhammer’s symbol (or shifted factorial), $\gamma$: arbitrary constant and $c_{j,k,n}$: coefficient Permalink: http://dlmf.nist.gov/3.9.E17 Encodings: TeX, pMML, png See also: Annotations for 3.9(v), 3.9 and 3

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

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