. 18
( 83 .)


[34] U.C. Jentschura, P.J. Mohr, G. So , E.J. Weniger, Convergence acceleration via combined nonlinear-condensation
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.
[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
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.
[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

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

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)
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)

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
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)

whence the problem sequence is modelled according to

sn ∼ s + ! n cj j (n): (5)
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
= + !m cj j (m); m ∈ N0 (6)

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
T({{sn }}; {{!n }}) = {{Tn ({{sn }}; {{!n }})}} (8)

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
= + cj gj (n); n ∈ N0 ; k ∈ N: (10)

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
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 }}.
To be more speciÿc, we consider transformations of the form T({{sn }}; {{!n }}) = {{Tn }}
j=0 n; j sn+j =!n+j
Tn = : (11)
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-
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};
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)


. 18
( 83 .)