Inexact perturbed Newton methods and applications to a class of Krylov solvers

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.

PDF

Scanned paper.

Publisher Name

Kluwer Academic Publishers-Plenum Publishers

0022-3239

1573-2878

0022-3239

1573-2878