<<

. 78
( 83 .)



>>


Wynn™s epsilon algorithm [116] is the following nonlinear recursive scheme:
(n) (n)
= 0; = sn ; n ∈ N0 ; (3.1a)
’1 0

(n) (n+1) (n+1) (n)
= + 1=[ ’ k ]; k; n ∈ N0 : (3.1b)
k+1 k’1 k
(n)
The elements 2k with even subscripts provide approximations to the (generalized) limit s of the
(n)
sequence {sn }∞ to be transformed, whereas the elements 2k+1 with odd subscripts are only auxiliary
n=0
quantities which diverge if the whole process converges.
338 E.J. Weniger / Journal of Computational and Applied Mathematics 122 (2000) 329“356


If the input data are the partial sums (1.4) of the (formal) power series (1.3), sn = fn (z), then
Wynn [116] could show that his epsilon algorithm produces Padà approximants
e
(n)
= [n + k=k]f (z): (3.2)
2k

The epsilon algorithm is a close relative of Aitken™s iterated 2 process, and they have similar
properties in convergence acceleration and summation processes. A straightforward calculation shows
(n) (n) (n)
that A1 = 2 . Hence, Aitken™s iterated 2 process may also be viewed as an iteration of 2 .
(n) (n)
However, for k ¿ 1; Ak and 2k are in general di erent.
There is an extensive literature on the epsilon algorithm. On p. 120 of Wimps book [113] it is
mentioned that over 50 articles on the epsilon algorithm were published by Wynn alone, and at least
30 articles by Brezinski. As a fairly complete source of references Wimp recommends Brezinski™s
ÿrst book [15]. However, this book was published in 1977, and since then many more articles on the
epsilon algorithm have been published. Consequently, any attempt to produce something resembling
a reasonably complete bibliography of Wynn™s epsilon algorithm would clearly be beyond the scope
of this article.
In spite of its numerous advantageous features, Wynn™s epsilon algorithm (3:1) is not suited for
our purposes. If the input data are the partial sums (1.4) of the (formal) power series (1.3), the
accuracy-through-order relationship (1.6) of Padà approximants in combination with (3.2) implies
e
that the elements of the epsilon table with even subscripts can be expressed as
(n) (n)
= fn+2k (z) + g2k z n+2k+1 + O(z n+2k+2 ); z ’ 0: (3.3)
2k
(n)
The constant g2k is the prediction made for the coe cient n+2k+1 , which is the ÿrst coe cient of
(n)
the power series (1.3) not used for the computation of 2k .
(n)
If we compute 2 from the partial sums fn (z); fn+1 (z), and fn+2 (z), we obtain because of
(n) (n)
A1 = 2 the same expressions as in the last section. Thus, we obtain a result which does not seem
to be in agreement with the accuracy-through-order relationship (3.3):
n+2
n+1 n+2 z
(n)
= fn+1 (z) + : (3.4)
2
’ n+2 z
n+1

Of course, the missing term n+2 z n+2 can easily be extracted from the rational expression on the
right-hand side. We only have to use 1=(1 ’ y) = 1 + y=(1 ’ y) with y = n+2 z= n+1 to obtain as in
the case of Aitken™s iterated 2 algorithm an expression with the desired features:
2 n+3
[ n+2 ] z
(n)
= fn+2 (z) + : (3.5)
2
’ n+2 z
n+1

This example shows that the accuracy-through-order relationship (1.6) of Padà approximants is by
e
no means immediately obvious from the epsilon algorithm (3:1). A further complication is that the
(n)
epsilon algorithm involves the elements 2k+1 with odd subscripts. These are only auxiliary quantities
which diverge if the whole process converges. Nevertheless, they make it di cult to obtain order
estimates and to reformulate the epsilon algorithm in such a way that it automatically produces
(n)
suitable expressions for 2k of the type of (3.5).
The starting point for the construction of an alternative recursive scheme, which would be suited
for our purposes, is Wynn™s cross rule [118, Eq. (13)]:
(n) (n+1) ’1 (n+2) (n+1) ’1 (n) (n+1) ’1 (n+2) (n+1) ’1
{ ’ } +{ ’ } ={ ’ } +{ ’ }: (3.6)
2k+2 2k 2k’2 2k 2k 2k 2k 2k
E.J. Weniger / Journal of Computational and Applied Mathematics 122 (2000) 329“356 339

