<< Ïðåäûäóùàÿ ñòð. 51(èç 83 ñòð.)ÎÃËÀÂËÅÍÈÅ Ñëåäóþùàÿ >>
algorithms. In Section 3 we show that the two algorithms are mathematically equivalent. In Section
4 we give an e cient implementation for the Fordâ€“Sidi algorithm. This implementation is slightly
more economical than the original implementation for the Fordâ€“Sidi algorithm.

2. The E-algorithm and the Fordâ€“Sidi algorithm â€” review

Throughout this paper let s = (sn ) be any sequence to be transformed and gj = (gj (n)), j = 1; 2; : : : ;
be any auxiliary sequences. We denote 1 by the constant sequence with 1n = 1, for n = 0; 1; : : : :
Assume that all denominators are nonzero.

2.1. The E-algorithm
(n) (n)
The E-algorithm is deÃ¿ned as follows. For n = 0; 1; : : : ; the quantities Ek and gk; j are deÃ¿ned by

(n)
E0 = sn ;
(n)
g0; j = gj (n); j = 1; 2; : : : ;

(n) (n+1) (n+1) (n)
Ekâˆ’1 gkâˆ’1; k âˆ’ Ekâˆ’1 gkâˆ’1; k
(n)
Ek = ; k = 1; 2; : : : ; (3)
(n+1) (n)
gkâˆ’1; k âˆ’ gkâˆ’1; k

(n) (n+1) (n+1) (n)
gkâˆ’1; j gkâˆ’1; k âˆ’ gkâˆ’1; j gkâˆ’1; k
(n)
gk; j = ; k = 1; 2; : : : ; j = k + 1; : : : : (4)
(n+1) (n)
gkâˆ’1; k âˆ’ gkâˆ’1; k

The recurrence relations (3) and (4) are called the main rule and the auxiliary rule of the E-algorithm,
respectively. Brezinski [1] proved the following theorem using Sylvesterâ€™s determinantal identity.
N. Osada / Journal of Computational and Applied Mathematics 122 (2000) 223â€“230 225

(n) (n)
Theorem 1. For n = 0; 1; : : : ; and k = 1; 2; : : : ; Ek and gk; j are represented as
sn Â·Â·Â· sn+k 1 Â·Â·Â· 1
g1 (n) Â· Â· Â· g1 (n + k) g1 (n) Â· Â· Â· g1 (n + k)
(n)
Ek = ;
Â·Â·Â· Â·Â·Â·
gk (n) Â· Â· Â· gk (n + k) gk (n) Â· Â· Â· gk (n + k)

gj (n) Â· Â· Â· gj (n + k) 1 Â·Â·Â· 1
g1 (n) Â· Â· Â· g1 (n + k) g1 (n) Â· Â· Â· g1 (n + k)
(n)
gk; j = ; j Â¿ k;
Â·Â·Â· Â·Â·Â·
gk (n) Â· Â· Â· gk (n + k) gk (n) Â· Â· Â· gk (n + k)
respectively.
(n) (n) (n+1) (n)
If we set ck = gkâˆ’1; k =(gkâˆ’1; k âˆ’ gkâˆ’1; k ), then (3) and (4) become
(n) (n) (n) (n+1) (n)
Ek = Ekâˆ’1 âˆ’ ck (Ekâˆ’1 âˆ’ Ekâˆ’1 ); k Â¿ 0; (5)

(n) (n) (n) (n+1) (n)
gk; j = gkâˆ’1; j âˆ’ ck (gkâˆ’1; j âˆ’ gkâˆ’1; j ); k Â¿ 0; j Â¿ k; (6)
respectively.
(nâˆ’k) (n)
, 06n6N; 06k6n, requires 1 N 3 + O(N 2 ) gk; j â€™s.
For given s0 ; : : : ; sN , the computation of Ek 3
The number of operation counts for the E-algorithm, as mentioned in [1], is 5 N 3 + O(N 2 ), while
3
that with the implementation using (5) and (6) becomes N 3 + O(N 2 ). More precisely, the latter is
N3 + 5N2 + 3N.
2 2
We remark that Ford and Sidi [4] implemented the E-algorithm by rewriting in the forms
(n+1) (n) (n)
Ekâˆ’1 âˆ’ ck Ekâˆ’1
(n)
Ek = ; k Â¿ 0; (7)
(n)
dk
(n+1) (n) (n)
gkâˆ’1; j âˆ’ ck gkâˆ’1; j
(n)
gk; j = ; k Â¿ 0; j Â¿ k; (8)
(n)
dk
(n) (n+1) (n) (n) (n)
where ck = gkâˆ’1; k =gkâˆ’1; k , and dk = 1 âˆ’ ck . The implementation using (7) and (8) requires exactly
the same number of arithmetic operations as that using (5) and (6). However, one can avoid the
loss of signiÃ¿cant Ã¿gures by using (5) and (6).

