Series acceleration


Series acceleration

In mathematics, series acceleration is one of a collection of sequence transformations for improving the rate of convergence of a series. Techniques for series acceleration are often applied in numerical analysis, where they are used to improve the speed of numerical integration. Series acceleration techniques may also be used, for example, to obtain a variety of identities on special functions. Thus, the Euler transform applied to the hypergeometric series gives some of the classic, well-known hypergeometric series identities.

Contents

Definition

Given a sequence

S=\{ s_n \}_{n\in\N}

having a limit

\lim_{n\to\infty} s_n = \ell,

an accelerated series is a second sequence

S'=\{ s'_n \}_{n\in\N}

which converges faster to \ell than the original sequence, in the sense that

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

If the original sequence is divergent, the sequence transformation acts as an extrapolation method to the antilimit \ell.

The mappings from the original to the transformed series may be linear (as defined in the article sequence transformations), or non-linear. In general, the non-linear sequence transformations tend to be more powerful.

Overview

Two classical techniques for series acceleration are Euler's transformation of series[1] and Kummer's transformation of series[2]. A variety of much more rapidly convergent and special-case tools have been developed in the 20th century, including Richardson extrapolation, introduced by Lewis Fry Richardson in the early 20th century but also known and used by Katahiro Takebe in 1722, the Aitken delta-squared process, introduced by Alexander Aitken in 1926 but also known and used by Takakazu Seki in the 18th century, the epsilon algorithm given by Peter Wynn in 1956, the Levin u-transform, and the Wilf-Zeilberger-Ekhad method or WZ method.

For alternating series, several powerful techniques, offering convergence rates from 5.828 n all the way to 17.93 n for a summation of n terms, are described by Cohen et al.. [3].

Euler's transform

A basic example of a linear sequence transformation, offering improved convergence, is Euler's transform. It is intended to be applied to an alternating series; it is given by

\sum_{n=0}^\infty (-1)^n a_n = \sum_{n=0}^\infty (-1)^n 
\frac {\Delta^n a_0} {2^{n+1}}

where Δ is the forward difference operator:

\Delta^n a_0 = \sum_{k=0}^n (-1)^k {n \choose k} a_{n-k}.

If the original series, on the left hand side, is only slowly converging, the forward differences will tend to become small quite rapidly; the additional power of two further improves the rate at which the right hand side converges.

A particularly efficient numerical implementation of the Euler transform is the van Wijngaarden transformation.[4]

Conformal mappings

A series

S = \sum_{n=0}^{\infty} a_n

can be written as f(1), where the function f(z) is defined as

f(z) = \sum_{n=0}^{\infty} a_n z^{n}

The function f(z) can have singularities in the complex plane (branch point singularities, poles or essential singularities), which limit the radius of convergence of the series. If the point z = 1 is close to or on the boundary of the disk of convergence, the series for S will converge very slowly. One can then improve the convergence of the series by means of a conformal mapping that moves the singularities such that the point that is mapped to z = 1, ends up deeper in the new disk of convergence.

The conformal transform z = Φ(w) needs to be chosen such that Φ(0) = 0, and one usually chooses a function that has a finite derivative at w = 0. One can assume that Φ(1) = 1 without loss of generality, as one can always rescale w to redefine Φ. We then consider the function

g(w)= f\left(\Phi(w)\right)

Since Φ(1) = 1, we have f(1) = g(1). We can obtain the series expansion of g(w) by putting z = Φ(w) in the series expansion of f(z) because Φ(0) = 0; the first n terms of the series expansion for f(z) will yield the first n terms of the series expansion for g(w) if \Phi'(0)\neq 0. Putting w = 1 in that series expansion will thus yield a series such that if it converges, it will converge to the same value as the original series.

Non-linear sequence transformations

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.

Aitken method

Main article: Aitken's delta-squared process

A simple nonlinear sequence transformation is the Aitken extrapolation or delta-squared method,

