ñòð. 29 |

j=0 n; j

H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147 123

one may perform the limit for n â†’ âˆž upon using the assumptions according to

â—¦ (k) â—¦

k n+j

c

(k) n (k)

Tn âˆ’ s c ()

j=0 j

â†’ = =0 (254)

â—¦ (k) â—¦

sn âˆ’ s k

c n âˆ’j (k) (1= ) c n

j=0 j

âˆ’j

since !n =!n+j â†’ .

Thus, the zeroes of the characteristic polynomial of the limiting transformation are of particular

importance.

It should be noted that the above assumptions correspond to a more complicated convergence type

than linear or logarithmic convergence if | 1 | = | 2 |Â¿| 3 |Â¿ Â· Â· Â· : This is the case, for instance, for the

H(k) transformation where the limiting transformation has the characteristic polynomial P (2k) ( ) with

k-fold zeroes at exp(Ãƒ ) and exp(âˆ’Ãƒ ). Another example is the I(k) transformation where the limiting

transformation has characteristic polynomials Q(2k) ( ) with zeroes at exp(Â±Ãƒ )= j ; j = 0; : : : ; k âˆ’ 1.

Specializing to A = 1 in Theorem 9, we obtain the following corollary:

Corollary 10. Assume that the following asymptotic relations hold for large n:

â—¦ (k) â—¦ (k)

(k)

âˆ¼ j; = 0; (255)

n; j k

sn âˆ’ s â—¦

âˆ¼ cq n ; (k)

cq = 0; (q) = 0; (256)

!n

!n+1 â—¦

(k)

âˆ¼ = 0; (1= ) = 0: (257)

!n

(k)

Then; {{Tn }} accelerates {{sn }} to s; i.e.; we have

(k)

Tn âˆ’ s

lim = 0: (258)

nâ†’âˆž sn âˆ’ s

Note that the assumptions of Corollary 10 imply

cq n+1

sn+1 âˆ’ s sn+1 âˆ’ s !n !n+1

= âˆ¼ =q (259)

sn âˆ’ s !n+1 sn âˆ’ s !n cq n

and thus, Corollary 10 corresponds to linear convergence for 0 Â¡ | q| Â¡ 1 and to logarithmic con-

vergence for q = 1.

Many important sequence transformations have convex limiting transformations, i.e., the character-

â—¦

istic polynomials satisfy (k) (1) = 0. In this case, they accelerate linear convergence. More exactly,

we have the following corollary:

Corollary 11. Assume that the following asymptotic relations hold for large n:

â—¦ (k) â—¦ (k)

(k)

âˆ¼ j; = 0; (260)

n; j k

sn âˆ’ s â—¦

(k)

âˆ¼ c; c = 0; (1) = 0; (261)

!n

124 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147

!n+1 â—¦

(k)

âˆ¼ = 0; (1= ) = 0: (262)

!n

(k)

Then; {{Tn }} accelerates {{sn }} to s; i.e.; we have

(k)

Tn âˆ’ s

lim = 0: (263)

nâ†’âˆž sn âˆ’ s

Hence; any Levin-type sequence transformation with a convex limiting transformation accelerates

linearly convergent sequences with

sn+1 âˆ’ s

lim =; 0Â¡| |Â¡1 (264)

nâ†’âˆž sn âˆ’ s

â—¦

(k)

such that (1= ) = 0 for suitably chosen remainder estimates !n satisfying (sn âˆ’ s)=!n â†’ c = 0.

Proof. Specializing Corollary 10 to q = 1, it su ces to prove the last assertion. Here, the proof

follows from the observation that (sn+1 âˆ’ s)=(sn âˆ’ s) âˆ¼ and (sn âˆ’ s)=!n âˆ¼ c imply !n+1 =!n âˆ¼ for

large n in view of the assumptions.

Note that Corollary 11 applies for instance to suitable variants of the Levin transformation, the

Ëœ

p J transformation and, more generally, of the J transformation. In particular, it applies to t; t ; u

and v variants, since in the case of linear convergence, one has sn = snâˆ’1 âˆ¼ which entails

(sn âˆ’ s)=!n âˆ¼ c for all these variants by simple algebra.

Now, some results for the speed of convergence are given. Matos [59] presented convergence

theorems for sequence transformations based on annihilation di erence operators with characteristic

polynomials with constants coe cients that are close in spirit to the theorems given below. However,

it should be noted that the theorems presented here apply to large classes of Levin-type transforma-

tions that have a limiting transformation (the latter, of course, has a characteristic polynomial with

constants coe cients).

Theorem 12. (C-1) Suppose that for a Levin-type sequence transformation T(k) of order k there

â—¦

â—¦

is a limiting transformation T (k) with characteristic polynomial âˆˆ Pk given by Eq. (242) where

the multiplicities mâ€˜ of the zeroes â€˜ = 0 satisfy m1 6m2 6 Â· Â· Â· 6mM . Let

âˆž

et(k)

nm1 âˆ’1 â—¦ (k)

(k) (k)

âˆ¼j ; e0 = 1 (265)

n; j

(n + j)m1 âˆ’1 (n + j)t

t=0

for n â†’ âˆž.

(C-2) Assume that {{sn }} âˆˆ SK and {{!n }} âˆˆ OK . Assume further that for n â†’ âˆž the

