<<

. 23
( 83 .)



>>

j
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

<<

. 23
( 83 .)



>>