ñòð. 18 |

transformations, Comput. Phys. Comm. 116 (1999) 28â€“54.

[35] K. Jbilou, H. Sadok, Vector extrapolation methods, Applications and numerical comparison, this volume, J. Comput.

Appl. Math. 122 (2000) 149â€“165.

[36] W.B. Jones, W. Thron, in: G.-C. Rota (Ed.), Continued Fractions, Encyclopedia of Mathematics and its Applications,

Vol. 11, Addison-Wesley, Reading, MA, USA, 1980.

[37] J.B. McLeod, A note on the -algorithm, Computing 7 (1972) 17â€“24.

[38] D.E. Roberts, Cli ord algebras and vector-valued rational forms I, Proc. Roy. Soc. London A 431 (1990) 285â€“300.

[39] D.E. Roberts, On the convergence of rows of vector PadÃƒ approximants, J. Comput. Appl. Math. 70 (1996) 95â€“109.

e

[40] D.E. Roberts, On a vector q-d algorithm, Adv. Comput. Math. 8 (1998) 193â€“219.

[41] D.E. Roberts, A vector Chebyshev algorithm, Numer. Algorithms 17 (1998) 33â€“50.

[42] D.E. Roberts, On a representation of vector continued fractions, J. Comput. Appl. Math. 105 (1999) 453â€“466.

[43] A. Salam, An algebraic approach to the vector -algorithm, Numer. Algorithms 11 (1996) 327â€“337.

[44] A. Salam, Formal vector orthogonal polynomials, Adv. Comput. Math. 8 (1998) 267â€“289.

[45] A. Salam, What is a vector Hankel determinant? Linear Algebra Appl. 278 (1998) 147â€“161.

80 P.R. Graves-Morris et al. / Journal of Computational and Applied Mathematics 122 (2000) 51â€“80

[46] A. Salam, PadÃƒ -type approximants and vector PadÃƒ approximants, J. Approx. Theory 97 (1999) 92â€“112.

e e

[47] D. Shanks, Non-linear transformations of divergent and slowly convergent sequences, J. Math. Phys. 34 (1955) 1â€“42.

[48] A. Sidi, W.F. Ford, D.A. Smith, SIAM J. Numer. Anal. 23 (1986) 178â€“196.

[49] R.C.E. Tan, Implementation of the topological epsilon algorithm, SIAM J. Sci. Statist. Comput. 9 (1988) 839â€“848.

[50] E.J. Weniger, Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent

series, Comput. Phys. Rep. 10 (1989) 371â€“1809.

[51] E.J. Weniger, A convergent, renormalised strong coupling perturbation expansion for the ground state energy of the

quartic, sextic and octic anharmonic oscillator, Ann. Phys. 246 (1996) 133â€“165.

E.J. Weniger, Prediction properties of Aitkenâ€™s iterated 2 process, of Wynnâ€™s epsilon algorithm and of Brezinskiâ€™s

[52]

iterated theta algorithm, this volume, J. Comp. Appl. Math. 122 (2000) 329â€“356.

[53] J. Wimp, Sequence Transformations and Their Applications, Academic Press, New York, 1981.

[54] P. Wynn, On a device for calculating the em (Sn ) transformations, Math. Tables Automat. Comp. 10 (1956) 91â€“96.

[55] P. Wynn, The epsilon algorithm and operational formulas of numerical analysis, Math. Comp. 15 (1961) 151â€“158.

[56] P. Wynn, Lâ€™ -algoritmo e la tavola di PadÃƒ , Rendi. Mat. Roma 20 (1961) 403â€“408.

e

[57] P. Wynn, Acceleration techniques for iterative vector problems, Math. Comp. 16 (1962) 301â€“322.

[58] P. Wynn, Continued fractions whose coe cients obey a non-commutative law of multiplication, Arch. Rational

Mech. Anal. 12 (1963) 273â€“312.

[59] P. Wynn, On the convergence and stability of the epsilon algorithm, SIAM J. Numer. Anal. 3 (1966) 91â€“122.

Journal of Computational and Applied Mathematics 122 (2000) 81â€“147

www.elsevier.nl/locate/cam

Scalar Levin-type sequence transformations

