Top

previous article Special volume on mathematical modeling with ap...

next article The simpler block CMRH method for linear systems

Hint

Swipe to navigate through the articles of this issue

01-08-2019 | Original Paper | Issue 4/2020

Some unusual results on extrapolation methods

Journal:: Numerical Algorithms > Issue 4/2020

Authors:: Claude Brezinski, Michela Redivo-Zaglia

» Get access to the full-text

Important notes

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

This paper is devoted to properties of sequence transformations and the corresponding recursive algorithms for their implementation, which were never considered before. We first give necessary conditions that are satisfied if the transformed sequence converges faster than the initial one. These conditions can be used for deciding if a method is worth to be used. They also serve as the basis for defining criteria for stopping the acceleration algorithm when the best possible precision is obtained. Then, prescribing the transformed sequence, we show how to obtain the initial sequence which produces it via the transformation or via its recursive algorithm. These results show that almost any behavior is possible for the transformed sequence. A similar problem about Padé-type approximants is studied.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Benchiboun, M.D.: Étude de certaines généralisations du procédé d’Aitken et comparaison de procédés d’accélération de la convergence, Thèse de 3ème cycle Université de Lille I (1987)

Brezinski, C.: Études sur les ε- and ρ-algorithms. Numer. Math. 17, 153–162 (1971) MathSciNetCrossRef

Brezinski, C.: L’ ε-algorithme et les suites totalement monotones et oscillantes. C. R. Acad. Sci. Paris 276 A, 305–308 (1973) MathSciNetMATH

Brezinski, C.: Génération de suites totalement monotones and oscillantes. C. R. Acad. Sci. Paris 280 A, 729–731 (1975) MATH

Brezinski, C.: Généralisation de la transformation de Shanks, de la table de Padé et de l’ ε-algorithme. Calcolo 12, 317–360 (1975) MathSciNetCrossRef

Brezinski, C.: Limiting relationships and comparison theorems for sequences. Rend. Circ. Mat Palermo, (2) 28, 273–280 (1979) MathSciNetCrossRef

Brezinski, C.: Rational approximation to formal power series. J. Approx. Theory 25, 295–317 (1979) MathSciNetCrossRef

Brezinski, C.: About Henrici’s Method for Nonlinear Equations. Symposium on Numerical Analysis and Computational Complex Analysis. Zürich, unpublished (1983)

Brezinski, C.: Quasi-linear extrapolation processes. In: Agarwal, R.P. et al. (eds.) Numerical Mathematics. Singapore 1988. ISNM, vol. 86, pp 61–78. Birkhäuser, Basel (1988)

10.

Brezinski, C.: The asymptotic behavior of sequences and new series transformations based on the Cauchy product, Rocky Mountain. J. Math. 21, 71–84 (1991) MathSciNetMATH

11.

Brezinski, C., Crouzeix, M.: Remarques sur le procédé Δ ² d’Aitken. C. R. Acad. Sci. Paris 270 A, 896–898 (1970) MATH

12.

Brezinski, C., Redivo-Zaglia, M.: Extrapolation Methods. Theory and Practice. North-Holland (1991)

13.

Brezinski, C., Redivo-Zaglia, M.: The simplified topological ε-algorithms for accelerating sequences in a vector space. SIAM J. Sci. Comput. 36, A2227–A2247 (2014) MathSciNetCrossRef

14.

Brezinski, C., Redivo-Zaglia, M.: The simplified topological ε-algorithms: software and applications. Numer. Algorithms 74, 1237–1260 (2017) MathSciNetCrossRef

15.

Brezinski, C., Redivo-Zaglia, M.: The genesis and early developments of Aitken’s process, Shanks’ transformation, the ε-algorithm, and related fixed point methods. Numer. Algorithms 80, 11–133 (2019) MathSciNetCrossRef

16.

Brezinski, C., Redivo-Zaglia, M., Saad, Y.: Shanks sequence transformations and Anderson acceleration. SIAM Rev. 60, 646–669 (2018) MathSciNetCrossRef

17.

Brezinski, C., Sadok, H., et al.: Vector sequence transformations and fixed point methods. In: Taylor, C. (ed.) Numerical Methods in Laminar and Turbulent Flows, pp 3–11. Pineridge Press, Swansea (1987)

18.

