A survey on the high convergence orders and computational convergence orders of sequences

Abstract

Twenty years after the classical book of Ortega and Rheinboldt was published, five definitions for the (Q)-convergence orders of sequences were independently and rigorously studied (i.e., some orders characterized in terms of others), by Potra (1989), resp. Beyer, Ebanks and Qualls (1990). The relationship between all the five definitions (only partially analyzed in each of the two papers) was not subsequently followed and, moreover, the second paper slept from the readers attention.

The main aim of this paper is to provide a rigorous, selfcontained, and, as much as possible, a comprehensive picture of the theoretical aspects of this topic, as the current literature has taken away the credit from authors who obtained important results long ago.

Moreover, this paper provides rigorous support for the numerical examples recently presented in an increasing number of papers, where the authors check the convergence orders of different iterative methods for solving nonlinear (systems of) equations.

Authors

Emil Cătinaş
(Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy)

Keywords

Convergent sequences in (mathbb{R}^n); (Q)-convergence orders; (C)-convergence orders; (R)-convergence orders; convergence rates; rates of convergence; convergence speed; speed of convergence; computational convergence orders.

Cite this paper as

E. Cătinaş, A survey on the high convergence orders and computational convergence orders of sequences, Appl. Math. Comput., 343 (2019) 1-20.
doi: 10.1016/j.amc.2018.08.006

PDF

About this paper

Print ISSN

0096-3003

Online ISSN

Google Scholar citations

google scholar citations

References

[1] W.A. Beyer, B.R. Ebanks, C.R. Qualls, Convergence rates and convergence-order profiles for sequences, Acta Appl. Math. 20 (1990) 267-284.
CrossRef (DOI)

[2] W.A. Beyer, P.R. Stein, Period doubling for trapezoid function iteration: metric theory, Adv. Appl. Math., 3 (1982), pp. 1-17.
CrossRef (DOI)

[3] W.A. Beyer, P.R. Stein, Further results on periods and period doubling for iterates of the trapezoid function, Adv. Appl. Math., 3 (1982), pp. 265-287.
CrossRef (DOI)

[4] E. Bodewig, On types of convergence and on the behaviour of approximations in the neighborhood of a multiple root of an equation, Quart. Appl. Math., 7 (1949), pp. 325-333
CrossRef (DOI)

[5] N. Bourbaki, Fonction d’une Variable Réelle. Livre 4. Chapitre 5. Hermann, Paris, 1951.

[6] R. Brent, The computational complexity of iterative methods for systems of nonlinear equations, in: Miller R.E., Thatcher J.W., Bohlinger J.D. (eds) Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston, MA, 1972

[7] R.P. Brent, Some efficient algorithms for solving systems of nonlinear equations, SIAM J. Numer. Anal., 10 (1973), pp. 327-344.
CrossRef (DOI)

[8] R.P. Brent, Algorithms for minimization without derivatives, Prentice-Hall, Englewood Cliffs, New Jersey, 1973.

[9] R.P. Brent, S. Winograd, P. Wolfe, Optimal iterative processes for root-finding, Numer. Math., 20 (1973), pp. 327-341.
CrossREf (DOI)

[10] C. Brezinski, Comparaison des suites convergences, Revue Française d’Informatique et de Recherche Operationelle, 5 (1971) no. 2, pp. 95-99.
CrossREf (DOI)

[11] C. Brezinski, Accélération de la Convergence en Analyse Numérique, Springer-Verlag, Berlin, 1977.

[12] C. Brezinski, Limiting relationships and comparison theorems for sequences, Rend. Circolo Mat. Palermo, Ser. II, vol. 28 (1979), pp. 273-280.
CrossRef (DOI)

[13] C. Brezinski, Vitesse de convergence d’une suite, Rev. Roumaine Math. Pures Appl., 30 (1985), pp. 403-417.

[14] W. Burmeister, J.W. Schmidt, On the R-Order of Coupled Sequences II, Computing, 29 1982, pp. 73-81.
CrossRef (DOI)

[15] W. Burmeister, J.W. Schmidt, On the R-Order of Coupled Sequences III, Computing, 30 1983, pp. 157-169.
CrossRef (DOI)

[16] E. Cătinaş, Inexact perturbed Newton methods and applications to a class of Krylov solvers, J. Optim. Theory Appl., 108 (2001) no. 3, pp. 543-570.
CrossRef (DOI)

[17] E. Cătinaş, On accelerating the convergence of the successive approximations method, Rev. Anal. Numér. Théor. Approx., 30 (2001) no. 1, pp. 3-8.
Paper on author’s website

[18] E. Cătinaş, On the superlinear convergence of the successive approximations method, J. Optim. Theory Appl., 113 (2002) no. 3, pp. 473-485.
CrossRef (DOI)