Herbert H.H. Homeier âˆ—; 1

Institut fur Physikalische und Theoretische Chemie, Universitat Regensburg, D-93040 Regensburg, Germany

Received 7 June 1999; received in revised form 15 January 2000

Abstract

Sequence transformations are important tools for the convergence acceleration of slowly convergent scalar sequences

or series and for the summation of divergent series. The basic idea is to construct from a given sequence {{sn }} a

new sequence {{sn }} = T({{sn }}) where each sn depends on a Ã¿nite number of elements sn1 ; : : : ; snm . Often, the sn

are the partial sums of an inÃ¿nite series. The aim is to Ã¿nd transformations such that {{sn }} converges faster than (or

sums) {{sn }}. Transformations T({{sn }}; {{!n }}) that depend not only on the sequence elements or partial sums sn

but also on an auxiliary sequence of the so-called remainder estimates !n are of Levin-type if they are linear in the sn ,

and nonlinear in the !n . Such remainder estimates provide an easy-to-use possibility to use asymptotic information on

the problem sequence for the construction of highly e cient sequence transformations. As shown Ã¿rst by Levin, it is

possible to obtain such asymptotic information easily for large classes of sequences in such a way that the !n are simple

functions of a few sequence elements sn . Then, nonlinear sequence transformations are obtained. Special cases of such

Levin-type transformations belong to the most powerful currently known extrapolation methods for scalar sequences and

series. Here, we review known Levin-type sequence transformations and put them in a common theoretical framework.

It is discussed how such transformations may be constructed by either a model sequence approach or by iteration of

simple transformations. As illustration, two new sequence transformations are derived. Common properties and results

on convergence acceleration and stability are given. For important special cases, extensions of the general results are

presented. Also, guidelines for the application of Levin-type sequence transformations are discussed, and a few numerical

examples are given. c 2000 Elsevier Science B.V. All rights reserved.

MSC: 65B05; 65B10; 65B15; 40A05; 40A25; 42C15

Keywords: Convergence acceleration; Extrapolation; Summation of divergent series; Stability analysis; Hierarchical

consistency; Iterative sequence transformation; Levin-type transformations; Algorithm; Linear convergence; Logarithmic

convergence; Fourier series; Power series; Rational approximation

âˆ—

Fax: +49-941-943-4719.

E-mail address: herbert.homeier@na-net.ornl.gov (H.H.H. Homeier)

1

WWW: http:==www.chemie.uni-regensburg.de= âˆ¼hoh05008

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 5 9 - 9

82 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147

1. Introduction

In applied mathematics and the numerate sciences, extrapolation methods are often used for the

convergence acceleration of slowly convergent sequences or series and for the summation of divergent

series. For an introduction to such methods, and also further information that cannot be covered here,

see the books of Brezinski and Redivo Zaglia [14] and Wimp [102] and the work of Weniger [84,88]

and Homeier [40], but also the books of Baker [3], Baker and Graves-Morris [5], Brezinski [7,8,10

â€“12], Graves-Morris [24,25], Graves-Morris, Sa and Varga [26], Khovanskii [52], Lorentzen and

Waadeland [56], Nikishin and Sorokin [62], Petrushev and Popov [66], Ross [67], Sa and Varga

[68], Wall [83], Werner and Buenger [101] and Wuytack [103].

For the discussion of extrapolation methods, one considers a sequence {{sn }} = {{s0 ; s1 ; : : :}} with

elements sn or the terms an = sn âˆ’ snâˆ’1 of a series âˆž aj with partial sums sn = n aj for large

j=0 j=0

n. A common approach is to rewrite sn as

sn = s + Rn ; (1)

where s is the limit (or antilimit in the case of divergence) and Rn is the remainder or tail. The aim

then is to Ã¿nd a new sequence {{sn }} such that

sn = s + Rn ; Rn =Rn â†’ 0 for n â†’ âˆž: (2)

Thus, the sequence {{sn }} converges faster to the limit s (or diverges less violently) than {{sn }}.

To Ã¿nd the sequence {{sn }}, i.e., to construct a sequence transformation {{sn }} = T({{sn }}),