(n)
This expression permits the recursive computation of the elements 2k with even subscripts without
(n)
having to compute the auxiliary quantities 2k+1 with odd subscripts. The price, one has to pay, is that
the cross-rule (3.6) has a more complicated structure than the extremely simple epsilon algorithm
(3:1).
(n)
A further complication is that for k = 0 the undeÿned element ’2 occurs in (3.6). However, we
(n)
obtain results that are consistent with Wynn™s epsilon algorithm (3:1) if we set ’2 = ∞.
Hence, instead of the epsilon algorithm (3:1), we can also use the following recursive scheme:
(n) (n)
= ∞; = sn ; n ∈ N0 ; (3.7a)
’2 0


1
(n) (n+1)
= + ; k; n ∈ N0 : (3.7b)
2k+2 2k (n+1) (n) (n+1) (n+2)
1= ’ 1= 2k + 1=( ’ 2k’2 )
2k 2k

For our purposes, this recursive scheme is an improvement over the epsilon algorithm (3:1) since
(n)
it does not contain the elements 2k+1 with odd subscripts. Nevertheless, it is not yet what we need.
(n)
The use of (3.7) for the computation of 2 would produce (3.4) but not (3.5). Fortunately, (3.7)
can easily be modiÿed to yield a recursive scheme having the desired features:
(n) (n)
= ∞; = sn ; n ∈ N0 ; (3.8a)
’2 0

(n+1) (n) (n+1) (n+1) (n+2)
= ’ =( ’ 2k’2 )
(n) (n+2) 2k 2k 2k 2k
= + ; k; n ∈ N0 : (3.8b)
2k+2 2k (n+1) (n) (n+1) (n+2)
1= ’ 1= 2k + 1=( ’ )
2k 2k 2k’2
(n)
If we use (3:8) for the computation of 2 , we obtain (3.5).
Next, we use in (3:8) the partial sums (1.4) of the (formal) power series (1.3) in the form of
(2.12). This yields
(n) (n)
= f(z) + z n+2k+1 r2k (z); k; n ∈ N0 : (3.9)
2k
(n)
The quantities r2k (z) can be computed with the help of the following recursive scheme which is a
(n)
direct consequence of the recursive scheme (3:8) for 2k :

fn (z) ’ f(z)
(n)
r0 (z) =’ n+ +1 z = ; n ∈ N0 ; (3.10a)
z n+1
=0

(n+1) (n)
r0 (z)= r0 (z)
(n) (n+2)
r2 (z) = r0 (z) + ; n ∈ N0 ; (3.10b)
(n+1) (n)
1= r0 (z) ’ z= r0 (z)
(n+1) (n) (n+1) (n+1) (n+2)
r2k (z)= r2k (z) ’ r2k (z)=(zr2k (z) ’ r2k’2 (z))
(n) (n+2)
r2k+2 (z) = r2k (z) + ; k; n ∈ N0 : (3.10c)
(n+1) (n) (n+1) (n+2)
1= r2k (z) ’ z= r2k (z) + z=(zr2k (z) ’ r2k’2 (z))
(n)
Here, r2k (z) is deÿned by (2:15). It should be noted that (3.10b) follows from (3.10c) if we deÿne
(n)
r’2 (z) = ∞.
Similar to the analogous accuracy-through-order relationship (2.13) for Aitken™s iterated 2 pro-
cess, (3.9) has the right structure to serve as an accuracy-through-order relationship for Wynn™s
epsilon algorithm. Thus, it seems that we have accomplished our aim. However, we are faced with
340 E.J. Weniger / Journal of Computational and Applied Mathematics 122 (2000) 329“356

