The moduli satisfy n 6( <k=2= ) = ˜ (k) for given k. Consequently, the Levin transformation is given

k

(k)

in subnormalized form. As characteristic polynomial we obtain

k

k

(k)

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

n (z) = (117)

j

j=0

3

Note that the order of indices is di erent from that in the literature.

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

Since n (1) = 0 because k annihilates any polynomial in n with degree less than k, the Levin

(k)

transformation is convex. The limiting transformation is identical to the Drummond transformation

—¦

L(k) ({{sn }}; {{!n }}) = Dn ({{sn }}; {{!n }}):

(k)

(118)

The Levin transformation may be computed using the recursive scheme [21,55,84,14, Section 2:7]

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

Dn = 1=!n ;

(ÿ + n)(ÿ + n + k ’ 1)k’2 (k’1)

(k’1)

Nn(k) = Nn+1 ’ Nn ;

(ÿ + n + k)k’1

(ÿ + n)(ÿ + n + k ’ 1)k’2 (k’1)

(k’1)

(k)

Dn = Dn+1 ’ Dn ;

(ÿ + n + k)k’1

Ln (ÿ; {{sn }}; {{!n }}) = Nn(k) =Dn :

(k) (k)

(119)

This is essentially the same as the recursive scheme (98) for the J transformation with

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

(k)

= ; (120)

n

(ÿ + n + k + 1)k

since the Levin transformation is a special case of the J transformation (see Table 1). Thus, the

Levin transformation can also be computed recursively using scheme (94)

1

(k)

= (121)

n

(n + ÿ)(n + ÿ + k + 1)

or scheme (96) with [46]

(n + ÿ + 1)k’1

(k)

= (n + ÿ + k + 1) : (122)

n

(n + ÿ)k

4.2.4. Weniger transformations

Weniger [84,87,88] derived sequence transformations related to factorial series. These may be

regarded as special cases of the transformation

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

[( [n + ])k’1 sn =!n ]

(k)

Cn ( ; ; {{sn }}; {{!n }}) = : (123)

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

k’1 =!n ]

In particular, the Weniger S transformation may be deÿned as

(k) (k)

Sn (ÿ; {{sn }}; {{!n }}) = Cn (1; ÿ; {{sn }}; {{!n }}) (124)

and the Weniger M transformation as

(k) (k)

Mn ( ; {{sn }}; {{!n }}) = Cn (’1; ; {{sn }}; {{!n }}): (125)

The parameters ÿ, , and are taken to be positive real numbers. Weniger considered the C trans-

formation only for ¿ 0 [87,88] and thus, he was not considering the M transformation as a special

case of the C transformation. He also found that one should choose ¿k ’ 1. In the u variant of

the M transformation he proposed to choose !n = (’n ’ ) sn’1 . This variant is denoted as u M

transformation in the present work.

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

Using the deÿnition (32) of the forward di erence operator, the coe cients may be taken as

k

(k)

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

n; j

j

in the case of the C transformation, as

k

(k)

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

n; j

j

in the case of the S transformation, and as

k

(k)

= (’1) j (’n ’ ’ j)k’1 =(’n ’ ’ k)k’1 (128)

n; j

j

in the case of the M transformation.

The S transformation in (124) may be computed using the recursive scheme (98) with [84,

Section 8:3]

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

(k)

= : (129)

n

(ÿ + n + 2k)(ÿ + n + 2k ’ 1)

The M transformation in (125) may be computed using the recursive scheme (98) with [84, Section

9:3]

+n’k +1

(k)

= : (130)

n

+n+k +1

The C transformation in (123) may be computed using the recursive scheme (98) with [87, Eq.

(3:3)]

( [n + + k ’ 1])k’2

(k)

= ( [ + n] + k ’ 2) : (131)

n

( [n + + k])k’1

Since the operator k for k ∈ N annihilates all polynomials in n of degree smaller than k,

the transformations S; M, and C are convex. The moduli satisfy n 6( <k=2= ) = ˜ (k) for given k.

k

(k)

Consequently, the three Weniger transformations are given in subnormalized form.

For ’ ∞, the Levin transformation is obtained from the C transformation [87]. The S trans-

formation is identical to the 3 J transformation. It is also the special case x n = n + ÿ of the F

transformation. Analogously, the C transformation is obtained for x n = [ + n]. All these Weniger

transformations are special cases of the J transformation (cf Table 1).

The limiting transformation of all these Weniger transformations is the Drummond transformation.

4.2.5. Levin“Sidi transformations and W algorithms

As noted above in Section 3.2, the d(m) transformations were introduced by Levin and Sidi [54]

as a generalization of the u variant of the Levin transformation, and these transformations may

implemented recursively using the W(m) algorithms.

