acceleration of Fourier series, Technical Report TC-NA-97-1, Institut fur Physikalische und Theoretische Chemie,

Universitat Regensburg, D-93040 Regensburg, 1997.

[44] H.H.H. Homeier, An asymptotically hierarchy-consistent iterative sequence transformation for convergence

acceleration of Fourier series, Numer. Algorithms 18 (1998) 1“30.

[45] H.H.H. Homeier, On convergence acceleration of multipolar and orthogonal expansions, Internet J. Chem. 1 (28)

(1998), online computer ÿle: URL: http:==www.ijc.com=articles=1998v1=28=, Proceedings of the Fourth Electronic

Computational Chemistry Conference.

[46] H.H.H. Homeier, On the stability of the J transformation, Numer. Algorithms 17 (1998) 223“239.

[47] H.H.H. Homeier, Convergence acceleration of logarithmically convergent series avoiding summation, Appl. Math.

Lett. 12 (1999) 29“32.

[48] H.H.H. Homeier, Transforming logarithmic to linear convergence by interpolation, Appl. Math. Lett. 12 (1999)

13“17.

[49] H.H.H. Homeier, B. Dick, Zur Berechnung der Linienform spektraler Locher (Engl.: on the computation of the

line shape of spectral holes), Technical Report TC-PC-95-1, Institut fur Physikalische und Theoretische Chemie,

Universitat Regensburg, D-93040 Regensburg, 1995, Poster CP 6.15, 59. Physikertagung Berlin 1995, Abstract:

Verhandlungen der Deutschen Physikalischen Gesellschaft, Reihe VI, Band 30, 1815 (Physik-Verlag GmbH,

D-69469 Weinheim, 1995).

[50] H.H.H. Homeier, E.J. Weniger, On remainder estimates for Levin-type sequence transformations, Comput. Phys.

Comm. 92 (1995) 1“10.

[51] U. Jentschura, P.J. Mohr, G. So , E.J. Weniger, Convergence acceleration via combined nonlinear-condensation

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

[52] A.N. Khovanskii, The Application of Continued Fractions and their Generalizations to Problems in Approximation

Theory, Noordho , Groningen, 1963.

[53] D. Levin, Development of non-linear transformations for improving convergence of sequences, Int. J. Comput.

Math. B 3 (1973) 371“388.

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

[54] D. Levin, A. Sidi, Two new classes of nonlinear transformations for accelerating the convergence of inÿnite integrals

and series, Appl. Math. Comput. 9 (1981) 175“215.

[55] I.M. Longman, Di culties of convergence acceleration, in: M.G. de Bruin, H. van Rossum (Eds.), PadÃ e

Approximation and its Applications Amsterdam 1980, Springer, Berlin, 1981, pp. 273“289.

[56] L. Lorentzen, H. Waadeland, Continued Fractions with Applications, North-Holland, Amsterdam, 1992.

[57] S.K. Lucas, H.A. Stone, Evaluating inÿnite integrals involving Bessel functions of arbitrary order, J. Comput. Appl.

Math. 64 (1995) 217“231.

[58] W. Magnus, F. Oberhettinger, R.P. Soni, Formulas and Theorems for the Special Functions of Mathematical Physics,

Springer, New York, 1966.

[59] A.C. Matos, Linear di erence operators and acceleration methods, Publication ANO-370, Laboratoire d™Analyse

NumÃ rique et d™Optimisation, UniversitÃ des Sciences et Technologies de Lille, France, 1997, IMA J. Numer.

e e

Anal. (2000), to appear.

[60] K.A. Michalski, Extrapolation methods for Sommerfeld integral tails, IEEE Trans. Antennas Propagation 46 (10)

(1998) 1405“1418.

[61] J.R. Mosig, Integral equation technique, in: T. Itoh (Ed.), Numerical Techniques for Microwave and

Millimeter-Wave Passive Structures, Wiley, New York, 1989, pp. 133“213.

[62] E.M. Nikishin, V.N. Sorokin, Rational Approximations and Orthogonality, American Mathematical Society,

Providence, RI, 1991.

[63] C. Oleksy, A convergence acceleration method of Fourier series, Comput. Phys. Comm. 96 (1996) 17“26.

[64] K.J. Overholt, Extended Aitken acceleration, BIT 5 (1965) 122“132.

[65] P.J. Pelzl, F.W. King, Convergence accelerator approach for the high-precision evaluation of three-electron correlated

integrals, Phys. Rev. E 57 (6) (1998) 7268“7273.

