also [38] for determinantal representations of the J transformations and the relation to its kernel.

Examples of annihilation operators and the functions j (n) that are annihilated are given in

Table 2. Examples for the Levin-type sequence transformations that have been derived using the ap-

proach of model sequences are discussed in Section 5.1.2.

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

Table 2

Examples of annihilation operatorsa

Type Operator j (n); j = 0; : : : ; k ’ 1

k

(n + ÿ) j

Di erences

(n + ÿ)j

( [n + ]) j

( [n + ])j

pj (n); pj ∈ P( j)

k

(n + ÿ)k’1 1=(n + ÿ) j

Weighted di erences

k

(n + ÿ)k’1 1=(n + ÿ)j

k

( [n + ])k’1 1=( [n + ]) j

k

( [n + ])k’1 1=( [n + ])j

j

(k)

Divided di erences n [{{tn }}] tn

(k)

pj (tn ); pj ∈ P( j)

n [{{tn }}]

(k)

n [{{x n }}](x n )k’1 1=(x n )j

P[P (2k) ( )] exp(+i n)pj (n); pj ∈ P( j)

Polynomial

exp(’i n)pj (n); pj ∈ P( j)

P[P (2k) ( )](n + ÿ)k’1 exp(+i n)=(n + ÿ) j

exp(’i n)=(n + ÿ) j

P[P (2k) ( )](n + ÿ)k’1 exp(+i n)=(n + ÿ)j

exp(’i n)=(n + ÿ)j

P[P (k) ] j (n) is solution of

k

p(k) vn+j = 0

m=0 n

P[P (k) ](n + ÿ)m (n + ÿ)m j (n) is solution of

k

p(k) vn+j = 0

m=0 n

n+1

j

L1 (see (188)) n!

nj n+1

L2 (see (189)) n!

(n+ j +1)

˜

L (see (191)) n!

a

See also Section 5.1.1.

Note that the annihilation operators used by Weniger [84,87,88] were weighted di erence opera-

(k)

tors Wn as deÿned in Eq. (37). Homeier [36,38,39] discussed operator representations for the J

transformation that are equivalent to many of the annihilation operators and related sequence trans-

formations as given by Brezinski and Matos [13]. The latter have been further discussed by Matos

[59] who considered among others Levin-type sequence transformations with constant coe cients,

(k) (k)

n; j = const:, and with polynomial coe cients n; j = j (n + 1), with j ∈ P, and n ∈ N0 , in particular

annihilation operators of the form

l l’1

L(un ) = ( + + ··· + l )(un ) (187)

1

with the special cases

L1 (un ) = ( ’ 1 )( ’ 2) · · · ( ’ l )(un ) ( = for all i = j) (188)

i j

and

L2 (un ) = ( ’ )l (un ); (189)

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

where

r

(un ) = (n + 1)r un+r ; n ∈ N0 (190)

and

˜

L(un ) = ( ’ 1 )( ’ 2) · · · ( ’ l )(un ); (191)

where

r r’1

(un ) = (n + 1) un ; (un ) = ( (un )); n ∈ N0 (192)

and the ™s and ™s are constants. Note that n is shifted in comparison to [59] where the convention

n ∈ N was used. See also Table 2 for the corresponding annihilated functions j (n).

Matos [59] also considered di erence operators of the form

k k’1

L(un ) = + pk’1 (n) + · · · + p1 (n) +p0 (n); (193)

where the functions fj given by fj (t) = pj (1=t)t ’k+j for j = 0; : : : ; k ’ 1 are analytic in the neigh-

borhood of 0. For such operators, there is no explicit formula for the functions that are annihilated.

However, the asymptotic behavior of such functions is known [6,59]. We will later return to such

annihilation operators and state some convergence results.

5.1.1. Derivation of the F transformation

As an example for the application of the annihilation operator approach, we derive the F trans-

formation. Consider the model sequence

k’1

1

= + !n cj ; (194)

n

(x n )j

j=0

that may be rewritten as

k’1

’ 1

n

= cj : (195)

!n (x n )j

j=0

We note that Eq. (194) corresponds to modeling n = Rn =!n as a truncated factorial series in x n

(instead as a truncated power series as in the case of the W algorithm). The x n are elements of

{{x n }} an auxiliary sequence {{x n }} such that limn’∞ 1=x n = 0 and also x n+˜ ¿ x n for ˜ ∈ N

and x0 ¿ 1, i.e., a diverging sequence of monotonously increasing positive numbers. To ÿnd an

