# Sequence transformation

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Sequence_transformation
> Markdown URL: https://mediated.wiki/source/Sequence_transformation.md
> Source: https://en.wikipedia.org/wiki/Sequence_transformation
> Source revision: 1338006700
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Mathematical operator acting on sequences}}
In [mathematics](/source/mathematics), a '''sequence transformation''' is an [operator](/source/Operator_(mathematics)) acting on a given space of [sequence](/source/sequence)s (a [sequence space](/source/sequence_space)). Sequence transformations include [linear mapping](/source/linear_mapping)s such as [discrete convolution](/source/convolution) with another sequence and [resummation](/source/resummation) of a sequence and nonlinear mappings, more generally. They are commonly used for [series acceleration](/source/series_acceleration), that is, for improving the [rate of convergence](/source/rate_of_convergence) of a slowly convergent sequence or [series](/source/series_(mathematics)). Sequence transformations are also commonly used to compute the  [antilimit](/source/antilimit) of a [divergent series](/source/divergent_series) numerically, and are used in conjunction with [extrapolation methods](/source/extrapolation_methods).

Classical examples for sequence transformations include the [binomial transform](/source/binomial_transform), [Möbius transform](/source/M%C3%B6bius_transform), and [Stirling transform](/source/Stirling_transform).

==Definitions==
For a given sequence 

:<math>(s_n)_{n\in\N},\,</math>

and a sequence transformation <math>\mathbf{T},</math> the sequence resulting from transformation by '''<math>\mathbf{T}</math>''' is 

:<math>\mathbf{T}( ( s_n ) ) = ( s'_n )_{n\in\N},</math>

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

:<math>s_n' = T_n(s_n,s_{n+1},\dots,s_{n+k_n})</math>

for some natural number <math>k_n</math> for each <math>n</math> and a [multivariate function](/source/multivariate_function) <math>T_n</math> of <math>k_n + 1</math> variables for each <math>n.</math> See for instance the [binomial transform](/source/binomial_transform) and [Aitken's delta-squared process](/source/Aitken's_delta-squared_process). In the simplest case the elements of the sequences, the <math>s_n</math> and <math>s'_n</math>, are [real](/source/real_number) or [complex number](/source/complex_number)s. More generally, they may be elements of some [vector space](/source/vector_space) or [algebra](/source/algebra_over_a_field). 

If the multivariate functions <math>T_n</math> are [linear](/source/linear_mapping) in each of their arguments for each value of <math>n,</math> for instance if

:<math>s'_n=\sum_{m=0}^{k_n} c_{n,m} s_{n+m}</math>

for some constants <math>k_n</math> and <math>c_{n,0},\dots,c_{n,k_n}</math> for each <math>n,</math> then the sequence transformation <math>\mathbf{T}</math> is called a '''linear sequence transformation'''. Sequence transformations that are not linear are called nonlinear sequence transformations.

In the context of [series acceleration](/source/series_acceleration), when the original sequence <math>(s_n)</math> and the transformed sequence <math>(s'_n)</math> share the same limit <math>\ell</math> as <math>n \rightarrow \infty,</math> the transformed sequence is said to have a faster [rate of convergence](/source/rate_of_convergence) than the original sequence if

:<math>\lim_{n\to\infty} \frac{s'_n-\ell}{s_n-\ell} = 0.</math>

If the original sequence is [divergent](/source/Divergent_sequence), the sequence transformation may act as an [extrapolation method](/source/extrapolation_method) to an [antilimit](/source/antilimit) <math>\ell</math>.

==Examples==
The simplest examples of sequence transformations include shifting all elements by an integer <math>k</math> that does not depend on <math>n,</math> <math>s'_n = s_{n+k}</math> if <math>n + k \geq 0</math> and 0 otherwise, and [scalar multiplication](/source/scalar_multiplication) of the sequence some constant <math>c</math> that does not depend on <math>n,</math> <math>s'_n = c s_{n}.</math> These are both examples of linear sequence transformations.

Less trivial examples include the [discrete convolution](/source/convolution) of sequences with another reference sequence. A particularly basic example is the [difference operator](/source/difference_operator), which is convolution with the sequence <math>(-1,1,0,\ldots)</math> and is a discrete analog of the [derivative](/source/derivative); technically the shift operator and scalar multiplication can also be written as trivial discrete convolutions. The [binomial transform](/source/binomial_transform) and the [Stirling transform](/source/Stirling_transform) are two linear transformations of a more general type.

An example of a nonlinear sequence transformation is [Aitken's delta-squared process](/source/Aitken's_delta-squared_process), used to improve the [rate of convergence](/source/rate_of_convergence) of a slowly convergent sequence. An extended form of this is the [Shanks transformation](/source/Shanks_transformation). The [Möbius transform](/source/M%C3%B6bius_transform) is also a nonlinear transformation, only possible for [integer sequence](/source/integer_sequence)s.

==See also ==
* [Aitken's delta-squared process](/source/Aitken's_delta-squared_process)
* [Anderson acceleration](/source/Anderson_acceleration)
* [Minimum polynomial extrapolation](/source/Minimum_polynomial_extrapolation)
* [Richardson extrapolation](/source/Richardson_extrapolation)
* [Series acceleration](/source/Series_acceleration)
* [Steffensen's method](/source/Steffensen's_method)

==References==
<references/>
*Hugh J. Hamilton, "[http://www.ams.org/bull/1947-53-08/S0002-9904-1947-08882-0/S0002-9904-1947-08882-0.pdf Mertens' Theorem and Sequence Transformations]", AMS (1947)

==External links==
* [http://oeis.org/transforms.html Transformations of Integer Sequences], a subpage of the [On-Line Encyclopedia of Integer Sequences](/source/On-Line_Encyclopedia_of_Integer_Sequences)

Category:Series (mathematics)
Category:Asymptotic analysis
Category:Perturbation theory

---
Adapted from the Wikipedia article [Sequence transformation](https://en.wikipedia.org/wiki/Sequence_transformation) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Sequence_transformation?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.