An Extension Of The Theory Of Secant Preconditioners

A theory of inexact Newton methods with secant preconditioners for solving large nonlinear systems of equations has been developed recently by Martínez (Math. Comput., 1993). According to this theory, local and superlinear convergence with bounded work per iteration of the inexact Newton method is obtained if the first trial increment at each iteration is a suitable quasi-Newton step computed using least-change secant-update procedures. The Jacobian approximation is interpreted as a preconditioner of the iterative linear method. In this paper, we extend the theory in two ways. On the one hand, since in many iterative methods the true residual is not computed but the preconditioned residual is, we show how to stop the linear iteration using the preconditioned residual instead of the original one. On the other hand, we introduce damping parameters that modify the usual unitary secant step. Two natural damping parameters are introduced, one of them tries to reduce the true residual and the other one tries to reduce the preconditioned residual. We prove that the main results of the theory of secant preconditioners hold under these modifications. © 1995.601-2115125Broyden, A class of methods for solving nonlinear simultaneous equations (1965) Mathematics of Computation, 19, pp. 577-593Broyden, Dennis, Jr., Moré, On the local and superlinear convergence of quasi-Newton methods (1973) J. Inst. Math. Appl., 12, pp. 223-245Dembo, Eisenstat, Steihaug, Inexact Newton Methods (1982) SIAM Journal on Numerical Analysis, 19, pp. 400-408Dennis, Jr., Moré, A characterization of superlinear convergence and its application to quasi-Newton methods (1974) Mathematics of Computation, 28, pp. 549-560Dennis, Jr., Schnabel, Least Change Secant Updates for Quasi-Newton Methods (1979) SIAM Review, 21, pp. 443-459Dennis, Jr., Schnabel, (1983) Numerical Methods for Unconstrained Optimization and Nonlinear Equations, , Prentice-Hall, Englewood Cliffs, NJDennis, Jr., Walker, Convergence Theorems for Least-Change Secant Update Methods (1981) SIAM Journal on Numerical Analysis, 18, pp. 949-987Deuflhard, Global inexact Newton methods for very large scale nonlinear problems (1991) Impact Comput. Sci. Eng., 3, pp. 366-393Deuflhard, Freund, Walter, Fast secant methods for the iterative solution of large nonsymmetric linear systems (1990) Impact Comput. Sci. Eng., 2, pp. 244-276Duff, Erisman, Reid, (1986) Direct Methods for Sparse Matrices, , Clarendon Press, OxfordS.C. Eisenstat and H.F. Walker, Globally convergent inexact Newton methods, SIAM J. Optim., to appearGeorge, Ng, Symbolic Factorization for Sparse Gaussian Elimination with Partial Pivoting (1987) SIAM Journal on Scientific and Statistical Computing, 8, pp. 877-898Golub, Van Loan, (1989) Matrix Computations, , The Johns Hopkins Univ. Press, Baltimore and LondonGomes-Ruggiero, Martínez, The column-updating method for solving nonlinear equations in Hilbert space (1992) RAIRO Math. Modelling Numer. Anal., 26, pp. 309-330Gomes-Ruggiero, Martínez, Moretti, Comparing Algorithms for Solving Sparse Nonlinear Systems of Equations (1992) SIAM Journal on Scientific and Statistical Computing, 13, pp. 459-483Hestenes, Stiefel, Methods of conjugate gradients for solving linear systems (1952) Journal of Research of the National Bureau of Standards, 49 B, pp. 409-436D.N. Kozakevich, J.M. Martínez and M.C. Zambaldi, Experiments using secant preconditioners, in preparationMartínez, A quasi-Newton method with modification of one column per iteration (1984) Computing, 33, pp. 353-362Martínez, Local Convergence Theory of Inexact Newton Methods Based on Structured Least Change Updates (1990) Mathematics of Computation, 55, pp. 143-168Martínez, On the Relation between Two Local Convergence Theories of Least-Change Secant Update Methods (1992) Mathematics of Computation, 59, pp. 457-481Martínez, A Theory of Secant Preconditioners (1993) Mathematics of Computation, 60, pp. 681-698Martínez, On the convergence of the column-updating method (1993) Mat. Apl. Comput., 12, pp. 83-94Martínez, Qi, Inexact Newton methods for solving nonsmooth equations (1993) Relatório de Pesquisa 67/93, , Instituto de Matemática, Universidade Estadual de Campinas, BrazilMartínez, Zambaldi, An inverse column-updating method for solving large-scale nonlinear systems of equations (1991) Optimization Methods and Software, 1, pp. 129-140Nash, Newton-type minimization via the Lanczos method (1984) SIAM J. Numer. Anal., 21, pp. 770-787Nash, Preconditioning of Truncated-Newton Methods (1985) SIAM Journal on Scientific and Statistical Computing, 6, pp. 599-616Nazareth, Nocedal, A study of conjugate-gradient methods (1978) Tech. Report SOL 78-29, , Department of Operations Research, Stanford UniversityOrtega, Rheinboldt, (1970) Interative Solution of Nonlinear Equations in Several Variables, , Academic Press, New YorkOstrowski, (1973) Solution of Equations in Euclidean and Banach Spaces, , Academic Press, New YorkSaad, Schultz, GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems (1986) SIAM Journal on Scientific and Statistical Computing, 7, pp. 856-869Schwetlick, (1978) Numerische Lösung Nichtlinearer Gleichungen, , Deutscher Verlag der Wissenschaften, BerlinYpma, Local convergence of inexact Newton methods (1984) SIAM J. Numer. Anal., 21, pp. 583-59