<<

. 35
( 83 .)



>>

[43] H.H.H. Homeier., On propertiesand the application of Levin-type sequence transformations for the convergence
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 .
˜ ˜ ˜ ˜

<<

. 35
( 83 .)



>>