<<

. 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)

˜=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)

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

See also [14, Theorem 2:18].
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 .)



>>