[19] E. Cătinaş, The inexact, inexact perturbed and quasi-Newton methods are equivalent models, Math. Comp., 74 (2005) no. 249, pp. 291-301.
Crossref (DOI)

[20] R. Cavanagh, Difference equations and iterative processes, Doctoral thesis, Univ. of Maryland, College Park, 1970.

[21] A.I. Cohen, Rate of convergence and optimality properties of root finding and optimization algorithms, Doctoral dissertation, University of California, Berkeley, 1970.

[22] A. Cordero, J.R. Torregrosa, Variants of Newton’s method using fifth-order quadrature formulas, Appl. Math. Comput. 190 (1) (2007), 686-698.
CrossRef (DOI)

[23] R.S. Dembo, S.C. Eisenstat, T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 19 (2) (1982) 400-408.
CrossRef (DOI)

[24] J.E. Dennis, On Newton-like methods, Numer. Math. 11 (1968) 324-330.
CrossRef (DOI)

[25] J.E. Dennis Jr., J.J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comput. 28 (126) (1974) 549-560.
CrossRef (DOI)

[26] F. Dubeau, On comparisons of Chebyshev-Halley iteration functions based on their asymptotic constants, Int. J. Pure Appl. Math. 85 (5) (2013) 965-981.
CrossRef (DOI)

[27] S.C. Eisenstat, H.F. Walker, Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput. 17 (1) (1996) 16-32.
CrossRef (DOI)

[28] A. Feldstein, R.M. Firestone, Hermite interpolatory iteration theory and parallel numerical theory, Division of Applied Mathematics, Brown University, 1967 Report.

[29] A. Feldstein, R.M. Firestone, A study of Ostrowski efficiency for composite iteration algorithms, in: Proceedings of the 1969 24th National Conference, ACM, 1969.
CrossRef (DOI)

[30] A. Feldstein, Bounds on order and Ostrowski efficiency for interpolatory iteration algorithms, California University/Lawrence Livermore Lab., Livermore, USA, 1969 Report ucrl-72238.

[31] J. Fourier, Question d’analyse algébrique, Bull. Sci. Soc. Philos. 67 (1818) (2018) 61–67. http://gallica.bnf.fr/ark:/12148/bpt6k33707/f248.item, accessed February 23, 2018

[32] M. Grau-Sánchez, M. Noguera, J.M. Gutiérrez, On some computational orders of convergence, Appl. Math. Lett. 23 (2010) 472-478.
CrossRef (DOI)

[33] M. Grau-Sánchez, M. Noguera, A. Grau, J.R. Herrero, On new computational local orders of convergence, Appl. Math. Lett. 25 (2012) 2023-2030.
CrossRef (DOI)

[34] M. Grau-Sánchez, M. Noguera, On convergence and efficiency in the resolution of systems of nonlinear equations from a local analysis, in: S. Amat, S. Busquier (Eds.), Advances in Iterative Methods for Nonlinear Equations, SEMA SIMAI Springer Series, 10, Springer, 2016.
CrossRef (DOI)

[35] R. Hauser, J. Nedic, On the relationship between the convergence rates of iterative and continuous processes, SIAM J. Optim. Appl. 18 (1) (2007) 52-64.
CrossRef (DOI)

[36] J. Herzberger, L. Metzner, On the q-orders of convergence of coupled sequences arising in iterative numerical processes, Computing 57 (1976) 357–363.
CrossRef (DOI)

[37] N.J. Higham, Functions of Matrices: Theory and Computation, SIAM, Philadelphia, 2008.

[38] M. Igarashi, T. Ypma, Empirical versus asymptotic rate of convergence of a class of methods for solving a polynomial equation, J. Comput. Appl. Math. 82 (1997) 229-237.
CrossREf (DOI)

[39] L.O. Jay, A note on q-order of convergence, BIT 41 (2) (2001) 422-429.
CrossRef (DOI)

[40] J.M. Ortega, W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
CrossRef (DOI)

[41] J.M. Ortega, M.L. Rockoff, Nonlinear difference equations and Gauss-Seidel type iterative methods, SIAM J. Numer. Anal. 3 (3) (1966) 49–513.
CrossRef (DOI)

[42] A. Ostrowski, Solution of Equations and Systems of Equations, Academic Press, New York, 1960 (2nd ed. 1966). 3rd edition published as Solution of Equations in Euclidean and Banach Spaces, Academic Press, 1973, New York and London.

[43] I. Pavaloiu, Sur l’ordre de convergence des méthodes d’itération, Mathematica, 23 46 (1) (1981) 261–272. (in French). http://ictp.acad.ro/convergence-order-iterative-methods/ accessed March 22, 2018.
paper on author’s website

