Convergence acceleration of series

(Click here for a Postscript version of this page.)

1  Introduction

Numerous mathematical constants are calculated as limit of series and many of those series are very slow to converge requiring therefore methods to accelerate their convergence. In this section, we recall some definitions and elementary results on well known series.

For any series å_ka_k, we denote by s_n its partial sums, that is

ê ê ê ê ê ê s0=a0, s1=a0+a1, sn=a0+a1+...+an= n å k=0  ak.

We are interested in the behavior of s_n as n tends to infinite (that is infinite series). The series whose terms have alternative signs are said to be alternating series, we write them as

sn=a0-a1+...+(-1)nan= n å k=0  (-1)kak,

where the (a_k) are positive numbers.

Definition 1 An infinite series å a_k is said to be convergent if its partial sums (s_n) tends to a limit S (called the sum of the series) as n tends to infinite. Otherwise the series is said to be divergent.

The following examples are elementary and occur frequently and it's usual to compare a given series to one of those.

Example 2 (Geometric series) For the geometric series which is defined by a_k=x^k, the partial sum s_n is then given by

sn=1+x+x2+...+xn=  1-xn+1 1-x ,

hence it converges for | x| < 1 to S=1/(1-x) and diverges otherwise.

Example 3 (Harmonic series) The harmonic series is defined for k > 0 by a_k=1/k, and the partial sum s_n (sometimes denoted H_n and called Harmonic number) is

sn=1+  1 2 +  1 3 ...+  1 n .

We have for n=2^p

sn = æ è 1+  1 2 ö ø + æ è  1 3 +  1 4 ö ø + æ è  1 5 +..+  1 8 ö ø +...+ æ è  1 2p-1+1 +...+  1 2p ö ø sn > 1.  1 2 +2.  1 4 +4.  1 8 +...+2p-1.  1 2p =  p 2 ,

therefore the partial sums are unbounded and the harmonic series is divergent (this important result was known to Jakob Bernoulli (1654-1705)  and much before to the french bishop Nicolas Oresme (1323-1382)).

Example 4 (Riemann Zeta series) A natural generalization of the harmonic series is to consider the partial sum

sn=1+  1 2s +  1 3s +...+  1 ns

which converges to the Riemann Zeta function z (s) for any complex numbers s such as  (s) > 1. The case s=1 is the Harmonic series and the limits for s=2p are well known since Euler who established for example that z(2)=p²/6, z(4)=p⁴/90,...

2  Kummer's acceleration method

Ernst Kummer's (1810-1893) method is very natural to understand and may be used to accelerate the convergence of many series. It goes back to 1837 and the idea is to subtract from a given convergent series åa_k another equivalent series åb_k whose sum C=å_{k ³ 0}b_k is well known. More precisely suppose that

lim k®¥  æ è  ak bk ö ø =r ¹ 0,

then the transformation is given by

¥ å k=0  ak=r ¥ å k=0  bk+ ¥ å k=0  æ è 1-r  bk ak ö ø ak=rC+ ¥ å k=0  æ è 1-r  bk ak ö ø ak.

(1)

The convergence of the latest series is faster because 1-rb_k/a_k tends to 0 as k tends to infinity [1].

Example 5 Consider

S = ¥ å k=1   1 k2 , C = ¥ å k=1   1 k(k+1) = ¥ å k=1  æ è  1 k -  1 k+1 ö ø =1,

we have r = C=1 and Kummer's transformation (1) becomes

S=1+ ¥ å k=1  æ è 1-  k2 k(k+1) ö ø  1 k2 =1+ ¥ å k=1   1 k2(k+1) .

The process can be repeated with this time

S* = ¥ å k=1   1 k2(k+1) C = ¥ å k=1   1 k(k+1)(k+2) =  1 4 ,

giving

S=  5 4 +2 ¥ å k=1   1 k2(k+1)(k+2) .

After N applications of the transformation

S= N å k=1   1 k2 +N! ¥ å k=1   1 k2(k+1)(k+2)...(k+N) ,

whose convergence may be rapid enough for suitable values of N (this example is due to Knopp [8]). Note, that we have used the following family of series to improve the convergence

