Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

The inexact, inexact perturbed, and quasi-Newton methods are equivalent models


Author: Emil Catinas
Journal: Math. Comp. 74 (2005), 291-301
MSC (2000): Primary 65H10
DOI: https://doi.org/10.1090/S0025-5718-04-01646-1
Published electronically: March 23, 2004
MathSciNet review: 2085412
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. I. Argyros, Advances in the Efficiency of Computational Methods and Applications, World Scientific Publishing Co., Inc., River Edge, NJ, 2000. MR 2002k:65003
  • 2. I. Argyros, Concerning the convergence of inexact Newton methods, J. Comp. Appl. Math. 79 (1997), 235-247. MR 98c:47077
  • 3. R. E. Bank and D. J. Rose, Global approximate Newton methods, Numer. Math. 37 (1981), 279-295. MR 83c:65127
  • 4. -, Parameter selection for Newton-like methods applicable to nonlinear partial differential equations, SIAM J. Numer. Anal. 17 (1980), 806-822. MR 81m:65071
  • 5. P. N. Brown, A local convergence theory for combined inexact-Newton/finite-difference projection methods, SIAM J. Numer. Anal. 24 (1987), 407-434. MR 88d:65088
  • 6. E. Catinas, Newton and Newton-Krylov Methods for Solving Nonlinear Systems in $\mathbb{R}^{n}$, Ph.D. thesis, ``Babes-Bolyai'' University Cluj-Napoca, Romania, 1999.
  • 7. -, A note on the quadratic convergence of the inexact Newton methods, Rev. Anal. Numér. Théor. Approx. 29 (2000), 129-134. MR 2003i:65049
  • 8. -, Inexact perturbed Newton methods and applications to a class of Krylov solvers, J. Optim. Theory Appl. 108 (2001), 543-570. MR 2002c:65074
  • 9. -, On the superlinear convergence of the successive approximations method, J. Optim. Theory Appl. 113 (2002), 473-485. MR 2003e:65086
  • 10. -, Inexact perturbed Newton methods for nonlinear systems with singular Jacobians, submitted.
  • 11. -, Accurate finite differences in the Newton-Krylov methods, manuscript.
  • 12. R. S. Dembo, S. C. Eisenstat and T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 19 (1982), 400-408. MR 83b:65056
  • 13. J. E. Dennis, Jr. and J. J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp. 28 (1974), 549-560. MR 49:8322
  • 14. -, Quasi-Newton methods, motivation and theory, SIAM Rev. 19 (1977), 46-89. MR 56:4146
  • 15. J. E. Dennis, Jr. and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall Series in Computational Mathematics, Englewood Cliffs, NJ, 1983. MR 85j:65001
  • 16. P. Deuflhard and G. Heindl, Affine invariant convergence theorems for Newton's method and extensions to related methods, SIAM J. Numer. Anal. 16 (1979), 1-10. MR 80i:65068
  • 17. P. Deuflhard and F. A. Potra, Asymptotic mesh independence of Newton-Galerkin methods via a refined Mysovskii theorem, SIAM J. Numer. Anal. 29 (1992), 1395-1412. MR 94a:65031
  • 18. S. C. Eisenstat and H. F. Walker, Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput. 17 (1996), 16-32. MR 96k:65037
  • 19. M. Gasparo and B. Morini, Inexact methods: forcing terms and conditioning, J. Optim. Theory Appl. 107 (2000), 573-589. MR 2001k:65089
  • 20. G. H. Golub and C. F. Van Loan, Matrix Computations, Third ed., The Johns Hopkins University Press, Baltimore, 1996. MR 97g:65006
  • 21. E. M. Kasenally, GMBACK: a generalised minimum backward error algorithm for nonsymmetric linear systems, SIAM J. Sci. Comput. 16 (1995), 698-719. MR 95m:65054
  • 22. E. M. Kasenally and V. Simoncini, Analysis of a minimum perturbation algorithm for nonsymmetric linear systems, SIAM J. Numer. Anal. 34 (1997), 48-66. MR 98a:65040
  • 23. C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, Philadelphia, 1995. MR 96d:65002
  • 24. St. Maruster, Numerical Methods for Solving Nonlinear Equations, Ed. Tehnica, Bucharest, Romania, 1981 (in Romanian).
  • 25. 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 1 (1995), 137-148. MR 97d:90090
  • 26. B. Morini, Convergence behaviour of inexact Newton methods, Math. Comp. 68 (1999), 1605-1613. MR 99m:65114
  • 27. J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. MR 42:8686
  • 28. I. Pavaloiu, Introduction to the Theory of Approximating the Solutions of Equations, Ed. Dacia, Cluj-Napoca, Romania, 1976 (in Romanian).
  • 29. F. A. Potra, On the numerical stability of a class of iterative processes, Itinerant Seminar of Functional Equations: Approximation and Convexity, Timisoara, Romania, 1983, 51-54.
  • 30. -, On a class of iterative procedures for solving nonlinear equations in Banach spaces, Computational Mathematics, Banach Center Publications, PWN-Polish Scientific Publishers, Warsaw, Poland, vol. 13, 607-621, 1984. MR 87c:65068
  • 31. -, On $Q$-order and $R$-order of convergence, J. Optim. Theory Appl. 63 (1989), 415-431. MR 91d:65077
  • 32. -, $Q$-superlinear convergence of the iterates in primal-dual interior-point methods, Math. Progr., to appear. MR 2002i:90120
  • 33. W. C. Rheinboldt, Methods for Solving Systems of Nonlinear Equations, Second ed., SIAM, Philadelphia, PA, 1998. MR 2000c:65001
  • 34. Y. Saad and M. H. Schultz, GMRES: a minimum residual algorithm, SIAM J. Sci. Statist. Comput. 7 (1986), 856-869. MR 87g:65064
  • 35. 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.
  • 36. J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. MR 32:1894
  • 37. T. J. Ypma, Local convergence of inexact Newton methods, SIAM J. Numer. Anal. 21 (1984), 583-590. MR 85k:65043

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65H10

Retrieve articles in all journals with MSC (2000): 65H10


Additional Information

Emil Catinas
Affiliation: Romanian Academy, “T. Popoviciu” Institute of Numerical Analysis, P.O. Box 68–1, Cluj-Napoca 3400, Romania
Email: ecatinas@ictp.acad.ro

DOI: https://doi.org/10.1090/S0025-5718-04-01646-1
Keywords: Inexact, inexact perturbed and quasi-Newton methods, convergence orders
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.
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society