<<

. 77
( 83 .)



>>

and Sablonniere [76]. Then, there is a close connection between the Aitken process and Fibonacci
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
( 83 .)



>>