C = ¥ å k=1  bk= ¥ å k=1   1 k(k+1)...(k+N) =  1 N.N! , bk ~  1 kN+1 when k® ¥.

3  Richardson Extrapolation method

Suppose that the partial sum verifies the relation

S=sn+  a np +O æ è  1 np+1 ö ø ,

(2)

where S is the limit of the sum, p a known integer and a a constant which we don't need to determine. Then, following the ideas of Lewis Fry Richardson (1881-1953) [10], it's natural to define the transformation

sn(1)=  2ps2n-sn 2p-1 =s2n+  1 2p-1 (s2n-sn)

in order to eliminate the term in a from relation (2). The process may be repeated on the new series

sn(2) =  2p+1s2n(1)-sn(1) 2p+1-1 , sn(3) =  2p+2s2n(2)-sn(2) 2p+2-1 , ...

Example 6 Suppose that you have computed, by geometric means and like Archimedes did, the perimeters of the circumscribed polygon with respectively 6,12,24,48 and 96 sides on a unit circle then in this case S=p, p=2 and Richardson's process becomes here

sn(1) = s2n+  1 3 ( s2n-sn) , sn(2) = s2n(1)+  1 15 (s2n(1)-sn(1)) , sn(3) = s2n(2)+  1 63 (s2n(2)-sn(2)) , ...

It produces the approximations (the number of sides is 6n)

n sn sn(1) sn(2) sn(3) 1 3.4641016151... 3.1324865405... 3.1416562605... 3.1415925429... 2 3.2153903091... 3.1410831530... 3.1415935385... 3.1415926532... 4 3.1596599420... 3.1415616394... 3.1415926670... 8 3.1460862151... 3.1415907278... 16 3.1427145996...

and finally we find p » s₁⁽⁴⁾ =3.141592653(637...) which is correct to nearly 10 digits and therefore much more accurate than the 2 digits value estimated by Archimedes !

4  Aitken's acceleration and related methods

4.1  Aitken's d²-process

In 1926, Alexander Aitken (1895-1967) found a new procedure to accelerate the rate of convergence of a series, the Aitken d²-process [2]. It consists in constructing a new series S⁽¹⁾, whose partial sums s_n⁽¹⁾ are given by

sn(1)=sn+1-  (sn+1-sn)2 sn+1-2sn+sn-1 =  sn-1sn+1-sn2 sn+1-2sn+sn-1 ,

(3)

where (s_n-1,s_n,s_n+1) are three successive partial sums of the original series. Of course, it's possible to repeat the process on the new series S⁽¹⁾ to obtain S⁽²⁾... This process was in fact known to the Japanese mathematician Takakazu Seki Kowa (1642-1708) who used it to compute 10 correct digits of the constant p by accelerating the convergence of the polygon algorithm.

For example for the converging geometric series with 0 < x < 1:

sn = 1+x+x2+...+xn=  1-xn+1 1-x  and the limit is S = lim n® ¥  sn=  1 1-x ,

hence

sn=(1-xn+1)S=S-xn+1S,

and if we replace (s_n-1,s_n,s_n+1) by this expression in (3) we have s_n⁽¹⁾=S ..., the exact limit is given just by three evaluations of the original series. This indicates that for a series almost geometric, Aitken's process may be very efficient.

Example 7 If we consider the extremely slow (logarithmic rate) converging series

S= lim n® ¥  sn= lim n® ¥  æ è n å k=0   (-1)k k+1 ö ø =log(2),

The following array illustrates the result of three consecutive applications of Aitken's process to the 7 first computed terms of this series :

n sn sn(1) sn(2) sn(3) 0 1.0000000000... 1 0.5000000000... 0.7000000000... 2 0.8333333333... 0.6904761904... 0.6932773109... 3 0.5833333333... 0.6944444444... 0.6931057563... 0.6931488693... 4 0.7833333333... 0.6924242424... 0.6931633407... 5 0.6166666666... 0.6935897435... 6 0.7595238095...

A formal expression may be obtained in this case ; the expressions of (s_n-1,s_n,s_n+1) are

sn=sn-1+  (-1)n n+1 ,sn+1=sn+  (-1)n+1 n+2

so that

