<< Ïðåäûäóùàÿ ñòð. 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:
tËœ
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 ñòð.)ÎÃËÀÂËÅÍÈÅ Ñëåäóþùàÿ >>