Mathematics of Computation

Author(s): Emil Catinas.
Journal: Math. Comp. 74 (2005), 291-301.
MSC (2000): Primary 65H10
Posted: March 23, 2004
Retrieve article in: PDF DVI PostScript

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.

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 -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 -order and -order of convergence, J. Optim. Theory Appl. 63 (1989), 415-431. MR 91d:65077
32.: -, -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

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: 10.1090/S0025-5718-04-01646-1
PII: S 0025-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
Posted: 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 of article: Copyright 2004, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS