<<

. 5
( 83 .)



>>

and to new results. He also discussed applications to linear systems. In fact, as showed by Sidi [133],
and Jbilou and Sadok [75], vector sequence transformations are closely related to projection methods
for the solution of systems of equations. In particular, the RPA, a vector sequence transformation
deÿned by Brezinski [20] was extensively studied by Messaoudi who showed its connections to
direct and iterative methods for solving systems of linear equations [98,99].
Vector sequence transformations lead to new methods for the solution of systems of nonlinear
equations. They also have other applications. First of all, it is quite important to accelerate the con-
vergence of iterative methods for the solution of systems of linear equations, see [32,33,36]. Special
vector extrapolation techniques were designed for the regularization of ill-posed linear systems in
[43] and the idea of extrapolation was used in [35] to obtain estimates of the norm of the error
when solving a system of linear equations by an arbitrary method, direct or iterative.
General theoretical results similar to those obtained in the scalar case are still lacking in the vector
case although some partial results have been obtained. Relevant results on quasilinear transformations
are in the papers by Sadok [123] and Benazzouz [8]. The present author proposed a mechanism for
vector sequence transformations in [45,34].


4. Conclusions and perspectives

In this paper, I have tried to give a survey of the development of convergence acceleration
methods for scalar and vector sequences in the 20th century. These methods are based on the idea
of extrapolation. Since a universal algorithm for accelerating the convergence of all sequences cannot
exist (and this is even true for some restricted classes of sequences), it was necessary to deÿne and
study a large variety of algorithms, each of them being appropriate for some special subsets of
sequences.
It is, of course, always possible to construct other convergence acceleration methods for scalar
sequences. However, to be of interest, such new processes must provide a major improvement
over existing ones. For scalar sequence transformations, the emphasis must be placed on the theory
rather than on special devices (unless a quite powerful one is found) and on the application of new
16 C. Brezinski / Journal of Computational and Applied Mathematics 122 (2000) 1“21


methods to particular algorithms in numerical analysis and to various domains of applied sciences. In
particular, the connection between convergence acceleration algorithms and continuous and discrete
integrable systems brings a di erent and fresh look to both domains and could be of beneÿt to them.
An important problem in numerical analysis is the solution of large, sparse systems of linear
equations. Most of the methods used nowadays are projection methods. Often the iterates obtained
in such problems must be subject to acceleration techniques. However, many of the known vector
convergence acceleration algorithms require the storage of too many vectors to be useful. New
and cheaper acceleration algorithms are required. This di cult project, in my opinion, o ers many
opportunities for future research.
In this paper, I only brie y mentioned the con uent algorithms whose aim is the computation of
the limit of a function when the variable tends to inÿnity (the continuous analog of the problem
of convergence acceleration for a sequence). This subject and its applications will provide fertile
ground for new discoveries.


Acknowledgements

I would like to thank Jet Wimp for his careful reading of the paper. He corrected my English
in many places, he asked me to provide more explanations when needed, and suggested many
improvements in the presentation. I am also indebted to Naoki Osada for his informations about
Takakazu Seki.


References