[66] P.P. Petrushev, V.A. Popov, Rational Approximation of Real Functions, Cambridge University Press, Cambridge,

1987.

[67] B. Ross, Methods of Summation, Descartes Press, Koriyama, 1987.

[68] E.B. Sa , R.S. Varga (Eds.), PadÃ and Rational Approximation, Academic Press, New York, 1977.

e

[69] L. Schumaker, Spline Functions: Basic Theory, Wiley, New York, 1981.

[70] D. Shanks, Non-linear transformations of divergent and slowly convergent sequences, J. Math. Phys. (Cambridge,

MA) 34 (1955) 1“42.

[71] A. Sidi, Convergence properties of some nonlinear sequence transformations, Math. Comp. 33 (1979) 315“326.

[72] A. Sidi, Some properties of a generalization of the Richardson extrapolation process, J. Inst. Math. Appl. 24 (1979)

327“346.

[73] A. Sidi, An algorithm for a special case of a generalization of the Richardson extrapolation process, Numer. Math.

38 (1982) 299“307.

[74] A. Sidi, Generalization of Richardson extrapolation with application to numerical integration, in: H. Brass,

G. Hammerlin (Eds.), Numerical Integration, Vol. III, Birkhauser, Basel, 1988, pp. 237“250.

[75] A. Sidi, A user-friendly extrapolation method for oscillatory inÿnite integrals, Math. Comp. 51 (1988) 249“266.

[76] A. Sidi, On a generalization of the Richardson extrapolation process, Numer. Math. 47 (1990) 365“377.

[77] A. Sidi, Acceleration of convergence of (generalized) Fourier series by the d-transformation, Ann. Numer. Math.

2 (1995) 381“406.

[78] A. Sidi, Convergence analysis for a generalized Richardson extrapolation process with an application to the d(1)

transformation on convergent and divergent logarithmic sequences, Math. Comp. 64 (212) (1995) 1627“1657.

[79] D.A. Smith, W.F. Ford, Acceleration of linear and logarithmic convergence, SIAM J. Numer. Anal. 16 (1979)

223“240.

[80] D.A. Smith, W.F. Ford, Numerical comparisons of nonlinear convergence accelerators, Math. Comp. 38 (158)

(1982) 481“499.

[81] E.O. Steinborn, H.H.H. Homeier, J. FernÃ ndez Rico, I. Ema, R. LÃ pez, G. RamÃrez, An improved program for

a o

molecular calculations with B functions, J. Mol. Struct. (Theochem) 490 (1999) 201“217.

[82] E.O. Steinborn, E.J. Weniger, Sequence transformations for the e cient evaluation of inÿnite series representations

of some molecular integrals with exponentially decaying basis functions, J. Mol. Struct. (Theochem) 210 (1990)

71“78.

[83] H.S. Wall, Analytic Theory of Continued Fractions, Chelsea, New York, 1973.

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

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

divergent series, Comput. Phys. Rep. 10 (1989) 189“371.

[85] E.J. Weniger, On the summation of some divergent hypergeometric series and related perturbation expansions,

J. Comput. Appl. Math. 32 (1990) 291“300.

[86] E.J. Weniger, On the derivation of iterated sequence transformations for the acceleration of convergence and the

summation of divergent series, Comput. Phys. Comm. 64 (1991) 19“45.

[87] E.J. Weniger, Interpolation between sequence transformations, Numer. Algorithms 3 (1992) 477“486.

[88] E.J. Weniger, Verallgemeinerte Summationsprozesse als numerische Hilfsmittel fur quantenmechanische und

quantenchemische Rechnungen, Habilitationsschrift, Universitat Regensburg, 1994.

[89] E.J. Weniger, Computation of the Whittaker function of the second kind by summing its divergent asymptotic series

with the help of nonlinear sequence transformations, Comput. Phys. 10 (5) (1996) 496“503.

[90] E.J. Weniger, Construction of the strong coupling expansion for the ground state energy of the quartic, sextic,

and octic anharmonic oscillator via a renormalized strong coupling expansion, Phys. Rev. Lett. 77 (14) (1996)

2859“2862.

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

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

[92] E.J. Weniger, Erratum: nonlinear sequence transformations: a computational tool for quantum mechanical and

quantum chemical calculations, Int. J. Quantum Chem. 58 (1996) 319“321.

[93] E.J. Weniger, Nonlinear sequence transformations: a computational tool for quantum mechanical and quantum

chemical calculations, Int. J. Quantum Chem. 57 (1996) 265“280.

„„

[94] E.J. Weniger, J. CÃzek, Rational approximations for the modiÿed Bessel function of the second kind, Comput. Phys.

