<<

. 30
( 83 .)



>>

∼ : (279)
!n C( n ) n2m1

Proof. The proof proceeds as the proof of Theorem 12 but in the denominator we use
k
!n
(k)
∼ C( n ) (280)
n; j
!n+j
j=0

that follows from Lemma C.2 given in Appendix C.

Thus, the e ect of the sequence transformation in this case essentially depends on the question
whether ( n )’ n’2m1 goes to 0 for large n or not. In many important cases like the Levin transfor-
mation and the p J transformations, we have M = 1 and m1 = k. We note that Theorem 11 becomes
especially important in the case of logarithmic convergence since for instance for M =1 one observes
n
that (sn+1 ’ s)=(sn ’ s) ∼ 1 and (sn ’ s)=!n ∼ 1 c1; 0 = 0 imply !n+1 =!n ∼ 1= 1 for large n such that
the denominators vanish asymptotically. In this case, we have = m1 whence ( n )’ n’2m1 = O(n’m1 )
if n = O(1=n). This reduction of the speed of convergence of the acceleration process from O(n’2k )
to O(n’k ) in the case of logarithmic convergence is a generic behavior that is re ected in a number
of theorems regarding convergence acceleration properties of Levin-type sequence transformations.
Examples are Sidi™s theorem for the Levin transformation given below (Theorem 15), and for the
p J transformation the Corollaries 18 and 19 given below, cf. also [84, Theorems 13:5, 13:9, 13:11,
13:12, 14:2].
The following theorem was given by Matos [59] where the proof may be found. To formulate it,
we deÿne that a sequence {{un }} has property M if it satisÿes
un+1 ˜
rn = o( ˜ (1=n)) for n ’ ∞:
∼ 1 + + rn with rn = o(1=n); (281)
un n
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147 127


