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.

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.

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

• Hugh J. Hamilton, "Mertens' Theorem and Sequence Transformations", AMS (1947)