ñòð. 77 |

numbers, as discussed by McCabe and Phillips [71] and Arai et al. [2]. The properties of Aitkenâ€™s

2

process are also discussed in books by Baker and Graves-Morris [8], Brezinski [15,16], Brezinski

and Redivo Zaglia [26], Delahaye [43], Walz [94], and Wimp [113].

The power of Aitkenâ€™s 2 process is of course limited since it is designed to eliminate only a

single exponential term. However, its power can be increased considerably by iterating it, yielding

the following nonlinear recursive scheme:

(n)

A0 = sn ; n âˆˆ N0 ; (2.4a)

(n)

[ A k ]2

(n) (n)

Ak+1 = Ak âˆ’ ; k; n âˆˆ N0 : (2.4b)

2 A(n)

k

334 E.J. Weniger / Journal of Computational and Applied Mathematics 122 (2000) 329â€“356

(n)

In the case of doubly indexed quantities like Ak , it will always be assumed that the di erence

operator only acts on the superscript n but not on the subscript k:

(n) (n+1) (n)

Ak = Ak âˆ’ Ak : (2.5)

The numerical performance of Aitkenâ€™s iterated 2 process was studied in [88,95]. Concerning

the theoretical properties of Aitkenâ€™s iterated 2 process, very little seems to be known. Hillion [60]

was able to Ã¿nd a model sequence for which the iterated 2 process is exact. He also derived a

(n) (n)

determinantal representation for Ak . However, Hillionâ€™s expressions for Ak contain explicitly the

(n) (n) (n+k) (n+k)

lower order transforms A0 ; : : : ; Akâˆ’1 ; : : : ; A0 ; : : : ; Akâˆ’1 . Consequently, it seems that Hillionâ€™s

result [60] â€” although interesting from a formal point of view â€” cannot help much to analyze the

(n)

prediction properties of Ak .

If we want to use Aitkenâ€™s iterated 2 process for the prediction of unknown series coe cients,

we Ã¿rst have to derive its accuracy-through-order relationship of the type of (1.6) on the basis of

the recursive scheme (2:4).

It is a direct consequence of the recursive scheme (2:4) that 2k + 1 sequence elements sn ; sn+1 ; : : : ;

(n)

sn+2k are needed for the computation of Ak . Thus, we now choose as input data the partial sums

(1.4) of the (formal) power series (1.3) according to sn = fn (z), and conjecture that all coe cients

(n)

0 ; 1 ; : : : ; n+2k , which were used for the construction of Ak , are exactly reproduced by a

Taylor expansion. This means that we have to look for an accuracy-through-order relationship of the

following kind:

(n)

f(z) âˆ’ Ak = O(z n+2k+1 ); z â†’ 0: (2.6)

(n)

Such an accuracy-through-order relationship would imply that Ak can be expressed as follows:

(n) (n)

Ak = fn+2k (z) + Gk z n+2k+1 + O(z n+2k+2 ); z â†’ 0: (2.7)

(n)

The constant Gk 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 Ak .

Unfortunately, the recursive scheme (2:4) is not suited for our purposes. This can be shown by

(n)

computing A1 from the partial sums fn (z); fn+1 (z), and fn+2 (z):

2 n+1

[ n+1 ] z

(n)

A1 = fn (z) + : (2.8)

n+1 âˆ’ n+2 z

(n)

SuperÃ¿cially, it looks as if A1 is not of the type of (2.7). However, the rational expression on the

right-hand side contains the missing terms n+1 z n+1 and n+2 z n+2 . We only have to use 1=(1 âˆ’ y) =

1 + y + y2 =(1 âˆ’ y) with y = n+2 z= n+1 to obtain an equivalent expression with the desired features:

2 n+3

[ n+2 ] z

(n)

A1 = fn+2 (z) + : (2.9)

âˆ’ n+2 z

n+1

Thus, an expression, which is in agreement with (2.7), can be obtained easily in the case of the

(n) (n)

simplest transform A1 . Moreover, (2.9) makes the prediction G1 = [ n+2 ]2 = n+1 for the Ã¿rst series

(n)

coe cient n+3 not used for the computation of A1 . Of course, by expanding the denominator

on the right-hand side of (2.9) further predictions on series coe cients with higher indices can be

made.

(n)

In the case of more complicated transforms Ak with k Â¿ 1, it is by no means obvious whether

