ñòð. 25 |

n

P[P (k; M ) (e)][(n + Ã¿)kâˆ’1 =!n ]

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

This shows that the generalized H(k; M ) is a Levin-type sequence transformation of order kM . The

generalized H transformation can be computed recursively using the scheme [40,43]

Nn(0) = (n + Ã¿)âˆ’1 sn =!n ; Dn = (n + Ã¿)âˆ’1 =!n ;

(0)

M

(kâˆ’1)

Nn(k) = qj (n + Ã¿ + j k)Nn+j ;

j=0

M

(kâˆ’1)

(k)

Dn = qj (n + Ã¿ + jk)Dn+j ; (162)

j=0

Nn(k)

Hn (k; M )(Ã¿; {{sn }}; {{!n }}; e) = (k) :

Dn

Here, the qj are deÃ¿ned by

M M

qj x j :

(x âˆ’ em ) = (163)

m=1 j=0

Algorithm (155) is a special case of algorithm (162). To see this, one observes that M = 2; e1 =

exp(i ) und e2 = exp(âˆ’i ) imply q0 = q2 = 1 and q1 = âˆ’2 cos( ).

For M = 1 and e1 = 1, the Levin transformation is recovered.

4.2.10. I transformation

The I transformation was in a slightly di erent form introduced by Homeier [35]. It was derived

via (asymptotically) hierarchically consistent iteration of the H(1) transformation, i.e., of

sn+2 =!n+2 âˆ’ 2 cos( )sn+1 =!n+1 + sn =!n

sn = : (164)

1=!n+2 âˆ’ 2 cos( )=!n+1 + 1=!n

For the derivation and an analysis of the properties of the I transformation see [40,44]. The I

transformation may be deÃ¿ned via the recursive scheme

Nn(0) = sn =!n ; (0)

Dn = 1=!n ;

Nn(k+1) = (k)

]Nn(k) ;

n[

(k+1) (k) (k)

Dn = n[ ]Dn ; (165)

Nn(k)

(k) (k)

In ( ; {{sn }}; {{!n }}; { n }) = (k) ;

Dn

(k) (k)

where the generalized di erence operator n [ ] deÃ¿ned in Eq. (35) involves quantities n = 0

(k)

for k âˆˆ N0 . Special cases of the I transformation result from corresponding choices of the n .

From Eq. (165) one easily obtains the alternative representation

(kâˆ’1) (kâˆ’2) (0)

[ ] [ ]::: n[ ][sn =!n ]

n n

(k) (k)

In ({{sn }}; {{!n }}; { n }) = : (166)

(kâˆ’1) (kâˆ’2) (0)

[ ] [ ]::: n[ ][1=!n ]

n n

Thus, I(k) is a Levin-type sequence transformation of order 2k. It is not convex.

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

(0)

Put = 1 and for k Â¿ 0 deÃ¿ne

n

(0) (kâˆ’1)

n ::: n

(k)

= : (167)

n (0) (kâˆ’1)

n+1 : : : n+1

If for all k âˆˆ N the limits

(k)

lim = (168)

k

n

nâ†’âˆž

â—¦

exist (we have always 0 = 1), then one can deÃ¿ne a limiting transformation I for large n. It is a

special case of the I transformation according to [44]

â—¦(k) (k) n

I n ( ; {{sn }}; {{!n }}; {{ k }}) = In ( ; {{sn }}; {{!n }}; {{( k= k+1 ) }}): (169)

â—¦

This is a transformation of order 2k. The characteristic polynomials of I are known [44] to be

kâˆ’1

(2k) 2k (2k)

Q ( )âˆˆP :Q ( )(z) = [(1 âˆ’ z exp(i ))(1 âˆ’ z exp(âˆ’i ))]: (170)

j j

j=0

4.2.11. K transformation

The K transformation was introduced by Homeier [37] in a slightly di erent form. It was obtained

via iteration of the simple transformation

(0) (1) (2)

n sn =!n + n sn+1 =!n+1 + n sn+2 =!n+2

sn = ; (171)

(0) (1) (2)

1=!n + n 1=!n+1 + n 1=!n+2

n

that is exact for sequences of the form

sn = s + !n (cPn + dQn ); (172)

where c and d are arbitrary constants, while Pn and Qn are two linearly independent solutions of

the three-term recurrence

(0) (1) (2)

n vn + n vn+1 + n vn+2 = 0: (173)

The K transformation may be deÃ¿ned via the recursive scheme

Nn(0) = sn =!n ; (0)

Dn = 1=!n ;

Nn(k+1) = @n [ ]Nn(k) ;

(k)

(k+1) (k) (k)

Dn = @n [ ]Dn ; (174)

Nn(k)Ëœ (k) }; {

(k) ( j)

Kn ({{sn }}; {{!n }}; { n })

= (k) ;

n

Dn

(k)

where the generalized di erence operator @n [ ] deÃ¿ned in Eq. (36) involves recursion coe cients

(k)

with j = 0; 1; 2 and quantities Ëœ n = 0 for k âˆˆ N0 . Special cases of the K transformation for

( j)

n+k

(k)

given recursion, i.e., for given nj) , result from corresponding choices of the Ëœ n . From Eq. (174)