[1] A.C. Aitken, On Bernoulli™s numerical solution of algebraic equations, Proc. Roy. Soc. Edinburgh 46 (1926)
289“305.
[2] H. Andoyer, Interpolation, in: J. Molk (Ed.), Encyclopà die des Sciences Mathà matiques Pures et Appliquà es, Tome
e e e
I, Vol. 4, Fasc. 1, I“21, Gauthier“Villars, Paris, 1904 “1912, pp.127“160; (reprint by Editions Gabay, Paris, 1993).
[3] F.L. Bauer, La mà thode d™intà gration numà rique de Romberg, in: Colloque sur l™Analyse Numà rique, Librairie
e e e e
Universitaire, Louvain, 1961, pp. 119 “129.
[4] B. Beckermann, A connection between the E-algorithm and the epsilon-algorithm, in: C. Brezinski (Ed.), Numerical
and Applied Mathematics, Baltzer, Basel, 1989, pp. 443“446.
[5] M.D. Benchiboun, Etude de Certaines Gà nà ralisations du 2 d™Aitken et Comparaison de Procà dà s d™Accà là ration
ee ee ee
de la Convergence, Th‚ se 3‚ me cycle, Università de Lille I, 1987.
e e e
[6] M.D. Benchiboun, Extension of Henrici™s method to matrix sequences, J. Comput. Appl. Math. 75 (1996) 1“21.
[7] A. Benazzouz, Quasilinear sequence transformations, Numer. Algorithms 15 (1997) 275“285.
[8] A. Benazzouz, GL(E)-quasilinear transformations and acceleration, Appl. Numer. Math. 27 (1998) 109“122.
[9] A. Berlinet, Sequence transformations as statistical tools, Appl. Numer. Math. 1 (1985) 531“544.
[10] A.H. Bentbib, Acceleration of convergence of interval sequences, J. Comput. Appl. Math. 51 (1994) 395“409.
[11] N. Bogolyubov, N. Krylov, On Rayleigh™s principle in the theory of di erential equations of mathematical physics
and upon Euler™s method in the calculus of variation, Acad. Sci. Ukraine (Phys. Math.) 3 (1926) 3“22 (in Russian).
[12] H.C. Bolton, H.I. Scoins, Eigenvalues of di erential equations by ÿnite-di erence methods, Proc. Cambridge Philos.
Soc. 52 (1956) 215“229.
[13] C. Brezinski, Application de l™ -algorithme a la rà solution des syst‚ mes non linà aires, C.R. Acad. Sci. Paris 271
‚ e e e
A (1970) 1174“1177.
[14] C. Brezinski, Accà là ration de suites a convergence logarithmique, C. R. Acad. Sci. Paris 273 A (1971) 727“730.
ee ‚
[15] C. Brezinski, Etude sur les et -algorithmes, Numer. Math. 17 (1971) 153“162.
C. Brezinski / Journal of Computational and Applied Mathematics 122 (2000) 1“21 17


[16] C. Brezinski, L™ -algorithme et les suites totalement monotones et oscillantes, C.R. Acad. Sci. Paris 276 A (1973)
305“308.
[17] C. Brezinski, Gà nà ralisation de la transformation de Shanks, de la table de Padà et de l™ -algorithme, Calcolo 12
ee e
(1975) 317“360.
[18] C. Brezinski, Padà -Type Approximation and General Orthogonal Polynomials, Birkhauser, Basel, 1980.
e
[19] C. Brezinski, A general extrapolation algorithm, Numer. Math. 35 (1980) 175“187.
[20] C. Brezinski, Recursive interpolation, extrapolation and projection, J. Comput. Appl. Math. 9 (1983) 369“376.
[21] C. Brezinski, Error control in convergence acceleration processes, IMA J. Numer. Anal. 3 (1983) 65“80.
[22] C. Brezinski, Prediction properties of some extrapolation methods, Appl. Numer. Math. 1 (1985) 457“462.
[23] C. Brezinski, Composite sequence transformations, Numer. Math. 46 (1985) 311“321.
[24] C. Brezinski, A. Lembarki, Acceleration of extended Fibonacci sequences, Appl. Numer. Math. 2 (1986) 1“8.
[25] C. Brezinski, A new approach to convergence acceleration methods, in: A. Cuyt (Ed.), Nonlinear Numerical Methods
and Rational Approximation, Reidel, Dordrecht, 1988, pp. 373“405.
[26] C. Brezinski, Quasi-linear extrapolation processes, in: R.P. Agarwal et al. (Eds.), Numerical Mathematics, Singapore
1988, International Series of Numerical Mathematics, Vol. 86, Birkhauser, Basel, 1988, pp. 61“78.
[27] C. Brezinski, A survey of iterative extrapolation by the E-algorithm, Det Kong. Norske Vid. Selsk. Skr. 2 (1989)
1“26.
[28] C. Brezinski, A Bibliography on Continued Fractions, Padà Approximation, Extrapolation and Related Subjects,
e
Prensas Universitarias de Zaragoza, Zaragoza, 1991.
[29] C. Brezinski, History of Continued Fractions and Padà Approximants, Springer, Berlin, 1991.
e
[30] C. Brezinski, The generalizations of Newton™s interpolation formula due to Muhlbach and Andoyer, Electron Trans.
Numer. Anal. 2 (1994) 130“137.
[31] C. Brezinski, Extrapolation algorithms and Padà approximations: a historical survey, Appl. Numer. Math. 20 (1996)
e
299“318.
[32] C. Brezinski, Variations on Richardson™s method and acceleration, in: Numerical Analysis, A Numerical Analysis
Conference in Honour of Jean Meinguet, Bull. Soc. Math. Belgium 1996, pp. 33“ 44.
[33] C. Brezinski, Projection Methods for Systems of Equations, North-Holland, Amsterdam, 1997.
[34] C. Brezinski, Vector sequence transformations: methodology and applications to linear systems, J. Comput. Appl.
Math. 98 (1998) 149“175.
[35] C. Brezinski, Error estimates for the solution of linear systems, SIAM J. Sci. Comput. 21 (1999) 764“781.
[36] C. Brezinski, Acceleration procedures for matrix iterative methods, Numer. Algorithms, to appear.
[37] C. Brezinski, J.P. Delahaye, B. Germain-Bonne, Convergence acceleration by extraction of linear subsequences,
SIAM J. Numer. Anal. 20 (1983) 1099“1105.
[38] C. Brezinski, A.C. Matos, A derivation of extrapolation algorithms based on error estimates, J. Comput. Appl.
Math. 66 (1996) 5“26.
[39] C. Brezinski, M. Redivo Zaglia, Construction of extrapolation processes, Appl. Numer. Math. 8 (1991) 11“23.
[40] C. Brezinski, M. Redivo Zaglia, Extrapolation Methods, Theory and Practice, North-Holland, Amsterdam, 1991.
[41] C. Brezinski, M. Redivo Zaglia, A general extrapolation procedure revisited, Adv. Comput. Math. 2 (1994) 461“477.
[42] C. Brezinski, M. Redivo Zaglia, Vector and matrix sequence transformations based on biorthogonality, Appl. Numer.
Math. 21 (1996) 353“373.
[43] C. Brezinski, M. Redivo Zaglia, G. Rodriguez, S. Seatzu, Extrapolation techniques for ill-conditioned linear systems,
Numer. Math. 81 (1998) 1“29.
[44] C. Brezinski, A.C. Rieu, The solution of systems of equations using the vector -algorithm, and an application to
boundary value problems, Math. Comp. 28 (1974) 731“741.
[45] C. Brezinski, A. Salam, Matrix and vector sequence transformation revisited, Proc. Edinburgh Math. Soc. 38 (1995)
495“510.
[46] C. Brezinski, G. Walz, Sequences of transformations and triangular recursion schemes with applications in numerical
analysis, J. Comput. Appl. Math. 34 (1991) 361“383.
[47] R. Bulirsch, J. Stoer, Numerical treatment of ordinary di erential equations by extrapolation methods, Numer. Math.
8 (1966) 1“13.
[48] C. Carstensen, On a general epsilon algorithm, in: C. Brezinski (Ed.), Numerical and Applied Mathematics, Baltzer,
Basel, 1989, pp. 437“441.
18 C. Brezinski / Journal of Computational and Applied Mathematics 122 (2000) 1“21


