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