and how the necessary manipulations, which would transform an expression of the type of (2.8)

E.J. Weniger / Journal of Computational and Applied Mathematics 122 (2000) 329â€“356 335

into an expression of the type of (2.9), can be done. Consequently, it is advantageous to replace

the recursive scheme (2:4) by an alternative recursive scheme, which directly leads to appropriate

(n)

expressions for Ak with k Â¿ 1.

(n)

Many di erent expressions for A1 in terms of sn ; sn+1 , and sn+2 are known [95, Section 5.1].

These expressions are all mathematically equivalent although their numerical properties may di er.

Comparison with (2.9) shows that the for our purposes appropriate expression is [95, Eq. (5:1-7)]

[ sn+1 ]2

(n)

A1 = sn+2 âˆ’ : (2.10)

2s

n

Just like (2.2), this expression can be iterated and yields

(n)

A0 = sn ; n âˆˆ N0 ; (2.11a)

(n+1)

[ Ak ]2

(n) (n+2)

Ak+1 = Ak âˆ’ ; k; n âˆˆ N0 : (2.11b)

2 A(n)

k

The recursive schemes (2:4) and (2:11) are mathematically completely equivalent. However, for our

purposes â€” the analysis of the prediction properties of Aitkenâ€™s iterated 2 process in the case of

power series â€” the recursive scheme (2:11) is much better suited.

Next, we rewrite the partial sums (1.4) of the (formal) power series (1.3) according to

âˆž

n+ +1

fn (z) = f(z) âˆ’ n+ +1 z (2.12)

=0

and use them as input data in the recursive scheme (2:11). This yields the following expression:

(n) (n)

Ak = f(z) + z n+2k+1 Rk (z); k; n âˆˆ N0 : (2.13)

(n)

The quantities Rk (z) can be computed with the help of the following recursive scheme which is a

(n)

direct consequence of the recursive scheme (2:11) for Ak :

âˆž

fn (z) âˆ’ f(z)

(n)

R0 (z) =âˆ’ n+ +1 z = ; n âˆˆ N0 ; (2.14a)

z n+1

=0

(n+1)

[ Rk (z)]2

(n) (n+2)

Rk+1 (z) = Rk (z) âˆ’ ; k; n âˆˆ N0 : (2.14b)

2 R(n) (z)

k

In (2:14), we use the shorthand notation

Xk(n) (z) = zXk(n+1) (z) âˆ’ Xk(n) (z); (2.15a)

Xk(n) (z) = z Xk(n+1) (z) âˆ’ Xk(n) (z)

2

= z 2 Xk(n+2) (z) âˆ’ 2zXk(n+1) (z) + Xk(n) (z): (2.15b)

It seems that we have now accomplished our aim since (2.13) has the right structure to serve as an

accuracy-through-order relationship for Aitkenâ€™s iterated 2 process. Unfortunately, this conclusion

is in general premature and we have to require that the input data satisfy some additional conditions.

One must not forget that Aitkenâ€™s 2 formula (2.10) as well as its iteration (2:11) cannot be applied

to arbitrary input data. One obvious potential complication, which has to be excluded, is that (2.11b)

336 E.J. Weniger / Journal of Computational and Applied Mathematics 122 (2000) 329â€“356

(n)

becomes undeÃ¿ned if 2 Ak =0. Thus, if we want to transform the partial sums (1.4) of the (formal)

power series (1.3), it is natural to require that all series coe cients are nonzero, i.e., = 0 for all

âˆˆ N0 .

Unfortunately, this is only a minimal requirement and not yet enough for our purposes. If

n+2k+1 (n) (n)

Rk (z) in (2.13) is to be of order O(z n+2k+1 ) as z â†’ 0, then the z-independent part Ck

z

(n)

of Rk (z) deÃ¿ned by

(n) (n)

Rk (z) = Ck + O(z); z â†’ 0; (2.16)

has to satisfy

(n)

Ck = 0; k; n âˆˆ N0 : (2.17)

If these conditions are satisÃ¿ed, we can be sure that (2.13) is indeed the accuracy-through-order

relationship we have been looking for.

Personally, I am quite sceptical that it would be easy to characterize theoretically those power

(n)

series which give rise to truncation errors Rk (z) satisfying (2.16) and (2.17). Fortunately, it can

easily be checked numerically whether a given (formal) power series leads to truncation errors whose