[49] J.L. Chabert et al., Histoire d™Algorithmes, Belin, Paris, 1994.
[50] L. Collatz, Numerische Behandlung von Di erentialgleichungen, Springer, Berlin, 1951.
[51] F. Cordellier, Dà monstration algà brique de l™extension de l™identità de Wynn aux tables de Padà non normales, in:
e e e e
L. Wuytack (Ed.), Padà Approximation and its Applications, Lecture Notes in Mathematics, Vol. 765, Springer,
e
Berlin, 1979, pp. 36“60.
[52] M. Crouzeix, A.L. Mignot, Analyse Numà rique des Equations Di erentielles, 2nd Edition, Masson, Paris, 1989.
e Ã
[53] A. Cuyt, L. Wuytack, Nonlinear Methods in Numerical Analysis, North-Holland, Amsterdam, 1987.
[54] J.P. Delahaye, Automatic selection of sequence transformations, Math. Comp. 37 (1981) 197“204.
[55] J.P. Delahaye, Sequence Transformations, Springer, Berlin, 1988.
[56] J.P. Delahaye, B. Germain-Bonne, Rà sultats nà gatifs en accà là ration de la convergence, Numer. Math. 35 (1980)
e e ee
443“457.
[57] J. Dutka, Richardson-extrapolation and Romberg-integration, Historia Math. 11 (1984) 3“21.
[58] A. Fdil, Sà lection entre procà dà s d™accà là ration de la convergence, M2AN 30 (1996) 83“101.
e ee ee
[59] A. Fdil, A new technique of selection between sequence transformations, Appl. Numer. Math. 25 (1997) 21“40.
[60] W.F. Ford, A. Sidi, An algorithm for a generalization of the Richardson extrapolation process, SIAM J. Numer.
Anal. 24 (1987) 1212“1232.
[61] E. Gekeler, On the solution of systems of equations by the epsilon algorithm of Wynn, Math. Comp. 26 (1972)
427“436.
[62] B. Germain-Bonne, Transformations de suites, RAIRO R1 (1973) 84“90.
[63] B. Germain-Bonne, Estimation de la Limite de Suites et Formalisation de Procà dà s d™Accà là ration de la
ee ee
Convergence, Th‚ se d™Etat, Università de Lille I, 1978.
e e
[64] J. Gilewicz, Numerical detection of the best Padà approximant and determination of the Fourier coe cients of
e
insu ciently sampled function, in: P.R. Graves-Morris (Ed.), Padà Approximants and their Applications, Academic
e
Press, New York, 1973, pp. 99“103.
[65] W.B. Gragg, On extrapolation algorithms for initial-value problems, SIAM J. Numer. Anal. 2 (1965) 384“403.
[66] B. Grammaticos, A. Ramani, Integrability “ and how to detect it, in: Y. Kosmann-Schwarzbach et al. (Eds.),
Integrability of Nonlinear Systems, Springer, Berlin, 1997, pp. 30“94.
[67] B. Grammaticos, A. Ramani, V.G. Papageorgiou, Do integrable mappings have the Painlevà property? Phys. Rev.
e
Lett. 67 (1991) 1825“1828.
[68] P.R. Graves-Morris, Vector valued rational interpolants I, Numer. Math. 42 (1983) 331“348.
[69] P.R. Graves-Morris, C.D. Jenkins, Vector valued rational interpolants III, Constr. Approx. 2 (1986) 263“289.
[70] H.L. Gray, T.A. Atchison, G.V. McWilliams, Higher order G “ transformations, SIAM J. Numer. Anal. 8 (1971)
365“381.
[71] T. Havie, Generalized Neville type extrapolation schemes, BIT 19 (1979) 204“213.
[72] H. Hankel, Ueber eine besondere Classe der symmetrischen Determinanten, Inaugural Dissertation, Universitat
Gottingen, 1861.
[73] A. Hirayama, K. Shimodaira, H. Hirose, Takakazu Seki™s Collected Works Edited with Explanations, Osaka Kyoiku
Tosho, Osaka, 1974.
[74] H.H.H. Homeier, A hierarchically consistent, iterative sequence transformation, Numer. Algorithms 8 (1994) 47“81.
[75] K. Jbilou, H. Sadok, Some results about vector extrapolation methods and related ÿxed-point iterations, J. Comput.
Appl. Math. 36 (1991) 385“398.
[76] K. Jbilou, H. Sadok, Hybrid vector transformations, J. Comput. Appl. Math. 81 (1997) 257“267.
[77] D.C. Joyce, Survey of extrapolation processes in numerical analysis, SIAM Rev. 13 (1971) 435“490.
[78] K. Kommerell, Das Grenzgebiet der Elementaren und Hoheren Mathematik, Verlag Kohler, Leipzig, 1936.
[79] M. Kzaz, Gaussian quadrature and acceleration of convergence, Numer. Algorithms 15 (1997) 75“89.
[80] M. Kzaz, Convergence acceleration of the Gauss“Laguerre quadrature formula, Appl. Numer. Math. 29 (1999)
201“220.
[81] P.J. Laurent, Un thà or‚ me de convergence pour le procà dà d™extrapolation de Richardson, C.R. Acad. Sci. Paris
ee ee
256 (1963) 1435“1437.
[82] H. Lavastre, On the stochastic acceleration of sequences of random variables, Appl. Numer. Math. 15 (1994) 77“98.
[83] H. Le Ferrand, Convergence of the topological -algorithm for solving systems of nonlinear equations, Numer.
Algorithms 3 (1992) 273“284.
C. Brezinski / Journal of Computational and Applied Mathematics 122 (2000) 1“21 19


