<< Ïðåäûäóùàÿ ñòð. 20(èç 83 ñòð.)ÎÃËÀÂËÅÍÈÅ Ñëåäóþùàÿ >>
nk
m
Ã¿ki
(m; j) k kâˆ’1
s l =s + ( + )[ a l] ; j6l6j + N (49)
l
( l + )i
i=0
k=1

with Â¿ 0; N = m nk and the N +1 unknowns s(m; j) and Ã¿k i . The [ k aj ] are deÃ¿ned via [ 0 aj ]=aj
k=1
k kâˆ’1
aj+1 ] âˆ’ [ kâˆ’1 aj ]; k = 1; 2; : : : . In most cases, all nk are chosen equal and one
and [ aj ] = [
puts = (n; n; : : : ; n). Apart from the value of , only the input of m and of â€˜ is required from the
(m; 0)
user. As transformed sequence, often one chooses the elements s(n; :::; n) for n = 0; 1; : : : . The u variant
of the Levin transformation is obtained for m = 1; = Ã¿ and l = l. The deÃ¿nition above di ers
slightly from the original one [54] and was given in Ref. [22] with = 1.
Ford and Sidi have shown, how these transformations can be calculated recursively with the
W(m) algorithms [22]. The d(m) transformations are the best known special cases of the generalised
Richardson Extrapolation process (GREP) as deÃ¿ned by Sidi [72,73,78].
The d(m) transformations are derived by asymptotic analysis of the remainders sr âˆ’ s for r â†’ âˆž
Ëœ (m)
for the family B of sequences {{ar }} as deÃ¿ned in Ref. [54]. For such sequences, the ar satisfy
a di erence equation of order m of the form
m
k
ar = pk (r) ar : (50)
k=1
90 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147

The pk (r) satisfy the asymptotic relation
âˆž
pkâ€˜
ik
pk (r) âˆ¼ r for r â†’ âˆž: (51)
râ€˜
â€˜=0

The ik are integers satisfying ik 6k for k = 1; : : : ; m. This family of sequences is very large. But still,
Levin and Sidi could prove [54, Theorem 2] that under mild additional assumptions, the remainders
for such sequences satisfy
m âˆž
Ã¿kâ€˜
jk kâˆ’1
sr âˆ’ s âˆ¼ r( ar ) for r â†’ âˆž: (52)
râ€˜
k=1 â€˜=0

The jk are integers satisfying jk 6k for k = 1; : : : ; m. A corresponding result for m = 1 was proven
by Sidi [71, Theorem 6:1].
System (49) now is obtained by truncation of the expansions at â€˜ = nn , evaluation at r = l , and
some further obvious substitutions.
The introduction of suitable l was shown to improve the accuracy and stability in di cult situ-
ations considerably [77].

3.3. Shanks transformation and epsilon algorithm

An important special case of the E algorithm is the choice gj (n) = sn+jâˆ’1 leading to the Shanks
transformation [70]
(k)
En [{{sn }}; {{ sn+jâˆ’1 }}]
ek (sn ) = (k) : (53)
En [{{1}}; {{ sn+jâˆ’1 }}]
Instead of using one of the recursive schemes for the E algorithms, the Shanks transformation may
be implemented using the epsilon algorithm [104] that is deÃ¿ned by the recursive scheme
(n) (n)
= 0; = sn ;
âˆ’1 0
(n) (n+1) (n+1) (n)
= + 1=[ âˆ’ k ]: (54)
k+1 kâˆ’1 k

The relations
(n) (n)
= ek (sn ); = 1=ek ( sn ) (55)
2k 2k+1
(n)
hold and show that the elements 2k+1 are only auxiliary quantities.
The kernel of the Shanks transformation ek is given by sequences of the form
kâˆ’1
sn = s + cj sn+j : (56)
j=0

Additionally, one can use the Shanks transformation â€“ and hence the epsilon algorithm â€“ to
compute the upper-half of the PadÃƒ table according to [70,104]
e
ek (fn (z)) = [n + k=k]f (z) (kÂ¿0; nÂ¿0); (57)
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147 91

where
n
cj z j
fn (z) = (58)
j=0

are the partial sums of a power series of a function f(z). PadÃƒ approximants of f(z) are rational
e
functions in z given as ratio of two polynomials pâ€˜ âˆˆ P and qm âˆˆ P(m) according to
(â€˜)

[â€˜=m]f (z) = pâ€˜ (z)=qm (z); (59)
where the Taylor series of f and [â€˜=m]f are identical to the highest possible power of z, i.e.,
f(z) âˆ’ pâ€˜ (z)=qm (z) = O(z â€˜+m+1 ): (60)
Methods for the extrapolation of power series will be treated later.

3.4. Aitken process
(n) 2
The special case = e1 (sn ) is identical to the famous method of Aitken [2]
2
(sn+1 âˆ’ sn )2
(1)
sn = sn âˆ’ (61)
sn+2 âˆ’ 2sn+1 + sn
with kernel
sn = s + c (sn+1 âˆ’ sn ); n âˆˆ N0 : (62)
2
Iteration of the method yields the iterated Aitken process [14,84,102]
(0)
An = sn ;
(k)
(An+1 âˆ’ An )2
(k)
(k+1) (k)
An = An
âˆ’ (k) : (63)
(k) (k)
An+2 âˆ’ 2An+1 + An
The iterated Aitken process and the epsilon algorithm accelerate linear convergence and can some-
times be applied successfully for the summation of alternating divergent series.

3.5. Overholt process

The Overholt process is deÃ¿ned by the recursive scheme [64]
Vn(0) ({{sn }}) = sn ;
(kâˆ’1)
( sn+kâˆ’1 )k Vn+1 ({{sn }}) âˆ’ ( sn+k )k Vn(kâˆ’1) ({{sn }})
Vn(k) ({{sn }})
= (64)
( sn+kâˆ’1 )k âˆ’ ( sn+k )k
for k âˆˆ N and n âˆˆ N0 . It is important for the convergence acceleration of Ã¿xed point iterations.

4. Levin-type sequence transformations

4.1. DeÃ¿nitions for Levin-type transformations
(k)
A set (k) = { n; j âˆˆ K | n âˆˆ N0 ; 06j6k} is called a coe cient set of order k with k âˆˆ N if
(k)
= { (k) | k âˆˆ N} is called coe cient set. Two coe cient sets
n; k = 0 for all n âˆˆ N0 . Also,
92 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147

(k)
and Ë† = {{ Ë†n; j }} are called equivalent, if for all n and k, there is a constant cn = 0
(k) (k)
= {{ n; j }}
(k)
such that Ë†n; j = cn n; j for all j with 06j6k.
(k) (k)

(k)
For each coe cient set (k) = { n; j |n âˆˆ N0 ; 06j6k} of order k, one may deÃ¿ne a Levin-type
sequence transformation of order k by
(k)
] : SK Ã— Y(k) â†’ SK
T[
(k)
: ({{sn }}; {{!n }}) â†’ {{sn }} = T[ ]({{sn }}; {{!n }}) (65)
with
(k)
k
j=0 n; j sn+j =!n+j
(k)
sn = Tn ({{sn }}; {{!n }}) = (66)
(k)
k
j=0 n; j =!n+j

and
ï£± ï£¼
ï£² ï£½
k
(k)
Y(k) = {{!n }} âˆˆ OK : n; j =!n+j = 0 for all n âˆˆ N0 : (67)
ï£³ ï£¾
j=0

We call T[ ] = {T[ (k) ]| k âˆˆ N} the Levin-type sequence transformation corresponding to the
coe cient set = { (k) | k âˆˆ N}. We write T(k) and T instead of T[ (k) ] and T[ ], respectively,
and Ë† are
(k)
whenever the coe cients n; j are clear from the context. Also, if two coe cient sets
equivalent, they give rise to the same sequence transformation, i.e., T[ ] = T[ Ë† ], since
Ë†(k) sn+j =!n+j (k)
k k
j=0 n; j sn+j =!n+j (k)
for Ë†n; j = cn
n; j
j=0 (k) (k)
= (68)
n
(k) (k)
k
Ë† =!n+j j=0 n; j =!n+j
k
n; j
j=0
(k)
with arbitrary cn = 0.
(k)
The number Tn are often arranged in a two-dimensional table
(0) (1) (2)
T0 T0 T0 Â·Â·Â·
(0) (1) (2)
T1 T1 T1 Â·Â·Â·
(69)
(0) (1) (2)
T2 T2 T2 Â·Â·Â·
. . . ..
. . . .
. . .
that is called the T table. The transformations T(k) thus correspond to columns, i.e., to following
vertical paths in the table. The numerators and denominators such that Tn = Nn(k) =Dn also are
(k) (k)

often arranged in analogous N and D tables.
Note that for Ã¿xed N , one may also deÃ¿ne a transformation
(k)
TN : {{sn+N }} â†’ {{TN }}âˆž : (70)
k=0

This corresponds to horizontal paths in the T table. These are sometimes called diagonals, because
rearranging the table in such a way that elements with constant values of n + k are members of the
(k)
same row, TN for Ã¿xed N correspond to diagonals of the rearranged table.
For a given coe cient set deÃ¿ne the moduli by
(k)
(k)
= max {| n; j |} (71)
n
06j6k
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147 93

and the characteristic polynomials by
k
(k) j
(k) (k) (k)
âˆˆP : n (z) = n; j z (72)
n
j=0

for n âˆˆ N0 and k âˆˆ N.
(k)
Then, T[ ] is said to be in normalized form if n = 1 for all k âˆˆ N and n âˆˆ N0 . Is is said to be
in subnormalized form if for all k âˆˆ N there is a constant Ëœ (k) such that n 6 Ëœ (k) for all n âˆˆ N0 .
(k)

Any Levin-type sequence transformation T[ ] can rewritten in normalized form. To see this, use
(k) (k)
cn = 1= (73)
n

in Eq. (68). Similarly, each Levin-type sequence transformation can be rewritten in (many di erent)
 << Ïðåäûäóùàÿ ñòð. 20(èç 83 ñòð.)ÎÃËÀÂËÅÍÈÅ Ñëåäóþùàÿ >>