# §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.$

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

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}{\left({{k}\atop{m}}\right)}a_{k-m}.$ Symbols: ${\left({{m}\atop{n}}\right)}$: 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: $!$: factorial (as in $n!$) Permalink: http://dlmf.nist.gov/3.9.E6 Encodings: TeX, pMML, png

## §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

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

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}.$ Defines: $H_{m}(u)$: Hankel determinant (locally) Symbols: $\det$: 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 $\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

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

## §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}{\left({{k}\atop{j}}\right)}% c_{j,k,n}\ifrac{s_{n+j}}{a_{n+j+1}}}{\sum_{j=0}^{k}(-1)^{j}{\left({{k}\atop{j}% }\right)}c_{j,k,n}/a_{n+j+1}},$ Symbols: ${\left({{m}\atop{n}}\right)}$: 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}}.$ Defines: $c_{j,k,n}$: coefficient (locally) 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}},$

or

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

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