ñòð. 76 |

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 |