Series acceleration

In

gives some of the classic, well-known hypergeometric series identities.

Definition

Given a sequence

${\displaystyle S=\{s_{n}\}_{n\in \mathbb {N} }}$

having a limit

${\displaystyle \lim _{n\to \infty }s_{n}=\ell ,}$

an accelerated series is a second sequence

${\displaystyle S'=\{s'_{n}\}_{n\in \mathbb {N} }}$

which converges faster to ${\displaystyle \ell }$ than the original sequence, in the sense that

${\displaystyle \lim _{n\to \infty }{\frac {s'_{n}-\ell }{s_{n}-\ell }}=0.}$

If the original sequence is

${\displaystyle \ell }$.

The mappings from the original to the transformed series may be

), or non-linear. In general, the non-linear sequence transformations tend to be more powerful.

Overview

Two classical techniques for series acceleration are

WZ method

.

For alternating series, several powerful techniques, offering convergence rates from ${\displaystyle 5.828^{-n}}$ all the way to ${\displaystyle 17.93^{-n}}$ for a summation of ${\displaystyle n}$ terms, are described by Cohen et al.^[3]

Euler's transform

A basic example of a

, offering improved convergence, is Euler's transform. It is intended to be applied to an alternating series; it is given by

${\displaystyle \sum _{n=0}^{\infty }(-1)^{n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n}{\frac {(\Delta ^{n}a)_{0}}{2^{n+1}}}}$

where ${\displaystyle \Delta }$ is the

, for which one has the formula

${\displaystyle (\Delta ^{n}a)_{0}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}a_{n-k}.}$

If the original series, on the left hand side, is only slowly converging, the forward differences will tend to become small quite rapidly; the additional power of two further improves the rate at which the right hand side converges.

A particularly efficient numerical implementation of the Euler transform is the van Wijngaarden transformation.^[4]

Conformal mappings

A series

${\displaystyle S=\sum _{n=0}^{\infty }a_{n}}$

can be written as f(1), where the function f is defined as

${\displaystyle f(z)=\sum _{n=0}^{\infty }a_{n}z^{n}.}$

The function f(z) can have

that moves the singularities such that the point that is mapped to z = 1 ends up deeper in the new disk of convergence.

The conformal transform ${\displaystyle z=\Phi (w)}$ needs to be chosen such that ${\displaystyle \Phi (0)=0}$, and one usually chooses a function that has a finite derivative at w = 0. One can assume that ${\displaystyle \Phi (1)=1}$ without loss of generality, as one can always rescale w to redefine ${\displaystyle \Phi }$. We then consider the function

${\displaystyle g(w)=f(\Phi (w)).}$

Since ${\displaystyle \Phi (1)=1}$, we have f(1) = g(1). We can obtain the series expansion of g(w) by putting ${\displaystyle z=\Phi (w)}$ in the series expansion of f(z) because ${\displaystyle \Phi (0)=0}$; the first n terms of the series expansion for f(z) will yield the first n terms of the series expansion for g(w) if ${\displaystyle \Phi '(0)\neq 0}$. Putting w = 1 in that series expansion will thus yield a series such that if it converges, it will converge to the same value as the original series.

Non-linear sequence transformations

Examples of such nonlinear sequence transformations are Padé approximants, the Shanks transformation, and Levin-type sequence transformations.

Especially nonlinear sequence transformations often provide powerful numerical methods for the

.

Aitken method

A simple nonlinear sequence transformation is the Aitken extrapolation or delta-squared method,

${\displaystyle \mathbb {A} :S\to S'=\mathbb {A} (S)={(s'_{n})}_{n\in \mathbb {N} }}$

defined by

${\displaystyle s'_{n}=s_{n+2}-{\frac {(s_{n+2}-s_{n+1})^{2}}{s_{n+2}-2s_{n+1}+s_{n}}}.}$

This transformation is commonly used to improve the

.

See also

• Shanks transformation
• Minimum polynomial extrapolation
• Van Wijngaarden transformation

References

• C. Brezinski and M. Redivo Zaglia, Extrapolation Methods. Theory and Practice, North-Holland, 1991.
• G. A. Baker Jr. and P. Graves-Morris, Padé Approximants, Cambridge U.P., 1996.
• Weisstein, Eric W. "Convergence Improvement". MathWorld.
• Herbert H. H. Homeier: Scalar Levin-Type Sequence Transformations, Journal of Computational and Applied Mathematics, vol. 122, no. 1–2, p 81 (2000). Homeier, H. H. H. (2000). "Scalar Levin-type sequence transformations". Journal of Computational and Applied Mathematics. 122 (1–2): 81–147.
  arXiv:math/0005209
  .
• Brezinski Claude and Redivo-Zaglia Michela : "The genesis and early developments of Aitken's process, Shanks transformation, the ${\displaystyle \epsilon }$-algorithm, and related fixed point methods", Numerical Algorithms, Vol.80, No.1, (2019), pp.11-133.
• Delahaye J. P. : "Sequence Transformations", Springer-Verlag, Berlin, ISBN 978-3540152835 (1988).
• Sidi Avram : "Vector Extrapolation Methods with Applications", SIAM, ISBN 978-1-61197-495-9 (2017).
• Brezinski Claude, Redivo-Zaglia Michela and Saad Yousef : "Shanks Sequence Transformations and Anderson Acceleration", SIAM Review, Vol.60, No.3 (2018), pp.646–669. doi:10.1137/17M1120725 .
• Brezinski Claude : "Reminiscences of Peter Wynn", Numerical Algorithms, Vol.80(2019), pp.5-10.
• Brezinski Claude and Redivo-Zaglia Michela : "Extrapolation and Rational Approximation", Springer, ISBN 978-3-030-58417-7 (2020).

External links

• Convergence acceleration of series
• GNU Scientific Library, Series Acceleration
• Digital Library of Mathematical Functions