Brezinski, C., Walz, G.: Sequences of transformations and triangular recursion schemes, with applications in numerical analysis. J. Comput. Appl. Math. 34, 361–383 (1991) MathSciNetCrossRef

19.

Delahaye, J.-P.: Liens entre la suite du rapport des erreurs et celle du rapport des differences. C. R. Acad. Sci. Paris 290 A, 343–346 (1980) MathSciNetMATH

20.

Delahaye, J.-P.: Sequence Transformations. Springer, Berlin (1988) CrossRef

21.

Delahaye, J.-P., Germain-Bonne, B.: Résultats négatifs en accélération de la convergence. Numer. Math. 35, 443–457 (1980) MathSciNetCrossRef

22.

Delahaye, J.-P., Germain-Bonne, B.: The set of logarithmically congergent sequences cannot be accelerated. SIAM J. Numer. Anal. 19, 840–844 (1982) MathSciNetCrossRef

23.

Higham, N.J.: The Matrix Computation Toolbox, http://www.ma.man.ac.uk/~higham/mctoolbox

24.

Jbilou, K.: Méthodes d’Extrapolation et de Projection. Applications aux Suites de Vecteurs, Thèse de 3ème cycle Université des Sciences et Techniques de Lille (1988)

25.

Jbilou, K., Sadok, H.: Some results about vector extrapolation methods and related fixed point iteration. J. Comp. Appl. Math. 36, 385–398 (1991) MathSciNetCrossRef

26.

Korevaar, J.: Tauberian Theory. A Century of Developments, Grundlehren der mathematischen Wissenschaften, vol. 329. Springer, Berlin (2004)

27.

Meurant, G.: On prescribing the convergence behavior of the conjugate gradient algorithm, Numer. Algorithms, this issue

28.

Meurant, G., Duintjer Tebbens, J.: Krylov Methods for Nonsymmetric Linear Systems, from Theory to Computations, to appear

29.

Pugachëv, B. P.: Acceleration of convergence of iterative processes and a method of solving systems of non-linear equations. Zh. Vychisl. Mat. Mat. Fiz. 17 (5), 1302–1308 (1977). USSR Comput. Maths. Math. Phys. 17(5), 199–207 (1977)

30.

Richardson, L.F.: The approximate arithmetical solution by finite difference of physical problems involving differential equations, with an application to the stress in a masonry dam. Philos. Trans. Roy. Soc. London, ser. A 210, 307–357 (1910)

31.

Richardson, L.F.: The deferred approach to the limit. Part I: Single lattice. Philos. Trans. Roy. Soc. London, ser. A 226, 299–349 (1927) CrossRef

32.

Shanks, D.: Non-linear transformations of divergent and slowly convergent sequences. J. Math. Phys. 34, 1–42 (1955) MathSciNetCrossRef

33.

Toeplitz, O.: Über die lineare Mittelbildungen. Prace Mat.-Fiz. 22, 113–118 (1911) MATH

34.

Wynn, P.: On a device for computing the e _m( S _n) transformation. Math. Tables Aids Comput. 10, 91–96 (1956) MathSciNetCrossRef

35.

Wynn, P.: Acceleration techniques for iterated vector and matrix problems. Math. Comp. 16, 301–322 (1962) MathSciNetCrossRef

36.

Wynn, P.: On the convergence and stability of the epsilon algorithm. SIAM Numer. Anal. 3, 91–122 (1966) MathSciNetCrossRef

Title: Some unusual results on extrapolation methods
Authors:: Claude Brezinski
Michela Redivo-Zaglia
Publication date: 01-08-2019
DOI: https://doi.org/10.1007/s11075-019-00782-y
Publisher: Springer US
Journal: Numerical Algorithms
Issue 4/2020
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265

Premium Partner

Image Credits

Springer Professional

Hint

Swipe to navigate through the articles of this issue

Publisher’s note

Abstract

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 4/2020

FDEMtools: a MATLAB package for FDEM data inversion

Special volume on mathematical modeling with applications

Simple stopping criteria for the LSQR method applied to discrete ill-posed problems

Preconditioned Krylov subspace and GMRHSS iteration methods for solving the nonsymmetric saddle point problems

On the calculation of the poles of multivariate meromorphic functions using the symbolic-numeric two-point qd-algorithm

RMVPIA: a new algorithm for computing the Lagrange multivariate polynomial interpolation

Premium Partner