<<

. 26
( 83 .)



>>

determinantal representations for known j (n) as noted above in the context of the E algorithm. See
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

<<

. 26
( 83 .)



>>