Series acceleration

<h2 id="definition">Definition</h2>
<p>Given an infinite <a href="/facts/Series_(mathematics)/yDnlsgIe">series</a> with a <a href="/facts/Sequence/gV2S4uqp">sequence</a> of partial sums
</p>

(
        
          S
          
            n
          
        
        
          )
          
            n
            ∈
            
              N
            
          
        
      
    
    {\displaystyle (S_{n})_{n\in \mathbb {N} }}

<p>having a <a href="/facts/Limit_of_a_sequence/Ktge2RwL">limit</a>
</p>

lim
          
            n
            →
            ∞
          
        
        
          S
          
            n
          
        
        =
        S
        ,
      
    
    {\displaystyle \lim _{n\to \infty }S_{n}=S,}

<p>an accelerated series is an infinite series with a second sequence of partial sums
</p>

(
        
          S
          
            n
          
          ′
        
        
          )
          
            n
            ∈
            
              N
            
          
        
      
    
    {\displaystyle (S'_{n})_{n\in \mathbb {N} }}

<p>which <a href="/facts/Asymptotic_analysis/kt87qLpu">asymptotically</a> <a href="/facts/Rate_of_convergence/JVGuzPoS">converges faster</a> to 
  
    
      
        S
      
    
    {\displaystyle S}
  
 than the original sequence of partial sums would:
</p>

lim
          
            n
            →
            ∞
          
        
        
          
            
              
                S
                
                  n
                
                ′
              
              −
              S
            
            
              
                S
                
                  n
                
              
              −
              S
            
          
        
        =
        0.
      
    
    {\displaystyle \lim _{n\to \infty }{\frac {S'_{n}-S}{S_{n}-S}}=0.}

<p>A series acceleration method is a <a href="/facts/Sequence_transformation/42yK8Id0">sequence transformation</a> 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 <a href="/facts/Divergent_series/c8Vjjjdx">divergent series</a> then the proper limit of the series is undefined, but the sequence transformation can still act usefully as an <a href="/facts/Extrapolation_method/wggUrqjF">extrapolation method</a> to an <a href="/facts/Antilimit/pt0xS3Yb">antilimit</a> of the series.
</p><p>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.
</p>
<h2 id="overview">Overview</h2>
<p>Two classical techniques for series acceleration are <a href="/facts/Euler%2527s_transformation_of_series/Wu345jgq">Euler's transformation of series</a><a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> and <a href="/facts/Kummer%2527s_transformation_of_series/3fQUXxFS">Kummer's transformation of series</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> A variety of much more rapidly convergent and special-case tools have been developed in the 20th century, including <a href="/facts/Richardson_extrapolation/46hdzKDA">Richardson extrapolation</a>, introduced by <a href="/facts/Lewis_Fry_Richardson/kKQR6lFu">Lewis Fry Richardson</a> in the early 20th century but also known and used by <a href="/facts/Takebe_Kenko/8LUodDfG">Katahiro Takebe</a> in 1722; the <a href="/facts/Aitken_delta-squared_process/Pxz8bNem">Aitken delta-squared process</a>, introduced by <a href="/facts/Alexander_Aitken/UbhEranD">Alexander Aitken</a> in 1926 but also known and used by <a href="/facts/Takakazu_Seki/pLD8pLIM">Takakazu Seki</a> in the 18th century; the <a href="http://mathworld.wolfram.com/WynnsEpsilonMethod.html">epsilon method</a> given by <a href="/facts/Peter_Wynn_(mathematician)/1tWmX59w">Peter Wynn</a> in 1956; the Levin u-transform; and the Wilf-Zeilberger-Ekhad method or <a href="/facts/WZ_theory/QyjCrezt">WZ method</a>.
</p><p>For <a href="/facts/Alternating_series/wXpYnQ8b">alternating series</a>, several powerful techniques, offering convergence rates  from 
  
    
      
        
          5.828
          
            −
            n
          
        
      
    
    {\displaystyle 5.828^{-n}}
  
 all the way to 
  
    
      
        
          17.93
          
            −
            n
          
        
      
    
    {\displaystyle 17.93^{-n}}
  
 for a summation of 
  
    
      
        n
      
    
    {\displaystyle n}
  
 terms, are described by Cohen <i>et al</i>.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<h2 id="eulers-transform">Euler's transform</h2>
<p>A basic example of a <a href="/facts/Linear_sequence_transformation/42yK8Id0">linear sequence transformation</a>, offering improved convergence, is Euler's transform. It is intended to be applied to an alternating series; it is given by
</p>

∑
          
            n
            =
            0
          
          
            ∞
          
        
        (
        −
        1
        
          )
          
            n
          
        
        
          a
          
            n
          
        
        =
        
          ∑
          
            n
            =
            0
          
          
            ∞
          
        
        (
        −
        1
        
          )
          
            n
          
        
        
          
            
              (
              
                Δ
                
                  n
                
              
              a
              
                )
                
                  0
                
              
            
            
              2
              
                n
                +
                1
              
            
          
        
      
    
    {\displaystyle \sum _{n=0}^{\infty }(-1)^{n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n}{\frac {(\Delta ^{n}a)_{0}}{2^{n+1}}}}

<p>where 
  
    
      
        Δ
      
    
    {\displaystyle \Delta }
  
 is the <a href="/facts/Forward_difference_operator/aY1txFhj">forward difference operator</a>, for which one has the formula
</p>

(
        
          Δ
          
            n
          
        
        a
        
          )
          
            0
          
        
        =
        
          ∑
          
            k
            =
            0
          
          
            n
          
        
        (
        −
        1
        
          )
          
            k
          
        
        
          
            
              (
            
            
              n
              k
            
            
              )
            
          
        
        
          a
          
            n
            −
            k
          
        
        .
      
    
    {\displaystyle (\Delta ^{n}a)_{0}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}a_{n-k}.}

<p>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.
</p><p>A particularly efficient numerical implementation of the Euler transform is the <a href="/facts/Van_Wijngaarden_transformation/FvgBRoTl">van Wijngaarden transformation</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
<h2 id="conformal-mappings">Conformal mappings</h2>
<p>A series
</p>

S
        =
        
          ∑
          
            n
            =
            0
          
          
            ∞
          
        
        
          a
          
            n
          
        
      
    
    {\displaystyle S=\sum _{n=0}^{\infty }a_{n}}

<p>can be written as 
  
    
      
        f
        (
        1
        )
      
    
    {\displaystyle f(1)}
  
, where the <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> <i>f</i> is defined as
</p>

f
        (
        z
        )
        =
        
          ∑
          
            n
            =
            0
          
          
            ∞
          
        
        
          a
          
            n
          
        
        
          z
          
            n
          
        
        .
      
    
    {\displaystyle f(z)=\sum _{n=0}^{\infty }a_{n}z^{n}.}

<p>The function 
  
    
      
        f
        (
        z
        )
      
    
    {\displaystyle f(z)}
  
 can have <a href="/facts/Singularity_(mathematics)/Y5sMQY4I">singularities</a> in the <a href="/facts/Complex_plane/vE0QrxJp">complex plane</a> (<a href="/facts/Branch_point/lJ7Y6Iht">branch point</a> singularities, <a href="/facts/Pole_(complex_analysis)/gnA3U8VP">poles</a> or <a href="/facts/Essential_singularity/KMb1R292">essential singularities</a>), which limit the <a href="/facts/Radius_of_convergence/4Un0ANfP">radius of convergence</a> of the series. If the point 
  
    
      
        z
        =
        1
      
    
    {\displaystyle z=1}
  
 is close to or on the boundary of the disk of convergence, the series for 
  
    
      
        S
      
    
    {\displaystyle S}
  
 will converge very slowly. One can then improve the convergence of the series by means of a <a href="/facts/Conformal_mapping/cEpQnMad">conformal mapping</a> that moves the singularities such that the point that is mapped to 
  
    
      
        z
        =
        1
      
    
    {\displaystyle z=1}
  
ends up deeper in the new disk of convergence.
</p><p>The conformal transform 
  
    
      
        z
        =
        Φ
        (
        w
        )
      
    
    {\displaystyle z=\Phi (w)}
  
 needs to be chosen such that 
  
    
      
        Φ
        (
        0
        )
        =
        0
      
    
    {\displaystyle \Phi (0)=0}
  
, and one usually chooses a function that has a finite <a href="/facts/Derivative/7Ito70Dh">derivative</a> at <i>w</i> = 0. One can assume that 
  
    
      
        Φ
        (
        1
        )
        =
        1
      
    
    {\displaystyle \Phi (1)=1}
  
 without loss of generality, as one can always rescale <i>w</i> to redefine 
  
    
      
        Φ
      
    
    {\displaystyle \Phi }
  
. We then consider the function
</p>

g
        (
        w
        )
        =
        f
        (
        Φ
        (
        w
        )
        )
        .
      
    
    {\displaystyle g(w)=f(\Phi (w)).}

<p>Since 
  
    
      
        Φ
        (
        1
        )
        =
        1
      
    
    {\displaystyle \Phi (1)=1}
  
, we have 
  
    
      
        f
        (
        1
        )
        =
        g
        (
        1
        )
      
    
    {\displaystyle f(1)=g(1)}
  
. We can obtain the series expansion of 
  
    
      
        g
        (
        w
        )
      
    
    {\displaystyle g(w)}
  
 by putting 
  
    
      
        z
        =
        Φ
        (
        w
        )
      
    
    {\displaystyle z=\Phi (w)}
  
 in the series expansion of 
  
    
      
        f
        (
        z
        )
      
    
    {\displaystyle f(z)}
  
 because 
  
    
      
        Φ
        (
        0
        )
        =
        0
      
    
    {\displaystyle \Phi (0)=0}
  
; the first 
  
    
      
        n
      
    
    {\displaystyle n}
  
 terms of the series expansion for 
  
    
      
        f
        (
        z
        )
      
    
    {\displaystyle f(z)}
  
 will yield the first 
  
    
      
        n
      
    
    {\displaystyle n}
  
 terms of the series expansion for 
  
    
      
        g
        (
        w
        )
      
    
    {\displaystyle g(w)}
  
 if 
  
    
      
        
          Φ
          ′
        
        (
        0
        )
        ≠
        0
      
    
    {\displaystyle \Phi '(0)\neq 0}
  
. Putting 
  
    
      
        w
        =
        1
      
    
    {\displaystyle 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.
</p>
<h2 id="non-linear-sequence-transformations">Non-linear sequence transformations</h2>
<p>Examples of such nonlinear sequence transformations are <a href="/facts/Pad%25C3%25A9_approximant/cR5BjAb8">Padé approximants</a>, the <a href="/facts/Shanks_transformation/RAS4mDuo">Shanks transformation</a>, and Levin-type sequence transformations.
</p><p>Especially nonlinear sequence transformations often provide powerful numerical methods for the <a href="/facts/Summation/V2WUxoKn">summation</a> of <a href="/facts/Divergent_series/c8Vjjjdx">divergent series</a> or <a href="/facts/Asymptotic_series/4W79BNve">asymptotic series</a> that arise for instance in <a href="/facts/Perturbation_theory/JWrNgbVm">perturbation theory</a>, and therefore may be used as effective <a href="/facts/Extrapolation_method/wggUrqjF">extrapolation methods</a>.
</p>
<h3>Aitken method</h3>
<p class="note">Main article: <a href="/facts/Aitken%2527s_delta-squared_process/Pxz8bNem">Aitken's delta-squared process</a></p>
<p>A simple nonlinear sequence transformation is the Aitken extrapolation or delta-squared method,
</p>

A
        
        :
        S
        →
        
          S
          ′
        
        =
        
          A
        
        (
        S
        )
        =
        
          
            (
            
              s
              
                n
              
              ′
            
            )
          
          
            n
            ∈
            
              N
            
          
        
      
    
    {\displaystyle \mathbb {A} :S\to S'=\mathbb {A} (S)={(s'_{n})}_{n\in \mathbb {N} }}

<p>defined by
</p>

s
          
            n
          
          ′
        
        =
        
          s
          
            n
            +
            2
          
        
        −
        
          
            
              (
              
                s
                
                  n
                  +
                  2
                
              
              −
              
                s
                
                  n
                  +
                  1
                
              
              
                )
                
                  2
                
              
            
            
              
                s
                
                  n
                  +
                  2
                
              
              −
              2
              
                s
                
                  n
                  +
                  1
                
              
              +
              
                s
                
                  n
                
              
            
          
        
        .
      
    
    {\displaystyle s'_{n}=s_{n+2}-{\frac {(s_{n+2}-s_{n+1})^{2}}{s_{n+2}-2s_{n+1}+s_{n}}}.}

<p>This transformation is commonly used to improve the <a href="/facts/Rate_of_convergence/JVGuzPoS">rate of convergence</a> of a slowly converging sequence; heuristically, it eliminates the largest part of the <a href="/facts/Absolute_error/orSvvIMC">absolute error</a>.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Shanks_transformation/RAS4mDuo">Shanks transformation</a></li>
<li><a href="/facts/Minimum_polynomial_extrapolation/GNNUIdmr">Minimum polynomial extrapolation</a></li>
<li><a href="/facts/Van_Wijngaarden_transformation/FvgBRoTl">Van Wijngaarden transformation</a></li></ul>

<ul><li>C. Brezinski and <a href="/facts/Michela_Redivo-Zaglia/KdkkvcC9">M. Redivo Zaglia</a>, <i>Extrapolation Methods. Theory and Practice</i>, North-Holland, 1991.</li>
<li>G. A. Baker Jr. and P. Graves-Morris, <i>Padé  Approximants</i>, Cambridge U.P., 1996.</li>
<li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/ConvergenceImprovement.html">"Convergence Improvement"</a>. <i><a href="/facts/MathWorld/yc1jodbq">MathWorld</a></i>.</li>
<li>Herbert H. H. Homeier: <i>Scalar Levin-Type Sequence Transformations</i>, Journal of Computational and Applied Mathematics, vol. 122, no. 1–2, p 81 (2000). Homeier, H. H. H. (2000). "Scalar Levin-type sequence transformations". <i>Journal of Computational and Applied Mathematics</i>. 122 (1–2): 81–147. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/math/0005209">math/0005209</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2000JCoAM.122...81H">2000JCoAM.122...81H</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0377-0427%2800%2900359-9">10.1016/S0377-0427(00)00359-9</a>., <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/math/0005209">math/0005209</a>.</li>
<li>Brezinski Claude and Redivo-Zaglia Michela : "The genesis and early developments of Aitken's process, Shanks transformation, the 
  
    
      
        ϵ
      
    
    {\displaystyle \epsilon }
  
-algorithm, and related fixed point methods", Numerical Algorithms, Vol.80, No.1, (2019), pp.11-133.</li>
<li>Delahaye J. P. : "Sequence Transformations", Springer-Verlag, Berlin, ISBN 978-3540152835 (1988).</li>
<li>Sidi Avram : "Vector Extrapolation Methods with Applications", SIAM, ISBN 978-1-61197-495-9 (2017).</li>
<li>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 .</li>
<li>Brezinski Claude : "Reminiscences of <a href="/facts/Peter_Wynn_(mathematician)/1tWmX59w">Peter Wynn</a>", Numerical Algorithms, Vol.80(2019), pp.5-10.</li>
<li>Brezinski Claude and Redivo-Zaglia Michela : "Extrapolation and Rational Approximation", Springer, ISBN 978-3-030-58417-7 (2020).</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://numbers.computation.free.fr/Constants/Miscellaneous/seriesacceleration.html">Convergence acceleration of series</a></li>
<li><a href="https://www.gnu.org/software/gsl/manual/html_node/Series-Acceleration.html">GNU Scientific Library, Series Acceleration</a></li>
<li><a href="http://dlmf.nist.gov/3.9">Digital Library of Mathematical Functions</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Abramowitz, Milton; Stegun, Irene Ann, eds. (1983) [June 1964]. "Chapter 3, eqn 3.6.27". Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Applied Mathematics Series. Vol. 55 (Ninth reprint with additional corrections of tenth original printing with corrections (December 1972); first ed.). Washington D.C.; New York: United States Department of Commerce, National Bureau of Standards; Dover Publications. p. 16. ISBN 978-0-486-61272-0. LCCN 64-60036. MR 0167642. LCCN 65-12253. <a href="978-0-486-61272-0" target="_blank">978-0-486-61272-0</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Abramowitz, Milton; Stegun, Irene Ann, eds. (1983) [June 1964]. "Chapter 3, eqn 3.6.26". Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Applied Mathematics Series. Vol. 55 (Ninth reprint with additional corrections of tenth original printing with corrections (December 1972); first ed.). Washington D.C.; New York: United States Department of Commerce, National Bureau of Standards; Dover Publications. p. 16. ISBN 978-0-486-61272-0. LCCN 64-60036. MR 0167642. LCCN 65-12253. <a href="978-0-486-61272-0" target="_blank">978-0-486-61272-0</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Henri Cohen, Fernando Rodriguez Villegas, and Don Zagier,
"Convergence Acceleration of Alternating Series", Experimental Mathematics, 9:1 (2000) page 3. <a href="/wiki/Henri_Cohen_(number_theorist)" target="_blank">/wiki/Henri_Cohen_(number_theorist)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>William H. Press, et al., Numerical Recipes in C, (1987) Cambridge University Press, ISBN 0-521-43108-5 (See section 5.1). <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

Series acceleration open-in-new

Series acceleration