Äðóãèå àëãîðèòìû.

Ìàòåìàòèêà: Áûñòðîå âû÷èñëåíèå ôóíêöèé è êîíñòàíò.

Acceleration of the convergence of series

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 åa_n, we denote by s_n its partial sums, that is

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

where the (a_k) are positive numbers.

Definition 1 An infinite series åa_n 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.

Example 1 For the geometric series is defined by a_k = x^k, the partial sum s_n is then given by

Example 2 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

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 åa_n another equivalent series åb_n whose sum å_{n ³ 0}b_n is well known. More precisely suppose that

then the transformation is given by

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

Example 3 Consider

3  Aitken's acceleration method

In 1926, Alexander Aitken 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

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^* ... For example for the converging geometric series with 0 < x < 1:

hence

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

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

4  Euler-Maclaurin summation formula

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

and so

the following famous result due to Euler (1732) and Colin Maclaurin (1742) states that

where e_m,n is a remainder given by

Example 5 Suppose that s > 1 and

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

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

with

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

then

and

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

with

and the first difference operator is denoted by

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

with this time

and the second difference operator is denoted by

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

Theorem 1 Let S = å_{k = 0}ⁿ(-1)^ka_k be a convergent alternating series, then

The first values of D^ka₀ are

Example 6 Sometime it's possible to give a closed form for the transformation, take

relation founded by Euler.

5.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

This relation permits to write the sum of the series as

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

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

The number S_n satisfies

Therefore we deduce

This inequality suggests to choose polynomials with small value of M_n/|P_n(-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 = 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)

   (2)

   and explicitly writes in the form

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

   The relation (2) show that M_n = 1 and |P_n(-1)| ³ ¹/₂(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].

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

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 [5]). Suppose that you want to estimate a series which has the form

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

then

hence

Observe that

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

and again

but this time

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  æ ç è 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

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

   With the same method come the two other relations

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

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

References

[1]

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

[2]

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

[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]

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

[7]

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

Ââåðõ ïî ñòðàíèöå, ê îãëàâëåíèþ è íàâèãàöèè.