ñòð. 31 |

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â€˜

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