annihilation operator for the j (n) = 1=(x n )j , we make use of the fact that the divided di erence

(k) (k)

operator n = n [{{x n }}] annihilates polynomials in x n of degree less than k. Also, we observe

that the deÿnition of the Pochhammer symbols entails that

(x n )k’1 =(x n )j = (x n + j)k’1’j (196)

is a polynomial of degree less than k in x n for 06j6k ’ 1. Thus, the sought annihilation operator

(k)

is A = n (x n )k’1 because

1

(k)

n (x n )k’1 = 0; 06j ¡ k: (197)

(x n )j

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

Hence, for the model sequence (194), one can calculate via

(k)

n ((x n )k’1 n =!n )

= (198)

(k)

n ((x n )k’1 =!n )

and the F transformation (140) results by replacing by sn in the right-hand side of Eq. (198).

n

5.1.2. Important special cases

Here, we collect model sequences and annihilation operators for some important Levin-type se-

quence transformations that were derived using the model sequence approach. For further examples

see also [13]. The model sequences are the kernels by construction. In Section 5.2.2, kernels and

annihilation operators are stated for important Levin-type transformation that were derived using

iterative methods.

Levin transformation: The model sequence for L(k) is

k’1

cj =(n + ÿ) j :

= + !n (199)

n

j=0

The annihilation operator is

(k) k

(n + ÿ)k’1 :

An = (200)

Weniger transformations: The model sequence for S(k) is

k’1

= + !n cj =(n + ÿ)j : (201)

n

j=0

The annihilation operator is

(k) k

An = (n + ÿ)k’1 : (202)

The model sequence for M(k) is

k’1

= + !n cj =(’n ’ )j : (203)

n

j=0

The annihilation operator is

(k) k

An = (’n ’ )k’1 : (204)

The model sequence for C(k) is

k’1

= + !n cj =( [n + ])j : (205)

n

j=0

The annihilation operator is

(k) k

An = ( [n + ])k’1 : (206)

W algorithm: The model sequence for W (k) is

k’1

j

= + !n cj tn : (207)

n

j=0

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

The annihilation operator is

(k) (k)

An = n [{{tn }}]: (208)

H transformation: The model sequence for H(k) is

«

k’1 k’1

+ !n exp(i n) cj =(n + ÿ) j :

cj =(n + ÿ) j + exp(’i n)

+ ’

= (209)

n

j=0 j=0

The annihilation operator is

An = P[P (2k) ( )](n + ÿ)k’1 :

(k)

(210)

Generalized H transformation: The model sequence for H(k; m) is

M k’1

n

cm; j (n + ÿ)’j :

= + !n em (211)

n

m=1 j=0

The annihilation operator is

An = P[P (k; m) (e)](n + ÿ)k’1 :

(k)

(212)

5.2. Hierarchically consistent iteration

As alternative to the derivation of sequence transformations using model sequences and possibly

annihilation operators, one may take some simple sequence transformation T and iterate it k times

to obtain a transformation T (k) = T —¦ · · · —¦ T . For the iterated transformation, by construction one

has a simple algorithm by construction, but the theoretical analysis is complicated since usually

no kernel is known. See for instance the iterated Aitken process where the 2 method plays the

role of the simple transformation. However, as is discussed at length in Refs. [36,86], there are

usually several possibilities for the iteration. Both problems “ unknown kernel and arbitrariness of

iteration “ are overcome using the concept of hierarchical consistency [36,40,44] that was shown to

give rise to powerful algorithms like the J and the I transformations [39,40,44]. The basic idea

of the concept is to provide a hierarchy of model sequences such that the simple transformation

provides a mapping between neighboring levels of the hierarchy. To ensure the latter, normally one

has to ÿx some parameters in the simple transformation to make the iteration consistent with the

hierarchy.

A formal description of the concept is given in the following taken mainly from the literature

[44]. As an example, the concept is later used to derive the JD transformation in Section 5.2.1.

Let {{ n (c; p)}}∞ be a simple “basic” model sequence that depends on a vector c ∈ Ka of

n=0

constants, and further parameters p. Assume that its (anti)limit (p) exists and is independent of c.

Assume that the basic transformation T = T (p) allows to compute the (anti)limit exactly according

to

T (p ) : {{ n (c; p )}} ’ {{ (p)}}: (213)

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

Let the hierarchy of model sequences be given by

(˜)

(˜) (˜) (˜) (˜)

∈ Ka }}}L