Abstract
Inexact Newton methods are variant of the Newton method in which each step satisfies only approximately the linear system [1]. The local convergence theory given by the authors of [1] and most of the results based on it consider the error terms as being provided only by the fact that the linear systems are not solved exactly. The few existing results for the general case (when some perturbed linear systems are considered, which in turn are not solved exactly) do not offer explicit formulas in terms of the perturbations and residuals.
We extend this local convergence theory to the general case, characterizing the rate of convergence (the q-convergence orders) in terms of the perturbations and residuals.
The Newton iterations are then analyzed when, at each step, an approximate solution of the linear system is determined by the following Krylov solvers based on backward error minimization properties: GMRES, GMBACK, MINPERT. We obtain results concerning the following topics: monotone properties of the errors in these Newton-Krylov iterates when the initial guess is taken 0 in the Krylov algorithms; control of the convergence orders of the Newton-Krylov iterations by the magnitude of the backward errors of the approximate steps; similarities of the asymptotical behavior of GMRES and MINPERT when used in a converging Newton method.
At the end of the paper, the theoretical results are verified on some numerical examples.
Authors
Emil Cătinaş
(Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy)
Keywords
nonlinear system of equations in Rn; inexact Newton method; perturbed Newton method; Krylov methods; linear systems of equation in Rn; backward errors; GMRES; GMBACK; MINPERT; Newton-Krylov methods; residual; local convergence; q-convergence order.
Cite this paper as:
E. Cătinaş, Inexact perturbed Newton methods and applications to a class of Krylov solvers, J. Optim. Theory Appl., 108 (2001) no. 3, pp. 543-570.
Scanned paper.
Latex-pdf version of the paper.
About this paper
Publisher Name
Kluwer Academic Publishers-Plenum Publishers
Print ISSN
0022-3239
Online ISSN
1573-2878
MR
0022-3239
Online ISSN
1573-2878
Google Scholar citations
[1] Dembo, R. S., Eisenstat, S. C., and Steigaug, T., Inexact Newton Methods, SIAM Journal on Numerical Analysis, Vol. 19, pp. 400–408, 1982. 568 JOTA: VOL. 108, NO. 3, MARCH 2001
[2] Ortega, J. M., and Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, NY, 1970.
[3] Kantorovich, L. V., and Akrilov, G. P., Functional Analysis, Editura S¸tiint¸ificaˇ s¸i Enciclopedicaˇ, Bucharest, Romania, 1986 (in Romanian).
[4] Pavaloiu, I., Introduction to the Theory of Approximating the Solutions of Equations, Editura Dacia, Cluj–Napoca, Romania, 1976 (in Romanian).
[5] Maruster St., Numerical Methods for Solûing Nonlinear Equations, Editura Tehnicaˇ, Bucharest, Romania, 1981 (in Romanian).
[6] Dennis, J. E., JR., and Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Series in Computational Mathematics, Prentice-Hall, Englewood Cliffs, New Jersey, 1983.
[7] Potra, F. A., and Ptak, V., Nondiscrete Induction and Iterative Processes, Pitman, London, England, 1984.
[8] Argyros, I., and Szidarovszky, F., The Theory and Applications of Iteration Methods, CRC Press, Boca Raton, Florida, 1993.
[9] Kelley, C. T., Iterative Methods for Linear and Nonlinear Equations, SIAM, Philadelphia, Pennsylvania, 1995.
[10] Rheinboldt, W. C., Methods for Solving Systems of Nonlinear Equations, SIAM, Philadelphia, Pennsylvania, 1998.
[11] Dennis, J. E., JR., and Walker, H. F., Inaccuracy in Quasi-Newton Methods: Local Improvement Theorems, Mathematical Programming Study, Vol. 22, pp. 70–85, 1984.
[12] Potra, F. A., and Ptak, K, V., Sharp Error Bounds for Newton’s Process, Numerische Mathematik, Vol. 34, pp. 63–72, 1980.
[13] Deuflhard, P., and Potra, F. A., Asymptotic Mesh Independence of Newton– Galerkin Methods via a Refined Mysovskii Theorem, SIAM Journal on Numerical Analysis, Vol. 29, pp. 1395–1412, 1992.
[14] Argyros, I., Concerning the Conûergence of Inexact Newton Methods, Journal of Computational and Applied Mathematics, Vol. 79, pp. 235–247, 1997.
[15] Argyros, I., On a New Newton–Mysoûskii-Type Theorem with Applications to Inexact Newton-Like Methods and Their Discretization, IMA Journal of Numerical Analysis, Vol. 18, pp. 37–56, 1998.
[16] Sherman, A. H., On Newton-Iterative Methods for the Solution of Systems of Nonlinear Equations, SIAM Journal on Numerical Analysis, Vol. 15, pp. 755– 771, 1978.
[17] Dennis, J. E., JR., and More , J. J., A Characterization of Superlinear Conûergence and Its Application to Quasi-Newton Methods, Mathematics of Computation, Vol. 28, pp. 549–560, 1974.
[18] Dennis, J. E., JR., and More, J. J., Quasi-Newton Methods, Motivation and Theory, SIAM Review, Vol. 19, pp. 46–89, 1977.
[19] Eisenstat, S. C., and Walker, H. F., Choosing the Forcing Terms in an Inexact Newton Method, SIAM Journal on Statistical and Scientific Computing, Vol. 17, pp. 16–32, 1996.
[20] Eisenstat, S. C., and Walker, H. F., Globally Convergent Inexact Newton Methods, SIAM Journal on Optimization, Vol. 4, pp. 393–422, 1994. JOTA: VOL. 108, NO. 3, MARCH 2001 569
[21] Ypma, T. J., The Effect of Rounding Errors on Newton-Like Methods, IMA Journal of Numerical Analysis, Vol. 3, pp. 109–118, 1983.
[22] Martinez, H. J., Parada, Z., and Tapia, R. A., On the Characterization of Q-Superlinear Convergence of Quasi-Newton Interior-Point Methods for Nonlinear Programming, Boletin de la Sociedad Matematica Mexicana, Vol. 1, pp. 137–148, 1995.
[23] Ypma, T. J., Local Convergence of Inexact Newton Methods, SIAM Journal on Numerical Analysis, Vol. 21, pp. 583–590, 1983.
[24] Cores, D., and Tapia, R. A., Perturbation Lemma for the Newton Method with Application to the SQP Newton Method, Journal of Optimization Theory and Applications, Vol. 97, pp. 271–280, 1998
[25] Potra, F. A., On Q-Order and R-Order of Convergence, Journal of Optimization Theory and Applications, Vol. 63, pp. 415–431, 1989.
[26] Brown, P. N., A Local Convergence Theory for Combined Inexact-Newton Finite-Difference Projection Methods, SIAM Journal on Numerical Analysis, Vol. 24, pp. 407–434, 1987.
[27] Catinas, E., A Note on Inexact Secant Methods, Revue d’Analyse Numerique et de Theorie de l’Approximation, Vol. 25, pp. 33–41, 1996.
[28] Krolikowska, M., Nonlinear Mappings with an Almost Sparse Jacobian Matrix, Annales Universitatis Mariae Curie–Skåodowska, Lublin, Poland, Vol. 49A, pp. 145–157, 1995.
[29] Rigal, J. L., and Gaches, J., On the Compatibility of a Given Solution with the Data of a Linear System, Journal of the Association for Computing Machinery, Vol. 14, pp. 543–548, 1967.
[30] Saad, Y., and Schultz, M. H., GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems, SIAM Journal on Scientific and Statistical Computing, Vol. 7, pp. 856–869, 1986.
[31] Saad, Y., Krylov, Subspace Methods for Solving Large Unsymmetric Linear Systems, Mathematics of Computation, Vol. 37, pp. 105–126, 1981.
[32] Kasenally, E. M., GMBACK: A Generalized Minimum Backward Error Algorithm for Nonsymmetric Linear Systems, SIAM Journal on Statistical and Scientific Computing, Vol. 16, pp. 698–719, 1995.
[33] Saad, Y., Iterative Methods for Sparse Linear Systems, PWS Publishing Company, Boston, Massachusetts, 1996.
[34] Brown, P. N., and SAAD, Y., Hybrid Krylov Methods for Nonlinear Systems of Equations, SIAM Journal on Scientific and Statistical Computing, Vol. 11, pp. 450–481, 1990.
[35] Turner, K., and Walker, H. F., Efficient High Accuracy Solutions with GMRES(m), SIAM Journal on Scientific and Statistical Computing, Vol. 13, pp. 815–825, 1992.
[36] Brown, P. N., and Hindmarsh, A. C., Reduced Storage Matrix Methods in Stiff ODE Systems, Applied Mathematics and Computation, Vol. 31, pp. 40– 91, 1989.
[37] Greenbaum, A., Ptak, V., and Strakos, Z., Any Nonincreasing Convergence Curve is Possible for GMRES, SIAM Journal on Matrix Analysis and Applications, Vol. 17, pp. 465–469, 1996. 570 JOTA: VOL. 108, NO. 3, MARCH 2001
[38] Brown, P. N., and Saad, Y., Convergence Theory of Nonlinear Newton–Krylov Algorithms, SIAM Journal on Optimization, Vol. 4, pp. 297–330, 1994.
[39] Brown, P. N., A Theoretical Comparison of the Arnoldi and GMRES Algorithms, SIAM Journal on Scientific and Statistical Computing, Vol. 12, pp. 58– 78, 1991.
[40] Kasenally, E. M., and Simoncini, V., Analysis of a Minimum Perturbation Algorithm for Nonsymmetric Linear Systems, SIAM Journal on Numerical Analysis, Vol. 34, pp. 48–66, 1997.
[41] Stewart, G. W., and Sun, J. G., Matrix Perturbation Theory, Academic Press, New York, NY, 1990.
[42] More, J. J., A Collection of Nonlinear Model Problems, Computational Solutions of Nonlinear Systems of Equations, Lectures in Applied Mathematics, Edited by E. L. Allgower and K. Georg, American Mathematical Society, Providence, Rhode Island, Vol. 26, pp. 723–762, 1990.
[43] Glowinski, R., Keller, H. B., and Reinhart, L., Continuation-Conjugate Gradient Methods for the Least-Squares Solution of Nonlinear Boundary-Value Problems, SIAM Journal on Scientific and Statistical Computing, Vol. 6, pp. 793–832, 1985.
[44] Catinas, E., Newton and Newton–Krylov Methods for Solving Nonlinear Systems in n , PhD Thesis, Babes–Bolyai University of Cluj–Napoca, Cluj–Napoca, Romania, 1999.