<<

. 27
( 83 .)



>>

{{{ n (c ; p )|c (214)
˜=0


with a(˜) ¿ a(˜ ) for ˜ ¿ ˜ . Here, ˜ numbers the levels of the hierarchy. Each of the model sequences
{{ n (c (˜) ; p(˜) )}} depends on an a(˜) -dimensional complex vector c (˜) and further parameters p(˜) .
(˜)

Assume that the model sequences of lower levels are also contained in those of higher levels: For
all ˜ ¡ L and all ˜ ¿ ˜ and ˜ 6L, every sequence {{ n (c (˜) ; p(˜) )}} is assumed to be representable
(˜)

as a model sequence {{ n ) (c (˜ ) ; p(˜ ) )}} where c (˜ ) is obtained from c (˜) by the natural injection

(˜) (˜ )
Ka ’ Ka . Assume that for all ˜ with 0 ¡ ˜6L

T (p(˜) ) : {{ (˜) (˜) (˜) (˜’1) (˜’1) (˜’1)
n (c ; p )}} ’ {{ (c ;p )}} (215)
n


is a mapping between neighboring levels of the hierarchy. Composition yields an iterative transfor-
mation

T (L) = T (p(0) ) —¦ T (p(1) ) —¦ · · · —¦ T (p(L) ): (216)

This transformation is called “hierarchically consistent” or “consistent with the hierarchy”. It maps
model sequences n (c (˜) ; p(˜) ) to constant sequences if Eq. (213) holds with
(˜)


(0) (0) (0)
{{ n (c ; p )}} = {{ n (c; p)}}: (217)

If instead of Eq. (215) we have

T (p(˜) )({{ (˜) (˜) (˜) (˜’1) (˜’1) (˜’1)
n (c ; p )}}) ∼ {{ (c ;p )}} (218)
n


for n ’ ∞ for all ˜ ¿ 0 then the iterative transformation T (L) is called “asymptotically consistent
with the hierarchy” or “asymptotically hierarchy-consistent”.


5.2.1. Derivation of the JD transformation
The simple transformation is the D(2) transformation
2
(sn =!n )
sn = T ({{!n }})({{sn }}) = (219)
2 (1=! )
n


depending on the “parameters” {{!n }}, with basic model sequences

1
n
= + (an + b): (220)
!n !n

The more complicated model sequences of the next level are taken to be

1
n
= + (an + b + (a1 n + b1 )rn ): (221)
!n !n
116 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147

2
Application of eliminates the terms involving a and b. The result is
2 2
n =!n 1=!n rn
= + a1 n + b1 + 2a1 (222)
2r 2r 2r
n n n
2
for rn = 0. Assuming that for large n
rn
= An + B + o(1) (223)
2r
n

holds, the result is asymptotically of the same form as the model sequence in Eq. (220), namely
1
n
= + (a n + b + o(1)) (224)
!n !n
with renormalized “parameters”
2
(1=!n )
1=!n = (225)
2r
n

and obvious identiÿcations for a and b .
We now assume that this mapping between two neighboring levels of the hierarchy can be extended
to any two neighboring levels, provided that one introduces ˜-dependent quantities, especially rn ’
rn with n = 2 rn = 0; sn =!n ’ Nn(˜) , 1=!n ’ Dn and sn =!n ’ Nn(˜+1) , 1=!n ’ Dn .
(˜) (˜) (˜) (˜) (˜+1)

Iterating in this way leads to algorithm (151).
Condition (223) or more generally
(˜)
rn
= A˜ n + B˜ + o(1) (226)
2 r (˜)
n

for given ˜ and for large n is satisÿed in many cases. For instance, it is satisÿed if there are constants
ÿ˜ = 0, ˜ and ˜ = 0 such that
± n
+1

 ˜
 for = 0;
 ˜
 ˜
(˜)
rn ∼ ÿ ˜ (227)
 ˜+1

 ˜
 otherwise:

˜ ˜
n n
(˜)
This is for instance the case for rn = n ˜ with ˜ ( ˜ ’ 1) = 0.
The kernel of JD(k) may be found inductively in the following way:
Nn(k) ’ Dn = 0
(k)


2
(Nn(k’1) ’ Dn ) = 0
(k’1)


’ Nn(k’1) ’ Dn
(k’1)
= ak’1 n + bk’1
2
(Nn(k’2) ’ Dn ) = (ak’1 n + bk’1 )
(k’2) (k’2)
’ n

j
n’2
(k’2)
Nn(k’2) (k’2)
’ ’ Dn ) = ak’2 n + bk’2 + (ak’1 n + bk’1 ) (228)
n
j=0 n =0
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147 117


yielding the result
j
n’2
Nn(0) (0) (0)
(a1 n1 + b1 + · · ·
’ Dn = a0 n + b 0 + n1
j=0 n1 =0

nk’2 ’2 jk’2
+ bk’1 ) :
(k’2)
+ (ak’2 n + bk’2 + nk’1 (ak’1 nk’1 (229)
jk’2 =0 nk’1 =0

Here, the deÿnitions Nn(0) = n =!n and Dn = 1=!n may be used to obtain the model sequence
(0)

{{ n }} for JD(k) , that may be identiÿed as kernel of that transformation, and also may be regarded
as model sequence of the kth level according to {{ n (c (k) ; p(k) )}} with c (k) = (a0 ; b0 ; : : : ; ak’1 ; bk’1 )
(k)

and p(k) corresponds to !n = 1=Dn and the { n |06„6k ’ 2}.
(k) (k) („)

We note this as a theorem:

Theorem 2. The kernel of JD(k) is given by the set of sequences {{ n }} such that Eq. (229) holds
with Nn(0) = n =!n and Dn = 1=!n .
(0)



5.2.2. Important special cases
Here, we give the hierarchies of model sequences for sequence transformations derived via hier-
archically consistent iteration.
J transformation: The most prominent example is the J transformation (actually a large class
of transformations). The corresponding hierarchy of model sequences provided by the kernels that
are explicitly known according to the following theorem:

Theorem 3 (Homeier [36]). The kernel of the J(k) transformation is given by the sequences {{ n }}
with elements of the form
k’1
= + !n cj j (n) (230)
n
j=0

with
0 (n) = 1;
n’1
(0)
1 (n) = n1 ;
n1 =0

n1 ’1
n’1
(0) (1)
2 (n) = n2 ; (231)
n1
n1 =0 n2 =0

.
.
.
(0) (1) (k’2)
k’1 (n) = ···
n1 n2 nk’1
n¿n1 ¿n2 ¿···¿nk’1

with arbitrary constants c0 ; : : : ; ck’1 .
118 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147


I transformation: Since the I transformation is a special case of the J transformation (cf. Table
1) and [44], its kernels (corresponding to the hierarchy of model sequences) are explicitly known
according to the following theorem:

Theorem 4 (Homeier [44, Theorem 8]). The kernel of the I(k) transformation is given by the se-
quences {{ n }} with elements of the form
®

= + exp(’i n)!n °d0 + d1 exp(2i n)
n


n’1 n1 ’1
(0)
+ exp(2i (n1 ’ n2 ))(d2 + d3 exp(2i n2 )) + ···
n2
n1 =0 n2 =0

+ exp(2i [n1 ’ n2 + · · · + n2k’3 ’ n2k’2 ])
n¿n1 ¿n2 ¿···¿n2k’2

k’2
( j) »
(d2k’2 + d2k’1 exp(2i n2k’2 )) (232)
n2j+2
j=0


with constants d0 ; : : : ; d2k’1 . Thus; we have s = In ) ( ; {{sn }}; {{!n }}; {
(k (k)
n }) for k ¿k for se-
quences of this form.

5.3. A two-step approach

In favorable cases, one may use a two-step approach for the construction of sequence transforma-
tions:
Step 1: Use asymptotic analysis of the remainder Rn = sn ’ s of the given problem to ÿnd the
adequate model sequence (or hierarchy of model sequences) for large n.
Step 2: Use the methods described in Sections 5:1 or 5:2 to construct the sequence transformation

<<

. 27
( 83 .)



>>