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

:$(s_n)_,\,$

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

:$\mathbf( ( s_n ) ) = ( s'_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_,\dots,s_)$

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_^ c_ s_$

for some constants $k_n$ and $c_,\dots,c_$ for each $n,$ then the sequence transformation $\mathbf$ 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_ \frac = 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_$ 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 = c s_{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 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

a subpage of the On-Line Encyclopedia of Integer Sequences

Series (mathematics)
Asymptotic analysis
Perturbation theory