(n)
the same complications as in the case of (2.13). If z n+2k+1 r2k (z) in (3.9) is to be of order O(z n+2k+1 )
(n) (n)
as z ’ 0, then the z-independent part c2k of r2k (z) deÿned by
(n) (n)
r2k (z) = c2k + O(z); z’0 (3.11)
has to satisfy
(n)
c2k = 0; k; n ∈ N0 : (3.12)
If this condition is satisÿed, we can be sure that (3.9) is indeed the accuracy-through-order relation-
ship we have been looking for.
As in the case of Aitken™s iterated 2 process, it is by no means obvious whether and how it
(n)
can be proven that a given power series gives rise to truncation errors r2k (z) satisfying (3.11) and
(3.12). Fortunately, it can easily be checked numerically whether a given (formal) power series
leads to truncations errors whose z-independent parts are nonzero. If we set z = 0 in (3.10) and use
(3.11), we obtain the following recursive scheme:
(n)
c0 = ’ n+1 ; n ∈ N0 ; (3.13a)
(n+1)
[c0 ]2
(n) (n+2)
c2 = c0 ’ ; n ∈ N0 ; (3.13b)
(n)
c0
(n+1) (n+1)
[c2k ]2 [c2k ]2
(n) (n+2)
c2k+2 = c2k ’ + (n+2) ; k ∈ N; n ∈ N0 : (3.13c)
(n)
c2k c2k’2
(n)
If we deÿne c’2 = ∞, then (3.13b) follows from (3.13c).
Let us now assume that we know for a given (formal) power series that the z-independent parts
(n) (n)
c2k of the truncation errors r2k (z) in (3.9) are nonzero ” either from a mathematical proof or from
a brute force calculation using (3.13). Then, (3.9) is indeed the accuracy-through-order relationship
(n)
we have been looking for. This implies that 2k can be expressed as follows:
(n) (n)
= fn+2k (z) + z n+2k+1 ™2k (z): (3.14)
2k

If we use this ansatz in (3:8), we obtain the following recursive scheme:
(n)
™0 (z) = 0; n ∈ N0 ; (3.15a)
2
[ n+2 ]
(n)
™2 (z) = ; n ∈ N0 ; (3.15b)
’ n+2 z
n+1

(n)
2k+2 (z)
(n) (n+2)
™2k+2 (z) = ™2k (z) + ; k ∈ N; n ∈ N0 ; (3.15c)
(n)
ÿ2k+2 (z)
(n+1) (n+1)
+ ™2k (z) n+2k+2 + ™2k (z)
n+2k+2
(n)
2k+2 (z) = ’ ; (3.15d)
(n) (n+1) (n+2)
n+2k+1 + ™2k (z) n+2k+1 + z™2k (z) ’ ™2k’2 (z)
1 z
(n)
ÿ2k+2 (z) = ’
(n+1) (n)
+ ™2k (z) n+2k+1 + ™2k (z)
n+2k+2
z
+ : (3.15e)
(n+1) (n+2)
+ z™2k (z) ’ ™2k’2 (z)
n+2k+1
E.J. Weniger / Journal of Computational and Applied Mathematics 122 (2000) 329“356 341

(n) (n)
Here, ™2k (z) is deÿned by (2:15). Moreover, we could also deÿne ™’2 (z) = ∞. Then, (3.15b)
would follow from (3.15c).
A comparison of (3.3) and (3.14) yields
(n) (n)
™2k (z) = g2k + O(z); z ’ 0: (3.16)
(n) (n)
Consequently, the z-independent part g2k of ™2k (z) is the prediction for the ÿrst coe cient n+2k+1
(n)
not used for the computation of 2k .
If we set z = 0 in the recursive scheme (3:15) and use (3.16), we obtain the following recursive
(n)
scheme for the predictions g2k :
(n)
g0 = 0; n ∈ N0 ; (3.17a)
2
[ n+2 ]
(n)
g2 = ; n ∈ N0 ; (3.17b)
n+1

(n+1) (n+1)

<<

. 78
( 83 .)



>>