z-independent parts are nonzero. If we set z = 0 in (2:14) and use (2.16), we obtain the following

recursive scheme:

(n)

C0 = âˆ’ n+1 ; n âˆˆ N0 ; (2.18a)

(n+1)

[Ck ]2

(n) (n+2)

Ck+1 = Ck âˆ’ ; k; n âˆˆ N0 : (2.18b)

(n)

Ck

Let us now assume that we know for a given (formal) power series that the z-independent parts

(n) (n)

Ck of the truncation errors Rk (z) in (2.13) are nonzero â€” either from a mathematical proof

or from a brute force calculation using (2:18). Then, (2.13) is indeed the accuracy-through-order

(n)

relationship we have been looking for, which implies that Ak can be expressed as follows:

(n) (n)

Ak = fn+2k (z) + z n+2k+1 k (z); k; n âˆˆ N0 : (2.19)

If we use this ansatz in (2:11), we obtain the following recursive scheme:

(n)

0 (z) = 0; n âˆˆ N0 ; (2.20a)

(n+1)

(z)]2

[ +

n+2k+2

(n) (n+2) k

k+1 (z) = (z) âˆ’ ; k; n âˆˆ N0 : (2.20b)

k 2 (n) (z)

n+2k+2 z âˆ’ n+2k+1 + k

(n) (n)

2

Here, k (z) and k (z) are deÃ¿ned by (2:15). For k = 0, (2.20b) yields

2

[ n+2 ]

(n)

1 (z) = ; (2.21)

âˆ’ n+2 z

n+1

which is in agreement with (2.9).

A comparison of (2.7) and (2.19) yields

(n) (n)

k (z) = Gk + O(z); z â†’ 0: (2.22)

(n) (n)

Consequently, the z-independent part Gk of k (z) is the prediction for the Ã¿rst coe cient n+2k+1

(n)

not used for the computation of Ak .

E.J. Weniger / Journal of Computational and Applied Mathematics 122 (2000) 329â€“356 337

If we set z = 0 in the recursive scheme (2:20) and use (2.22), we obtain the following recursive

(n)

scheme for the predictions Gk :

(n)

G0 = 0; n âˆˆ N0 ; (2.23a)

(n) 2

G1 = [ n+2 ] = n+1 ; n âˆˆ N0 ; (2.23b)

(n+1)

âˆ’ G k ]2

[ n+2k+2

(n) (n+2)

Gk+1 = Gk + ; k; n âˆˆ N0 : (2.23c)

(n)

âˆ’ Gk

n+2k+1

(n) (n) (n) (n)

The z-independent parts Ck of Rk (z) and Gk of k (z), respectively, are connected. A com-

parison of (2.13), (2.16), (2.19), and (2.22) yields

(n) (n)

Gk = Ck + n+2k+1 : (2.24)

In this article, rational approximants will always be used in such a way that the input data â€” the

partial sums (1.4) of the (formal) power series (1.3) â€” are computed in an outer loop, and for each

new partial sum a new approximation to the limit is calculated. If the index m of the last partial

sum fm (z) is even, m = 2 , we use in the case of Aitkenâ€™s iterated 2 process as approximation to

the limit f(z) the transformation

{f0 (z); f1 (z); : : : ; f2 (z)} â†’ A(0) ; (2.25)

and if m is odd, m = 2 + 1, we use the transformation

â†’ A(1) :

{f1 (z); f2 (z); : : : ; f2 +1 (z)} (2.26)

With the help of the notation <x= for the integral part of x, which is the largest integer satisfying

the inequality 6x, these two relationships can be combined into a single equation, yielding [95,

Eq. (5:2â€“6)]

(mâˆ’2<m=2=)

{fmâˆ’2<m=2= (z); fmâˆ’2<m=2=+1 (z); : : : ; fm (z)} â†’ A<m=2= ; m âˆˆ N0 : (2.27)

(n)

The same strategy will also be used if for example the rational expressions Rk (z) deÃ¿ned by

(n)

(2.13) are listed in a table. This means that the Rk (z) will also be listed according to (2.27). The

(n)

only di erence is that the Rk (z) use as input data not the partial sums fn (z) but the remainders

[fn (z) âˆ’ f(z)]=z n+1 .

3. Wynnâ€™s epsilon algorithm

ñòð. 77 |