asymptotic expansion

M âˆž

sn âˆ’ s n

câ€˜; r nâˆ’r

âˆ¼ (266)

â€˜

!n r=0

â€˜=1

holds; and put

râ€˜ = min{r âˆˆ N0 | fâ€˜; r+m1 = 0}; (267)

H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147 125

where

v

(k)

fâ€˜; v = evâˆ’r câ€˜; r (268)

r=0

and

â—¦

mâ€˜ (k)

mâ€˜ d

Bâ€˜ = (âˆ’1) ( â€˜) (269)

d xmâ€˜

for â€˜ = 1; : : : ; M .

(C-3) Assume that the following limit exists and satisÃ¿es

!n+1 âˆ’1

0 = lim = âˆˆ { â€˜ | â€˜ = 1; : : : ; M }: (270)

nâ†’âˆž !n

Then we have

râ€˜ + mâ€˜

M n+mâ€˜

Bâ€˜ =nrâ€˜ +mâ€˜ âˆ’m1

fâ€˜; râ€˜ +m1

râ€˜

â€˜

â€˜=1

(k)

Tn ({{sn }}; {{!n }}) âˆ’s 1

âˆ¼ : (271)

â—¦

!n n2m1

(k) (1= )

(k)

Thus; {{Tn ({{sn }}; {{!n }})}} accelerates {{sn }} to s at least with order 2m1 ; i.e.;

(k)

Tn âˆ’ s

= O(nâˆ’2m1 âˆ’ ); Â¿0 (272)

sn âˆ’ s

if câ€˜; 0 = 0 for all â€˜.

(k) (k)

Proof. We rewrite Tn ({{sn }}; {{!n }}) = Tn as deÃ¿ned in Eq. (11) in the form

â—¦ (k) et(k) (n+j)m1 âˆ’1 sn+j âˆ’s

k âˆž

(k)

k

n; j (sn+j âˆ’ s)=!n+j j=0 j t=0 (n+j)t nm1 âˆ’1 !n+j

j=0

(k)

Tn âˆ’ s = !n âˆ¼ !n (273)

â—¦ (k)

(k)

k

j=0 n; j !n =!n+j

k 1

j=0 j j

for large n where we used Eq. (265) in the numerator, and in the denominator the relation !n =!n+j â†’

âˆ’j

that follows by repeated application of Eq. (270). Insertion of (266) now yields

M âˆž k n+j

!n â—¦ (k) â€˜

(k)

Tn âˆ’sâˆ¼ fâ€˜; r+m1 ; (274)

j

â—¦

(n + j)r+1

nm1 âˆ’1 (k) (1= ) â€˜=1 r=0 j=0

â—¦

where Eq. (268) was used. Also the fact was used that P[ (k) ] annihilates any linear combination

(k)

of the solutions â€™n; â€˜; jâ€˜ = njâ€˜ â€˜ with â€˜ = 1; : : : ; M and jâ€˜ = 0; : : : ; m1 âˆ’ 1 of the recursion relation (244)

n

since each â€˜ is a zero with multiplicity exceeding m1 âˆ’ 1. Invoking Lemma C.1 given in Appendix

C one obtains

â—¦

M âˆž

(âˆ’1)mâ€˜ d mâ€˜ (k)

!n r + mâ€˜

n+mâ€˜

(k)

Tn âˆ’ s âˆ¼ fâ€˜; r+m1 ( â€˜ ): (275)

r

â€˜

â—¦

nr+mâ€˜ +1 d xmâ€˜

nm1 âˆ’1 (k) (1= ) â€˜=1 r=0

The proof of Eq. (271) is completed taking leading terms in the sums over r. Since sn âˆ’ s âˆ¼

!n Z n â€˜âˆˆI ( â€˜ =Z)n câ€˜; 0 where Z = max{| â€˜ | |â€˜ = 1; : : : ; M }, and I = {â€˜ = 1; : : : ; M | Z = | â€˜ |}, Eq. (272)

is obtained where = min{râ€˜ + mâ€˜ âˆ’ m1 | â€˜ âˆˆ I }.

126 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147

â—¦

(k)

If !n+1 =!n âˆ¼ , where (1= ) = 0, i.e., if (C-3) of Theorem 12 does not hold, then the

denominators vanish asymptotically. In this case, one has to investigate whether the numerators or

the denominators vanish faster.

Theorem 13. Assume that (C-1) and (C-2) of Theorem 12 hold.

(C-3 ) Assume that for n â†’ âˆž the asymptotic relation

!n+1

âˆ¼ exp( n ); =0 (276)

!n

holds where

â—¦

(k)

1d 0 for = 0; : : : ; âˆ’ 1

(1= ) = (277)

C = 0 for =

! dx

and

n+1

â†’ 0; â†’1 (278)

n

n

for large n. DeÃ¿ne n via exp(âˆ’ n ) = 1 + .

n

Then we have for large n

râ€˜ + mâ€˜

M n+mâ€˜

Bâ€˜ =nrâ€˜ +mâ€˜ âˆ’m1

fâ€˜; râ€˜ +m1

râ€˜

â€˜

â€˜=1

(k)

Tn ({{sn }}; {{!n }}) âˆ’s 1

ñòð. 29 |