\mathbb{A} : S \to S'=\mathbb{A}(S) = {(s'_n)}_{n\in\N}

defined by

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

This transformation is commonly used to improve the rate of convergence of a slowly converging sequence; heuristically, it eliminates the largest part of the absolute error.

See also

References

  1. ^ Abramowitz, Milton; Stegun, Irene A., eds. (1965), "Chapter 3, eqn 3.6.27", Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, New York: Dover, pp. 16, ISBN 978-0486612720, MR0167642, http://www.math.sfu.ca/~cbm/aands/page_16.htm .
  2. ^ Abramowitz, Milton; Stegun, Irene A., eds. (1965), "Chapter 3, eqn 3.6.26", Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, New York: Dover, pp. 16, ISBN 978-0486612720, MR0167642, http://www.math.sfu.ca/~cbm/aands/page_16.htm .
  3. ^ Henri Cohen, Fernando Rodriguez Villegas, and Don Zagier, "Convergence Acceleration of Alternating Series", Experimental Mathematics, 9:1 (2000) page 3.
  4. ^ William H. Press, et al., Numerical Recipes in C, (1987) Cambridge University Press, ISBN 0-521-43108-5 (See section 5.1).

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Acceleration — Accelerate redirects here. For other uses, see Accelerate (disambiguation). Classical mechanics Newton s Second Law …   Wikipedia

  • Accélération de Coriolis — L accélération de Coriolis (nommée ainsi en l honneur du savant français Gaspard Gustave Coriolis) est un terme d accélération qui intervient lorsque l on étudie le mouvement d un corps se déplaçant dans un référentiel en rotation par rapport au… …   Wikipédia en Français

  • GeForce 6 Series — Nvidia GeForce 6 Series Codename(s) NV40, NV41, NV42, NV43, NV44, NV45, NV48 Release date April 2004 2005 Entry level GPU 6100 (IGP), 6150 (IGP), 6200, 6500 Mid range GPU 6600, 6700 …   Wikipedia

  • AMD 700 chipset series — AMD chipsets Table name = AMD 700 chipset series/ AMD 7 Series Chipsets img w = 100px Codename = Wahoo (790FX, Quad FX) Hammerhead (790FX) Seahorse (780G) CPU = Phenom series Athlon 64 series Sempron series Socket = Socket F+/F (790FX/DSDC)… …   Wikipedia

  • Skylark (series) — Skylark is a science fiction/space opera series by the late E. E. Doc Smith. The first book The Skylark of Space (first published in Amazing Stories in 1928) is revolutionary in the genre, in which a scientist discovers a space drive, builds a… …   Wikipedia

  • 400-series highways — redirects here. For other uses, see 400 series highways (disambiguation). The current 400 series Highway network in Southern Ontario. The 400 series highways are a network of controlled access freeways throughout the southern portion of the… …   Wikipedia

  • List of Simple series games — This is a list of video games in the Simple series. PlayStation Simple 1500 Series * Vol. 1: The Mahjong (developed by Chatnoir ) * Vol. 2: The Shougi (developed by Alpha Beta ) * Vol. 3: The Gomoku Narabe (developed by Itsui ) * Vol. 4: The… …   Wikipedia

  • Compact wind acceleration turbine — Compact Wind Acceleration Turbines (CWATs) are a class of wind turbine that uses structures to accelerate wind before it enters the wind generating element.[1] The concept of these structures has been around for decades [2] but has not gained… …   Wikipedia

  • 400-series highways (Ontario) — The 400 series highways are a network of controlled access freeways throughout the southern portion of the province of Ontario, Canada, forming a special subset of the provincial highway system. They function similarly to the Interstate Highway… …   Wikipedia

  • N700 Series Shinkansen — N700 series JR Central N700 series set Z28 on the Sanyō Shinkansen, April 2009 In service 2007–Present Manufacturer Hitachi, Kawasaki Heavy Industries …   Wikipedia