(1)

k

(n)

Theorem 4. The Ek (u) deÿned by (18) satisÿes (12) and (13).

Proof. Since (10), we have

(n)

k (gk+1 ) = 1:

Hence, by the deÿnition (18), we obtain

1

(n)

Ek (gk+1 ) = : (19)

(n)

(1)

k

By (18) and (10),

(n+1) (n)

(n)

k’1 (u) ’ k’1 (u)

k (u)

(n)

Ek (u) = =

(n) (n+1) (n)

k (1) k’1 (1) ’ k’1 (1)

(n+1) (n+1) (n) (n)

Ek’1 (u)=Ek’1 (gk ) ’ Ek’1 (u)=Ek’1 (gk )

= (n+1) (n)

1=Ek’1 (gk ) ’ 1=Ek’1 (gk )

(n+1) (n) (n) (n+1)

Ek’1 (gk )Ek’1 (u) ’ Ek’1 (gk )Ek’1 (u)

= :

(n+1) (n)

Ek’1 (gk ) ’ Ek’1 (gk )

By Theorems 3 and 4, we consider that the E-algorithm and the Ford“Sidi algorithm are mathe-

matically equivalent.

N. Osada / Journal of Computational and Applied Mathematics 122 (2000) 223“230 229

4. An e cient implementation for the Ford“Sidi algorithm

(n)

be deÿned by (9) and (10). By (11) and (10), Tk(n) in Eq. (2) is represented as

Let k (u)

(n+1) (n)

k’1 (s) ’ k’1 (s)

Tk(n) = ; k ¿ 0: (20)

(n+1) (n)

k’1 (1) ’ (1)

k’1

Using (20), the Ford“Sidi algorithm is implemented as follows.

{read s0 , g1 (0)}

(0) (0) (0)

0 (s):=s0 =g1 (0); 0 (1):=1=g1 (0); T0 :=s0 ;

{save T0(0) , 0 (s), 0 (1)}

(0) (0)

{read s1 , g1 (1)}

(1) (1) (1)

0 (s):=s1 =g1 (1); 0 (1):=1=g1 (1); T0 :=s1 ;

TN := 0 (s) ’ 0 (s); TD:= 0 (1) ’ 0 (1); T1(0) :=TN=TD;

(1) (0) (1) (0)

{save T0(1) , T1(0) , 0 (s), 0 (1), TN , TD, discard 0 (s), 0 (1)}

(1) (1) (0) (0)

for n:=2 to N do

begin

{read sn , gj (n), 16j6n ’ 1, gn (m), 06m6n}

(n)

for j:=2 to n ’ 1 do 0 (gj ):=gj (n)=g1 (n);

(m)

for m:=0 to n do 0 (gn ):=gn (m)=g1 (m);

for k:=1 to n ’ 2 do for m:=0 to n ’ k ’ 1 do

(m) (m+1) (m) (m)

k (gn ):=( k’1 (gn ) ’ k’1 (gn ))=Dk ;

(0) (1) (0)) (0) (0) (0) (0)

Dn’1 := n’2 (gn ) ’ n’2 (gn ); n’1 (s):=TN=Dn’1 ; n’1 (1):=TD=Dn’1 ;

T0(n) :=sn ; 0 (s):=sn =g1 (n); 0 (1):=1=g1 (n);

(n) (n)

for k:=1 to n ’ 1 do

begin

(n’k) (n’k+1) (n’k)

Dk := k’1 (gk+1 ) ’ k’1 (gk+1 );

(n’k) (n’k+1) (n’k) (n’k)

(s):=( k’1 (s) ’ k’1 (s))=Dk ;

k

(n’k) (n’k+1) (n’k) (n’k)

(1):=( k’1 (1) ’ k’1 (1))=Dk ;

k

Tk(n’k) := k(n’k) (s)= k(n’k) (1);

for j:=k + 2 to n do

(n’k) (n’k+1) (n’k) (n’k)

(gj ):=( k’1 (gj ) ’ k’1 (gj ))=Dk ;

k

end

(1) (0) (1) (0)

TN := n’1 (s) ’ n’1 (s); TD:= n’1 (1) ’ n’1 (1); Tn(0) :=TN=TD;

{save k(n’k) (s), k(n’k) (1), 06k6n ’ 1, k(n’k) (gj ), 06k6n ’ 2;

k + 26j6n, TN , TD, discarding all others}

{save all Tk(n’k) ,06k6n, Dk , 16l + k6n, 16k6n ’ 1}

(l)

end;

(The for statements of the form “for k:=k1 to k2 do” are not executed if k1 ¿ k2 .)

This algorithm will be called the e cient implementation for the Ford“Sidi algorithm. It is clear

that this algorithm is mathematically equivalent to the E-algorithm and the Ford“Sidi algorithm.

230 N. Osada / Journal of Computational and Applied Mathematics 122 (2000) 223“230

Table 1

The numbers of arithmetic operation counts of three algorithms

Algorithm Operation counts N = 10 N = 20

N3 + 5N2 + 3N

The E-algorithm using (5) and (6) 1265 9030

2 2

23

N + 4N 2 + 16 N + 2

The Ford“Sidi algorithm 1122 7042

3 3

23

N + 3N 2 + 10 N

The present method 1000 6600

3 3

The computation of Tk(n’k) ; 06n6N; 06k6n, by the e cient implementation for the Ford“Sidi al-

gorithm, requires 1 N 3 + N 2 + 2 N subtractions, and 1 N 3 + 2N 2 + 8 N divisions, a total of

3 3 3 3

23

N + 3N 2 + 10 N arithmetic operations. Although operation counts of the present method and the

3 3

Ford“Sidi algorithm are asymptotically equal, the present method is slightly more economical than

