• Source: 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



      )

      n
      ∈

      N



      ,



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


      and a sequence transformation




      T

      ,


      {\displaystyle \mathbf {T} ,}

      the sequence resulting from transformation by




      T



      {\displaystyle \mathbf {T} }

      is





      T

      (
      (

      s

      n


      )
      )
      =
      (

      s

      n

      ′


      )

      n
      ∈

      N



      ,


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





      s

      n

      ′

      =

      T

      n


      (

      s

      n


      ,

      s

      n
      +
      1


      ,
      …
      ,

      s

      n
      +

      k

      n




      )


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


      for some natural number




      k

      n




      {\displaystyle k_{n}}

      for each



      n


      {\displaystyle n}

      and a multivariate function




      T

      n




      {\displaystyle T_{n}}

      of




      k

      n


      +
      1


      {\displaystyle k_{n}+1}

      variables for each



      n
      .


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




      {\displaystyle s_{n}}

      and




      s

      n

      ′



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




      {\displaystyle T_{n}}

      are linear in each of their arguments for each value of



      n
      ,


      {\displaystyle n,}

      for instance if





      s

      n

      ′

      =

      ∑

      m
      =
      0



      k

      n





      c

      n
      ,
      m



      s

      n
      +
      m




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


      for some constants




      k

      n




      {\displaystyle k_{n}}

      and




      c

      n
      ,
      0


      ,
      …
      ,

      c

      n
      ,

      k

      n






      {\displaystyle c_{n,0},\dots ,c_{n,k_{n}}}

      for each



      n
      ,


      {\displaystyle n,}

      then the sequence transformation




      T



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



      (

      s

      n


      )


      {\displaystyle (s_{n})}

      and the transformed sequence



      (

      s

      n

      ′

      )


      {\displaystyle (s'_{n})}

      share the same limit



      ℓ


      {\displaystyle \ell }

      as



      n
      →
      ∞
      ,


      {\displaystyle n\rightarrow \infty ,}

      the transformed sequence is said to have a faster rate of convergence than the original sequence if





      lim

      n
      →
      ∞






      s

      n

      ′

      −
      ℓ



      s

      n


      −
      ℓ



      =
      0.


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



      k


      {\displaystyle k}

      that does not depend on



      n
      ,


      {\displaystyle n,}






      s

      n

      ′

      =

      s

      n
      +
      k




      {\displaystyle s'_{n}=s_{n+k}}

      if



      n
      +
      k
      ≥
      0


      {\displaystyle n+k\geq 0}

      and 0 otherwise, and scalar multiplication of the sequence some constant



      c


      {\displaystyle c}

      that does not depend on



      n
      ,


      {\displaystyle n,}






      s

      n

      ′

      =
      c

      s

      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



      (
      −
      1
      ,
      1
      ,
      0
      ,
      …
      )


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

    Kata Kunci Pencarian: