<<

. 76
( 83 .)



>>




Prediction properties of Aitken™s iterated 2 process, of Wynn™s
epsilon algorithm, and of Brezinski™s iterated theta algorithm
Ernst Joachim Weniger
Institut fur Physikalische und Theoretische Chemie, Universitat Regensburg, D-93040 Regensburg, Germany


Received 15 July 1999; received in revised form 20 October 1999



Abstract
The prediction properties of Aitken™s iterated 2 process, Wynn™s epsilon algorithm, and Brezinski™s iterated theta
algorithm for (formal) power series are analyzed. As a ÿrst step, the deÿning recursive schemes of these transformations
are suitably rearranged in order to permit the derivation of accuracy-through-order relationships. On the basis of these
relationships, the rational approximants can be rewritten as a partial sum plus an appropriate transformation term. A
Taylor expansion of such a transformation term, which is a rational function and which can be computed recursively,
produces the predictions for those coe cients of the (formal) power series which were not used for the computation of
the corresponding rational approximant. c 2000 Elsevier Science B.V. All rights reserved.



1. Introduction

In applied mathematics and in theoretical physics, Padà approximants are now used almost rou-
e
tinely to overcome problems with slowly convergent or divergent power series. Of course, there
is an extensive literature on Padà approximants: In addition to countless articles, there are several
e
textbooks [4,5,8,17,28,41,44,52,73], review articles [3,6,9,24,25,55,119], collections of articles and
proceedings [7,21,29,39,40,42,53,56 “58,78,112,114], bibliographies [14,20,115], and there is even a
book [19] and an article [22], respectively, treating the history of Padà approximants and related
e
topics. A long but by no means complete list of applications of Padà approximants in physics and
e
chemistry can be found in Section 4 of Weniger [100].
The revival of the interest in Padà approximants was initiated by two articles by Shanks [84] and
e
Wynn [116], respectively. These articles, which stimulated an enormous amount of research, were
published in 1956 at a time when electronic computers started to become more widely available.
Shanks [84] introduced a sequence transformation which produces Padà approximants if the input
e

E-mail address: joachim.weniger@chemie.uni-regensburg.de (E.J. Weniger)

0377-0427/00/$ - see front matter c 2000 Elsevier Science B.V. All rights reserved.
PII: S 0 3 7 7 - 0 4 2 7 ( 0 0 ) 0 0 3 6 3 - 0
330 E.J. Weniger / Journal of Computational and Applied Mathematics 122 (2000) 329“356


data are the partial sums of a power series, and Wynn [116] showed that this transformation can
be computed conveniently and e ectively by a recursive scheme now commonly called the epsilon
algorithm. As a consequence of the intense research initiated by Shanks [84] and Wynn [116], the
mathematical properties of Padà approximants are now fairly well understood, and it is generally
e
accepted that Padà approximants are extremely useful numerical tools which can be applied proÿtably
e
in a large variety of circumstances.
This intense research of course also showed that Padà approximants have certain limitations and
e
shortcomings. For example, Padà approximants are in principle limited to convergent and divergent
e
power series and cannot help in the case of many other slowly convergent sequences and series with
di erent convergence types.
The convergence type of numerous practically important sequences {sn }∞ can be classiÿed by
n=0
the asymptotic condition
sn+1 ’ s
lim =; (1.1)
sn ’ s
n’∞

which closely resembles the well-known ratio test for inÿnite series. Here, s = s∞ is the limit of
{sn }∞ as n ’ ∞. A convergent sequence satisfying (1.1) with | | ¡ 1 is called linearly convergent,
n=0
and it is called logarithmically convergent if =1. The partial sums of a power series with a nonzero,
but ÿnite radius of convergence are a typical example of a linearly convergent sequence. The partial
sums of the Dirichlet series for the Riemann zeta function

(m + 1)’z ;
(z) = Re(z) ¿ 1; (1.2)
m=0

which is notorious for its extremely slow convergence if Re(z) is only slightly larger than one, are
a typical example of a logarithmically convergent sequence.
Padà approximants as well as the closely related epsilon algorithm [116] are known to accelerate
e
e ectively the convergence of linearly convergent power series and they are also able to sum many
divergent power series. However, they fail completely in the case of logarithmic convergence (com-
pare for example [117, Theorem 12]). Moreover, in the case of divergent power series whose series
coe cients grow more strongly than factorially, Padà approximants either converge too slowly to
e
be numerically useful [35,86] or are not at all able to accomplish a summation to a unique ÿnite
generalized limit [54]. Consequently, the articles by Shanks [84] and Wynn [116] also stimulated
research on sequence transformations. The rapid progress in this ÿeld is convincingly demonstrated
by the large number of monographs and review articles on sequence transformations which appeared
in recent years [15,16,23,26,43,67,70,94,95,113].
In some, but by no means in all cases, sequence transformations are able to do better than Padà e
approximants, and it may even happen that they clearly outperform Padà approximants. Thus, it may
e
well be worth while to investigate whether it is possible to use instead of Padà approximants more
e
specialized sequence transformations which may be better adapted to the problem under consideration.
For example, the present author used sequence transformations successfully as computational tools
in such diverse ÿelds as the evaluation of special functions [61,63,95,96,99,100,103,106], the eval-
uation of molecular multicenter integrals of exponentially decaying functions [59,90,100,109,111],
the summation of strongly divergent quantum mechanical perturbation expansions [33,34,36,96,98,
100 “102,104,105,107,108], and the extrapolation of quantum chemical ab initio calculations for
E.J. Weniger / Journal of Computational and Applied Mathematics 122 (2000) 329“356 331


