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.

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

Definitions

For a given sequence

${\displaystyle (s_{n})_{n\in \mathbb {N} },\,}$

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

${\displaystyle \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

${\displaystyle s_{n}'=T_{n}(s_{n},s_{n+1},\dots ,s_{n+k_{n}})}$

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

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

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

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

${\displaystyle \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 ${\displaystyle \ell }$.

Examples

The simplest examples of sequence transformations include shifting all elements by an integer ${\displaystyle k}$ that does not depend on ${\displaystyle n,}$${\displaystyle s'_{n}=s_{n+k}}$ if ${\displaystyle n+k\geq 0}$ and 0 otherwise, and scalar multiplication of the sequence some constant ${\displaystyle c}$ that does not depend on ${\displaystyle n,}$${\displaystyle 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 ${\displaystyle (-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 and the Stirling transform are two linear transformations 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