one needs asymptotic information about the sn or the terms an for large n, and hence about the

Rn . This information then allows to eliminate the remainder at least asymptotically, for instance by

substracting the dominant part of the remainder. Either such information is obtained by a careful

mathematical analysis of the behavior of the sn and=or an , or it has to be extracted numerically from

the values of a Ã¿nite number of the sn and=or an by some method that ideally can be proven to

work for a large class of problems.

Suppose that one knows quantities !n such that Rn =!n = O(1) for n â†’ âˆž, for instance

lim Rn =!n = c = 0; (3)

nâ†’âˆž

where c is a constant. Such quantities are called remainder estimates. Quite often, such remainder

estimates can be found with relatively low e ort but the exact value of c is often quite hard to

calculate. Then, it is rather natural to rewrite the rest as Rn = !n n where n â†’ c. The problem is

how to describe or model the n . Suppose that one has a system of known functions j (n) such that

âˆ’j

0 (n) = 1 and j+1 = o( j (n)) for j âˆˆ N0 . An example of such a system is j (n) = (n + Ã¿) for some

Ã¿ âˆˆ R+ . Then, one may model n as a linear combination of the j (n) according to

âˆž

âˆ¼ cj j (n) for n â†’ âˆž; (4)

n

j=0

whence the problem sequence is modelled according to

âˆž

sn âˆ¼ s + ! n cj j (n): (5)

j=0

H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147 83

The idea now is to eliminate the leading terms of the remainder with the unknown constants cj up

to j = k âˆ’ 1, say. Thus, one uses a model sequence with elements

kâˆ’1

= + !m cj j (m); m âˆˆ N0 (6)

m

j=0

and calculates exactly by solving the system of k + 1 equations resulting for m = n; n + 1; : : : ; n + k

for the unknowns and cj , j = 0; : : : ; k âˆ’ 1. The solution for is a ratio of determinants (see below)

and may be denoted symbolically as

= T ( n; : : : ; n+k ; !n ; : : : ; !n+k ; j (n); : : : ; j (n + k)): (7)

The resulting sequence transformation is

(k)

T({{sn }}; {{!n }}) = {{Tn ({{sn }}; {{!n }})}} (8)

with

(k)

Tn ({{sn }}; {{!n }}) = T (sn ; : : : ; sn+k ; !n ; : : : ; !n+k ; j (n); : : : ; j (n + k)): (9)

It eliminates the leading terms of the asymptotic expansion (5). The model sequences (6) are in the

kernel of the sequence transformation T, deÃ¿ned as the set of all sequences such that T reproduces

their (anti)limit exactly.

A somewhat more general approach is based on model sequences of the form

k

= + cj gj (n); n âˆˆ N0 ; k âˆˆ N: (10)

n

j=1

Virtually all known sequence transformations can be derived using such model sequences. This

leads to the E algorithm as described below in Section 3.1. Also, some further important examples

of sequence transformations are described in Section 3.

However, the introduction of remainder estimates proved to be an important theoretical step since

it allows to make use of asymptotic information of the remainder easily. The most prominent of the

resulting sequence transformations T({{sn }}; {{!n }}) is the Levin transformation [53] that corre-

sponds to the asymptotic system of functions given by j (n) = (n + Ã¿)âˆ’j , and thus, to Poincare-type

expansions of the n . But also other systems are of importance, like j (n) = 1=(n + Ã¿)j leading to

j

factorial series, or j (n) = tn corresponding to Taylor expansions of t-dependent functions at the

abscissae tn that tend to zero for large n. The question which asymptotic system is best, cannot

be decided generally. The answer to this question depends on the extrapolation problem. To obtain

e cient extrapolation procedures for large classes of problems requires to use various asymptotic

systems, and thus, a larger number of di erent sequence transformations. Also, di erent choices of

!n lead to di erent variants of such transformations. Levin [53] has pioneered this question and

introduced three variants that are both simple and rather successful for large classes of problems.

These variants and some further ones will be discussed. The question which variant is best, also

84 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147

cannot be decided generally. There are, however, a number of results that favor certain variants for

certain problems. For example, for Stieltjes series, the choice !n = an+1 can be theoretically justiÃ¿ed