The case m = 1 corresponding to the d(1) transformation and the W(1) = W algorithm is relevant

for the present survey of Levin-type transformations. In the following, the kth-order transformation

T(k) of Levin-type transformation T as given by the W algorithm is denoted by W (k) which should

not be confused with the W(m) algorithms of Ford and Sidi [22].

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

The W algorithm [73] was also studied by other authors [84, Section 7:4], [14, p. 71f, 116f]

and may be regarded as a special case of the J transformation [36]. It may be deÿned as (cf [78,

Theorems 1:1 and 1:2])

sn 1

Nn(0) = (0)

; Dn = ;

!n !n

(k’1)

Nn+1 ’ Nn(k’1)

Nn(k) = ;

tn+k ’ tn

(k’1) (k’1)

Dn+1 ’ Dn

(k)

Dn = ;

tn+k ’ tn

Wn(k) ({{sn }}; {{!n }}; {{tn }}) = Nn(k) =Dn

(k)

(132)

and computes

(k)

n (sn =!n )

Wn(k) ({{sn }}; {{!n }}; {{tn }}) = ; (133)

(k)

n (1=!n )

(k) (k)

where the divided di erence operators n = n [{{tn }}] are used. The W algorithm may be used

to calculate the Levin transformation on putting tn = 1=(n + ÿ). Some authors call a linear variant

of the W algorithm with !n = (’1)n+1 e’n q tn the W transformation, while the t˜ variant of the W

algorithm [74,75] is sometimes called mW transformation [31,57,60].

—¦

If tn+1 =tn ’ for large n, one obtains as limiting transformation the J transformation with j = ’j

and characteristic polynomial

k’1

—¦

(k) j

(z) = (z= ’ 1): (134)

j=0

For the d(1) transformation, we write

(d(1) )n ( ; {{sn }}; {{ n }}) = Wn(k) ({{s n }}; {{(

(k)

+ )(s n ’ s )}}; {{1=( + )}}): (135)

n n ’1 n

Thus, it corresponds to the variant of the W algorithm with remainder estimates chosen as ( n +

)(s n ’ s n ’1 ) operating on the subsequence {{s n }} of {{sn }} with tn = 1=( n + ). It should be

noted that this is not(!) identical to the u variant

u

Wn(k) ({{s n }}; {{1=( + )}}) = Wn(k) ({{s n }}; {{u !n }}; {{1=( + )}}); (136)

n n

neither for u !n = (n + )(s n ’ s n’1 ) nor for u !n = ( n + )(s n ’ s n’1 ), since the remainder estimates

are chosen di erently in Eq. (135).

The d(1) transformation was thoroughly analyzed by Sidi (see [77,78] and references therein).

4.2.6. Mosig“Michalski transformation

The Mosig“Michalski transformation ” also known as “weighted“averages algorithm” ” was

introduced by Mosig [61] and modiÿed later by Michalski who gave the t˜ variant of the transforma-

tion the name K transformation (that is used for a di erent transformation in the present article(!)),

and applied it to the computation of Sommerfeld integrals [60].

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

The Mosig“Michalski transformation M may be deÿned via the recursive scheme

(0)

s n = sn ;

(k) (k)

(k)

sn + Án sn+1

(k+1)

sn = ;

(k)

1 + Án

Mn(k) ({{sn }}; {{!n }}; {{x n }}) = sn

(k)

(137)

for n ∈ N0 and k ∈ N0 where {{x n }} is an auxiliary sequence with limn’∞ 1=x n = 0 such that

x n+˜ ¿ x n for ˜ ∈ N0 and x0 ¿ 1, i.e., a diverging sequence of monotonously increasing positive

numbers, and

2k

!n x n+1

(k)

Án =’ : (138)

!n+1 xn

Putting !n = !n =x2k ; Nn(k) = sn =!n , and Dn = 1=!n , it is easily seen that the recursive scheme

(k) (k) (k) (k) (k)

n

(137) is equivalent to the scheme (94) with

!n x2k

1 n+1

(k)

=2 1’ : (139)

n

xn !n+1 x2k

n

Thus, the Mosig“Michalski transformation is a special case of the J transformation. Its character

(k)

(k)

as a Levin-type transformation is somewhat formal since the n and, hence, the coe cients n; j

depend on the !n .

If x n+1 =x n ∼ ¿ 1 for large n, then a limiting transformation exists, namely M ({{sn }}; {{!n }};

—¦

{{ n+1 }}). It corresponds to the J transformation with 2k

= . This may be seen by putting

k

Dn = 1=!n ; Nn(k) = sn Dn and n = 2k in Eq. (96).

(k) (k) (k) (k)

4.2.7. F transformation

This transformation is seemingly new. It will be derived in a later section. It may be deÿned as

(k) (k)

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

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