Abstract
In inexact Newton methods for solving nonlinear systems of equations, an approximation to the step s k of the Newton’s system J(x k )s=−F(x k ) is found. This means that s k must satisfy a condition like ‖F(x k )+J(x k )s k ‖≤η k ‖F(x k )‖ for a forcing term η k ∈[0,1). Possible choices for η k have already been presented. In this work, a new choice for η k is proposed. The method is globalized using a robust backtracking strategy proposed by Birgin et al. (Numerical Algorithms 32:249–260, 2003), and its convergence properties are proved. Several numerical experiments with boundary value problems are presented. The numerical performance of the proposed algorithm is analyzed by the performance profile tool proposed by Dolan and Moré (Mathematical Programming Series A 91:201–213, 2002). The results obtained show a competitive inexact Newton method for solving academic and applied problems in several areas.
Similar content being viewed by others
References
Averick, B. M., Carter, R. G., Moré, J. J., & Xue, G.-L. (1992). The minpack-2 test problem collection. Preprint MCS-P153-0692, Mathematics and Computer Science Division, Argonne National Laboratory.
Birgin, E. G., Krejić, N., & Martínez, J. M. (2003). Globally convergent inexact quasi-Newton methods for solving nonlinear systems. Numerical Algorithms, 32, 249–260.
Bleistein, N. (1984). Mathematical methods for wave phenomena. San Diego: Academic.
Briggs, W. L., Henson, V. E., & McCormick, S. F. (2000). A multigrid tutorial (2nd ed.). Philadelphia: SIAM.
Brown, P. N., & Saad, Y. (1990). Hybrid Krylov methods for nonlinear systems of equations. SIAM Journal on Scientific and Statistical Computing, 11(3), 450–481.
Broyden, C. G. (1965). A class of methods for solving sparse nonlinear systems. Mathematics of Computation, 25, 285–294.
Broyden, C. G., Dennis, Jr., J.E., & Moré, J. J. (1973). On the local and superlinear convergence of quasi-Newton methods. Journal of the Institute of Mathematical Applications, 12, 223–245.
Dembo, R. S., Eisenstat, S. C., & Steihaug, T. (1982). Inexact Newton methods. SIAM Journal on Numerical Analysis, 19(2), 401–408.
Dennis Jr., J. E., & Schnabel, R. B. (1996). Numerical methods for unconstrained optimization and nonlinear equations. SIAM Classics in Applied Mathematics.
Diniz-Ehrhardt, M. A., Gomes-Ruggiero, M. A., Lopes, V. L. R., & Martínez, J. M. (2003). Discrete Newton’s method with local variations for solving large-scale nonlinear systems. Optimization, 52(4–5), 417–440.
Dolan, E. D., & Moré, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical Programming Series A, 91, 201–213.
Eisenstat, S. C., & Walker, H. F. (1994). Globally convergent inexact newton methods. SIAM Journal Optimization, 4(2), 393–422.
Eisenstat, S. C., & Walker, H. F. (1996). Choosing the forcing terms in inexact newton method. SIAM Journal on Scientific Computing, 17(1), 16–32.
Gomes-Ruggiero, M. A., & Martínez, J. M. (1992). The column-updating method for solving nonlinear equations in Hilbert space. Mathematical Modeling and Numerical Analysis, 26(2), 309–330.
Gomes-Ruggiero, M. A., Martínez, J. M., & Moretti, A. C. (1992). Comparing algorithms for solving sparse nonlinear systems of equations. SIAM Journal Scientific and Statistical Computing, 13(2), 459–483.
Gomes-Ruggiero, M. A., Kozakevich, D. N., & Martínez, J. M. (1996). A numerical study on large-scale nonlinear solver. Computers and Mathematics with Applications, 32(3), 1–13.
Kelley, C. T. (1995). Iterative methods for linear and nonlinear equations. Philadelphia: SIAM.
Li, D.-H., & Fukushima, M. (2000). Derivative-free line search and global convergence of Broyden-like method for nonlinear equations. Optimization Methods and Software, 13, 181–201.
Lopes, V. L. R., & Martínez, J. M. (1995). Convergence properties of the inverse column-updating method. Optimization Methods and Software, 6, 127–144.
Martínez, J. M. (1984). A quasi-Newton method with modification of one column per iteration. Computing, 33, 353–362.
Martínez, J. M., & Zambaldi, M. C. (1992). An inverse column-updating method for solving large-scale nonlinear systems of equations. Optimization Methods and Software, 1, 129–140.
Pernice, M., & Walker, H. F. (1998). NITSOL: a Newton iterative solver for nonlinear systems. SIAM Journal on Scientific Computing, 19(1), 302–318.
Saad, Y., & Schultz, M. H. (1986). GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on Scientific and Statistical Computing, 7(3), 856–869.
Toledo-Benavides, J. V. (2005). Um método Newton-GMRES globalmente convergente com um nova escolha para o termo forçante e algumas estratégias para melhorar o desempenho de GMRES( m ). PhD Thesis, Department of Applied Mathematics, State University of Campinas Imecc-Unicamp, T/Unicamp T575m.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by FAPESP, CNPq, PRONEX-Optimization.
Rights and permissions
About this article
Cite this article
Gomes-Ruggiero, M.A., Lopes, V.L.R. & Toledo-Benavides, J.V. A globally convergent inexact Newton method with a new choice for the forcing term. Ann Oper Res 157, 193–205 (2008). https://doi.org/10.1007/s10479-007-0196-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-007-0196-y