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

7 years ago

(original), inexact/perturbed iterations, ISI/JCR, Krylov methods, linear systems in Rn, local convergence, Newton method, nonlinear systems in Rn, Numerical Analysis, paper, solving F(x)=0 iteratively

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 q-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 q-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 q-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 q-convergence orders of the other two. We also study the relationship in the case of linear convergence and we deduce a new convergence result.

Authors

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

Keywords

nonlinear system of equations in Rn; inexact Newton method; perturbed Newton method; quasi-Newton methods; linear systems of equation in Rn; backward errors; GMRES; GMBACK; MINPERT; Newton-Krylov methods; residual; local convergence; convergence order.

Cite this paper as:

E. Cătinaş, The inexact, inexact perturbed and quasi-Newton methods are equivalent models, Math. Comp., 74 (2005) no. 249, pp. 291-301
doi: 10.1090/S0025-5718-04-01646-1

PDF

Scanned paper.

Latex-pdf version of the paper.

About this paper

Journal

Mathematics of Computation

Publisher Name

American Mathematical Society

DOI

10.1090/S0025-5718-04-01646-1

Print ISSN

0025-5718

Online ISSN

1088-6842

MR

ZBL

Google Scholar citations

[1] I. Argyros, Advances in the Efficiency of Computational Methods and Applications, World Scientific Publishing Co., Inc., River Edge, NJ, 2000.
CrossRef (DOI) MR 2002k:65003

[2] I. Argyros, Concerning the convergence of inexact Newton methods, J. Comp. Appl. Math. 79 (1997), 235–247.
CrossRef (DOI) MR 98c:47077

[3] R. E. Bank and D. J. Rose, Global approximate Newton methods, Numer. Math. 37 (1981), 279–295.
CrossRef (DOI) MR 83c:65127

[4] – , Parameter selection for Newton-like methods applicable to nonlinear partial differential equations, SIAM J. Numer. Anal. 17 (1980), 806–822.
CrossRef (DOI) 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.
CrossRef (DOI) MR 88d:65088

[6] E. Catinas, Newton and Newton-Krylov Methods for Solving Nonlinear Systems in Rn, Ph.D. thesis, “Babes-Bolyai” University Cluj-Napoca, Romania, 1999.

[7] – , A note on the quadratic convergence of the inexact Newton methods, Rev. Anal. Numer. Th´eor. 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.
CrossRef (DOI) MR 2002c:65074

[9] – , On the superlinear convergence of the successive approximations method, J. Optim. Theory Appl. 113 (2002), 473–485.
CrossRef (DOI) 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.
CrossRef (DOI) MR 83b:65056

[13] J. E. Dennis, Jr. and J. J. More, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp. 28 (1974), 549–560.
CrossRef (DOI) MR 49:8322

[14] -, Quasi-Newton methods, motivation and theory, SIAM Rev. 19 (1977), 46–89.
CrossRef (DOI) 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.
CrossRef (DOI) 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.
CrossRef (DOI) 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.
CrossRef (DOI) MR 96k:65037

[19] M. Gasparo and B. Morini, Inexact methods: forcing terms and conditioning, J. Optim. Theory Appl. 107 (2000), 573–589.
CrossRef (DOI) 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.
CrossRef (DOI) 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.
CrossRef (DOI) 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, Timi¸soara, 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.
CrossRef (DOI) MR 87c:65068

[31] – , On Q-order and R-order of convergence, J. Optim. Theory Appl. 63 (1989), 415– 431. CrossRef (DOI) 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.
CrossRef (DOI) 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.
CrossRef (DOI) MR 85k:65043

2005

Sheffer sequences, probability distributions and approximation operators

December 10, 2019

On the extension of semi-Lipschitz functions on asymmetric normed spaces

May 2, 2023

Existence and localization results for semi-linear problems

April 13, 2022