Newtonlike method with modification of the righthandside vector
Authors:
Natasa Krejic and Zorana Luzanin
Journal:
Math. Comp. 71 (2002), 237250
MSC (2000):
Primary 65H10
Published electronically:
May 9, 2001
MathSciNet review:
1862997
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: This paper proposes a new Newtonlike method which defines new iterates using a linear system with the same coefficient matrix in each iterate, while the correction is performed on the righthandside 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.
 1.
I.
D. L. Bogle and J.
D. Perkins, A new sparsity preserving quasiNewton update for
solving nonlinear equations, SIAM J. Sci. Statist. Comput.
11 (1990), no. 4, 621–630. MR 1054629
(91f:65099), http://dx.doi.org/10.1137/0911036
 2.
Kenneth
M. Brown, A quadratically convergent Newtonlike method based upon
Gaussian elimination, SIAM J. Numer. Anal. 6 (1969),
560–569. MR 0263229
(41 #7834)
 3.
J.
C. P. Bus, Numerical solution of systems of nonlinear
equations, Mathematical Centre Tracts, vol. 122, Mathematisch
Centrum, Amsterdam, 1980. MR 589340
(81m:65072)
 4.
Ron
S. Dembo, Stanley
C. Eisenstat, and Trond
Steihaug, Inexact Newton methods, SIAM J. Numer. Anal.
19 (1982), no. 2, 400–408. MR 650059
(83b:65056), http://dx.doi.org/10.1137/0719025
 5.
J.
E. Dennis Jr. and Earl
S. Marwil, Direct secant updates of matrix
factorizations, Math. Comp.
38 (1982), no. 158, 459–474. MR 645663
(83d:65159), http://dx.doi.org/10.1090/S00255718198206456638
 6.
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
(85j:65001)
 7.
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
(93c:90079), http://dx.doi.org/10.1137/0801028
 8.
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
(96k:65037), http://dx.doi.org/10.1137/0917003
 9.
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
(97b:65086), http://dx.doi.org/10.1137/0733056
 10.
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
(85h:65063)
 11.
Márcia
A. GomesRuggiero, 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
(92j:65077), http://dx.doi.org/10.1137/0913025
 12.
Dragoslav
Herceg, Nataša
Krejić, and Zorana
Lužanin, QuasiNewton’s method with correction,
Novi Sad J. Math. 26 (1996), no. 1, 115–127. MR 1458571
(98h:65021)
 13.
D. Herceg, N. Krejic, On a numerical method for discrete analogues of boundary value problems, Nonlinear Analysis, Theory, Methods & Applications, 30,1 (1997), 915. CMP 98:06
 14.
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
(95b:65072), http://dx.doi.org/10.1007/BF02193101
 15.
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. 34,
201–223. MR 1623249
(99a:65071), http://dx.doi.org/10.1080/10556789808805677
 16.
Z. Luzanin, Global and local convergence of modifications of Newton method, Ph.D. Thesis, Institute of Mathematics, Faculty of Science, University of Novi Sad, 1997.
 17.
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
(96d:65002)
 18.
José
Mario Martínez, A family of quasiNewton methods for
nonlinear equations with direct secant updates of matrix
factorizations, SIAM J. Numer. Anal. 27 (1990),
no. 4, 1034–1049. MR 1051122
(91h:65084), http://dx.doi.org/10.1137/0727061
 19.
J.
M. Ortega and W.
C. Rheinboldt, Iterative solution of nonlinear equations in several
variables, Academic Press, New YorkLondon, 1970. MR 0273810
(42 #8686)
 20.
L.
K. Schubert, Modification of a quasiNewton method
for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 0258276
(41 #2923), http://dx.doi.org/10.1090/S00255718197002582769
 1.
 I. D. L. Bogle, J. D. Perkins, A new sparsity preserving quasiNewton update for solving nonlinear equations, SIAM J. Sci. Statist. Comp., 11 (1990), pp. 621630. MR 91f:65099
 2.
 K. M. Brown, A quadratically convergent Newtonlike method based upon Gaussian elimination, SIAM J. Numer. Anal., 6 (1969), pp.560569. MR 41:7834
 3.
 J. C. P. Bus, Numerical solution of systems of nonlinear equations, Tract 122, Mathematisch Centrum, Amsterdam, 1980. MR 81m:65072
 4.
 R. S. Dembo, S. C. Eisenstat and T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal., 19 (1982), pp.400408. MR 83b:65056
 5.
 J. E. Dennis and E. S. Marwil, Direct secant updates of matrix factorizations, Math. Comp., 38 (1982), pp.459474. MR 83d:65159
 6.
 J. E. Dennis, Jr. and R. B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall, Englewood Cliffs, NJ, 1983. MR 85j:65001
 7.
 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), 475486. MR 93c:90079
 8.
 S. C. Eisenstat and H. F. Walker, Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput., 17 (1996), pp.1632. MR 96k:65037
 9.
 P.A. Farrell, J.J.H. Miller, E. O'Riordan, G. I. Shishkin, A uniformly convergent finite difference scheme for a singularly perturbed semilinear equation, SIAM J. Numer. Anal. 33(3), (1996), 11351149. MR 97b:65086
 10.
 G. H. Golub, C. F. van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore, MD, 1983. MR 85h:65063
 11.
 M. A. GomesRuggiero, J. M. Martínez and A. C. Moretti, Comparing algorithms for solving sparse nonlinear system of equations, SIAM J. Sci. Comput., 13 (1992), pp.459483. MR 92j:65077
 12.
 D. Herceg, N. Krejic, Z. Luzanin, QuasiNewton's method with correction, Novi Sad J. Math., 26(1), 1996, pp. 115127. MR 98h:65021
 13.
 D. Herceg, N. Krejic, On a numerical method for discrete analogues of boundary value problems, Nonlinear Analysis, Theory, Methods & Applications, 30,1 (1997), 915. CMP 98:06
 14.
 L. Luksan, Inexact trust region method for large sparse systems of nonlinear equations, JOTA, 81(3), 1994, pp. 569590. MR 95b:65072
 15.
 L. Luksan, J. Vlcek, Computational experience with globally convergent descent methods for large sparse systems of nonlinear equations, Optimization Methods and Software 8 (1998), 201224. MR 99a:65071
 16.
 Z. Luzanin, Global and local convergence of modifications of Newton method, Ph.D. Thesis, Institute of Mathematics, Faculty of Science, University of Novi Sad, 1997.
 17.
 C. T. Kelley, Iterative methods for linear and nonlinear equations, SIAM, Philadelphia, 1995. MR 96d:65002
 18.
 J. M. Martínez, A Family of quasiNewton methods for nonlinear equations with direct secant updates of matrix factorizations, SIAM J. Numer. Anal. 27 (1990), pp.10341049. MR 91h:65084
 19.
 J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York, 1970. MR 42:8686
 20.
 I. K. Schubert, Modification of a quasiNewton method for nonlinear equation with a sparse Jacobian, Math. Comp. 24 (1970), pp.2730. MR 41:2923
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
65H10
Retrieve articles in all journals
with MSC (2000):
65H10
Additional Information
Natasa Krejic
Affiliation:
Institute of Mathematics, University of Novi Sad, Trg Dositeja Obradovića 4, 21000 Novi Sad, Yugoslavia
Email:
natasa@unsim.im.ns.ac.yu
Zorana Luzanin
Affiliation:
Institute of Mathematics, University of Novi Sad, Trg Dositeja Obradovića 4, 21000 Novi Sad, Yugoslavia
Email:
luzanin@uns.ns.ac.yu
DOI:
http://dx.doi.org/10.1090/S0025571801013229
PII:
S 00255718(01)013229
Keywords:
Nonlinear systems,
Newton method,
chord method
Received by editor(s):
June 22, 1998
Received by editor(s) in revised form:
August 22, 1999, and March 29, 2000
Published electronically:
May 9, 2001
Article copyright:
© Copyright 2001
American Mathematical Society