oligomers to the inÿnite chain limit of quasi-onedimensional stereoregular polymers [32,100,110]. In
vast majority of these applications, it was either not possible to use Padà approximants at all, or
e
alternative sequence transformations did a better job.
In most practical applications of Padà approximants or also of sequence transformations, the
e
partial sums of (formal) power series are transformed into rational approximants with the intention
of either accelerating convergence or to accomplish a summation to a ÿnite (generalized) limit in the
case of divergence. Padà approximants and sequence transformations are normally not used for the
e
computation of the coe cients of the power series. In the majority of applications, the computation
of the coe cients of power series is not the most serious computational problem, and conventional
methods for the computation of the coe cients usually su ce.
However, in the case of certain perturbation expansions as they for instance occur in high energy
physics, in quantum ÿeld theory, or in quantum chromodynamics, the computational problems can be
much more severe. Not only do these perturbation expansions, which are power series in some cou-
pling constant, diverge quite strongly for every nonzero value of the coupling constant, but it is also
extremely di cult to compute more than just a few of the perturbation series coe cients. Moreover,
due to the complexity of the computations and the necessity of making often drastic approximations,
the perturbation series coe cients obtained in this way are usually a ected by comparatively large
relative errors. Under such adverse circumstances, it has recently become customary to use Padà e
approximants to make predictions about the leading unknown coe cients of perturbation expansions
as well as to make consistency checks for the previously calculated coe cients [27,30,31,46 “50,65,
79 “83,89].
On a heuristic level, the prediction capability of Padà approximants, which was apparently ÿrst
e
used by Gilewicz [51], can be explained quite easily. Let us assume that a function f possesses the
following (formal) power series:

f(z) = z (1.3)
=0

and that we want to transform the sequence of its partial sums
n
fn (z) = z (1.4)
=0

into a doubly indexed sequence of Padà approximants
e
[l=m]f (z) = Pl (z)=Qm (z): (1.5)
As is well known [4,8], the coe cients of the polynomials Pl (z) = p0 + p1 z + · · · + pl z l and
Qm (z) = 1 + q1 z + · · · + qm z m are chosen in such a way that the Taylor expansion of the PadÃ
e
approximant agrees as far as possible with the (formal) power series (1.3):
f(z) ’ Pl (z)=Qm (z) = O(z l+m+1 ); z ’ 0: (1.6)
This accuracy-through-order relationship implies that the Padà approximant to f(z) can be written as
e
the partial sum, from which it was constructed, plus a term which was generated by the transformation
of the partial sum to the rational approximant:
l+m
z + z l+m+1 Pl (z) = fl+m (z) + z l+m+1 Pl (z):
m m
[l=m]f (z) = (1.7)
=0
332 E.J. Weniger / Journal of Computational and Applied Mathematics 122 (2000) 329“356


Similarly, the (formal) power series (1.3) can be expressed as follows:
l+m
z + z l+m+1 Fl+m+1 (z) = fl+m (z) + z l+m+1 Fl+m+1 (z):
f(z) = (1.8)
=0

