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 discrete convolution with another sequence and resummation of a sequence and nonlinear mappings, more generally. They 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_{n})_{n\in \mathbb {N} },\,$

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

$\mathbf {T} ((s_{n}))=(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_{n}(s_{n},s_{n+1},\dots ,s_{n+k_{n}})$

for some natural number $k_{n}$ for each $n$ and a multivariate function $T_{n}$ of $k_{n}+1$ variables for each $n.$ See for instance the binomial transform and Aitken's delta-squared process. In the simplest case the elements of the sequences, the $s_{n}$ and $s'_{n}$, are real or complex numbers. More generally, they may be elements of some vector space or algebra.

If the multivariate functions $T_{n}$ are linear in each of their arguments for each value of $n,$ for instance if

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

for some constants $k_{n}$ and $c_{n,0},\dots ,c_{n,k_{n}}$ for each $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 series acceleration, when the original sequence $(s_{n})$ and the transformed sequence $(s'_{n})$ share the same limit $\ell$ as $n\rightarrow \infty ,$ the transformed sequence is said to have a faster rate of convergence than the original sequence if

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

If the original sequence is divergent, the sequence transformation may act as an extrapolation method to an antilimit $\ell$.

Examples

The simplest examples of sequence transformations include shifting all elements by an integer $k$ that does not depend on $n,$ $s'_{n}=s_{n+k}$ if $n+k\geq 0$ and 0 otherwise, and scalar multiplication of the sequence some constant $c$ that does not depend on $n,$ $s'_{n}=cs_{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; technically the shift operator and scalar multiplication can also be written as trivial discrete convolutions. 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