ñòð. 78 |

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 |