<<

. 61
( 83 .)



>>

Dnj) {(d=d )g(t)}. Consequently, from (2.16) we have
(



d a(t) a(t)
™ a(t)™(t)

™ ( j)
M n = Dnj)
(
= Dnj)
(
’ : (2.23)
[™(t)]2
d ™(t) ™(t)

Next, substituting (2.23) in (2.22), and using the fact that Dnj) is a linear operator, we obtain
(


™( j)
An = Y1 + Y2 + Y3 ; (2.24)

where
n
Dnj) {a(t)=™(t)}
(
™ ( j)
Y1 = = ni a(tj+i );

Nn( j) i=0


™ ( j) ( ™ ( j) n
N n Dnj) {a(t)=™(t)} Nn ( j)
Y2 = ’ = ’ ( j) ni a(tj+i );
( j) 2
[Nn ] Nn i=0

n
Dnj) {a(t)™(t)=[™(t)]2 }
(
™ ( j)
Y3 = ’ =’ ni a(tj+i ) (2.25)
Nn( j) i=0

( j) ( j)
with = ni ™(tj+i )=™(tj+i ).
™ Here we have used the fact that
ni

n
Dnj) {h(t)=™(t)}
(
( j)
= ni h(tj+i ) for any h(t): (2.26)
Dnj) {1=™(t)}
(
i=0

Recalling (2.20), we identify

™ ( j)
Nn ( j) ( j)
™( j) = ’ ( j) ’ ni ; i = 0; 1; : : : ; n: (2.27)
ni
ni
Nn
Therefore,

™ ( j) ™ ( j) ™(tj+i )
n n n n
Nn Nn ™
( j) ( j) ( j) ( j) ( j)
( j)
= | ni | + + = | ni | + | ni | + : (2.28)
ni ni
n
Nn( j) ( j)
™(tj+i )
Nn
i=0 i=0 i=0 i=0
262 A. Sidi / Journal of Computational and Applied Mathematics 122 (2000) 251“273


Now even though the ÿrst summation is simply nj) , and hence can be computed very inexpensively,
(

™ ( j)
the second sum cannot, as its general term depends also on N n =Nn( j) ; hence on j and n. We can,
( j)
however, compute, again very inexpensively, an upper bound ˜ n on nj) , deÿned by
(

( j)
™ n
|N n |
˜ ( j) ( j)
( j) ( j) ( j) ( j)
= + ( j) + where ≡ | ni | (2.29)
n n n n n
|Nn | i=0

which is obtained by manipulating the second summation in (2.28) appropriately. This can be
achieved by ÿrst realizing that
|Dnj) {v(t)}|
(
( j)
= ; (2.30)
n
|Nn( j) |
where v(t) is arbitrarily deÿned for all t except for t0 ; t1 ; : : : ; for which it is deÿned by
v(tl ) = (’1)l |™(tl )|=|™(tl )|2 ;
™ l = 0; 1; : : : (2.31)
and then by applying Lemma 2.1.

™( j)
2.2.3. The (d=d )W-algorithm for An
™( j)
Combining all of the developments above, we can now extend the W-algorithm to compute An
( j)
and ˜ n . We shall denote the resulting algorithm the (d=d )W-algorithm. Here are the steps of this
algorithm.

1. For j = 0; 1; : : : ; set
a(tj ) 1
M0( j) = N0( j) = H0( j) = (’1)j |N0( j) |;
; ; and
™(tj ) ™(tj )

™ ( j) a(tj ) ’ a(tj )™(tj ) ;
™ ™ ™(tj )
™ ˜ ( j)
™ ( j) ™ ( j)
H 0 = (’1)j |N 0 |:
M0 = N0 = ’ ; (2.32)
[™(tj )]2 [™(tj )]2
™(tj )
˜ ( j)
™ ( j) ™ ( j)
2. For j =0; 1; : : : ; and n=1; 2; : : : ; compute Mn( j) ; Nn( j) ; Hn( j) ; M n ; N n , and H n recursively from
( j+1) ( j)
Qn’1 ’ Qn’1
Qnj)
(
= : (2.33)
tj+n ’ tj
3. For all j and n set
Mn( j) |Hn( j) |
A( j) ( j)
= ( j) ; = ( j) ; and
n n
Nn |Nn |
« 
˜ ( j)
™ ( j) ™ ( j) ™ ( j)
Mn ( j) N n |H n |  |N n | 
( j)
( j)
˜n =
™ ( j)
An = ( j) ’ An ( j) ; + 1 + ( j) n: (2.34)
|Nn( j) |
Nn Nn |Nn |
It is interesting to note that we need six tables of the form (1.11) in order to carry out the
(d=d )W-algorithm. This is twice the number of tables needed to carry out the W-algorithm. Note
( j)
™( j)
also that no tables need to be saved for A( j) ; nj) ; An ; and ˜ n . This seems to be the situation for
(
n
all extrapolation methods.
A. Sidi / Journal of Computational and Applied Mathematics 122 (2000) 251“273 263


3. Column convergence for (d=d )GREP (1)
( j) ∞

In this section we shall give a detailed analysis of the column sequences {An }j=0 with n ÿxed
for the case in which the tl are picked such that
tm+1
t0 ¿ t1 ¿ · · · ¿ 0 and lim =! for some ! ∈ (0; 1): (3.1)
m’∞ tm

We also assume that
™(tm+1 )
lim =! for some (complex) = 0; ’1; ’2; : : : : (3.2)
m’∞ ™(tm )


Recalling from Deÿnition 2.1 that ÿ(y) ≡ B(t) ∼ ∞ ÿi t i as t ’ 0+; we already have the following
i=0
optimal convergence and stability results for An and nj) , see Theorems 2:1 and 2:2 in [10].
( j) (



Theorem 3.1. Under the conditions given in (3:1) and (3:2); we have
n
cn+ +1 ’ ci
ÿn+ ™(tj )tjn+
A( j) ’A∼ as j ’ ∞; (3.3)
n
1 ’ ci
i=1

where ÿn+ is the ÿrst nonzero ÿi with i¿n; and
n n n
z ’ ci
( j) i
˜ni z i ;
lim ni z = ≡ Un (z) ≡ (3.4)
1 ’ ci
j’∞
i=0 i=1 i=0

so that for each ÿxed n
n
1 + |ci |
( j) ( j)
lim = hence sup ¡ ∞: (3.5)
n n
|1 ’ ci |
j’∞ j
i=1

Here
+k’1
ck = ! ; k = 1; 2; : : : : (3.6)

We shall see below that what we need for the analysis of (d=d )GREP(1) are the asymptotic
behaviors of ( j) and ™( j) . Now that we know the behavior of ( j) as j ’ ∞ from (3.4), we turn to
ni ni
ni
( j)
the study of ™ni . We start with
n n
cnij) i
(
Tn( j) (z)
( j) i
Tn( j) (z)
ni z = ( j) with = z; (3.7)
™(tj+i )
Tn (1)
i=0 i=0

which follows from the fact that ( j) = [cnij) =™(tj+i )]=Dnj) {1=™(t)}. Of course, Tn( j) (1) = Dnj) {1=™(t)}.
( ( (
ni
™ ( j)
Di erentiating (3.7) with respect to , and denoting T n (z) = (d=d )Tn( j) (z), we obtain
™ ( j) ™ ( j)
n
T n (z)Tn( j) (1) ’ Tn( j) (z)T n (1)
™( j) z i = : (3.8)
ni
[Tn( j) (1)]2
i=0
264 A. Sidi / Journal of Computational and Applied Mathematics 122 (2000) 251“273


Obviously,

n
™(tj+i ) i

™ ( j) cnij)
(

<<

. 61
( 83 .)



>>