[84] H. Le Ferrand, Recherches d™extrema par des mà thodes d™extrapolation, C.R. Acad. Sci. Paris, Sà r. I 318 (1994)
e e
1043“1046.
[85] D. Levin, Development of non-linear transformations for improving convergence of sequences, Int. J. Comput.
Math. B3 (1973) 371“388.
[86] P.M. Lima, M.P. Carpentier, Asymptotic expansions and numerical approximation of nonlinear degenerate
boundary-value problems, Appl. Numer. Math. 30 (1999) 93“111.
[87] P. Lima, T. Diogo, An extrapolation method for a Volterra integral equation with weakly singular kernel, Appl.
Numer. Math. 24 (1997) 131“148.
[88] P.M. Lima, M.M Graca, Convergence acceleration for boundary value problems with singularities using the
E-algorithm, J. Comput. Appl. Math. 61 (1995) 139“164.
[89] S. Lubkin, A method of summing inÿnite series, J. Res. Natl. Bur. Standards 48 (1952) 228“254.
[90] C. Maclaurin, Treatise of Fluxions, Edinburgh, 1742.
[91] G.I. Marchuk, V.V. Shaidurov, Di erence Methods and their Extrapolations, Springer, Berlin, 1983.
[92] A.C. Matos, Acceleration methods based on convergence tests, Numer. Math. 58 (1990) 329“340.
[93] A.C. Matos, Linear di erence operators and acceleration methods, IMA J. Numer. Anal., to appear.
[94] A.C. Matos, M. Prà vost, Acceleration property for the columns of the E-algorithm, Numer. Algorithms 2 (1992)
e
393“408.
[95] J.C. Maxwell, A Treatise on Electricity and Magnetism, Oxford University Press, Oxford, 1873.
[96] J.B. McLeod, A note on the -algorithm, Computing 7 (1971) 17“24.
[97] G. Meinardus, G.D. Taylor, Lower estimates for the error of the best uniform approximation, J. Approx. Theory
16 (1976) 150“161.
[98] A. Messaoudi, Recursive interpolation algorithm: a formalism for solving systems of linear equations “ I, Direct
methods, J. Comput. Appl. Math. 76 (1996) 13“30.
[99] A. Messaoudi, Recursive interpolation algorithm: a formalism for solving systems of linear equations “ II, Iterative
methods, J. Comput. Appl. Math. 76 (1996) 31“53.
[100] A. Messaoudi, Matrix extrapolation algorithms, Linear Algebra Appl. 256 (1997) 49“73.
[101] R.M. Milne, Extension of Huygens™ approximation to a circular arc, Math. Gaz. 2 (1903) 309“311.
[102] P. Mortreux, M. Prà vost, An acceleration property for the E-algorithm for alternate sequences, Adv. Comput. Math.
e
5 (1996) 443“482.

