×

Inexact methods: Forcing terms and conditioning. (English) Zbl 1068.65505

Summary: In this paper, we consider inexact Newton and Newton-like methods and provide new convergence conditions relating the forcing terms to the conditioning of the iteration matrices. These results can be exploited when inexact methods with iterative linear solvers are used. In this framework, preconditioning techniques can be used to improve the performance of iterative linear solvers and to avoid the need of excessively small forcing terms. Numerical experiments validating the theoretical results are discussed.

MSC:

65H10 Numerical computation of solutions to systems of equations

Software:

KELLEY; NITSOL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brown, P. N., and Saad, Y., Convergence Theory ofNonlinear Newton–Krylov Algorithms, SIAM Journal on Optimization, Vol. 4, pp. 297–330, 1994. · Zbl 0814.65048 · doi:10.1137/0804017
[2] Dembo, R. S., Eisenstat, S. C., and Steihaug, T., Inexact Newton Methods, SIAM Journal on Numerical Analysis, Vol. 19, pp. 400–408, 1982. · Zbl 0478.65030 · doi:10.1137/0719025
[3] Eisenstat, S. C., and Walker, H. F., Choosing the Forcing Terms in an Inexact Newton Method, SIAM Journal on Scienti.c Computation, Vol. 17, pp. 16–32, 1996. · Zbl 0845.65021 · doi:10.1137/0917003
[4] Kelley, C. T., Iterative Methods for Linear and Nonlinear Equations, Frontiers in Applied Mathematics, SIAM, Philadelphia, Pennsylvania, Vol. 16, 1995. · Zbl 0832.65046
[5] Luksan, L., Inexact Trust–Region Method for Large Sparse Systems of Nonlinear Equations, Journal of Optimization Theory and Applications, Vol. 81, pp. 569–591, 1994. · Zbl 0803.65071 · doi:10.1007/BF02193101
[6] Luksan, L., and Vlceck, J., Computational Experience with Globally Convergent Descent Methods for Large Sparse Systems of Nonlinear Equations, Optimization Methods and Software, Vol. 8, pp. 201–223, 1998. · Zbl 0927.65068 · doi:10.1080/10556789808805677
[7] Morini, B., Convergence Behavior ofInexact Newton Methods, Mathematics of Computation, Vol. 68, pp. 1605–1613, 1999. · Zbl 0933.65050 · doi:10.1090/S0025-5718-99-01135-7
[8] Ypma, T. J., Local Convergence ofInexact Newton Methods, SIAM Journal on Numerical Analysis, Vol. 21, pp. 583–590, 1984. · Zbl 0566.65037 · doi:10.1137/0721040
[9] Brown, P. N., and Hindmarsh, A. C., Matrix-Free Methods for Stiff Systems of ODEs, SIAM Journal on Numerical Analysis, Vol. 23, pp. 610–638, 1986. · Zbl 0615.65078 · doi:10.1137/0723039
[10] Jackson, K. R., and Seward, K. R., Adaptive Linear Equation Solvers in Codes for Large Stiff Systems of ODEs, SIAM Journal on Scienti.c and Statistic Computation, Vol. 14, pp. 800–823, 1993. · Zbl 0795.65039 · doi:10.1137/0914051
[11] Morini, B., and Macconi, M., Inexact Methods in the Numerical Solution of Stiff Initial-Value Problems, Computing, Vol. 63, pp. 265–281, 1999. · Zbl 0946.65050 · doi:10.1007/s006070050034
[12] Pernice, M., and Walker, H. F., NITSOL: A Newton Iterative Solver, SIAM Journal on Scientific Computation, Vol. 19, pp. 302–318, 1998. · Zbl 0916.65049 · doi:10.1137/S1064827596303843
[13] Rheinboldt, W. C., On Measures ofIll-Conditioning for Nonlinear Equations, Mathematics of Computation, Vol. 30, pp. 104–111, 1976. · Zbl 0328.65032 · doi:10.1090/S0025-5718-1976-0400702-1
[14] Ortega, J. M., and Rheinboldt, W. C., Iterative Solution ofNonlinear Equations in Several Variables, Academic Press, New York, NY, 1970. · Zbl 0241.65046
[15] Dennis, J. E., and Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice Hall, Englewood Cliff, New Jersey, 1983. · Zbl 0579.65058
[16] Axelsson, O., Iterative Solution Methods, Cambridge University Press, Cambridge, England, 1994. · Zbl 0795.65014
[17] Greenbaum, A., Iterative Methods for Solving Linear Systems, Frontiers in Applied Mathematics, SIAM, Philadephia, Pennsylvania, Vol. 17, 1997. · Zbl 0883.65022
[18] Broyden, C.G., The Convergence ofan Algorithm for Solving Sparse Nonlinear Systems, Mathematics of Computation, Vol. 25, pp. 285–294, 1971. · Zbl 0227.65038 · doi:10.1090/S0025-5718-1971-0297122-5
[19] Schubert, L. K., Modification of a Quasi-Newton Method for Nonlinear Equations with Sparse Jacobian, Mathematics of Computation, Vol. 24, pp. 17–30, 1970. · Zbl 0198.49402 · doi:10.1090/S0025-5718-1970-0258276-9
[20] Saad, Y., and Schultz, M. H., GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems, SIAM Journal on Scientific and Statistic Computation, Vol. 7, pp. 856–869, 1986. · Zbl 0599.65018 · doi:10.1137/0907058
[21] Kelley, C. T., Solution ofthe Chandrasekhar H-Equation by Newton’s Method, Journal of Mathematical Physics, Vol. 21, pp. 1625–1628, 1980. · Zbl 0439.45020 · doi:10.1063/1.524647
[22] Golub, H., and Van Loan, C. F., Matrix Computations, 2nd Edition, Johns Hopkins University Press, Baltimore, Maryland, 1989. · Zbl 0733.65016
[23] Bischof, C. H., Incremental Condition Estimation, SIAM Journal on Matrix Analysis and Applications, Vol. 11, pp. 335–381, 1989.
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.