Newton-like method with modification of the right-hand-side vector

Krejić, Nataša; Lužanin, Zorana

doi:10.1090/S0025-5718-01-01322-9

Newton-like method with modification of the right-hand-side vector
HTML articles powered by AMS MathViewer

by Nataša Krejić and Zorana Lužanin PDF

Math. Comp. 71 (2002), 237-250 Request permission

Abstract:

This paper proposes a new Newton-like method which defines new iterates using a linear system with the same coefficient matrix in each iterate, while the correction is performed on the right-hand-side vector of the Newton system. In this way a method is obtained which is less costly than the Newton method and faster than the fixed Newton method. Local convergence is proved for nonsingular systems. The influence of the relaxation parameter is analyzed and explicit formulae for the selection of an optimal parameter are presented. Relevant numerical examples are used to demonstrate the advantages of the proposed method.

References

I. D. L. Bogle and J. D. Perkins, A new sparsity preserving quasi-Newton update for solving nonlinear equations, SIAM J. Sci. Statist. Comput. 11 (1990), no. 4, 621–630. MR 1054629, DOI 10.1137/0911036
Kenneth M. Brown, A quadratically convergent Newton-like method based upon Gaussian elimination, SIAM J. Numer. Anal. 6 (1969), 560–569. MR 263229, DOI 10.1137/0706051
J. C. P. Bus, Numerical solution of systems of nonlinear equations, Mathematical Centre Tracts, vol. 122, Mathematisch Centrum, Amsterdam, 1980. MR 589340
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 Earl S. Marwil, Direct secant updates of matrix factorizations, Math. Comp. 38 (1982), no. 158, 459–474. MR 645663, DOI 10.1090/S0025-5718-1982-0645663-8
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
L. C. W. Dixon, On the impact of automatic differentiation on the relative performance of parallel truncated Newton and variable metric algorithms, SIAM J. Optim. 1 (1991), no. 4, 475–486. MR 1129416, DOI 10.1137/0801028
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
Paul A. Farrell, John J. H. Miller, Eugene O’Riordan, and Grigori I. Shishkin, A uniformly convergent finite difference scheme for a singularly perturbed semilinear equation, SIAM J. Numer. Anal. 33 (1996), no. 3, 1135–1149. MR 1393906, DOI 10.1137/0733056
Gene H. Golub and Charles F. Van Loan, Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103
Márcia A. Gomes-Ruggiero, José Mario Martínez, and Antonio Carlos Moretti, Comparing algorithms for solving sparse nonlinear systems of equations, SIAM J. Sci. Statist. Comput. 13 (1992), no. 2, 459–483. MR 1149101, DOI 10.1137/0913025
Dragoslav Herceg, Nataša Krejić, and Zorana Lužanin, Quasi-Newton’s method with correction, Novi Sad J. Math. 26 (1996), no. 1, 115–127. MR 1458571
D. Herceg, N. Krejić, On a numerical method for discrete analogues of boundary value problems, Nonlinear Analysis, Theory, Methods & Applications, 30,1 (1997), 9-15.
L. Lukšan, Inexact trust region method for large sparse systems of nonlinear equations, J. Optim. Theory Appl. 81 (1994), no. 3, 569–590. MR 1281739, DOI 10.1007/BF02193101
L. Lukšan and J. Vlček, Computational experience with globally convergent descent methods for large sparse systems of nonlinear equations, Optim. Methods Softw. 8 (1998), no. 3-4, 201–223. MR 1623249, DOI 10.1080/10556789808805677
Z. Lužanin, Global and local convergence of modifications of Newton method, Ph.D. Thesis, Institute of Mathematics, Faculty of Science, University of Novi Sad, 1997.
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
José Mario Martínez, A family of quasi-Newton methods for nonlinear equations with direct secant updates of matrix factorizations, SIAM J. Numer. Anal. 27 (1990), no. 4, 1034–1049. MR 1051122, DOI 10.1137/0727061
J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
L. K. Schubert, Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 258276, DOI 10.1090/S0025-5718-1970-0258276-9