<<

. 21
( 83 .)



>>

subnormalized forms.
(k)
A Levin-type sequence transformation of order k is said to be convex if n (1) = 0 for all n
in N0 . Equivalently, it is convex if {{1}} ∈ Y(k) , i.e., if the transformation vanishes for {{sn }} =
{{c!n }}; c ∈ K. Also, T[ ] is called convex, if T[ (k) ] is convex for all k ∈ N. We will see that
this property is important for ensuring convergence acceleration for linearly convergent sequences.
A given Levin-type transformation T can also be rewritten as
k
(k)
(k)
Tn ({{sn }}; {{!n }}) = n; j (!n ) sn+j ; !n = (!n ; : : : ; !n+k ) (74)
j=0

with
® ’1
(k)
(k) k k
n; j n; j
(k) (k)
° »
n; j (!n ) = ; n; j (!n ) = 1: (75)
!n+j !n+j j=0
j =0

Then, one may deÿne stability indices by
k
(k)
(k)
n (T) = | n; j (!n )|¿1: (76)
j=0

Note that any sequence transformation Q
k
(k)
(k)
Qn = qn; j sn+j (77)
j=0

with
k
(k)
qn; j = 1 (78)
j=0

(k) (k)
can formally be rewritten as a Levin-type sequence transformation according to Qn = Tn ({{sn }};
(k) (k) (k)
{{!n }}) with coe cients n; j = !n+j qn; j n where the validity of Eq. (78) requires to set
k
(k)
(k)
= n; j =!n+j : (79)
n
j=0
94 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147