[44] I. Pavaloiu, Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo 32 (1–2) (1995) 69-82.
CrossRef (DOI), paper on author’s website

[45] I. Pavaloiu, Optimal algorithms concerning the solving of equations by interpolation, in: Research on Theory of Allure, Approximation, Convexity and Optimization, Editura Srima, Cluj-Napoca, Romania, 1999, pp. 222-248. ISBN 973-98551-4-3. http://ictp.acad.ro/optimal-algorithms-concerning-solving-equations-interpolation/ accessed March 22, 2018.
paper on author’s website

[46] I. Pavaloiu, On the convergence of one step and multistep iterative methods, Unpublished manuscript, http://ictp.acad.ro/convergence- one- step- multistep- iterative- methods/, accessed April 1st, 2018.
paper on author’s website

[47] F.A. Potra, On Q-order and R-order of convergence, J. Optim. Theory Appl. 63 (3) (1989) 415-431.
CrossRef (DOI)

[48] F.A. Potra, V. Pták, Nondiscrete Induction and Iterative Processes, Pitman, Boston, Massachusetts, 1984.

[49] F.A. Potra, Q-superlinear convergence of the iterates in primal-dual interior-point methods, Math. Program. Ser. A 91 (2001) 99-115
CrossRef DOI)

[50] F.A. Potra, Primal-dual affine scaling interior point methods for linear complementarity problems, SIAM J. Optim. 19 (1) (2008) 114-143.
CrossRef (DOI)

[51] M. Raydan, Exact order of convergence of the secant method, J. Optim. Theory Appl. 78 (3) (1993) 541-551.
CrossRef (DOI)

[52] W.C. Rheinboldt, Methods for Solving Systems of Nonlinear Equations, 2nd. ed., SIAM, Philadelphia, 1998

[53] J.W. Schmidt, On the r-order of coupled sequences, Computing 26 (1981) 333-342.
CrossREf (DOI)

[54] H. Schwetlick, Numerische Lösung Nichtlinearer Gleichungen, VEB, Berlin, 1979.

[55] F. Soleymani, On finding robust approximate inverses for large sparse matrices, Linear Multilinear Algebra 62 (10) (2014) 1314-1334.
CrossRef (DOI)

[56] R.A. Tapia, J.E. Dennis Jr., J.P. Schäfermeyer, Inverse, shifted inverse, and Rayleigh quotient iteration as Newton’s method, SIAM Rev. 60 (1) (2018) 3-55.
CrossRef (DOI)

[57] L. Tornheim, Convergence of multipoint iterative methods, J. ACM 11 (1964) 210-220.
CrossRef (DOI)

[58] J.F. Traub, Iterative Methods for the Solution of Equations, Prentice-Hall, Englewood Cliffs, N.J., 1964.

[59] R. Varga, Matrix Iterative Analysis, Prentice Hall, Englewood Cliffs, New Jersey, 1962.

[60] R.G. Voigt, Rates of Convergence for Iterative Methods for Nonlinear Systems of Equations, University of Maryland, College Park, Maryland, Ph.D. Diss.

[61] R.G. Voigt, Orders of convergence for iterative procedures, SIAM J. Numer. Anal. 8 (1971) 222-243
CrossRef (DOI)

[62] H.F. Walker, An approach to continuation using Krylov subspace methods, in: J. Periaux (Ed.), Computational Science in the 21st Century, John Wiley and Sons, Ltd., 1997, pp. 72-81
paper on author website

[63] D.D. Wall, The order of an iteration formula, Math. Comput. 10 (55) (1956) 167-168.
CrossRef (DOI)

[64] L. Wang, Symbolic dynamics for a class of unimodal maps and a metric property of bifurcation in trapezoidal maps (period doubling, contiguity of harmonics, quadratic convergence), State University of New York at Buffalo, 1986 Ph.D. thesis.

[65] S. Weerakoon, T.G.I. Fernando, A variant of Newton’s method with accelerated third-order convergence, Appl. Math. Lett. 13 (8) (20 0 0) 87-93.
CrossRef (DOI)

[66]  S.J. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, 1997.

[67] Y. Ye, Interior Point Algorithms: Theory and Analysis, Wiley, 1997.

[68] T.J. Ypma, Historical development of the Newton-Raphson method, SIAM Rev. 37 (4) (1995) 531-551
CrossRef (DOI)

[69] R. Zhang, L. Wang, Two convergence problems for monotone sequences, Acta Appl. Math. 47 (1997) 213-220.
CrossRef (DOI)

Paper in html form

to be inserted

Related Posts

No results found

Leave a Reply

Your email address will not be published. Required fields are marked *

Fill out this field
Fill out this field
Please enter a valid email address.

Menu