2.2. The Fordâ€“Sidi algorithm

The Fordâ€“Sidi algorithm is deÃ¿ned as follows. Let u = (un ) be one of sequences s = (sn ), 1, or
gj = (gj (n)). The quantities k(n) (u) are deÃ¿ned by
un
(n)
0 (u) = ; (9)
g1 (n)
226 N. Osada / Journal of Computational and Applied Mathematics 122 (2000) 223â€“230

(n+1) (n)
kâˆ’1 (u) âˆ’ kâˆ’1 (u)
(n)
k (u) = ; k Â¿ 0: (10)
(n+1) (n)
kâˆ’1 (gk+1 ) âˆ’ (gk+1 )
kâˆ’1

Ford and Sidi [4] proved the following theorem using Sylvesterâ€™s determinantal identity.

(n)
Theorem 2. For n = 0; 1; : : : ; and k = 1; 2; : : : ; k (u) are represented as
un Â·Â·Â· un+k gk+1 (n) Â· Â· Â· gk+1 (n + k)
g1 (n) Â· Â· Â· g1 (n + k) g1 (n) Â· Â· Â· g1 (n + k)
(n)
k (u) = :
Â·Â·Â· Â·Â·Â·
gk (n) Â· Â· Â· gk (n + k) gk (n) Â· Â· Â· gk (n + k)

By Theorems 1 and 2, Tk(n) can be evaluated by
(n)
k (s)
Tk(n) = : (11)
(n)
(1)
k

Following the implementation by Ford and Sidi [4], the computation of Tk(nâˆ’k) , 06n6N , 06k6n,
requires 1 N 3 + 3 N 2 + 7 N subtractions, and 1 N 3 + 5 N 2 + 25 N +2 divisions, a total of 2 N 3 +4N 2 + 16 N +2
3 2 6 3 2 6 3 3
arithmetic operations.

Remark. (1) The Fordâ€“Sidi algorithm requires gk+1 for computing k(n) . However, for computing
Tk(n) the Fordâ€“Sidi algorithm does not require gk+1 . The reason is as follows: Let a1 ; : : : ; ak+1 be any
sequence such that
a1 Â·Â·Â· ak+1
g1 (n) Â· Â· Â· g1 (n + k)
= 0:
Â·Â·Â·
gk (n) Â· Â· Â· gk (n + k)
Let
u1 Â·Â·Â· uk+1 a1 Â·Â·Â· ak+1
g1 (n) Â· Â· Â· g1 (n + k) g1 (n) Â· Â· Â· g1 (n + k)
(n)
k (u) = :
Â·Â·Â· Â·Â·Â·
gk (n) Â· Â· Â· gk (n + k) gk (n) Â· Â· Â· gk (n + k)
Then by (11) we have
(n)
k (s)
Tk(n) = :
(n)
k (1)

Using the above trick, when s0 ; : : : ; sN , g1 ; : : : ; gN are given, we can determine all the Tk(n) , 06n +
k6N , by the Fordâ€“Sidi algorithm.
N. Osada / Journal of Computational and Applied Mathematics 122 (2000) 223â€“230 227

(2) Moreover, neither the value of gk+1 nor sequence a1 ; : : : ; ak+1 is required in computing Tk(n) ,
when we use
(n+1) (n)
kâˆ’1 (s) âˆ’ kâˆ’1 (s)
(n)
Tk = (n+1) ;
(n)
(1) âˆ’ kâˆ’1 (1)
kâˆ’1

which is derived from (10) and (11). The implementation of this fact is just the e cient Fordâ€“Sidi
algorithm described in Section 4 of this paper.