(k)
If for given k ∈ N and for a transformation T[ ] the following limits exist and have the
values:
—¦ (k)
(k)
lim n; j = j (80)
n’∞
—¦ —¦ (k)
(k)
for all 06j6k, and if is a coe cient set of order k which means that at least the limit k
—¦ —¦ —¦ (k)
—¦
(k) (k)
does not vanish, then a limiting transformation T [ ] exists where = { j }. More explicitly,
we have
—¦ —¦
(k)
] : SK — Y(k) ’ SK
T[
: ({{sn }}; {{!n }}) ’ {{sn }} (81)
with
—¦ (k)
k
j=0 j sn+j =!n+j
—¦ (k)
sn = T ({{sn }}; {{!n }}) = (82)
—¦ (k)
k
j=0 j =!n+j

and
± 
 
k
—¦ (k)
—¦ (k)
{{!n }} ∈ OK :
= j =!n+j =0 for all n ∈ N0 : (83)
Y  
j=0

Obviously, this limiting transformation itself is a Levin-type sequence transformation and automati-
cally is given in subnormalized form.

4.1.1. Variants of Levin-type transformations
For the following, assume that ÿ ¿ 0 is an arbitrary constant, an = sn’1 , and an are Kummer-related
ˆ
to the an with limit or antilimit s (cf. Section 2.2.1).
ˆ
A variant of a Levin-type sequence transformation T is obtained by a particular choice !n . For
!n = fn ({{sn }}), the transformation T is nonlinear in the sn . In particular, we have [50,53,79]:
t Variant:
t
sn’1 = an : t Tn ({{sn }}) = Tn ({{sn }}; {{t !n }}):
(k) (k)
!n = (84)
u Variant:
u
sn’1 = (n + ÿ)an : u Tn (ÿ; {{sn }}) = Tn ({{sn }}; {{u !n }}):
(k) (k)
!n = (n + ÿ) (85)
v Variant:
sn’1 sn an an+1 v (k)
v
: Tn ({{sn }}) = Tn ({{sn }}; {{v !n }}):
(k)
!n = ’ = (86)
2s an ’ an+1
n’1

t˜ Variant:

sn = an+1 : t˜Tn ({{sn }}) = Tn ({{sn }}; {{t˜!n }}):
(k) (k)
!n = (87)
lt Variant:
lt
!n = an : lt Tn ({{sn }}) = Tn ({{sn }}; {{lt !n }}):
(k) (k)
ˆ (88)
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147 95


lu Variant:
lu
!n = (n + ÿ)an : lu Tn (ÿ; {{sn }}) = Tn ({{sn }}; {{lu !n }}):
(k) (k)
ˆ (89)
lv Variant:
an an+1 lv (k)
ˆˆ
lv
: Tn ({{sn }}) = Tn ({{sn }}; {{lv !n }}):
(k)
!n = (90)
an ’ an+1
ˆ ˆ
lt˜ Variant:
lt˜
!n = an+1 : lt˜Tn ({{sn }}) = Tn ({{sn }}; {{lt˜!n }}):
(k) (k)
ˆ (91)
K Variant:
K
!n = sn ’ s: K Tn ({{sn }}) = Tn ({{sn }}; {{K !n }}):
(k) (k)
ˆ ˆ (92)
The K variant of a Levin-type transformation T is linear in the sn . This holds also for the lt, lu,
lv and lt˜ variants.

4.2. Important examples of Levin-type sequence transformations

In this section, we present important Levin-type sequence transformations. For each transformation,
we give the deÿnition, recursive algorithms and some background information.

4.2.1. J transformation
The J transformation was derived and studied by Homeier [35,36,38“ 40,46]. Although the J
transformation was derived by hierarchically consistent iteration of the simple transformation
sn
sn = sn+1 ’ !n+1 ; (93)
!n
it was possible to derive an explicit formula for its kernel as is discussed later. It may be deÿned
via the recursive scheme
Nn(0) = sn =!n ; (0)
Dn = 1=!n ;
Nn(k) = n
(k’1) (k’1) (k) (k’1) (k’1)
Nn ; Dn = n Dn ;
(k) (k)
= Nn(k) =Dn ;
(k)
Jn ({{sn }}; {{!n }}; { n }) (94)
(k)
where the generalized di erence operator deÿned in Eq. (33) involves quantities n = 0 for k ∈
(k)
N0 . Special cases of the J transformation result from corresponding choices of the n . These are
summarized in Table 1.
(k)
Using generalized di erence operators n , we also have the representation [36, Eq. (38)]
(k’1) (k’2) (0)
n n : : : n [sn =!n ]
(k) (k)
Jn ({{sn }}; {{!n }}; {{ n }})
= (k’1) (k’2) : (95)
(0)
n n : : : n [1=!n ]
The J transformation may also be computed using the alternative recursive schemes [36,46]
ˆ (0) ˆ (0)
Dn = 1=!n ; N n = sn =!n ;
ˆ (k) (k’1) ˆ (k’1) ˆ (k’1)
Dn = Dn+1 ’ Dn ; k ∈ N;
n

ˆ (k) (k’1) ˆ (k’1) ˆ (k’1)
Nn = N n+1 ’ Nn ; k ∈ N; (96)
n
96 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147

Table 1
Special cases of the J transformationa
(k) c
b
Case j (n) n


Drummond transformation
(k)
nj
Dn ({{sn }}; {{!n }}) 1
Homeier I transformation
In ( ; {{sn }}; {{!n }}; { (k) })
(k)
n
(2˜)
= exp(2i n);
n
=Jn ({{sn }}; {{e’i n !n }}; { (k) })
(2k)
Eq. (231)
n (2˜+1) (˜)
= exp(’2i n)
n n
Homeier F transformation
n’1 (xj +k)(xj+k+1 +k’1)
x n+k+1 ’x n
F(k) ({{sn }}; {{!n }}; {{x n }}) 1=(x n )j
n x n +k’1 j=0 (xj +k’1)(xj+k+2 +k)
Homeier p J transformation
(k) 1
p Jn (ÿ; {{sn }}; {{!n }}) Eq. (231) (n+ÿ+(p’1)k)2
Levin transformation
L(k) (ÿ; {{sn }}; {{!n }}) (n + ÿ)’j 1
n (n+ÿ)(n+ÿ+k+1)
generalized L transformation
L(k) ( ; ÿ; {{sn }}; {{!n }}) (n+ÿ+k+1) ’(n+ÿ)
(n + ÿ)’j
n (n+ÿ) (n+ÿ+k+1)
Levin-Sidi d(1) transformation
[22,54,77]
(d(1) )(k) ( ; {{sn }}) (Rn + )’j 1 1

n Rn+k+1 + Rn +
Mosig“Michalski algorithm
[60,61]
!n x2k
(k) 1
Mn ({{sn }}; {{!n }}; {{x n }}) Eq. (231) 1’ n+1
x2 !n+1 x2k
n n
Sidi W algorithm
(GREP(1) ) [73,77,78]
Wn(k) ({{sn }}; {{!n }}; {{tn }}) j
tn tn+k+1 ’ tn
Weniger C transformation

<<

. 21
( 83 .)



>>