Sequence transformation

In mathematics, a sequence transformation is an operator acting on a given space of sequences (a sequence space). 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, and Stirling transform.

Definitions

For a given sequence

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

and a sequence transformation $\mathbf {T} ,$ the sequence transformed by $\mathbf {T}$ is

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

where the elements of the transformed sequence are usually computed from some finite number of members of the original sequence, for instance

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

for some natural number $k,$ which may itself depend on $n,$ and a multivariate function $T$ of $k+1$ variables, which may also depend on $n.$ See for instance the 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.

If the multivariate function $T$ is linear in each of its arguments, for instance if

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

for some constants $k$ and $c_{0},\dots ,c_{k}$ that may depend on n, then the sequence transformation $\mathbf {T}$ is called a linear sequence transformation. Sequence transformations that are not linear are called nonlinear sequence transformations.

In the context of acceleration of convergence, the transformed sequence is said to converge asymptotically 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$.

Examples

The simplest examples of sequence transformations include shifting all elements, $s'_{n}=s_{n+k}$ if $n+k\geq 0$ and 0 otherwise for an integer k that does not depend on n, and scalar multiplication of the sequence, $s'_{n}=cs_{n}$ for some constant $c$ that does not depend on $n.$ These are both examples of linear sequence transformations.

Less trivial examples include the discrete convolution of sequences with another reference sequence. A particularly basic example is the difference operator, which is convolution with the sequence $(-1,1,0,\ldots )$ and is a discrete analog of the derivative. The binomial transform is another linear transformation of a more general type.

An example of a nonlinear sequence transformation is Aitken's delta-squared process, used to improve the rate of convergence of a slowly convergent sequence. An extended form of this is the Shanks transformation. The Möbius transform is also a nonlinear transformation, only possible for integer sequences.

See also

• Aitken's delta-squared process
• Minimum polynomial extrapolation
• Richardson extrapolation
• Series acceleration
• Steffensen's method

References

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

External links

• Transformations of Integer Sequences, a subpage of the On-Line Encyclopedia of Integer Sequences