Theorem 14 (Matos [59, Theorem 13]). Let {{sn }} be a sequence such that
(1) (k)
sn ’ s = !n (a1 g1 (n) + · · · + ak g1 (n) + n) (282)
with g1j+1) (n) = o(g1j) (n)); n = o(g1 (n)) for n ’ ∞. Let us consider an operator L of the form
( ( (k)

(193) for which we know a basis of solutions {{unj) }}; j = 1; : : : ; k; and each one can be written as
(


( j)
unj)
( ( j) ( j)
gm+1 (n) = o(gmj) (n))
(
∼ m gm (n); (283)
m=1

as n ’ ∞ for all m ∈ N and j = 1; : : : ; k. Suppose that
(a) g2j+1) (n) = o(g2j) (n)) for n ’ ∞; j = 1; : : : ; k ’ 1;
( (

(1) (k) (1)
(b) g2 (n) = o(g1 (n)); and n ∼ Kg2 (n) for n ’ ∞;
(284)
(c) {{gmj) (n)}} has property M for
(

m ∈ N; j = 1; : : : ; k:
Then
(k+1)
1. If {{!n }} satisÿes limn’∞ !n =!n+1 = = 1; the sequence transformation Tn corresponding
to the operator L accelerates the convergence of {{sn }}. Moreover; the acceleration can be
measured by
(1)
(k+1)
Tn ’s ’k g2 (n)
∼ Cn ; n ’ ∞: (285)
(1)
sn ’ s g1 (n)
(k+1)
2. If {{1=!n }} has property M; then the speed of convergence of Tn can be measured by
(1)
(k+1)
Tn ’s g2 (n)
∼ C (1) ; n ’ ∞: (286)
sn ’ s g1 (n)

7.2. Results for special cases

In the case that peculiar properties of a Levin-type sequence transformation are used, more stringent
theorems can often be proved as regards convergence acceleration using this particular transformation.
In the case of the Levin transformation, Sidi proved the following theorem:

Theorem 15 (Sidi [76] and Brezwski and Redivo Zaglia [14, Theorem 2:32]). If sn =s+!n fn where
fn ∼ ∞ ÿj =nj with ÿ0 = 0 and !n ∼ ∞ j =nj+a with a ¿ 0; 0 = 0 for n ’ ∞ then; if ÿk = 0
j=0 j=0

0 ÿk
(k)
· n’a’k
Ln ’ s ∼ (n ’ ∞): (287)
’a
k


For the W algorithm and the d(1) transformation that may be regarded as direct generalizations
of the Levin transformation, Sidi has obtained a large number of results. The interested reader is
referred to the literature (see [77,78] and references therein).
Convergence results for the Levin transformation, the Drummond transformation and the Weniger
transformations may be found in Section 13 of Weniger™s report [84].
128 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147


Results for the J transformation and in particular, for the p J transformation are given in [39,40].
Here, we recall the following theorems:

Theorem 16. Assume that the following holds:
(A-0) The sequence {{sn }} has the (anti)limit s.
(A-1a) For every n; the elements of the sequence {{!n }} are strictly alternating in sign and do
not vanish.
(k) (k)
(A-1b) For all n and k; the elements of the sequence {{ n }} = {{ rn }} are of the same sign
and do not vanish.
(A-2) For all n ∈ N0 the ratio (sn ’ s)=!n can be expressed as a series of the form

sn ’ s (0) (1) ( j’1)
= c0 + cj ··· (288)
n1 n2 nj
!n n¿n1 ¿n2 ¿···¿nj
j=1

with c0 = 0.
(k) (k) (k)
Then the following holds for sn = Jn ({{sn }}; {{!n }}; {{ n }}) :
(k)
(a) The error sn ’ s satisÿes
(k)
bn
(k)
sn ’ s = (k’1) (k’2) (289)
(0)
n n · · · n [1=!n ]
with

(k) (k) (k+1) ( j’1)
bn = ck + cj ··· : (290)
nk+1 nk+2 nj
n¿nk+1 ¿nk+2 ¿···¿nj
j=k+1
(k)
(b) The error sn ’ s is bounded in magnitude according to
(k) (k) (0) (1) (k’1)
|sn ’ s|6|!n bn ··· |: (291)
n n n

(c) For large n the estimate
(k)
sn ’ s (0) (1) (k’1)
= O( ··· ) (292)
n n n
sn ’ s
(k)
holds if bn = O(1) and (sn ’ s)=!n = O(1) as n ’ ∞.

(k) (k) (k) (k) (k) (k)
Theorem 17. Deÿne sn =Jn ({{sn }}; {{!n }}; {{ n }}) and !n =1=Dn where the Dn are deÿned
(k)
(k) (k) (k) (k) (k)
as in Eq. (94). Put en = 1 ’ !n+1 =!n and bn = (sn ’ s)=!n . Assume that (A-0) of Theorem
16 holds and that the following conditions are satisÿed:
(B-1) Assume that
(k)
bn
lim = Bk (293)
n’∞ b(0)
n

exists and is ÿnite.
(B-2) Assume that
(k)
!n+1
= lim (k) = 0 (294)
k
n’∞ !
n
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147 129


and
(k)
n+1
Fk = lim =0 (295)
(k)
n’∞
n
(k)
exist for all k ∈ N0 . Hence the limits = limn’∞ (cf. Eq. (97)) exist for all k ∈ N0 .
k n
Then; the following holds:
(a) If 0 ∈ { 0 = 1; 1 ; : : : ; k’1 }; then
’1
k’1
[ 0 ]k
(k)
sn ’ s (l)
lim = Bk (296)
n k’1
n’∞ sn ’ s
l=0 ( l ’ 0)
l=0

and; hence;
(k)
sn ’ s
= O( (0) (1) · · · n )
(k’1)
(297)
n n
sn ’ s
holds in the limit n ’ ∞.
(b) If l = 1 for l ∈ {0; 1; 2; : : : ; k} then
’1
k’1
(k) (l)
sn ’ s n
lim = Bk (298)
(l)
n’∞ sn ’ s
l=0 en

and; hence;
k’1
(k) (l)
sn ’ s n
=O (299)
(l)
sn ’ s l=0 en

holds in the limit n ’ ∞.

This theorem has the following two corollaries for the p J transformation [39]:

Corollary 18. Assume that the following holds:
(C-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.
(C-2) Assumptions (A-2) of Theorem 16 and (B-1) of Theorem 17 are satisÿed for the particular
(k)
choice (C-1) for n .
(C-3) The limit 0 = limn’∞ !n+1 =!n exists; and it satisÿes 0 ∈ {0; 1}. Hence; all the limits
(k) (k)
k = lim n’∞ !n+1 =!n exist for k ∈ N exist and satisfy k = 0 .
(k) (k)
Then the transformation sn =p Jn (ÿ; {{sn }}; {{!n }}) satisÿes
’1
k’1 k
(k)
sn ’ s 0
(l)
lim = Bk (300)
n
n’∞ sn ’ s 1’ 0
l=0

and; hence;
(k)
sn ’ s
= O((n + ÿ)’2k ) (301)
sn ’ s
holds in the limit n ’ ∞.
130 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147

<<

. 30
( 83 .)



>>