sn(1)=sn+1+  (-1)n(n+1) (n+2)(2n+3)

For n=1000, it becomes

s1000 = 0.69(264...), s1000(1) = 0.693147180(435...).

4.2  The e-algorithm

In 1956, Peter Wynn obtained a generalization of Aitken's algorithm which is called the e-algorithm [11]. It is defined by the transformation

en(k+1)=en+1(k-1)+  1 en+1(k)-en(k)

(4)

starting with e_n^(-1)=0 and e_n⁽⁰⁾=s_n where s_n is the series to be accelerated.

Example 8 Again we take the series

lim n®¥  æ è n å k=0   (-1)k k+1 ö ø =log(2),

the following array illustrates the result of consecutive applications of Wynn's process (4) to the same as in the previous example 7 first computed terms of the series :

n en(-1) en(0)=sn en(1) en(2) en(3) en(4) en(5) 0 0 1.0000000000... -2 0.7000000000... -102 0.6933333333... -3852 1 0 0.5000000000... 3 0.6904761904... 248 0.6930894308... 12015 2 0 0.8333333333... -4 0.6944444444... -490 0.6931693989... 3 0 0.5833333333... 5 0.6924242424... 852 4 0 0.7833333333... -6 0.6935897435... 5 0 0.6166666666... 7 6 0 0.7595238095...

and finally e_n⁽⁶⁾=0.6931524547... Note that the odd values of the index are intermediate quantities.

5  Euler-Maclaurin summation formula

Suppose that the (a_k) may be written as the image of a given differentiable function f, that is

ak=f(k)

and so

sn= n å k=0  ak= n å k=0  f(k)

the following famous result due to Leonhard Euler (1732) and Colin Maclaurin (1742, [9]) states that

sn= ó õ n 0  f(t)dt+  1 2 ( f(0)+f(n)) + m å k=1   B2k (2k)! ( f2k-1(n)-f2k-1(0)) +em,n

where e_m,n is a remainder given by

em,n=  1 (2m+1)! ó õ n 0  B2m+1(x- ëx û )f2m+1(x)dx

