<<

. 25
( 83 .)



>>

H(k; M ) (ÿ; {{sn }}; {{!n }}; e) = : (161)
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
( 83 .)



>>