(see Appendix A).

Thus, we will focus on sequence transformations that involve an auxiliary sequence {{!n }}.

(k)

To be more speciÃ¿c, we consider transformations of the form T({{sn }}; {{!n }}) = {{Tn }}

with

(k)

k

j=0 n; j sn+j =!n+j

(k)

Tn = : (11)

(k)

k

=!n+j

j=0 n; j

This will be called a Levin-type transformations. The known sequence transformations that involve

remainder estimates, for instance the C; S, and M transformations of Weniger [84], the W al-

gorithm of Sidi [73], and the J transformation of Homeier with its many special cases like the

important p J transformations [35,36,38â€“ 40,46], are all of this type. Interestingly, also the H; I,

and K transformations of Homeier [34,35,37,40 â€“ 44] for the extrapolation of orthogonal expan-

sions are of this type although the !n in some sense cease to be remainder estimates as deÃ¿ned

in Eq. (3).

The Levin transformation was also generalized in a di erent way by Levin and Sidi [54] who

introduced the d(m) transformations. This is an important class of transformations that would deserve

a thorough review itself. This, however, is outside the scope of the present review. We collect some

important facts regarding this class of transformations in Section 3.2.

Levin-type transformations as deÃ¿ned in Eq. (11) have been used for the solution of a

large variety of problems. For instance, Levin-type sequence transformations have been applied

for the convergence acceleration of inÃ¿nite series representations of molecular integrals [28,29,

33,65,82,98â€“100], for the calculation of the lineshape of spectral holes [49], for the extrapola-

tion of cluster- and crystal-orbital calculations of one-dimensional polymer chains to inÃ¿nite chain

length [16,88,97], for the calculation of special functions [28,40,82,88,89,94,100], for the sum-

mation of divergent and acceleration of convergent quantum mechanical perturbation series

[17,18,27,85,90 â€“93,95,96], for the evaluation of semiinÃ¿nite integrals with oscillating integrands

and Sommerfeld integral tails [60,61,75,81], and for the convergence acceleration of multipolar

and orthogonal expansions and Fourier series [34,35,37,40 â€“ 45,63,77,80]. This list is clearly not

complete but su cient to demonstrate the possibility of successful application of these trans-

formations.

The outline of this survey is as follows: After listing some deÃ¿nitions and notations, we discuss

some basic sequence transformations in order to provide some background information. Then, special

deÃ¿nitions relevant for Levin-type sequence transformations are given, including variants obtained

by choosing speciÃ¿c remainder estimates !n . After this, important examples of Levin-type sequence

transformations are introduced. In Section 5, we will discuss approaches for the construction of

Levin-type sequence transformations, including model sequences, kernels and annihilation operators,

and also the concept of hierarchical consistency. In Section 6, we derive basic properties, those

of limiting transformations and discuss the application to power series. In Section 7, results on

convergence acceleration are presented, while in Section 8, results on the numerical stability of the

transformations are provided. Finally, we discuss guidelines for the application of the transformations

and some numerical examples in Section 9.

H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147 85

2. DeÃ¿nitions and notations

2.1. General deÃ¿nitions

2.1.1. Sets

Natural numbers:

N = {1; 2; 3; : : :}; N0 = N âˆª {0}: (12)

Integer numbers:

Z = N âˆª {0; âˆ’1; âˆ’2; âˆ’3; : : :}: (13)

Real numbers and vectors:

R = {x : x real};

R+ = {x âˆˆ R : x Â¿ 0} (14)

Rn = {(x1 ; : : : ; x n ) | xj âˆˆ R; j = 1; : : : ; n}:

Complex numbers:

C = {z = x + iy : x âˆˆ R; y âˆˆ R; i2 = âˆ’1};

(15)

Cn = {(z1 ; : : : ; zn ) | zj âˆˆ C; j = 1; : : : ; n}:

For z = x + iy, real and imaginary parts are denoted as x = R (z); y = I (z). We use K to denote

R or C.

Vectors with nonvanishing components:

Fn = {(z1 ; : : : ; zn ) | zj âˆˆ C; zj = 0; j = 1; : : : ; n}: (16)

Polynomials:

ñòð. 18 |