<<

. 29
( 83 .)



>>

sn ’ s sn ’ s !n =!n+j
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

˜
˜=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

˜
˜=1
(k)
Tn ({{sn }}; {{!n }}) ’s 1

<<

. 29
( 83 .)



>>