The inexact, inexact perturbed, and quasi-Newton methods are equivalent models
HTML articles powered by AMS MathViewer
- by Emil Cǎtinaş;
- Math. Comp. 74 (2005), 291-301
- DOI: https://doi.org/10.1090/S0025-5718-04-01646-1
- Published electronically: March 23, 2004
- PDF | Request permission
Abstract:
A classical model of Newton iterations which takes into account some error terms is given by the quasi-Newton method, which assumes perturbed Jacobians at each step. Its high convergence orders were characterized by Dennis and Moré [Math. Comp. 28 (1974), 549–560]. The inexact Newton method constitutes another such model, since it assumes that at each step the linear systems are only approximately solved; the high convergence orders of these iterations were characterized by Dembo, Eisenstat and Steihaug [SIAM J. Numer. Anal. 19 (1982), 400–408]. We have recently considered the inexact perturbed Newton method [J. Optim. Theory Appl. 108 (2001), 543–570] which assumes that at each step the linear systems are perturbed and then they are only approximately solved; we have characterized the high convergence orders of these iterates in terms of the perturbations and residuals. In the present paper we show that these three models are in fact equivalent, in the sense that each one may be used to characterize the high convergence orders of the other two. We also study the relationship in the case of linear convergence and we deduce a new convergence result.References
- Ioannis K. Argyros, Advances in the efficiency of computational methods and applications, World Scientific Publishing Co., Inc., River Edge, NJ, 2000. MR 1878803, DOI 10.1142/4448
- Ioannis K. Argyros, Concerning the convergence of inexact Newton methods, J. Comput. Appl. Math. 79 (1997), no. 2, 235–247. MR 1450283, DOI 10.1016/S0377-0427(96)00162-8
- R. E. Bank and D. J. Rose, Global approximate Newton methods, Numer. Math. 37 (1981), no. 2, 279–295. MR 623045, DOI 10.1007/BF01398257
- R. E. Bank and D. J. Rose, Parameter selection for Newton-like methods applicable to nonlinear partial differential equations, SIAM J. Numer. Anal. 17 (1980), no. 6, 806–822. MR 595446, DOI 10.1137/0717068
- Peter N. Brown, A local convergence theory for combined inexact-Newton/finite-difference projection methods, SIAM J. Numer. Anal. 24 (1987), no. 2, 407–434. MR 881374, DOI 10.1137/0724031
- E. Cătinaş, Newton and Newton-Krylov Methods for Solving Nonlinear Systems in $\mathbb {R}^{n}$, Ph.D. thesis, “Babeş-Bolyai” University Cluj-Napoca, Romania, 1999.
- Emil Cătinaş, A note on the quadratic convergence of the inexact Newton methods, Rev. Anal. Numér. Théor. Approx. 29 (2000), no. 2, 129–133 (2002). MR 1929082
- E. Cǎtinaş, Inexact perturbed Newton methods and applications to a class of Krylov solvers, J. Optim. Theory Appl. 108 (2001), no. 3, 543–570. MR 1828672, DOI 10.1023/A:1017583307974
- E. Cǎtinaş, On the superlinear convergence of the successive approximations method, J. Optim. Theory Appl. 113 (2002), no. 3, 473–485. MR 1904235, DOI 10.1023/A:1015304720071
- —, Inexact perturbed Newton methods for nonlinear systems with singular Jacobians, submitted.
- —, Accurate finite differences in the Newton-Krylov methods, manuscript.
- Ron S. Dembo, Stanley C. Eisenstat, and Trond Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 19 (1982), no. 2, 400–408. MR 650059, DOI 10.1137/0719025
- J. E. Dennis Jr. and Jorge J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp. 28 (1974), 549–560. MR 343581, DOI 10.1090/S0025-5718-1974-0343581-1
- J. E. Dennis Jr. and Jorge J. Moré, Quasi-Newton methods, motivation and theory, SIAM Rev. 19 (1977), no. 1, 46–89. MR 445812, DOI 10.1137/1019005
- John E. Dennis Jr. and Robert B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR 702023
- P. Deuflhard and G. Heindl, Affine invariant convergence theorems for Newton’s method and extensions to related methods, SIAM J. Numer. Anal. 16 (1979), no. 1, 1–10. MR 518680, DOI 10.1137/0716001
- Peter Deuflhard and Florian A. Potra, Asymptotic mesh independence of Newton-Galerkin methods via a refined Mysovskiĭ theorem, SIAM J. Numer. Anal. 29 (1992), no. 5, 1395–1412. MR 1182736, DOI 10.1137/0729080
- Stanley C. Eisenstat and Homer F. Walker, Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput. 17 (1996), no. 1, 16–32. Special issue on iterative methods in numerical linear algebra (Breckenridge, CO, 1994). MR 1375263, DOI 10.1137/0917003
- M. G. Gasparo and B. Morini, Inexact methods: forcing terms and conditioning, J. Optim. Theory Appl. 107 (2000), no. 3, 573–589. MR 1807911, DOI 10.1023/A:1026499216100
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
- Ebrahim M. Kasenally, GMBACK: a generalised backward error algorithm for nonsymmetric linear systems, SIAM J. Sci. Comput. 16 (1995), no. 3, 698–719. MR 1326819, DOI 10.1137/0916042
- Ebrahim M. Kasenally and Valeria Simoncini, Analysis of a minimum perturbation algorithm for nonsymmetric linear systems, SIAM J. Numer. Anal. 34 (1997), no. 1, 48–66. MR 1445729, DOI 10.1137/S0036142994266844
- C. T. Kelley, Iterative methods for linear and nonlinear equations, Frontiers in Applied Mathematics, vol. 16, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1995. With separately available software. MR 1344684, DOI 10.1137/1.9781611970944
- Şt. Măruşter, Numerical Methods for Solving Nonlinear Equations, Ed. Tehnică, Bucharest, Romania, 1981 (in Romanian).
- H. J. Martinez, Z. Parada, and R. A. Tapia, On the characterization of $Q$-superlinear convergence of quasi-Newton interior-point methods for nonlinear programming, Bol. Soc. Mat. Mexicana (3) 1 (1995), no. 2, 137–148. MR 1387657
- Benedetta Morini, Convergence behaviour of inexact Newton methods, Math. Comp. 68 (1999), no. 228, 1605–1613. MR 1653970, DOI 10.1090/S0025-5718-99-01135-7
- J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 273810
- I. Păvăloiu, Introduction to the Theory of Approximating the Solutions of Equations, Ed. Dacia, Cluj-Napoca, Romania, 1976 (in Romanian).
- F. A. Potra, On the numerical stability of a class of iterative processes, Itinerant Seminar of Functional Equations: Approximation and Convexity, Timişoara, Romania, 1983, 51–54.
- Florian Alexandru Potra, On a class of iterative procedures for solving nonlinear equations in Banach spaces, Computational mathematics (Warsaw, 1980) Banach Center Publ., vol. 13, PWN, Warsaw, 1984, pp. 607–621. MR 798124
- F. A. Potra, On $Q$-order and $R$-order of convergence, J. Optim. Theory Appl. 63 (1989), no. 3, 415–431. MR 1031398, DOI 10.1007/BF00939805
- Florian A. Potra, $Q$-superlinear convergence of the iterates in primal-dual interior-point methods, Math. Program. 91 (2001), no. 1, Ser. A, 99–115. MR 1865264, DOI 10.1007/s101070100230
- Werner C. Rheinboldt, Methods for solving systems of nonlinear equations, 2nd ed., CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 70, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. MR 1645489, DOI 10.1137/1.9781611970012
- Youcef Saad and Martin H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), no. 3, 856–869. MR 848568, DOI 10.1137/0907058
- H. F. Walker, An approach to continuation using Krylov subspace methods, in Computational Science in the 21st Century, M.-O. Bristeau, G. Etgen, W. Fitzgibbon, J. L. Lions, J. Periaux and M. F. Wheeler, eds., John Wiley and Sons, Ltd., 1997, 72–82.
- J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 184422
- T. J. Ypma, Local convergence of inexact Newton methods, SIAM J. Numer. Anal. 21 (1984), no. 3, 583–590. MR 744174, DOI 10.1137/0721040
Bibliographic Information
- Emil Cǎtinaş
- Affiliation: Romanian Academy, “T. Popoviciu” Institute of Numerical Analysis, P.O. Box 68–1, Cluj-Napoca 3400, Romania
- Email: ecatinas@ictp.acad.ro
- Received by editor(s): July 23, 2001
- Received by editor(s) in revised form: May 3, 2003
- Published electronically: March 23, 2004
- Additional Notes: This research has been supported by the Romanian Academy under grant GAR 97/1999, and by the National Agency for Science, Technology and Innovation under grant GANSTI 6100 GR/2000.
- © Copyright 2004 American Mathematical Society
- Journal: Math. Comp. 74 (2005), 291-301
- MSC (2000): Primary 65H10
- DOI: https://doi.org/10.1090/S0025-5718-04-01646-1
- MathSciNet review: 2085412