the Ford“Sidi algorithm.

The number of arithmetic operation counts for the computation of Tk(n’k) , 06n6N , 06k6n, by

the E-algorithm using (5) and (6), the Ford“Sidi algorithm, and the present method are listed in

Table 1.

Suppose that we accelerate the convergence of a usual sequence by a suitable method such as

(0)

the Levin u transform in double precision, and that TN is an optimal extrapolated value. Then it

is usually 106N 620. (See, for example, [2,7].) Therefore, by Table 1, the present method is, in

practice, 6“11% more economical than the Ford“Sidi algorithm.

Acknowledgements

The author would like to thank Prof. C. Brezinski for valuable comments and pointing out the

Ref. [3]. The author would also like to thank Prof. A. Sidi for helpful comments, particularly remark

(1) in subsection 2:2 is owed to him.

References

[1] C. Brezinski, A general extrapolation algorithm, Numer. Math. 35 (1980) 175“187.

[2] C. Brezinski, M. Redivo Zaglia, Extrapolation Methods, Theory and Practice, North-Holland, Amsterdam, 1991.

[3] C. Brezinski, M. Redivo Zaglia, A general extrapolation procedure revisited, Adv. Comput. Math. 2 (1994) 461“ 477.

[4] W.F. Ford, A. Sidi, An algorithm for a generalization of the Richardson extrapolation process, SIAM J. Numer. Anal.

24 (5) (1987) 1212“1232.

[5] T. Havie, Generalized Neville type extrapolation schemes, BIT 19 (1979) 204“213.

[6] C. Schneider, Vereinfachte Rekursionen zur Richardson-Extrapolation in Spezialfallen, Numer. Math. 24 (1975) 177“

184.

[7] D.A. Smith, W.F. Ford, Acceleration of linear and logarithmic sequence, SIAM J. Numer. Anal. 16 (2) (1979)

223“240.

Journal of Computational and Applied Mathematics 122 (2000) 231“250

www.elsevier.nl/locate/cam

Diophantine approximations using PadÃ approximations

e

M. PrÃ vost

e

Laboratoire de MathÃ matiques Pures et AppliquÃ es Joseph Liouville, UniversitÃ du Littoral Cote d™Opale, Centre

e e e ˆ

Universitaire de la Mi-Voix, Batiment H. PoincarÃ , 50 Rue F. Buisson B.P. 699, 62228 Calais CÃ dex, France

ˆ e e

Received 9 June 1999; received in revised form 1 December 1999

Abstract

We show how PadÃ approximations are used to get Diophantine approximations of real or complex numbers, and

e

so to prove the irrationality. We present two kinds of examples. First, we study two types of series for which PadÃ e

approximations provide exactly Diophantine approximations. Then, we show how PadÃ approximants to the asymptotic

e

expansion of the remainder term of a value of a series also leads to Diophantine approximation. c 2000 Elsevier Science

B.V. All rights reserved.

1. Preliminary

Deÿnition 1 (Diophantine approximation). Let x a real or complex number and (pn =qn )n a sequence

of Q or Q(i):

If limn’∞ |qn x’pn |=0 and pn =qn = x; ∀n ∈ N, then the sequence (pn =qn )n is called a Diophantine

approximation of x.

It is well known that Diophantine approximation of x proves the irrationality of x.

So, to construct Diophantine approximation of a number, a mean is to ÿnd rational approximation,

for example with PadÃ approximation.

e

We ÿrst recall the theory of formal orthogonal polynomials and its connection with PadÃ approx-

e

imation and -algorithm.

1.1. PadÃ approximants

e

Let h be a function whose Taylor expansion about t = 0 is ∞ ci t i . The PadÃ approximant [m=n]h

e

i=0

to h is a rational fraction Nm (t)=Dn (t) whose Taylor series at t = 0 coincides with that of h up to

E-mail address: prevost@lmpa.univ-littoral.fr (M. PrÃ vost)

e

0377-0427/00/$ - see front matter c 2000 Elsevier Science B.V. All rights reserved.

PII: S 0 3 7 7 - 0 4 2 7 ( 0 0 ) 0 0 3 6 5 - 4

232 M. PrÃ vost / Journal of Computational and Applied Mathematics 122 (2000) 231“250

e

the maximal order, which is in general the sum of the degrees of numerator and denominator of the

fraction, i.e,

Dn (t)h(t) ’ Nm (t) = O(t m+n+1 );

deg(Nm )6m; deg(Dn )6n; t ’ 0:

Note that the numerator Nm and the denominator Dn both depend on the index m and n.

The theory of PadÃ approximation is linked with the theory of orthogonal polynomials (see [10]):

e

Let us deÿne the linear functional c acting on the space P of polynomials as follows:

c : P ’ R (or C);

xi ’ c; xi = ci ; i = 0; 1; 2; : : : and if p ∈ Z;

c(p) : P ’ R (or C);

xi ’ c(p) ; xi := c; xi+p = ci+p ; i = 0; 1; 2; : : : (ci = 0; i ¡ 0);

then the denominators of the PadÃ approximants [m=n] satisfy the following orthogonality property:

e

˜

c(m’n+1) ; xi Dn (x) = 0; i = 0; 1; 2; : : : ; n ’ 1;

˜

where Dn (x) = xn Dn (x’1 ) is the reverse polynomial. Since the polynomials Dn involved in the ex-

˜

pression of PadÃ approximants depend on the integers m and n, and since Dn is orthogonal with

e

(m’n+1)

respect to the shifted linear functional c , we denote

˜

(m’n+1)

Pn (x) = Dn (x);

˜ (m’n+1) (x) = Nm (x):

Qn

If we set

(m’n+1) (m’n+1)

Pn (x) ’ Pn (t)