Comm. 59 (1990) 471“493.

„„

[95] E.J. Weniger, J. CÃzek, F. Vinette, Very accurate summation for the inÿnite coupling limit of the perturbation series

expansions of anharmonic oscillators, Phys. Lett. A 156 (1991) 169“174.

„„

[96] E.J. Weniger, J. CÃzek, F. Vinette, The summation of the ordinary and renormalized perturbation series for the

ground state energy of the quartic, sextic and octic anharmonic oscillators using nonlinear sequence transformations,

J. Math. Phys. 34 (1993) 571“609.

[97] E.J. Weniger, C.-M. Liegener, Extrapolation of ÿnite cluster and crystal-orbital calculations on trans-polyacetylene,

Int. J. Quantum Chem. 38 (1990) 55“74.

[98] E.J. Weniger, E.O. Steinborn, Comment on “molecular overlap integrals with exponential-type integrals”, J. Chem.

Phys. 87 (1987) 3709“3711.

[99] E.J. Weniger, E.O. Steinborn, Overlap integrals of B functions, A numerical study of inÿnite series representations

and integral representations, Theor. Chim. Acta 73 (1988) 323“336.

[100] E.J. Weniger, E.O. Steinborn, Nonlinear sequence transformations for the e cient evaluation of auxiliary functions

for GTO molecular integrals, in: M. Defranceschi, J. Delhalle (Eds.), Numerical Determination of the Electronic

Structure of Atoms, Diatomic and Polyatomic Molecules, Dordrecht, Kluwer, 1989, pp. 341“346.

[101] H. Werner, H.J. Bunger (Eds.), PadÃ Approximations and its Applications, Bad Honnef 1983, Springer, Berlin,

e

1984.

[102] J. Wimp, Sequence Transformations and their Applications, Academic Press, New York, 1981.

[103] L. Wuytack (Ed.), PadÃ Approximations and its Applications, Springer, Berlin, 1979.

e

[104] P. Wynn, On a device for computing the em (Sn ) transformation, Math. Tables Aids Comput. 10 (1956) 91“96.

Journal of Computational and Applied Mathematics 122 (2000) 149“165

www.elsevier.nl/locate/cam

Vector extrapolation methods.

Applications and numerical comparison

K. Jbilou — , H. Sadok

UniversitÃ du Littoral, Zone Universitaire de la Mi-voix, Batiment H. PoincarÃ , 50 rue F. Buisson, BP 699,

e e

F-62228 Calais Cedex, France

Received 24 November 1999; received in revised form 15 February 2000

Abstract

The present paper is a survey of the most popular vector extrapolation methods such as the reduced rank extrapolation

(RRE), the minimal polynomial extrapolation (MPE), the modiÿed minimal polynomial extrapolation (MMPE), the vector

-algorithm (VEA) and the topological -algorithm (TEA). Using projectors, we derive a di erent interpretation of these

methods and give some theoretical results. The second aim of this work is to give a numerical comparison of the vector

extrapolation methods above when they are used for practical large problems such as linear and nonlinear systems of

equations. c 2000 Elsevier Science B.V. All rights reserved.

Keywords: Linear systems; Nonlinear systems; Extrapolation; Projection; Vector sequences; Minimal polynomial; Epsilon-

algorithm

1. Introduction

In the last decade, many iterative methods for solving large and sparse nonsymmetric linear systems

of equations have been developed. The extensions of these methods to nonlinear systems have been

considered. As the classical iteration processes may converge slowly, extrapolation methods are

required. The aim of vector extrapolation methods is to transform a sequence of vectors generated

by some process to a new one with the goal to converge faster than the initial sequence. The

most popular vector extrapolation methods can be classiÿed into two categories: the polynomial

methods and the -algorithms. The ÿrst family contains the minimal polynomial extrapolation (MPE)

method of Cabay and Jackson [8], the reduced rank extrapolation (RRE) method of Eddy [9] and

Mesina [24] and the modiÿed minimal polynomial extrapolation (MMPE) method of Sidi et al. [35],

Brezinski [3] and Pugachev [25]. The second class includes the topological -algorithm (TEA) of

—

Corresponding author.

E-mail addresses: jbilou@lma.univ-littoral.fr (K. Jbilou), sadok@lma.univ-littoral.fr (H. Sadok).

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

150 K. Jbilou, H. Sadok / Journal of Computational and Applied Mathematics 122 (2000) 149“165

Brezinski [3] and the scalar and vector -algorithms (SEA and VEA) of Wynn [39,40]. Some