[103] G. Muhlbach, Neville-Aitken algorithms for interpolating by functions of Ceby„ev-systems in the sense of Newton
s
and in a generalized sense of Hermite, in: A.G. Law, B.N. Sahney (Eds.), Theory of Approximation with
Applications, Academic Press, New York, 1976, pp. 200“212.
[104] H. Naegelsbach, Studien zu Furstenau™s neuer Methode der Darstellung und Berechnung der Wurzeln algebraischer
Gleichungen durch Determinanten der Coe cienten, Arch. Math. Phys. 59 (1876) 147“192; 61 (1877) 19 “85.
[105] A. Nagai, J. Satsuma, Discrete soliton equations and convergence acceleration algorithms, Phys. Lett. A 209 (1995)
305“312.
[106] A. Nagai, T. Tokihiro, J. Satsuma, The Toda molecule equation and the -algorithm, Math. Comp. 67 (1998)
1565“1575.
[107] T.H. O™Beirne, On linear iterative processes and on methods of improving the convergence of certain types of
iterated sequences, Technical Report, Torpedo Experimental Establishment, Greenock, May 1947.
[108] N. Osada, An acceleration theorem for the -algorithm, Numer. Math. 73 (1996) 521“531.
[109] N. Osada, Vector sequence transformations for the acceleration of logarithmic convergence, J. Comput. Appl. Math.
66 (1996) 391“400.
[110] K.J. Overholt, Extended Aitken acceleration, BIT 5 (1965) 122“132.
[111] V. Papageorgiou, B. Grammaticos, A. Ramani, Integrable di erence equations and numerical analysis algorithms,
in: D. Levi et al. (Eds.), Symmetries and Integrability of Di erence Equations, CRM Proceedings and Lecture
Notes, Vol. 9, AMS, Providence, RI, 1996, pp. 269“279.
[112] V. Papageorgiou, B. Grammaticos, A. Ramani, Integrable lattices and convergence acceleration algorithms, Phys.
Lett. A 179 (1993) 111“115.
[113] V. Papageorgiou, B. Grammaticos, A. Ramani, Orthogonal polynomial approach to discrete Lax pairs for

<<

. 5
( 83 .)



>>