(

one easily obtains the alternative representation

@n [ ]@n [ ] : : : @(0) [ ][sn =!n ]

(kâˆ’1) (kâˆ’2)

Ëœ (k) }; { n

(k) ( j)

Kn ({{sn }}; {{!n }}; { n }) = (kâˆ’1) : (175)

n

@n [ ]@n [ ] : : : @(0) [ ][1=!n ]

(kâˆ’2)

n

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

Thus, K(k) is a Levin-type sequence transformation of order 2k. It is not convex. For applications

of the K transformation see [37,40,42,45].

5. Methods for the construction of Levin-type transformations

In this section, we discuss approaches for the construction of Levin-type sequence transformations

and point out the relation to their kernel.

5.1. Model sequences and annihilation operators

As discussed in the introduction, the derivation of sequence transformations may be based on

model sequences. These may be of the form (10) or of the form (6). Here, we consider model

sequences of the latter type that involves remainder estimates !n . As described in Section 3.1,

determinantal representations for the corresponding sequence transformations can be derived using

Cramerâ€™s rule, and one of the recursive schemes of the E algorithm may be used for the computation.

However, for important special choices of the functions j (n), simpler recursive schemes and more

explicit representations in the form (11) can be obtained using the annihilation operator approach

of Weniger [84]. This approach was also studied by Brezinski and Matos [13] who showed that it

leads to a uniÃ¿ed derivation of many extrapolation algorithms and related devices and general results

about their kernels. Further, we mention the work of Matos [59] who analysed the approach further

and derived a number of convergence acceleration results for Levin-type sequence transformations.

(k)

In this approach, an annihilation operator A=An as deÃ¿ned in Eq. (31) is needed that annihilates

the sequences {{ j (n)}}, i.e., such that

(k)

An ({{ j (n)}}) = 0 for j = 0; : : : ; k âˆ’ 1: (176)

Rewriting Eq. (6) in the form

kâˆ’1

âˆ’

n

= cj j (n) (177)

!n j=0

and applying A to both sides of this equation, one sees that

âˆ’

n

(k)

An =0 (178)

!n

This equation may be solved for due to the linearity of A. The result is

(k)

An ({{ n =!n }})

= (179)

(k)

An ({{1=!n }})

leading to a sequence transformation

(k)

An ({{sn =!n }})

(k)

Tn ({{sn }}; {{!}}) = (k) : (180)

An ({{1=!n }})

Since A is linear, this transformation can be rewritten in the form (11), i.e., a Levin-type transfor-

mation has been obtained.

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

We note that this process can be reversed, that is, for each Levin-type sequence transformation

T[ (k) ] of order k there is an annihilation operator, namely the polynomial operator P[ n ] as

(k)

(k)

deÃ¿ned in Eq. (38) where n are the characteristic polynomials as deÃ¿ned in Eq. (72). Using this

operator, the deÃ¿ning Eq. (66) can be rewritten as

(k)

P[ n ](sn =!n )

(k)

Tn ({{sn }}; {{!n }}) = : (181)

(k)

P[ n ](1=!n )

Let n; m (k) for m = 0; : : : ; k âˆ’ 1 be k linearly independent solutions of the linear (k + 1)â€“term

recurrence

k

(k)

n; j vn+j = 0: (182)

j=0

(k) (k)

Then P[ n ] n; m (k) = 0 for m = 0; : : : ; k âˆ’ 1, i.e., P[ n ] is an annihilation operator for all solutions

of Eq. (182). Thus, all sequences that are annihilated by this operator are linear combinations of the

(k)

k sequences {{ n; m }}.

If {{ n }} is a sequence in the kernel of T(k) with (anti)limit , we must have

(k)

P[ n ]( n =!n )

= (183)

(k)

P[ n ](1=!n )

or after some rearrangement using the linearity of P

nâˆ’

(k)

P[ n ] = 0: (184)

!n

Hence, we must have

kâˆ’1

âˆ’

n (k)

= cm n; m ; (185)

!n m=0

or, equivalently

kâˆ’1

(k)

= + !n cm (186)

n n; m

m=0

for some constants cm . Thus, we have determined the kernel of T(k) that can also be considered as

the set of model sequences for this transformation. Thus, we have proved the following theorem:

(k)

Theorem 1. Let n; m for m = 0; : : : ; k âˆ’ 1 be the k linearly independent solutions of the linear

(k + 1)â€“term recurrence (182). The kernel of T[ (k) ]({{sn }}; {{!n }}) is given by all sequences

{{ n }} with (anti)limit and elements n of the form (186) for arbitrary constants cm .

(k)

We note that the j (n) for j =0; : : : ; k âˆ’1 can essentially be identiÃ¿ed with the n; j . Thus, we have

ñòð. 25 |