convergence results and properties of these methods were given in [3,16,18,28,30,33 “36].

Di erent recursive algorithms for implementing these methods were also proposed in [5,15,10,39,40].

However, in practice and for large problems, these algorithms become very unstable and are not

recommended. When solving large linear and nonlinear systems, Sidi [32] gives a more stable

implementation of the RRE and MPE methods using a QR decomposition while Jbilou and Sadok

[19] developed an LU-implementation of the MMPE method. These techniques require low storage

and work and are more stable numerically.

When applied to linearly generated vector sequences, the MPE, the RRE and the TEA methods are

mathematically related to some known Krylov subspace methods. It was shown in [34] that these

methods are equivalent to the method of Arnoldi [26], the generalized minimal residual method

(GMRES) [27] and the method of Lanczos [21], respectively. The MMPE method is mathematically

equivalent to Hessenberg method [30] and [38]. For linear problems, some numerical comparisons

have been given in [11].

We note also that, when the considered sequence is not generated linearly, these extrapolation

methods are still projection methods but not necessarily Krylov subspace methods [20].

An important property of the vector extrapolation methods above is that they could be applied

directly to the solution of linear and nonlinear systems. This comes out from the fact that the

deÿnitions of these methods do not require an explicit knowledge of how the sequence is generated.

Hence, these vector extrapolation methods are more e ective for nonlinear problems [29].

For nonlinear problems, these methods do not need the use of the Jacobian of the function and have

the property of quadratic convergence under some assumptions [17]. Note that for some nonlinear

problems, vector extrapolation methods such as nonlinear Newton“Krylov methods fail to converge

if the initial guess is “away” from a solution. In this case, some techniques such as the linear search

backtracting procedure could be added to the basic algorithms; see [2].

The paper is organized as follows. In Section 2, we introduce the polynomial extrapolation methods

(RRE, MPE and MMPE) by using the generalized residual. We will also see how these methods could

be applied for solving linear and nonlinear systems of equations. In this case some theoretical results

are given. Section 3 is devoted to the epsilon-algorithm™s family (SEA, VEA and TEA). In Section 4,

we give the computational steps and storage required for these methods. Some numerical experiments

are given in Section 5 and a comparison with the vector extrapolation methods cited above.

In this paper, we denote by (:; :) the Euclidean inner product in RN and by ||:|| the corresponding

norm. For an N — N matrix A and a vector v of RN the Krylov subspace Kk (A; v) is the subspace

generated by the vectors v; Av; : : : ; Ak’1 v. IN is the unit matrix and the Kronecker product — is deÿned

by C — B = [ci; j B] where B and C are two matrices.

2. The polynomial methods

2.1. Deÿnitions of the RRE, MPE and MMPE methods

Let (sn ) be a sequence of vectors of RN and consider the transformation Tk deÿned by

Tk : RN ’ RN ;

(n)

sn ’ tk

K. Jbilou, H. Sadok / Journal of Computational and Applied Mathematics 122 (2000) 149“165 151

with

k

(n)

ai(n) gi (n);

tk = sn + n¿0; (2.1)

i=1

where the auxiliary vector sequences (gi (n))n ; i = 1; : : : ; k, are given. The coe cients ai(n) are scalars.

˜

Let T k denote the new transformation obtained from Tk by

k

(n)

ai(n) gi (n + 1);

t˜k = sn+1 + n¿0: (2.2)

i=1

For these extrapolation methods, the auxiliary sequences are such that gi (n) = sn+i’1 ; i = 1; : : : ; k;

n¿0, and the coe cients ai(n) are the same in the two expressions (2.1) and (2.2).

(n)

We deÿne the generalized residual of tk by

(n)

˜ (n) (n)

r(tk ) = t˜k ’ tk

k

ai(n) gi (n):

= sn + (2.3)

i=1

The forward di erence operator acts on the index n, i.e., gi (n) = gi (n + 1) ’ gi (n); i = 1; : : : ; k.

We will see later that, when solving linear systems of equations, the sequence (sn )n is generated

by a linear process and then the generalized residual coincides with the classical residual.

The coe cients ai(n) involved in expression (2.1) are obtained from the orthogonality relation

˜ (n) (n) (n)

r(tk )⊥span{y1 ; : : : ; yk }; (2.4)

where yi(n) = sn+i’1 for the MPE; yi(n) = 2 sn+i’1 for the RRE and yi(n) = yi for the MMPE where

y1 ; : : : ; yk are arbitrary linearly independent vectors of RN .

˜ ˜ ˜ ˜