3. Mathematical equivalence of the E-algorithm and the Fordâ€“Sidi algorithm

3.1. The Fordâ€“Sidi algorithm is derived from the E-algorithm

Let u = (un ) be any sequence. Suppose that the sequence transformations Ek : u = (un ) â†’ Ek (u) =
(n)
(Ek (u)) are deÃ¿ned by
(n)
E0 (u) = un ; (12)
(n) (n+1) (n+1) (n)
Ekâˆ’1 (u)Ekâˆ’1 (gk ) âˆ’ Ekâˆ’1 (u)Ekâˆ’1 (gk )
(n)
Ek (u) = ; k Â¿ 0: (13)
(n+1) (n)
Ekâˆ’1 (gk ) âˆ’ Ekâˆ’1 (gk )
(n)
Suppose the sequence transformations : u = (un ) â†’ k (u) =( k (u)) are deÃ¿ned by
k
(n)
Ek (u)
(n)
k (u) = (n) ; k = 0; 1; : : : : (14)
Ek (gk+1 )

(n)
Theorem 3. The quantities k (u) deÃ¿ned by (14) satisfy (9) and (10).
(n)
Proof. It follows from (12) and (14) that 0 (u) = un =g1 (n).
(n)
Using the mathematical induction on k, it can be easily proved that Ek (1) = 1. Thus, we have
1
(n)
k (1) = ; k = 0; 1; : : : : (15)
(n)
Ek (gk+1 )
By (14), we have
(n)
Ek (gj )
(n)
k (gj ) = ; k = 0; 1; : : : ; j = k + 1; k + 2; : : : : (16)
(n)
Ek (gk+1 )
From (13) and (16), we obtain
(n+1) (n)
Ekâˆ’1 (gk+1 ) Ekâˆ’1 (gk+1 )
(n+1) (n)
kâˆ’1 (gk+1 ) âˆ’ kâˆ’1 (gk+1 ) = âˆ’ (n)
(n+1)
Ekâˆ’1 (gk ) Ekâˆ’1 (gk )
(n) (n+1) (n+1) (n) (n) (n+1)
Ekâˆ’1 (gk+1 )Ekâˆ’1 (gk ) âˆ’ Ekâˆ’1 (gk+1 )Ekâˆ’1 (gk ) Ekâˆ’1 (gk ) âˆ’ Ekâˆ’1 (gk )
= (n+1) (n) (n+1) (n)
Ekâˆ’1 (gk ) âˆ’ Ekâˆ’1 (gk ) Ekâˆ’1 (gk )Ekâˆ’1 (gk )

1 1
(n)
= Ek (gk+1 ) âˆ’ : (17)
(n+1) (n)
Ekâˆ’1 (gk ) Ekâˆ’1 (gk )
228 N. Osada / Journal of Computational and Applied Mathematics 122 (2000) 223â€“230

(n)
By dividing the both sides of (13) by Ek (gk+1 ), we have
(n) (n) (n+1) (n+1)
(n)
Ekâˆ’1 (u)=Ekâˆ’1 (gk ) âˆ’ Ekâˆ’1 (u)=Ekâˆ’1 (gk )
Ek (u)
= (n) ;
(n) (n) (n+1)
Ek (gk+1 ) Ek (gk+1 )(1=Ekâˆ’1 (gk ) âˆ’ 1=Ekâˆ’1 (gk ))
therefore from (14) and (17), we obtain
(n+1) (n)
kâˆ’1 (u) âˆ’ kâˆ’1 (u)
(n)
k (u) = :
(n+1) (n)
kâˆ’1 (gk+1 ) âˆ’ (gk+1 )
kâˆ’1

We note that Brezinski and Redivo Zaglia [3] derived the relations (14) â€“ (16) from their deÃ¿nitions
of Ek (u) and k(n) (u).
(n)

3.2. The E-algorithm is derived from the Fordâ€“Sidi algorithm

Suppose that the sequence transformations k satisfy (9) and (10) for any sequence u = (un ). Let
the sequence transformations Ek be deÃ¿ned by
(n)
k (u)
(n)
Ek (u) = : (18)
 << Ïðåäûäóùàÿ ñòð. 51(èç 83 ñòð.)ÎÃËÀÂËÅÍÈÅ Ñëåäóþùàÿ >>