<<

. 31
( 83 .)



>>


Note that Corollary 18 can be applied in the case of linear convergence because then 0 ¡ | 0 | ¡ 1
holds.
Corollary 18 allows to conclude that in the case of linear convergence, the p J transformations
should be superior to Wynn™s epsilon algorithm [104]. Consider for instance the case that

n‚
cj =nj ;
sn ∼ s + n c0 = 0; n’∞ (302)
n=0

is an asymptotic expansion of the sequence elements sn . Assuming = 1 and ‚ ∈ {0; 1; : : : ; k ’ 1}
it follows that [102; p: 127; 84; p: 333; Eq: (13:4“7)]
(n)
’s
2k
= O(n’2k ); n ’ ∞: (303)
sn ’ s
This is the same order of convergence acceleration as in Eq. (301). But it should be noted that
(n)
for the computation of 2k the 2k + 1 sequence elements {sn ; : : : ; sn+2k } are required. But for the
(k)
computation of p Jn only the k + 1 sequence elements {sn ; : : : ; sn+k } are required in the case of
the t and u variants, and additionally sn+k+1 in the case of the t˜ variant. Again, this is similar to
Levin-type accelerators [84, p. 333].
The following corollary applies to the case of logarithmic convergence:

Corollary 19. Assume that the following holds:
(D-1) Let ÿ ¿ 0; p¿1 and n = [(n+ÿ +(p’1)k)’1 ]. Thus; we deal with the p J transformation
(k)
(k) (k)
and; hence; the equations Fk = limn’∞ n+1 = n = 1 and k = 1 hold for all k.
(D-2) Assumptions (A-2) of Theorem 16 and (B-1) of Theorem 15 are satisÿed for the particular
(k)
choice (C-1) for n .
(D-3) Some constants a( j) ; j = 1; 2; exist such that
l

a(1) a(2)
(l) l l
(l) (l)
+ O((n + ÿ)’3 )
en =1’ !n+1 =!n = + (304)
n + ÿ (n + ÿ) 2


holds for l=0. This implies that this equation; and hence; l =1 holds for l ∈ {0; 1; 2; : : : ; k}.
Assume further that a(1) = 0 for l ∈ {0; 1; 2; : : : ; k ’ 1}.
l
(k) (k)
Then the transformation sn =p Jn (ÿ; {{sn }}; {{!n }}) satisÿes
’1
k’1
(k) (l)
sn ’ s n
lim = Bk (305)
(l)
n’∞ sn ’ s
l=0 en

and; hence;
(k)
sn ’ s
= O((n + ÿ)’k ) (306)
sn ’ s
holds in the limit n ’ ∞.

For convergence acceleration results regarding the H and I transformations, see [34,44].
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147 131


8. Stability results for Levin-type transformations

8.1. General results
(k)
We remind the reader of the deÿnition of the stability indices n (T)¿1 as given in Eq. (76).
We consider the sequence {{!n }} ∈ OK as given. We call the transformation T stable along the
path P = {(n˜ ; k˜ ) | [n˜ ¿ n˜’1 and k˜ ¿k˜’1 ] or [n˜ ¿n˜’1 and k˜ ¿ k˜’1 ]} in the T table if the limit
of its stability index along the path P exists and is bounded, i.e., if

(k˜ )
lim n˜ (T) = lim | n˜ ;j (k˜ )(!n )| ¡ ∞; (307)
˜’∞ ˜’∞
j=0

(k)
where the n; j (!n ) are deÿned in Eq. (75). The transformation T is called S-stable, if it is stable
along all paths P(k) = {(n; k) | n = 0; 1; : : :} for ÿxed k, i.e., along all columns in the T table.
The case of stability along diagonal paths is much more di cult to treat analytically unless
Theorem 22 applies. Up to now it seems that such diagonal stability issues have only been analysed
by Sidi for the case of the d(1) transformation (see [78] and references therein). We will treat only
S-stability in the sequel.
The higher the stability index (T) is, the smaller is the numerical stability of the transformation
T: If j is the numerical error of sj ,
= sj ’ fl(sj ); (308)
j

(k) (k)
then the di erence between the true value Tn and the numerically computed approximation fl(Tn )
may be bounded according to
(k)
(k) (k)
|Tn ’ fl(Tn )|6 n (T) max | n+j | ; (309)
j∈{0;1;:::; k}

cf. also [78].

