# Series acceleration

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

{{Short description|Mathematical technique for improving convergence}}
In [mathematics](/source/mathematics), a '''series acceleration''' method is any one of a collection of [sequence transformation](/source/sequence_transformation)s for improving the [rate of convergence](/source/rate_of_convergence) of a [series](/source/series_(mathematics)). Techniques for series acceleration are often applied in [numerical analysis](/source/numerical_analysis), where they are used to improve the speed of [numerical integration](/source/numerical_integration). Series acceleration techniques may also be used, for example, to obtain a variety of identities on [special functions](/source/special_functions). Thus, the [Euler transform](/source/Euler_transform) applied to the [hypergeometric series](/source/hypergeometric_series) gives some of the classic, well-known hypergeometric series identities.

== Definition ==
Given an infinite [series](/source/Series_(mathematics)) with a [sequence](/source/sequence) of partial sums

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

having a [limit](/source/limit_of_a_sequence)

:<math>\lim_{n\to\infty} S_n = S,</math>

an accelerated series is an infinite series with a second sequence of partial sums

:<math>( S'_n )_{n\in\N}</math>

which [asymptotically](/source/Asymptotic_analysis) [converges faster](/source/Rate_of_convergence) to <math>S</math> than the original sequence of partial sums would:

:<math>\lim_{n\to\infty} \frac{S'_n-S}{S_n-S} = 0.</math>

A series acceleration method is a [sequence transformation](/source/sequence_transformation) that transforms the convergent sequences of partial sums of a series into more quickly convergent sequences of partial sums of an accelerated series with the same limit. If a series acceleration method is applied to a [divergent series](/source/divergent_series) then the proper limit of the series is undefined, but the sequence transformation can still act usefully as an [extrapolation method](/source/extrapolation_method) to an [antilimit](/source/antilimit) of the series.

The mappings from the original to the transformed series may be linear sequence transformations or non-linear sequence transformations. 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](/source/Euler's_transformation_of_series)<ref>{{AS ref|3, eqn 3.6.27|16}}</ref> and [Kummer's transformation of series](/source/Kummer's_transformation_of_series).<ref>{{AS ref|3, eqn 3.6.26|16}}</ref> A variety of much more rapidly convergent and special-case tools have been developed in the 20th century, including [Richardson extrapolation](/source/Richardson_extrapolation), introduced by [Lewis Fry Richardson](/source/Lewis_Fry_Richardson) in the early 20th century but also known and used by [Katahiro Takebe](/source/Takebe_Kenko) in 1722; the [Aitken delta-squared process](/source/Aitken_delta-squared_process), introduced by [Alexander Aitken](/source/Alexander_Aitken) in 1926 but also known and used by [Takakazu Seki](/source/Takakazu_Seki) in the 18th century; the [http://mathworld.wolfram.com/WynnsEpsilonMethod.html epsilon method] given by [Peter Wynn](/source/Peter_Wynn_(mathematician)) in 1956; the Levin u-transform; and the Wilf-Zeilberger-Ekhad method or [WZ method](/source/WZ_theory).

For [alternating series](/source/alternating_series), several powerful techniques, offering convergence rates  from <math>5.828^{-n}</math> all the way to <math>17.93^{-n}</math> for a summation of <math>n</math> terms, are described by Cohen ''et al''.<ref>[Henri Cohen](/source/Henri_Cohen_(number_theorist)), Fernando Rodriguez Villegas, and [Don Zagier](/source/Don_Zagier),
"[http://people.mpim-bonn.mpg.de/zagier/files/exp-math-9/fulltext.pdf Convergence Acceleration of Alternating Series]", ''Experimental Mathematics'', '''9''':1 (2000) page 3.</ref>

==Euler's transform==
A basic example of a [linear sequence transformation](/source/linear_sequence_transformation), offering improved convergence, is Euler's transform. It is intended to be applied to an alternating series; it is given by

:<math>\sum_{n=0}^\infty (-1)^n a_n = \sum_{n=0}^\infty (-1)^n \frac{(\Delta^n a)_0}{2^{n+1}}</math>

where <math>\Delta</math> is the [forward difference operator](/source/forward_difference_operator), for which one has the formula

:<math>(\Delta^n a)_0 = \sum_{k=0}^n (-1)^k {n \choose k} a_{n-k}.</math>

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](/source/van_Wijngaarden_transformation).<ref>William H. Press, ''et al.'', ''Numerical Recipes in C'', (1987) Cambridge University Press, {{isbn|0-521-43108-5}} (See section 5.1).</ref>

==Conformal mappings==
A series

:<math>S = \sum_{n=0}^{\infty} a_n</math>

can be written as <math>f(1)</math>, where the [function](/source/function_(mathematics)) ''f'' is defined as

:<math>f(z) = \sum_{n=0}^{\infty} a_n z^n.</math>

The function <math>f(z)</math> can have [singularities](/source/Singularity_(mathematics)) in the [complex plane](/source/complex_plane) ([branch point](/source/branch_point) singularities, [poles](/source/pole_(complex_analysis)) or [essential singularities](/source/essential_singularity)), which limit the [radius of convergence](/source/radius_of_convergence) of the series. If the point <math>z = 1</math> is close to or on the boundary of the disk of convergence, the series for <math>S</math> will converge very slowly. One can then improve the convergence of the series by means of a [conformal mapping](/source/conformal_mapping) that moves the singularities such that the point that is mapped to <math>z = 1</math> ends up deeper in the new disk of convergence.

The conformal transform <math>z = \Phi(w)</math> needs to be chosen such that <math>\Phi(0) = 0</math>, and one usually chooses a function that has a finite [derivative](/source/derivative) at ''w'' = 0. One can assume that <math>\Phi(1) = 1</math> without loss of generality, as one can always rescale ''w'' to redefine <math>\Phi</math>. We then consider the function

:<math>g(w) = f(\Phi(w)).</math>

Since <math>\Phi(1) = 1</math>, we have <math>f(1) = g(1)</math>. We can obtain the series expansion of <math>g(w)</math> by putting <math>z = \Phi(w)</math> in the series expansion of <math>f(z)</math> because <math>\Phi(0)=0</math>; the first <math>n</math> terms of the series expansion for <math>f(z)</math> will yield the first <math>n</math> terms of the series expansion for <math>g(w)</math> if <math>\Phi'(0) \neq 0</math>. Putting <math>w = 1</math> 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é approximant](/source/Pad%C3%A9_approximant)s, the [Shanks transformation](/source/Shanks_transformation), and [Levin-type sequence transformations](/source/Levin-type_sequence_transformations).

Especially nonlinear sequence transformations often provide powerful numerical methods for the [summation](/source/summation) of [divergent series](/source/divergent_series) or [asymptotic series](/source/asymptotic_series) that arise for instance in [perturbation theory](/source/perturbation_theory), and therefore may be used as effective [extrapolation method](/source/extrapolation_method)s.

===Aitken method===
{{main|Aitken's delta-squared process}}
A simple nonlinear sequence transformation is the Aitken extrapolation or delta-squared method,

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

defined by

:<math>s'_n = s_{n+2} - \frac{(s_{n+2}-s_{n+1})^2}{s_{n+2}-2s_{n+1}+s_n}.</math>

This transformation is commonly used to improve the [rate of convergence](/source/rate_of_convergence) of a slowly converging sequence; heuristically, it eliminates the largest part of the [absolute error](/source/absolute_error).

== See also ==
* [Shanks transformation](/source/Shanks_transformation)
* [Minimum polynomial extrapolation](/source/Minimum_polynomial_extrapolation)
* [Van Wijngaarden transformation](/source/Van_Wijngaarden_transformation)

==References==
<references/>
* C. Brezinski and [M. Redivo Zaglia](/source/Michela_Redivo-Zaglia), ''Extrapolation Methods. Theory and Practice'', North-Holland, 1991.
* G. A. Baker Jr. and P. Graves-Morris, ''Padé  Approximants'', Cambridge U.P., 1996.
* {{mathworld|urlname=ConvergenceImprovement|title=Convergence Improvement}}
* Herbert H. H. Homeier: ''Scalar Levin-Type Sequence Transformations'', Journal of Computational and Applied Mathematics, vol. 122, no. 1–2, p 81 (2000). {{Cite journal | last1 = Homeier | first1 = H. H. H. | doi = 10.1016/S0377-0427(00)00359-9 | title = Scalar Levin-type sequence transformations | journal = Journal of Computational and Applied Mathematics | volume = 122 | pages = 81–147 | year = 2000 | issue = 1–2 | arxiv = math/0005209 | bibcode = 2000JCoAM.122...81H }}, {{arxiv|math/0005209}}.
* Brezinski Claude and Redivo-Zaglia Michela : "The genesis and early developments of Aitken's process, Shanks transformation, the <math>\epsilon</math>-algorithm, and related fixed point methods", Numerical Algorithms, Vol.80, No.1, (2019), pp.11-133.
* Delahaye J. P. : "Sequence Transformations", Springer-Verlag, Berlin, ISBN 978-3540152835 (1988).
* Sidi Avram : "Vector Extrapolation Methods with Applications", SIAM, ISBN 978-1-61197-495-9 (2017).
* Brezinski Claude, Redivo-Zaglia Michela and Saad Yousef : "Shanks Sequence Transformations and Anderson Acceleration", SIAM Review, Vol.60, No.3 (2018), pp.646–669. doi:10.1137/17M1120725 .
* Brezinski Claude : "Reminiscences of [Peter Wynn](/source/%3Aen%3APeter_Wynn_(mathematician))", Numerical Algorithms, Vol.80(2019), pp.5-10. 
* Brezinski Claude and Redivo-Zaglia Michela : "Extrapolation and Rational Approximation", Springer, ISBN 978-3-030-58417-7 (2020).

==External links==
* [http://numbers.computation.free.fr/Constants/Miscellaneous/seriesacceleration.html Convergence acceleration of series]
* [https://www.gnu.org/software/gsl/manual/html_node/Series-Acceleration.html GNU Scientific Library, Series Acceleration]
* [http://dlmf.nist.gov/3.9 Digital Library of Mathematical Functions]

Category:Numerical analysis
Category:Asymptotic analysis
Category:Summability methods
Category:Perturbation theory
Category:Series acceleration methods

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