Sequence transformations

From Wikipedia, the free encyclopedia

This is a page about mathematics. For other usages of "sequence", see: sequence (non-mathematical).

To evaluate the limit of a slowly convergent sequence or series, or the antilimit of a divergent series numerically, one may use extrapolation methods or sequence transformations $\mathbb{T}$ :

1 Definitions
2 Application
3 Example: The Aitken method
4 References

[edit] Definitions

For a given sequence

$S=\{ s_n \}_{n\in N_0}$ ,

the transformed sequence is

$\mathbb{T}(S)=S'=\{ s'_n \}_{n\in N_0}$ ,

where the members of the transformed sequence are usually computed from some finite number of members of the original sequence, e.g., there is a mapping $T$ according to

$T : \left(s_n,s_{n+1},\dots,s_{n+k}\right) \to s'_n$

for some finite $k$ . In the simplest case, the $s n$ and the $s' n$ are real or complex numbers. More generally, they may be elements of some vector space or algebra.

The transformed sequence is said to converge faster than the original sequence if

$\lim_{n\to\infty} \frac{s'_n-s}{s_n-s} = 0$

where $s$ is the limit of $S$ assumed to be convergent. In this case, convergence acceleration is obtained. If the original sequence is divergent, the sequence transformation acts as extrapolation method to the antilimit $s$ .

If the mapping $T$ is linear in each of its arguments, i.e., for

$s'_n=\sum_{m=0}^{k} c_m s_{n+m}$

for some constants $c_0,\dots,c_k$ , the sequence transformation $\mathbb{T}$ is called a linear sequence transformation.

Sequence transformations that are not linear are called nonlinear sequence transformations.

[edit] Application

Examples of such nonlinear sequence transformations are Padé approximants and Levin-type sequence transformations.

Especially nonlinear sequence transformations often provide powerful numerical methods for the summation of divergent series or asymptotic series that arise for instance in perturbation theory, and may be used as highly effective extrapolation methods.

[edit] Example: The Aitken method

A simple nonlinear sequence transformation is the Aitken method

$\mathbb{A} : S -> S'=\mathbb{A}(S)$

defined by the mapping

$A : \left(s_n,s_{n+1},s_{n+2}\right) \to s'_n$

with

$s'_n = s_n - \frac{(s_{n+1}-s_n)^2}{s_{n+2}-2s_{n+1}+s_n}$ .

Taking the sequence of partial sums

$s_n=\sum_{k=0}^{n} q^k=\frac{1-q^{n+1}}{1-q}$

of the geometric series as untransformed sequence, we obtain for the transformed sequence by simple algebra

$s'_n=\frac{1}{1-q}$

independent of $n$ . This, however is the limit of the geometric series for

$\displaystyle |q| < 1$ .

Thus, the Aitken method yields the exact result by extrapolation of only three consecutive partial sums.

For

$\displaystyle |q| >1$ ,

the geometric series diverges since it is power series in $q$ outside its radius of convergence. But even for this divergent series, the Aitken method sums the geometric series to its analytic continuation to

$\mathbb{C}\setminus\{1\}$ ,

i.e. the complex $q$ plane punctuated at

$\displaystyle q=1$ .

The Aitken method is often used iteratively by applying it again to the transformed sequence $\displaystyle S'$ etc.:

$\displaystyle S''=\mathbb{A}(S')$

$\displaystyle S'''=\mathbb{A}(S'')$

and so on.

[edit] References

Extrapolation Methods. Theory and Practice by C. Brezinski and M. Redivo Zaglia, North-Holland, 1991.
Padé Approximants by G. A. Baker, Jr. and P. Graves-Morris, Cambridge U.P., 1996.

Retrieved from "http://en.wikipedia.org../../../s/e/q/Sequence_transformations.html"

Categories: Mathematical series | Numerical analysis | Asymptotic analysis | Perturbation theory