×

A survey on the high convergence orders and computational convergence orders of sequences. (English) Zbl 1429.65110

Summary: Twenty years after the classical book of J. M. Ortega and W. C. Rheinboldt [Iterative solution of nonlinear equations in several variables. New York-London: Academic Press (1970; Zbl 0241.65046)] 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 F. A. Potra [J. Optim. Theory Appl. 63, No. 2, 415–431 (1989; Zbl 0663.65049)], resp. W. A. Beyer et al. [Acta Appl. Math. 20, No. 3, 267–284 (1990; Zbl 0742.41023)]. 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, self-contained, 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. Tight connections between some asymptotic quantities defined by theoretical and computational elements are shown to hold.

MSC:

65J05 General theory of numerical analysis in abstract spaces

Software:

BRENT; mftoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beyer, W. A.; Ebanks, B. R.; Qualls, C. R., Convergence rates and convergence-order profiles for sequences, Acta Appl. Math., 20, 267-284 (1990) · Zbl 0742.41023
[2] Beyer, W. A.; Stein, P. R., Period doubling for trapezoid function iteration: metric theory, Adv. Appl. Math., 3, 1-17 (1982) · Zbl 0495.58020
[3] Beyer, W. A.; Stein, P. R., Further results on periods and period doubling for iterates of the trapezoid function, Adv. Appl. Math., 3, 265-287 (1982) · Zbl 0519.58039
[4] Bodewig, E., On types of convergence and on the behaviour of approximations in the neighborhood of a multiple root of an equation, Q. Appl. Math., 7, 325-333 (1949) · Zbl 0034.37701
[5] Bourbaki, N., Fonction d’une variable Réelle (1951), Hermann: Hermann Paris · Zbl 0042.09201
[6] Brent, R., The computational complexity of iterative methods for systems of nonlinear equations, (Miller, R. E.; Thatcher, J. W.; Bohlinger, J. D., Complexity of Computer Computations. Complexity of Computer Computations, The IBM Research Symposia Series (1972), Springer: Springer Boston, MA)
[7] Brent, R. P., Some efficient algorithms for solving systems of nonlinear equations, SIAM J. Numer. Anal., 10, 327-344 (1973) · Zbl 0258.65051
[8] Brent, R. P., Algorithms for Minimization without Derivatives (1973), Prentice-Hall: Prentice-Hall Englewood Cliffs, New Jersey · Zbl 0245.65032
[9] Brent, R. P.; Winograd, S.; Wolfe, P., Optimal iterative processes for root-finding, Numer. Math., 20, 327-341 (1973) · Zbl 0252.65041
[10] Brezinski, C., Comparaison des suites convergences, Rev. Française d’Inf. Rech. Oper., 5, 2, 95-99 (1971) · Zbl 0225.65009
[11] Brezinski, C., Accélération de la Convergence en Analyse Numérique (1977), Springer-Verlag: Springer-Verlag Berlin · Zbl 0352.65003
[12] Brezinski, C., Limiting relationships and comparison theorems for sequences, Rend. Circolo Mat. Palermo, Ser. II, 28, 273-280 (1979) · Zbl 0459.40001
[13] Brezinski, C., Vitesse de convergence d’une suite, Rev. Roum. Math. Pures Appl., 30, 403-417 (1985) · Zbl 0578.65001
[14] Burmeister, W.; Schmidt, J. W., On the r-order of coupled sequences II, Computing, 29, 73-81 (1982) · Zbl 0499.65028
[15] Burmeister, W.; Schmidt, J. W., On the r-order of coupled sequences III, Computing, 30, 157-169 (1983) · Zbl 0499.65029
[16] Cătinaş, E., Inexact perturbed Newton methods and applications to a class of Krylov solvers, J. Optim. Theory Appl., 108, 3, 543-570 (2001) · Zbl 0980.65054
[17] Cătinaş, E., On accelerating the convergence of the successive approximations method, Rev. Anal. Numér. Théor. Approx., 30, 1, 3-8 (2001) · Zbl 1074.65518
[18] Cătinaş, E., On the superlinear convergence of the successive approximations method, J. Optim. Theory Appl., 113, 3, 473-485 (2002) · Zbl 1012.65042
[19] Cătinaş, E., The inexact, inexact perturbed and quasi-Newton methods are equivalent models, Math. Comput., 74, 249, 291-301 (2005) · Zbl 1054.65050
[20] Cavanagh, R., Difference Equations and Iterative Processes, (1970), University of Maryland: University of Maryland College Park, Doctoral thesis
[21] Cohen, A. I., Rate of Convergence and Optimality Properties of Root Finding and Optimization Algorithms (1970), University of California: University of California Berkeley, Doctoral dissertation
[22] Cordero, A.; Torregrosa, J. R., Variants of Newton’s method using fifth-order quadrature formulas, Appl. Math. Comput., 190, 1, 686-698 (2007) · Zbl 1122.65350
[23] Dembo, R. S.; Eisenstat, S. C.; Steihaug, T., Inexact Newton methods, SIAM J. Numer. Anal., 19, 2, 400-408 (1982) · Zbl 0478.65030
[24] Dennis, J. E., On Newton-like methods, Numer. Math., 11, 324-330 (1968) · Zbl 0165.17303
[25] Dennis, J. E.; Moré, J. J., A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comput., 28, 126, 549-560 (1974) · Zbl 0282.65042
[26] Dubeau, F., On comparisons of Chebyshev-Halley iteration functions based on their asymptotic constants, Int. J. Pure Appl. Math., 85, 5, 965-981 (2013)
[27] Eisenstat, S. C.; Walker, H. F., Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput., 17, 1, 16-32 (1996) · Zbl 0845.65021
[28] Feldstein, A.; Firestone, R. M., Hermite interpolatory iteration theory and parallel numerical theory (1967), Division of Applied Mathematics, Brown University, Report
[29] Feldstein, A.; Firestone, R. M., A study of Ostrowski efficiency for composite iteration algorithms, Proceedings of the 1969 24th National Conference (1969), ACM
[30] Feldstein, A., Bounds on order and Ostrowski efficiency for interpolatory iteration algorithms (1969), California University/Lawrence Livermore Lab.: California University/Lawrence Livermore Lab. Livermore, USA, Report ucrl-72238
[31] Fourier, J., Question d’analyse algébrique, Bull. Sci. Soc. Philos., 67, 1818, 61-67 (2018)
[32] Grau-Sánchez, M.; Noguera, M.; Gutiérrez, J. M., On some computational orders of convergence, Appl. Math. Lett., 23, 472-478 (2010) · Zbl 1189.65092
[33] Grau-Sánchez, M.; Noguera, M.; Grau, A.; Herrero, J. R., On new computational local orders of convergence, Appl. Math. Lett., 25, 2023-2030 (2012) · Zbl 1252.65091
[34] Grau-Sánchez, M.; Noguera, M., On convergence and efficiency in the resolution of systems of nonlinear equations from a local analysis, (Amat, S.; Busquier, S., Advances in Iterative Methods for Nonlinear Equations. Advances in Iterative Methods for Nonlinear Equations, SEMA SIMAI Springer Series, 10 (2016), Springer) · Zbl 1353.65043
[35] Hauser, R.; Nedić, J., On the relationship between the convergence rates of iterative and continuous processes, SIAM J. Optim. Appl., 18, 1, 52-64 (2007) · Zbl 1141.65053
[36] Herzberger, J.; Metzner, L., On the \(q\)-orders of convergence of coupled sequences arising in iterative numerical processes, Computing, 57, 357-363 (1976) · Zbl 0864.65035
[37] Higham, N. J., Functions of Matrices: Theory and Computation (2008), SIAM: SIAM Philadelphia · Zbl 1167.15001
[38] Igarashi, M.; Ypma, T., Empirical versus asymptotic rate of convergence of a class of methods for solving a polynomial equation, J. Comput. Appl. Math., 82, 229-237 (1997) · Zbl 0888.65058
[39] Jay, L. O., A note on q-order of convergence, BIT, 41, 2, 422-429 (2001) · Zbl 0973.40001
[40] Ortega, J. M.; Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables (1970), Academic Press: Academic Press New York · Zbl 0241.65046
[41] Ortega, J. M.; Rockoff, M. L., Nonlinear difference equations and Gauss-Seidel type iterative methods, SIAM J. Numer. Anal., 3, 3, 497-513 (1966) · Zbl 0276.65030
[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.; 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. · Zbl 0115.11201
[43] Păvăloiu, I., Sur l’ordre de convergence des méthodes d’itération, Mathematica, 23, 46, 1, 261-272 (1981) · Zbl 0541.65041
[44] Păvăloiu, I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo, 32, 1-2, 69-82 (1995) · Zbl 0871.65037
[45] Păvăloiu, I., Optimal algorithms concerning the solving of equations by interpolation, (Research on Theory of Allure, Approximation, Convexity and Optimization (1999), Editura Srima: Editura Srima Cluj-Napoca, Romania), 222-248
[46] I. Păvăloiu, On the convergence of one step and multistep iterative methods, Unpublished manuscript, http://ictp.acad.ro/convergence-one-step-multistep-iterative-methods/; I. Păvăloiu, On the convergence of one step and multistep iterative methods, Unpublished manuscript, http://ictp.acad.ro/convergence-one-step-multistep-iterative-methods/
[47] Potra, F. A., On \(Q\)-order and \(R\)-order of convergence, J. Optim. Theory Appl., 63, 3, 415-431 (1989) · Zbl 0663.65049
[48] Potra, F. A.; Pták, V., Nondiscrete Induction and Iterative Processes (1984), Pitman: Pitman Boston, Massachusetts · Zbl 0549.41001
[49] Potra, F. A., Q-superlinear convergence of the iterates in primal-dual interior-point methods, Math. Program. Ser. A, 91, 99-115 (2001) · Zbl 1051.90027
[50] Potra, F. A., Primal-dual affine scaling interior point methods for linear complementarity problems, SIAM J. Optim., 19, 1, 114-143 (2008) · Zbl 1171.90017
[51] Raydan, M., Exact order of convergence of the secant method, J. Optim. Theory Appl., 78, 3, 541-551 (1993) · Zbl 0795.65026
[52] Rheinboldt, W. C., Methods for Solving Systems of Nonlinear Equations (1998), SIAM: SIAM Philadelphia · Zbl 0906.65051
[53] Schmidt, J. W., On the r-order of coupled sequences, Computing, 26, 333-342 (1981) · Zbl 0443.65036
[54] Schwetlick, H., Numerische Lösung Nichtlinearer Gleichungen (1979), VEB: VEB Berlin · Zbl 0402.65028
[55] Soleymani, F., On finding robust approximate inverses for large sparse matrices, Linear Multilinear Algebra, 62, 10, 1314-1334 (2014) · Zbl 1317.65081
[56] Tapia, R. A.; Dennis, J. E.; Schäfermeyer, J. P., Inverse, shifted inverse, and Rayleigh quotient iteration as Newton’s method, SIAM Rev., 60, 1, 3-55 (2018) · Zbl 1382.65105
[57] Tornheim, L., Convergence of multipoint iterative methods, J. ACM, 11, 210-220 (1964) · Zbl 0133.37901
[58] Traub, J. F., Iterative Methods for the Solution of Equations (1964), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J. · Zbl 0121.11204
[59] Varga, R., Matrix Iterative Analysis (1962), Prentice Hall, Englewood Cliffs: Prentice Hall, Englewood Cliffs New Jersey · Zbl 0133.08602
[60] R.G. Voigt, Rates of Convergence for Iterative Methods for Nonlinear Systems of Equations, University of Maryland, College Park, Maryland, Ph.D. Diss.; R.G. Voigt, Rates of Convergence for Iterative Methods for Nonlinear Systems of Equations, University of Maryland, College Park, Maryland, Ph.D. Diss.
[61] Voigt, R. G., Orders of convergence for iterative procedures, SIAM J. Numer. Anal., 8, 222-243 (1971) · Zbl 0221.65082
[62] Walker, H. F., An approach to continuation using Krylov subspace methods, (Periaux, J., Computational Science in the 21st Century (1997), John Wiley and Sons, Ltd.), 72-81 · Zbl 0911.65043
[63] Wall, D. D., The order of an iteration formula, Math. Comput., 10, 55, 167-168 (1956) · Zbl 0070.12505
[64] Wang, L., Symbolic dynamics for a class of unimodal maps and a metric property of bifurcation in trapezoidal maps (period doubling, contiguity of harmonics, quadratic convergence) (1986), State University of New York at Buffalo, Ph.D. thesis
[65] Weerakoon, S.; Fernando, T. G.I., A variant of Newton’s method with accelerated third-order convergence, Appl. Math. Lett., 13, 8, 87-93 (2000) · Zbl 0973.65037
[66] Wright, S. J., Primal-Dual Interior-Point Methods (1997), SIAM: SIAM Philadelphia · Zbl 0863.65031
[67] Ye, Y., Interior Point Algorithms: Theory and Analysis (1997), Wiley · Zbl 0943.90070
[68] Ypma, T. J., Historical development of the Newton-Raphson method, SIAM Rev., 37, 4, 531-551 (1995) · Zbl 0842.01005
[69] Zhang, R.; Wang, L., Two convergence problems for monotone sequences, Acta Appl. Math., 47, 213-220 (1997) · Zbl 0870.40001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.