Sequence transformation

In mathematics, a sequence transformation is an operator acting on a given space of sequences. Sequence transformations include linear mappings such as convolution with another sequence, and resummation of a sequence and, more generally, are commonly used for series acceleration, that is, for improving the rate of convergence of a slowly convergent sequence or series. Sequence transformations are also commonly used to compute the antilimit of a divergent series numerically, and are used in conjunction with extrapolation methods.

Overview

Classical examples for sequence transformations include the binomial transform, Möbius transform, Stirling transform and others.

An important part of this article is about techniques for series acceleration, which are often applied in numerical analysis, where they are used to improve the speed of numerical integration. Series acceleration techniques may also be used, for example, to obtain a variety of identities on special functions. Thus, the Euler transform applied to the hypergeometric series gives some of the classic, well-known hypergeometric series identities.

Two classical techniques for series acceleration are Euler's transformation of series and Kummer's transformation of series. A variety of much more rapidly convergent and special-case tools have been developed in the 20th century, including Richardson extrapolation, introduced by Lewis Fry Richardson in the early 20th century but also known and used by Hirotaka Takebe in 1722, the Aitken delta-squared process, introduced by Alexander Aitken in 1926 but also known and used by Takakazu Seki in the 18th century, the e-algorithm given by Peter Wynn in 1956, the Levin u-transform, and the Wilf-Zeilberger-Ekhad method or WZ method.

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

Definitions

For a given sequence

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

the transformed sequence is

$\mathbf {T} (S)=S'=\{s'_{n}\}_{n\in \mathbb {N} }$,

where the members of the transformed sequence are usually computed from some finite number of members of the original sequence, i.e.

$s_{n}'=T(s_{n},s_{n+1},\dots ,s_{n+k})$

for some $k$ which often depends on $n$ (cf. e.g. Binomial transform). In the simplest case, the $s_{n}$ and the $s'_{n}$ are real or complex numbers. More generally, they may be elements of some vector space or algebra.

In the context of acceleration of convergence, the transformed sequence is said to converge faster than the original sequence if

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

where $\ell$ is the limit of $S$, assumed to be convergent. In this case, convergence acceleration is obtained. If the original sequence is divergent, the sequence transformation acts as extrapolation method to the antilimit $\ell$.

If the mapping $T$ is linear in each of its arguments, i.e., for

$s'_{n}=\sum _{m=0}^{k}c_{m}s_{n+m}$

for some constants $c_{0},\dots ,c_{k}$, the sequence transformation $\mathbb {T}$ is called a linear sequence transformation. Sequence transformations that are not linear are called nonlinear sequence transformations.

Application

Examples of such nonlinear sequence transformations are Padé approximants and Levin-type sequence transformations.

Especially nonlinear sequence transformations often provide powerful numerical methods for the summation of divergent series or asymptotic series that arise for instance in perturbation theory, and may be used as highly effective extrapolation methods.

Aitken method

Main article: Aitken's delta-squared process

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

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

defined by

$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 rate of convergence of a slowly converging sequence; heuristically, it eliminates the largest part of the absolute error.

Minimum polynomial extrapolation

While Aitken's method is the most famous, it often fails for vector sequences. An effective method for vector sequences is the Minimum Polynomial Extrapolation. It is usually phrased in terms of the fixed point iteration:

$x_{k+1}=f(x_{k}).$

Given iterates $x_{1},x_{2},...,x_{k}$ in ${\mathbb {R}}^{n}$, one constructs the $n\times (k-1)$ matrix $U=(x_{2}-x_{1},x_{3}-x_{2},...,x_{k}-x_{k-1})$ whose columns are the $k-1$ differences. Then, one computes the vector $c=U^{+}(x_{k+1}-x_{k})$ where $U^{+}$ denotes the Moore-Penrose Pseudoinverse of $U$. The number 1 is then appended to the end of $c$, and the extrapolated limit is

$s={Xc \over \sum _{i=1}^{k}c_{i}},$

where $X=(x_{2},x_{3},...,x_{k+1})$ is the matrix whose columns are the $k$ iterates starting at 2.

The following 4 line MATLAB code segment implements the MPE algorithm:

U=x(:,2:end-1)-x(:,1:end-2);
c=-pinv(U)*(x(:,end)-x(:,end-1));
c(end+1,1)=1;
s=(x(:,2:end)*c)/sum(c);

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.

External links

• MERTENS' THEOREM AND SEQUENCE TRANSFORMATIONS