—¦
Theorem 20. If the Levin-type sequence transformation T(k) has a limiting transformation T (k)
—¦
with characteristic polynomial (k) ∈ P(k) for all k ∈ N; and if {{!n }} ∈ OK satisÿes !n+1 =!n ∼
—¦
(k)
= 0 for large n with (1= ) = 0 for all k ∈ N then the transformation T is S-stable.
—¦ (k) —¦ (k)
If additionally; the coe cients j of the characteristic polynomial alternate in sign; i.e.; if j
—¦
—¦ (k)
= (’1) j | (k) (k)
j |= k with | k | = 1; then the limits (T) = limn’∞ n (T) obey
—¦
(k)
(’1=| |)
—¦
(k)
(T) = : (310)
k —¦
| (k) (1= )|

Proof. We have for ÿxed k
® ’1 ® ’1 —¦ (k)
k k ’j
(k) !n ° !n » —¦ (k) —¦ (k) ’j j
(k) (k) ° »
∼ j ’j
n; j (!n ) = n; j = ; (311)
n; j j —¦
!n+j j =0 !n+j (k) (1= )
j =0
132 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147


whence
—¦ (k)
k
k
| j || |’j
j=0
(k)
(k)
lim n (T) = lim | n; j (!n )| = ¡ ∞: (312)
—¦
n’∞ n’∞
| (k) (1= )|
j=0

—¦ (k)
If the alternate in sign, we obtain for these limits
j

—¦ (k)
k ’j
j=0 j (’| |)
—¦
(k)
(T) = : (313)
k —¦
| (k) (1= )|


This implies Eq. (310).

Corollary 21. Assume that the Levin-type sequence transformation T(k) has a limiting transforma-
—¦ —¦ (k)
—¦
tion T (k) with characteristic polynomial (k) ∈ P(k) and the coe cients j of the characteristic
—¦ —¦
(k) (k)
polynomial alternate in sign; i.e.; if j = (’1) j | j |= k with | k | = 1 for all k ∈ N. The sequence
{{!n }} ∈ OK is assumed to be alternating and to satisfy !n+1 =!n ∼ ¡ 0 for large n. Then the
—¦
(k)
transformation T is S-stable. Additionally the limits are (T) = 1.

Proof. Since
—¦ (k)
—¦
(k)
k k
(k)
!n (1= )
n; j j j
| |’j
∼ = ’1 (’1)
’1 ’1
!n+j
k k j =0 k
j =0
k
—¦ (k) —¦ (k)
|’j ¿| |=| |k ¿ 0:
= | j || (314)
k
j =0

—¦
(k)
1= cannot be a zero of . Then, Theorem 20 entails that T is S-stable. Furthermore, Eq. (310)
—¦
(k)
is applicable and yields (T) = 1.
(k)
This result can be improved if all the coe cients are alternating:
n; j



Theorem 22. Assume that the Levin-type sequence transformation T(k) has a characteristic poly-
(k) (k) (k)
nomials n ∈ P(k) with alternating coe cients n; j i.e.; n; j = (’1) j | n; j |= k with | k | = 1 for all
(k)

n ∈ N0 and k ∈ N. The sequence {{!n }} ∈ OK is assumed to be alternating and to satisfy
(k)
!n+1 =!n ¡ 0 for all n ∈ N0 . Then we have n (T) = 1. Hence; the transformation T is stable
along all paths for such remainder estimates.

Proof. We have for ÿxed n and k
(k) (k) (k)
j
n; j !n =!n+j n; j k (’1) |!n =!n+j | | n; j ||!n =!n+j |
(k)
n; j (!n ) = = = ¿0:
(k) (k) (k)
k k k
j =0 n; j !n =!n+j j =0 n; j k (’1) |!n =!n+j | j =0 | n; j | |!n =!n+j |
j

(315)
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147 133

(k)
Note that the denominators cannot vanish and are bounded from below by | n; k !n =!n+k | ¿ 0. Hence,
(k) (k) (k)
we have n; j (!n ) = | n; j (!n )| and consequently, n (T) = 1 since k n; j (!n ) = 1 according to
(k)
j=0
Eq. (75).

8.2. Results for special cases

Here, we collect some special results on the stability of various Levin-type sequence transforma-
tions that have been reported in [46] and generalize some results of Sidi on the S-stability of the
d(1) transformation.

Theorem 23. If the sequence !n+1 =!n possesses a limit according to
lim !n+1 =!n = =0 (316)
n’∞

and if ∈ {1; 1; : : : ; k ; : : :} such that the limiting transformation exists; the J transformation is
—¦
S-stable with the same limiting stability indices as the transformation J; i.e.; we have
(k) k’j
k
j=0 | j |
(k)
lim = ¡ ∞: (317)
n k’1
j =0 | j ’ |
n’∞

<<

. 31
( 83 .)



>>