<<

. 52
( 83 .)



>>

(n)
(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)

<<

. 52
( 83 .)



>>