Let us now assume that the Padà approximant [l=m]f (z) provides a su ciently accurate approxi-
e
m
mation to f(z). Then, the Padà transformation term Pl (z) must also provide a su ciently accurate
e
approximation to the truncation error Fl+m+1 (z) of the (formal) power series. In general, we have no
m
reason to assume that Pl (z) could be equal to Fl+m+1 (z) for ÿnite values of l and m. Consequently,
m
Taylor expansions of Pl (z) and Fl+m+1 (z), respectively, will in general produce di erent results.
m
Nevertheless, the leading coe cients of the Taylor expansion for Pl (z) should provide su ciently
accurate approximations to the corresponding coe cients of the Taylor series for Fl+m+1 (z).
It is important to note that this prediction capability does not depend on the convergence of
m
the power series expansions for Pl (z) and Fl+m+1 (z), respectively. Padà approximants are able to
e
make predictions about series coe cients even if the power series (1.3) for f as well as the power
m
series expansions for Pl and Fl+m+1 (z) are only asymptotic as z ’ 0. This fact explains why the
prediction capability of Padà approximants can be so very useful in the case of violently divergent
e
perturbation expansions.
Let us now assume that a sequence transformation also produces a convergent sequence of rational
approximants if it acts on the partial sums (1.4) of the (formal) power series (1.3). Then, by the
same line of reasoning, these rational approximants should also be able to make predictions about
the leading coe cients of the power series, which were not used for the construction of the rational
approximant. It seems that these ideas were ÿrst formulated by Sidi and Levin [85] and Brezinski
[18]. Recently, these ideas were extended by Prà vost and Vekemans [72] who discussed prediction
e
methods for sequences which they called p and partial Padà prediction, respectively. Moreover, in
e
[105] it was shown that suitably chosen sequence transformations can indeed make more accurate
predictions about unknown power series coe cients than Padà approximants.
e
Consequently, it should be interesting to analyze the prediction properties of sequence transfor-
mations. In this this article, only Aitken™s iterated 2 algorithm, Wynn™s epsilon algorithm and the
iteration of Brezinski™s theta algorithm will be considered. Further studies on the prediction properties
of other sequence transformations are in progress and will be presented elsewhere.
If the prediction properties of sequence transformations are to be studied, there is an additional
complication which is absent in the case of Padà approximants. The accuracy-through-order rela-
e
tionship (1.6) leads to a system of l + m + 1 linear equations for the coe cients of the polynomials
Pl (z) = p0 + p1 z + · · · + pl z l and Qm (z) = 1 + q1 z + · · · + qm z m of the Padà approximant (1.5)
e
[5,8]. If this system of equations has a solution, then it is automatically guaranteed that the Padà e
approximant obtained in this way satisÿes the accuracy-through-order relationship (1.6).
In the case of the sequence transformations considered in this article, the situation is in general
more complicated. These transformations are not deÿned as solutions of systems of linear equations,
but via nonlinear recursive schemes. Moreover, their accuracy-through-order relationships are with
the exception of Wynn™s epsilon algorithm unknown and have to be derived via their deÿning
recursive schemes.
On the basis of these accuracy-through-order relationships, it is possible to construct explicit
recursive schemes for the transformation errors as well as for the ÿrst coe cient of the power series
which was not used for the computation of the rational approximant.
E.J. Weniger / Journal of Computational and Applied Mathematics 122 (2000) 329“356 333


In Section 2, the accuracy-through-order and prediction properties of Aitken™s iterated 2 process
are analyzed. In Section 3, the analogous properties of Wynn™s epsilon algorithm are discussed, and
in Section 4, Brezinski™s iterated theta algorithm is treated. In Section 5, some applications of the
new results are presented. This article is concluded by Section 6 which contains a short summary.

2
2. Aitken™s iterated process

Let us consider the following model sequence:
sn = s + c n ; c = 0; | | = 1; n ∈ N0 : (2.1)
For n ’ ∞, this sequence obviously converges to its limit s if 0 ¡ | | ¡ 1, and it diverges away
from its generalized limit s if | | ¿ 1.
A sequence transformation, which is able to determine the (generalized) limit s of the model
sequence (2.1) from the numerical values of three consecutive sequence elements sn ; sn+1 and sn+2 ,
can be constructed quite easily. Just consider s; c, and as unknowns of the linear system sn+j =
s + c n+j with j = 0; 1; 2. A short calculation shows that
[ s n ]2
(n)
A1 = sn ’ 2 ; n ∈ N0 (2.2)
sn
(n)
is able to determine the (generalized) limit of the model sequence (2.1) according to A1 = s. It
should be noted that s can be determined in this way, no matter whether sequence (2.1) converges or
diverges. The forward di erence operator in (2.2) is deÿned by its action on a function g = g(n):
g(n) = g(n + 1) ’ g(n): (2.3)
The 2 formula (2.2) is certainly one of the oldest sequence transformations. It is usually attributed
to Aitken [1], but it is actually much older. Brezinski [19, pp. 90 “91] mentioned that in 1674
Seki Kowa, the probably most famous Japanese mathematician of that period, tried to obtain better
approximations to with the help of this 2 formula, and according to Todd [91, p. 5] it was in
principle already known to Kummer [66].
There is an extensive literature on Aitken™s 2 process. For example, it was discussed by Lubkin
[68], Shanks [84], Tucker [92,93], Clark et al. [37], Cordellier [38], Jurkat [64], Bell and Phillips
[10], and Weniger [95, Section 5]. A multidimensional generalization of Aitken™s transformation
to vector sequences was discussed by MacLeod [69]. Modiÿcations and generalizations of Aitken™s
2
process were proposed by Drummond [45], Jamieson and O™Beirne [62], BjHrstad et al. [12],

<<

. 76
( 83 .)



>>