where the B_2k are Bernoulli's Numbers and B_i(x) being Bernoulli's polynomials (see Bernoulli's number essay for more details or [7] for a proof).

Example 9 Suppose that s > 1 and

f(x)=  1 (x+1)s

then

sn-1 = 1+ 1 2s + 1 3s +...+ 1 ns = 1 s-1 æ ç è 1- 1 ns-1 ö ÷ ø + 1 2 æ ç è 1+ 1 ns ö ÷ ø + B2 2 æ ç è s 1 ö ÷ ø æ ç è 1- 1 ns+1 ö ÷ ø +... + B2m 2m æ ç è s+2m-2 2m-1 ö ÷ ø æ ç è 1- 1 ns+2m-1 ö ÷ ø +em,n

if n® ¥  in this identity, we find the relation

z(s) = ¥ å k = 1  1 ks = 1 s-1 + 1 2 + B2 2 æ ç è s 1 ö ÷ ø +...+ B2m 2m æ ç è s+2m-2 2m-1 ö ÷ ø +em,¥

and by computing z (s)-s_n-1 we find the useful algorithm to estimate z (s)

z(s) = 1+ 1 2s +...+ 1 ns + 1 s-1 1 ns-1 - 1 2ns + m å i = 1  B2i 2i æ ç è s+2i-2 2i-1 ö ÷ ø 1 ns+2i-1 +( em,¥-em,n) ,

and for any given integer m, the remainder tends to zero (Exercise : check this with care!).

6  Convergence improvement of alternating series

Very efficient methods exist to accelerate the convergence of an alternating series

S= ¥ å k=0  (-1)kak,

one of the first is due to Euler. Usually the transformed series converges geometrically with a rate of convergence depending on the method.

Because the speed of converge may be dramatically improved, there is a trick due to Van Wijngaarden which permits to transform any series åb_k with positive terms b_k into an alternating series. It may be written

¥ å k=0  bk= ¥ å k=0  (-1)kak

with

ak= ¥ å j=0  2j b2j(k+1)-1=bk+2b2k+1+4b4k+3+8b8k+7+...

and because 2^j(k+1)-1 increases very rapidly with j, only a few terms of this sum are required.

Sometimes a closed form exists for the a_k, for example if

bk=  1 (k+1)2 ,

then

ak = ¥ å j=0  2jb2j(k+1)-1= ¥ å j=0   2j ( 2j(k+1)) 2 =  1 (k+1)2 ¥ å j=0   1 2j =  2 (k+1)2 ,

and

¥ å k=0   1 (k+1)2 =2 ¥ å k=0   (-1)k (k+1)2 .

6.1  Euler's method

In 1755, Euler gave a first version of what is now called Euler's transformation. To establish it, observe that the sum of the alternating series may be written as

2S=a0+(a0-a1)-(a1-a2)+(a2-a3)-...=a0+S1,

with

S1=D1a0-D1a1+D1a2-...+(-1)kD1ak+...,

and the first difference operator is denoted by

D1ak=ak-ak+1.

The new series S₁ is also alternating and the process may be applied again

2S1=D1a0+(D1a0-D1a1)-(D1a1-D1a2)+(D1a2-D1a3)-...=D1a0+T1,

with this time

T1=D2a0-D2a1+D2a2-...+(-1)kD2ak+...,

and the second difference operator is denoted by

D2ak=D1ak-D1ak+1,

the following theorem is then easily deduced by repeating the process (we omit some details given in [8]).

Theorem 10 (Euler) Let S= å_k=0ⁿ(-1)^ka_k be a convergent alternating series, then

S= lim n®¥  sn= lim n®¥  æ è  1 2 n å k=0   (-1)k 2k Dka0 ö ø ,

(5)

and D is the forward difference operator defined by

Dka0 = Dk-1a0-Dk-1a1 = (-1)k k å j = 0  (-1)j æ ç è k j ö ÷ ø aj.

The first values of D^ka₀ are

D0a0 = a0, D1a0 = a0-a1, D2a0 = D1a0-D1a1=a0-2a1+a2, ..., Dka0 = a0-ka1+  k(k-1) 2! a2-  k(k-1)(k-2) 3! a3+...+(-1)kak.

Example 11 Sometimes it's possible to find a closed form for the transformation (5), take

S =  p 4 =1-  1 3 +  1 5 -  1 7 +...= ¥ å k=0  (-1)kak with ak =  1 2k+1 ,

the rate of convergence of this famous series is extremely slow, but Euler's method gives

D0a0 = 1, D1a0 = 1-  1 3 =  1.2 1.3 , D2a0 = D1a0-D1a1=  1.2 1.3 -  1.2 3.5 =  1.2.4 1.3.5 , D3a0 = D2a0-D2a1=  1.2.4 1.3.5 -  1.2.4 3.5.7 =  1.2.4.6 1.3.5.7 , ...

this suggest the expression (prove it by induction ...)

Dna0=  1.2.4...(2n) 1.3.5...(2n+1) .

and

p 4 = 1-  1 3 +  1 5 -  1 7 +...=  1 2 æ è 1+  1.2 1.3  1 2 +  1.2.4 1.3.5  1 22 +... ö ø  p 4 =  1 2 æ è 1+  1 3 +  1.2 3.5 +  1.2.3 3.5.7 ... ö ø =  1 2 ¥ å k=0   2kk!2 (2k+1)! ,

relation also given by Euler.

6.2  Improvement

In 1991, a generalization of Euler's method was given in [4] (this work in fact generalizes a technique that was used to obtain irrationality measures of some classical constants like log(2) for example). This algorithm is very general, powerful and easy to understand. For an alternating series å(-1)^k a_k, we assume that there exist a positive function w(x) such that

ak= ó õ 1 0  xkw(x)dx.

This relation permits to write the sum of the series as

¥ å k=0  (-1)kak = ó õ 1 0  æ è ¥ å k=0  (-1)kxk w(x)dx ö ø = ó õ 1 0   w(x) 1+x dx.

Now, for any sequence of polynomials P_n(x) of degree n with P_n(-1) ¹ 0, we denote by S_n the number

Sn=  1 Pn(-1) ó õ 1 0   Pn(-1)-Pn(x) 1+x w(x)dx.

Notice that S_n is a linear combination of the number (a_k)_{0 £ k < n} since if we write P_n(x) = å_k=0ⁿ p_k (-x)^k, we have easily

Sn =  1 Pn(-1) n-1 å k=0  ck (-1)k ak       with        ck= n å j = k+1  pj

(6)

The number S_n satisfies

Sn = ó õ 1 0   w(x) 1+x dx - ó õ 1 0   Pn(x)w(x) Pn(-1)(1+x) dx = S- ó õ 1 0   Pn(x)w(x) Pn(-1)(1+x) dx.

Therefore we deduce

| Sn-S| £  1 | Pn(-1)| ó õ 1 0   | Pn(x)| w(x) (1+x) dx £  Mn |Pn(-1)| | S| ,       Mn= sup x Î [0,1]  |pn(x)|

This inequality suggests to choose polynomials with small value of M_n/|P_n(-1)|.

6.2.1  Choice of a family of polynomials

1. A first possible choice is
   

   Pn(x) = (1-x)n = n å k = 0  æ ç è n k ö ÷ ø (-x)k,       for which    Pn(-1) = 2n,Mn = 1.

   It leads to the acceleration
   
   

   | Sn-S| £  | S| 2n

   where
   

   Sn = 1 2n n-1 å k = 0  (-1)kckak,      ck = n å j = k+1  æ ç è n j ö ÷ ø .

   This choice corresponds in fact to Euler's method.

2. Another choice is
   

   Pn(x) = (1-2x)n = n å k = 0  2k æ ç è n k ö ÷ ø (-x)k,    for which    Pn(-1) = 3n,Mn = 1.

   It leads to the acceleration
   

   | Sn-S| £  | S| 3n

   where
   

   Sn = 1 3n n-1 å k = 0  (-1)kckak,      ck = n å j = k+1  2j æ ç è n j ö ÷ ø .

3. Chebyshev's polynomials (see [1]) shifted to [0,1] provide a more efficient acceleration. They satisfy the relation
   

   Pn(sin2t)=cos(2nt)

   (7)

   and explicitly writes in the form
   

   Pn(x) = n å j = 0  n n+j æ ç è n+j 2j ö ÷ ø 4j(-x)j.

   The relation (7) show that M_n=1 and |P_n(-1)| ³ [ 1/2](3+Ö8)ⁿ > 5.828ⁿ/2. This family leads to the following acceleration process :
   

   | Sn-S| £  2| S| 5.828n

   where
   

   Sn = 1 Pn(-1) n-1 å k = 0  (-1)kckak,      ck = n å j = k+1  n n+j æ ç è n+j 2j ö ÷ ø 4j.

4. Other families of orthogonal polynomials such as Legendre's polynomials, Niven's polynomial may give interesting accelerations. More details and results may be found in the very interesting paper [4].

6.2.2  Examples

Once the choice of a sequence of polynomials is made, it can be applied to compute the value of many alternating series such as

log(2)= ¥ å k=0   (-1)k k+1        ak=  1 k+1 = ó õ 1 0  xk dx  p 4 = ¥ å k=0   (-1)k 2k+1 ak=  1 2k+1 = ó õ 1 0  xk   x-1/2 2  dx (1-2-s)z(s)= ¥ å k=0   (-1)k (k+1)s , ak=  1 (k+1)s =  1 G(s) ó õ 1 0  xk | log(x)| s-1dx.

Notice that this latest method is very efficient and may be used to compute the value of the zeta function at values of s with Â(s) > 0 (see [3]). Another beautiful alternating series whose convergence can be accelerated in this way is

log(2) æ è g-  1 2 log(2) ö ø =  log(2) 2 -  log(3) 3 +  log(4) 4 -  log(5) 5 +¼

where g is the Euler constant (see [6] for a proof of this formula).

7  Acceleration with the Zeta function

If you know how to evaluate the Zeta function at integers values, there is an easy and convenient way to transform your original series in a geometric converging one (based on [5]). Suppose that you want to estimate a series which has the form

S=A+ ¥ å k=2  f æ è  1 k ö ø

(8)

where A is a constant and where the analytic function f may be written

f(z)= ¥ å n=2  anzn

then

S=A+ ¥ å k=2  æ è ¥ å n=2   an kn ö ø =A+ ¥ å n=2  an æ è ¥ å k=2   1 kn ö ø

hence (8) may be transformed to

S=A+ ¥ å n=2  an( z(n)-1) .

(9)

Observe that

z(n)-1 ~  1 2n ,

therefore the transformed series (9) has a geometric rate of convergence. This rate may be improved if a few terms of the original series are computed, this time the limit is given by

S=A+ M å k=2  f æ è  1 k ö ø + ¥ å k=M+1  f æ è  1 k ö ø =A+ M å k=2  f æ è  1 k ö ø + ¥ å n=2  an æ è ¥ å k=M+1   1 kn ö ø

and again

S=A+f æ è  1 2 ö ø +...+f æ è  1 M ö ø + ¥ å n=2  an æ è z(n)-1-  1 2n -...-  1 Mn ö ø

but this time

z(n)-1-  1 2n -...-  1 Mn =z(n,M+1) ~  1 (M+1)n

and z(s,a) is the Hurwitz Zeta Function. The rate of convergence remains geometric but this rate may be taken as large as desired by taking a large enough value for M.

7.1  Examples

1. The first natural example comes with the (almost) definition series for Euler's constant
   

   S=g = 1+ ¥ å k=2  æ è  1 k +log æ è 1-  1 k ö ø ö ø

   here
   

   f(z)=z+log(1-z)=- ¥ å n=2   zn n

   and the transformed series is
   

   g = 1- ¥ å n=2   ( z(n)-1) n .

2. Another interesting series is Mercator's relation :
   

   S=log(2)=1-  1 2 +  1 3 -  1 4 +...=  1 2 + ¥ å k=2   1 (2k-1)2k

   and this time
   

   f(z)=  z2 2(2-z) = ¥ å n=2   zn 2n

   giving
   

   log(2)=  1 2 + ¥ å n=2   ( z(n)-1) 2n

   and if we compute two more terms
   

   log(2)=  37 60 + ¥ å n=2   (z(n)-1-1/2n-1/3n) 2n .

3. A check relation

   Observe that if we take for the function f ,a_n=1 for every n
   

   f(z)= ¥ å n=2  zn=  1 1-z -1-z=  z2 1-z

   so that for k > 1
   

   f æ è  1 k ö ø =  1 k(k-1) =  1 k-1 -  1 k

   and because clearly
   

   S= ¥ å k=2  f æ è  1 k ö ø = ¥ å k=2  æ è  1 k-1 -  1 k ö ø =1,

   we find the relation
   

   å n ³ 2  ( z(n)-1) = 1.

   With the same method come the two other relations
   

   å n ³ 1  ( z(2n)-1) =  3 4 å n ³ 1  ( z(2n+1)-1) =  1 4

   which may be used to check the evaluations of the Zeta function on consecutive integer values.

References

[1]

M. Abramowitz and I. Stegun, Handbook of Mathematical Functions, Dover, New York, (1964)

[2]

A.C. Aitken, On Bernoulli's numerical solution of algebraic equations, Proc. Roy. Soc. Edinburgh, (1926), vol. 46, p. 289-305

[3]

P. Borwein, An efficient algorithm for the Riemann Zeta function, (1995)

[4]

H. Cohen, F. Rodriguez Villegas, D. Zagier, Convergence acceleration of alternating series, Bonn, (1991)

[5]

P. Flajolet and I. Vardi, Zeta Function Expansions of Classical Constants, (1996)

[6]

X. Gourdon and P. Sebah, Numbers, Constants and Computation, World Wide Web site at the adress http://numbers.computation.free.fr/Constants/constants.html, (1999)

[7]

R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, (1994)

[8]

K. Knopp, Theory and application of infinite series, Blackie & Son, London, (1951)

[9]

C. Maclaurin, A Treatise of fluxions, Edinburgh, (1742)

[10]

L.W. Richardson, The deferred Approach to the Limit, Philosophical Transactions of the Royal Society of London, (1927), serie A, vol. 226

[11]

P. Wynn, On a device for computing the e_m(S_n) transformation, MTAC, (1956), vol. 10, p. 91-96