×

A globally convergent Newton-GMRES method for large sparse systems of nonlinear equations. (English) Zbl 1123.65040

A class of globally convergent inexact Newton methods, the Newton-GMRES with quasi-conjugate-gradient backtracking (NGQCGB) methods, for solving large sparse systems of nonlinear equations are presented. These methods can be considered as a suitable combination of the Newton-GMRES iteration and some efficient backtracking strategies. In some cases, known Newton-GMRES backtracking (NGB) methods stagnate for some iterations or even fail. To avoid this disadvantage of NGB methods the authors propose a new alternative strategy, called quasi-conjugate-gradient with backtracking (QCGB), using the known information such as the projection of the gradient of the merit function on a proper subspace and last nonlinear step. Numerical computations show that the NGQCGB method is more robust and efficient than both the NGB method and the Newton-GMRES with eqality curve backtracking (NGECB) method.

MSC:

65H10 Numerical computation of solutions to systems of equations

Software:

NITSOL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bai, Z.-Z.; Duff, I. S.; Wathen, A. J., A class of incomplete orthogonal factorization methods. I: Methods and theories, BIT Numer. Math., 41, 1, 53-70 (2001) · Zbl 0990.65038
[2] Bai, Z.-Z.; Golub, G. H.; Lu, L.-Z.; Yin, J.-F., Block triangular and skew-Hermitian splitting methods for positive-definite linear systems, SIAM J. Sci. Comput., 26, 3, 844-863 (2005) · Zbl 1079.65028
[3] Bai, Z.-Z.; Golub, G. H.; Ng, M. K., Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 24, 603-626 (2003) · Zbl 1036.65032
[4] Bai, Z.-Z.; Sun, J.-C.; Wang, D.-R., A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations, Comput. Math. Appl., 32, 12, 51-76 (1996) · Zbl 0870.65025
[5] Bai, Z.-Z.; Tong, P.-L., Multi-step update algorithms based on the factorization of Jacobian, J. Univ. Electr. Sci. Tech. China, 22, 3, 311-316 (1993), (in Chinese)
[6] Bai, Z.-Z.; Tong, P.-L., On the affine invariant convergence theorems of inexact Newton method and Broyden’s method, J. Univ. Electr. Sci. Tech. China, 23, 5, 535-540 (1994), (in Chinese)
[7] Bellavia, S.; Morini, B., A globally convergent Newton-GMRES subspace method for systems of nonlinear equations, SIAM J. Sci. Comput., 23, 940-960 (2001) · Zbl 0998.65053
[8] Bellavia, S.; Macconi, M.; Morini, B., A hybrid Newton-GMRES method for solving nonlinear equations, (Vulkov, L.; Wasniewski, J.; Yalamov, P., Lecture Notes in Computer Science, vol. 1988 (2000), Springer: Springer Berlin), 68-75 · Zbl 0978.65041
[9] Brown, P. N.; Saad, Y., Hybrid Krylov methods for nonlinear systems of equations, SIAM J. Sci. Statist. Comput., 11, 450-481 (1990) · Zbl 0708.65049
[10] Brown, P. N.; Saad, Y., Convergence theory of nonlinear Newton-Krylov algorithms, SIAM J. Optim., 4, 297-330 (1994) · Zbl 0814.65048
[11] Dembo, R. S.; Eisenstat, S. C.; Steihaug, T., Inexact Newton methods, SIAM J. Numer. Anal., 19, 400-408 (1982) · Zbl 0478.65030
[12] Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0579.65058
[13] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Prog. Ser. A, 19, 201-213 (2002) · Zbl 1049.90004
[14] Eisenstat, S. C.; Walker, H. F., Globally convergent inexact Newton methods, SIAM J. Optim., 4, 393-422 (1994) · Zbl 0814.65049
[15] Eisenstat, S. C.; Walker, H. F., Choosing the forcing term in an inexact Newton method, SIAM J. Sci. Comput., 17, 16-32 (1996) · Zbl 0845.65021
[16] Fokkema, D. R.; Sleijpen, G. L.G.; van der Vorst, H. A., Accelerated inexact Newton schemes for large systems of nonlinear equations, SIAM J. Sci. Comput., 19, 657-674 (1998) · Zbl 0916.65050
[17] Friedlander, A.; Gomes-Ruggiero, M. A.; Kozakevich, D. N.; Martinez, J. M.; Santos, S. A., Solving nonlinear systems of equations by means of quasi-Newton methods with a nonmonotone strategy, Optim. Methods Software, 8, 25-51 (1997) · Zbl 0893.65032
[18] Kaporin, I. E.; Axelsson, O., On a class of nonlinear equation solvers based on the residual norm reduction over a sequence of affine subspaces, SIAM J. Sci. Comput., 16, 228-249 (1995) · Zbl 0826.65048
[19] Knoll, D. A.; Keys, D. A., Jacobian-free Newton-Krylov method: A survey of approaches and applications, J. Comput. Phys., 193, 357-397 (2004) · Zbl 1036.65045
[20] Luksan, L., Inexact trust region method for large sparse systems of nonlinear equations, J. Optim. Theory Appl., 81, 569-591 (1994) · Zbl 0803.65071
[21] Ortega, J. M.; Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables (2000), SIAM: SIAM Philadelphia, PA · Zbl 0949.65053
[22] Pernice, M.; Walker, H. F., NITSOL: A Newton iterative solver for nonlinear systems, SIAM J. Sci. Comput., 19, 302-318 (1998) · Zbl 0916.65049
[23] Saad, Y., Iterative Methods for Sparse Linear Systems (1996), PWS Publishing Company: PWS Publishing Company Boston · Zbl 1002.65042
[24] Saad, Y.; Schultz, M. H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Comput., 7, 856-869 (1986) · Zbl 0599.65018
[25] Tuminaro, R. S.; Walker, H. F.; Shadid, J. N., On backtracking failure in Newton-GMRES methods with a demonstration for the Navier-Stokes equations, J. Comput. Phys., 180, 549-558 (2002) · Zbl 1143.76489
[26] Yuan, Y.-X.; Stoer, J., A subspace study on conjugate gradient algorithms, ZAMM, 75, 11, 69-77 (1995) · Zbl 0823.65061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.