         ╧ґҐ№: ╠рҐхьрҐшър » ┴√ёҐЁ√х т√ішёыхэш  » Acceleration of the convergence of series
Acceleration of the convergence of series  ┼ёыш ┬√ эрщфхҐх ёҐрҐ№■ яюыхчэющ ш шэҐхЁхёэющ - эх ёюіҐшҐх чр ҐЁґф, яхЁхтхфшҐх ьрҐхЁшры шыш єюҐ  с√ ірёҐ№ хую ш юҐяЁрт№Ґх эр рфЁхё algolist@manual.ru. ╟рфрҐ№ тюяЁюё√ шыш яЁюёҐю эряшёрҐ№ яшё№ью ьюцэю Ґръцх эр ёҐЁрэшІх ъюэҐръҐют.

╤ҐрҐ№  ы■схчэю яЁхфюёҐртыхэр:
web: numbers.computation.free.fr

1  Introduction  Many mathematical constant are calculated as limit of series. In this chapter, we recall some definitions and results related to series and acceleration of their convergence. For any series хan, we denote by sn 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 sn as n tends to infinite (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 (ak) are positive numbers.

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

Example 1 For the geometric series is defined by ak = xk, the partial sum sn is then given by

 sn = 1+x+x2+...+xn = 1-xn+11-x ,
hence it converges for | x| < 1 to S = 1/(1-x) and diverges otherwise.

Example 2 The harmonic series is defined for k > 0 by ak = 1/k, and the partial sum sn (sometimes denoted Hn and called Harmonic number) is

 sn = 1+ 12 +...+ 1n .

We have for n = 2p

 sn
 =
 цч ш 1+ 12 Іі Ї + цч ш 13 + 14 Іі Ї + цч ш 15 +..+ 18 Іі Ї +...+ цч ш 12p-1+1 +...+ 12p Іі Ї
 sn
 >
 1 12 2 14 4 18 +...+2p-1. 12p = p2 ,

therefore the partial sums are unbounded and the harmonic series is divergent (this important result was known to Jakob Bernoulli (1654-1705) ).

2  Kummer's acceleration method  Ernst Kummer's (1810-1893) method is elementary and may be used to accelerate the convergence of many series. The idea is to subtract from a given convergent series хan another equivalent series хbn whose sum хn 0bn is well known. More precisely suppose that

 lim nо е anbn = r ╣ 0,

then the transformation is given by

 е х n = 0 an = r е х n = 0 bn + е х n = 0 цч ш 1-r bnan Іі Ї an.

The convergence of the latest series is faster because 1-rbn/an tends to 0 as k tends to infinity.

Example 3 Consider

 S
 =
 е х k = 1 1k2
 C
 =
 е х k = 1 1k(k+1) = е х k = 1 цч ш 1k - 1k+1 Іі Ї = 1,

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

 S = 1+ е х k = 1 цч ш 1- k2k(k+1) Іі Ї 1k2 = 1+ е х k = 1 1k2(k+1) .

The process can be repeated with this time

 S*
 =
 е х k = 1 1k2(k+1)
 C
 =
 е х k = 1 1k(k+1)(k+2) = 14 ,

giving

 S = 54 +2 е х k = 1 1k2(k+1)(k+2) .

After N applications of the transformation

 S = N х k = 1 1k2 +N! е х k = 1 1k2(k+1)(k+2)...(k+N) ,

whose convergence may be rapid enough for suitable values of N (this example is due to Knopp ).

Note, that we have used the following family of series to improve the convergence

 C
 =
 е х k = 1 bk = е х k = 1 1k(k+1)...(k+N) = 1N.N! ,
 bk
 ~
 1kN+1 when kо е.

3  Aitken's acceleration method  In 1926, Alexander Aitken found a new procedure to accelerate the rate of convergence of a series, the Aitken d2-process . It consists in constructing a new series S*, whose partial sums sn* are given by

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

where (sn-1,sn,sn+1) are three successive partial sums of the original series. Of course, it's possible to repeat the process on the new series S* ... For example for the converging geometric series with 0 < x < 1:

 sn
 =
 1+x+x2+...+xn = 1-xn+11-x and the limit is
 S
 =
 lim nо е sn = 11-x ,

hence

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

and if we replace (sn-1,sn,sn+1) by this expression we have sn* = 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 efficient.

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

 S = lim nо е sn = lim nо е цч ш n х k = 0 (-1)kk+1 Іі Ї = log(2),

the expressions of (sn-1,sn,sn+1) are

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

so

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

for n = 1000

 s1000
 =
 0.69(264842756680534060..),
 s1000*
 =
 0.693147180(43550628120..).

4  Euler-Maclaurin summation formula  Suppose that the (ak) 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 Euler (1732) and Colin Maclaurin (1742) states that

 sn = ґє n 0 f(t)dt+ 12 ( f(0)+f(n)) + m х k = 1 B2k(2k)! ( f2k-1(n)-f2k-1(0)) +em,n

where em,n is a remainder given by

 em,n = 1(2m+1)! ґє n 0 B2m+1(x- ëx û )f2m+1(x)dx
where the B2k are Bernoulli's Numbers and Bi(x) being Bernoulli's polynomials (see Bernoulli's number essay for more details or  for a proof).

Example 5 Suppose that s > 1 and

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

then

 sn-1
 =
 1+ 12s + 13s +...+ 1ns
 =
 1s-1 цч ш 1- 1ns-1 Іі Ї + 12 цч ш 1+ 1ns Іі Ї + B22 цч ш s 1 Іі Ї цч ш 1- 1ns+1 Іі Ї +...
 + B2m2m цч ш s+2m-2 2m-1 Іі Ї цч ш 1- 1ns+2m-1 Іі Ї +em,n

if nо е in this identity, we find the relation

 z(s) = е х k = 1 1ks = 1s-1 + 12 + B22 цч ш s 1 Іі Ї +...+ B2m2m цч ш s+2m-2 2m-1 Іі Ї +em,е

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

 z(s) = 1+ 12s +...+ 1ns + 1s-1 1ns-1 - 12ns + m х i = 1 B2i2i цч ш s+2i-2 2i-1 Іі Ї 1ns+2i-1 +( em,е-em,n) ,

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

5  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 хbk with positive terms bk 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 2j(k+1)-1 increases very rapidly with j, only a few terms of this sum are required. Sometimes a closed form exists for the ak, 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 12j
 =
 2(k+1)2 ,

and

 е х k = 0 1(k+1)2 = 2 е х k = 0 (-1)k(k+1)2 .

### 5.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 S1is 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 ).

Theorem 1 Let S = хk = 0n(-1)kak be a convergent alternating series, then

 S = lim nо е sn = lim nо е цч ш 12 n х k = 0 (-1)k2k Dka0 Іі Ї ,

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 Dka0 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 6 Sometime it's possible to give a closed form for the transformation, take

 S
 =
 p4 = 1- 13 + 15 - 17 +... = е х k = 0 (-1)kakwith
 ak
 =
 12k+1 ,

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

 D0a0
 =
 1,
 D1a0
 =
 1- 13 = 1.21.3 ,
 D2a0
 =
 D1a0-D1a1 = 1.21.3 - 1.23.5 = 1.2.41.3.5 ,
 D3a0
 =
 D2a0-D2a1 = 1.2.41.3.5 - 1.2.43.5.7 = 1.2.4.61.3.5.7 ,
 ...

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

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

and

 p4
 =
 1- 13 + 15 - 17 +... = 12 цч ш 1+ 1.21.3 12 + 1.2.41.3.5 122 +... Іі Ї
 p4
 =
 12 цч ш 1+ 13 + 1.23.5 + 1.2.33.5.7 ... Іі Ї = 12 е х k = 0 2kk!2(2k+1)! ,

relation founded by Euler.

### 5.2  Improvement

In 1991, a generalization of Euler's method was given in  (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 ak, 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 Pn(x) of degree n with Pn(-1) 0, we denote by Sn the number

 Sn = 1Pn(-1) ґє 1 0 Pn(-1)-Pn(x)1+x w(x)dx.

Notice that Sn is a linear combination of the number (ak)0 г k < n since if we write Pn(x) = хk = 0n pk (-x)k, we have easily

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

The number Sn 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 Mn/|Pn(-1)|.

#### 5.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,       forwhich    Pn(-1) = 2n,Mn = 1.
It leads to the acceleration
 | Sn-S| г | S|2n
where
 Sn = 12n 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 = 13n n-1 х k = 0 (-1)kckak,      ck = n х j = k+1 2j цч ш n j Іі Ї .

3. Chebyshev's polynomials (see ) shifted to [0,1] provide a more efficient acceleration. They satisfy the relation
 Pn(sin2t) = cos(2nt)
(2)
and explicitly writes in the form
 Pn(x) = n х j = 0 nn+j цч ш n+j 2j Іі Ї 4j(-x)j.
The relation (2) show that Mn = 1 and |Pn(-1)| 1/2(3+8)n > 5.828n/2. This family leads to the following acceleration process :
 | Sn-S| г 2| S|5.828n
where
 Sn = 1Pn(-1) n-1 х k = 0 (-1)kckak,      ck = n х j = k+1 nn+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 .

#### 5.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)kk+1
 ak = 1k+1 = ґє 1 0 xk dx
 p4 = е х k = 0 (-1)k2k+1
 ak = 12k+1 = ґє 1 0 xk x-1/22 dx
 (1-2-s)z(s) = е х k = 0 (-1)k(k+1)s ,
 ak = 1(k+1)s = 1G(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 ). Another beautiful alternating series whose convergence can be accelerated in this way is
 log(2) цч ш g- 12 log(2) Іі Ї = log(2)2 - log(3)3 + log(4)4 - log(5)5 +╝
where g is the Euler constant.

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

 S = A+ е х k = 2 f цч ш 1k Іі Ї

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 ankn Іі Ї = A+ е х n = 2 an цч ш е х k = 2 1kn Іі Ї

hence

 S = A+ е х n = 2 an( z(n)-1) .

Observe that

 z(n)-1 ~ 12n ,

therefore the transformed series 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 цч ш 1k Іі Ї + е х k = M+1 f цч ш 1k Іі Ї = A+ M х k = 2 f цч ш 1k Іі Ї + е х n = 2 an цч ш е х k = M+1 1kn Іі Ї

and again

 S = A+f цч ш 12 Іі Ї +...+f цч ш 1M Іі Ї + е х n = 2 an цч ш z(n)-1- 12n -...- 1Mn Іі Ї

but this time

 z(n)-1- 12n -...- 1Mn = 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.

### 6.1  Examples

1. The first natural example comes with the (almost) definition series for Euler's constant
 S = g = 1+ е х k = 2 цч ш 1k +log цч ш 1- 1k Іі Ї Іі Ї
here
 f(z) = z+log(1-z) = - е х n = 2 znn
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- 12 + 13 - 14 +... = 12 + е х k = 2 1(2k-1)2k
and this time
 f(z) = z22(2-z) = е х n = 2 zn2n
giving
 log(2) = 12 + е х n = 2 ( z(n)-1)2n
and if we compute two more terms
 log(2) = 3760 + е х n = 2 ( z(n)-1-1/2n-1/3n)2n .

3. A check relation

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

 f(z) = е х n = 2 zn = 11-z -1-z = z21-z

so that for k > 1

 f цч ш 1k Іі Ї = 1k(k-1) = 1k-1 - 1k

and because clearly

 S = е х k = 2 f цч ш 1k Іі Ї = е х k = 2 цч ш 1k-1 - 1k Іі Ї = 1,

we find the relation

 1 = е х n = 2 ( z(n)-1) .

With the same method come the two other relations

 х k │ 1 ( z(2k)-1)
 =
 34
 х k │ 1 ( z(2k+1)-1)
 =
 14

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

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


A. C. Aitken, Proc. Roy. Soc. Edinburgh, (1926), vol. 46


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


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


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


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


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