Affine invariant conditions for the inexact perturbed Newton method

MSC 2000. 65 H 10 .
Keywords. inexact and inexact perturbed Newton methods, affine invariant conditions, convergence orders.

Given a nonlinear mapping $F:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$, the inexact Newton (IN) method for solving the system $F(x)=0$ is given by the iterations:

where $r_{k}$ represent the residuals of the approximate solutions $s_{k}$ of the linear systems. The local convergence of these iterates to a solution $x^{*}\in\mathbb{R}^{n}$ is usually studied under the following assumptions, which we shall implicitly assume throughout this paper:

• •

  the mapping $F$ is Fréchet differentiable on a neighborhood of $x^{*}$, with $F^{\prime}$ continuous at $x^{*}$;

  Report issue for preceding element
• •

  the Jacobian $F^{\prime}\left(x^{*}\right)$ is invertible.

  Report issue for preceding element

We recall that, given an arbitrary norm $\|\cdot\|$ on $\mathbb{R}^{n}$, a sequence $\left(x_{k}\right)_{k\geq 0}\subset\mathbb{R}^{n}$ is said that converges ( $q$-)superlinearly to its limit $\bar{x}\in\mathbb{R}^{n}$ if

also denoted by $\left\|x_{k+1}-\bar{x}\right\|=o\left(\left\|x_{k}-\bar{x}\right\|\right)$, as $k\rightarrow\infty$. For rigorous definitions and results concerning the high convergence orders we refer the reader to [11, ch. 9].

The high convergence orders of the IN iterates were characterized by Dembo, Eisenstat and Steihaug.

Theorem 1. 8. Assume that the IN iterates converge to $x^{*}$. Then the convergence is superlinear if and only if

If, additionally, $F^{\prime}$ is Hölder continuous with exponent $p\in(0,1]$ at $x^{*}$, i.e., there exist $L,\varepsilon>0$ such that

then the convergence is with order $1+p$ if and only if

In the inexact perturbed Newton (IPN) method there is assumed that at each step there appear different errors: the Jacobians are perturbed, the functions evaluations are approximately performed, and the resulting linear systems are only approximately solved:

We have obtained the following characterizations for the convergence of these iterates.

Theorem 2. 5. Assume that the IPN iterates are uniquely defined (i.e. the perturbations $\left(\Delta_{k}\right)_{k\geq 0}$ are such that the matrices $F^{\prime}\left(x_{k}\right)+\Delta_{k}$ are invertible for $k=0,1,\ldots$ ) and converge to $x^{*}$. Then the convergence is superlinear if and only if

If, additionally, $F^{\prime}$ is Hölder continuous with exponent $p\in(0,1]$ at $x^{*}$, then the convergence is with order $1+p$ if and only if

Theorem 3. [7]. Assume that the IPN iterates are well defined (i.e. the perturbed linear systems are compatible) and converge to $x^{*}$. Then the convergence is superlinear if and only if

If, additionally, $F^{\prime}$ is Hölder continuous with exponent $p\in(0,1]$ at $x^{*}$, then the convergence is with order $1+p$ if and only if

The affine invariant conditions are those conditions which do not change when considering, instead of the original system, the modified system $CF(x)=$ 0 , where $C\in\mathbb{R}^{n\times n}$ is nonsingular. The (exact) Newton iterates remain the same under such transformation, such that the conditions on the convergence of the iterates should also remain unchanged.

Ypma has obtained in [13] the following characterizations for the IN iterates, which are affine invariant.

Theorem 4. 13. Assume that the IN iterates converge to $x^{*}$. Then the convergence is superlinear if and only if

If, additionally, $F^{\prime}$ is Hölder continuous with exponent $p\in(0,1]$ at $x^{*}$, then the convergence is with order $1+p$ if and only if

Using this result, we obtain the following affine invariant results for the inexact perturbed Newton method:

Theorem 5. Assume that the IPN iterates are uniquely defined and converge to $x^{*}$. Then the convergence is superlinear if and only if

If, additionally, $F^{\prime}$ is Hölder continuous with exponent $p\in(0,1]$ at $x^{*}$, then the convergence is with order $1+p$ if and only if

Theorem 6. Assume that the IPN iterates are well defined and converge to $x^{*}$. Then the convergence is superlinear if and only if

If, additionally, $F^{\prime}$ is Hölder continuous with exponent $p\in(0,1]$ at $x^{*}$, then the convergence is with order $1+p$ if and only if

The proofs are easily obtained by using the fact that the IPN iterates are IN iterates having the residuals

[1] I. Argyros and F. Szidarovsky, The Theory and Applications of Iteration Methods, C.R.C. Press Inc., Boca Raton, FL, 1993.
[2] E. Cătinaş, On the high convergence orders of the Newton-GMBACK methods, Rev. Anal. Numér. Théor. Approx., 28 (1999) no. 2, 125-132.
[3] E. Cătinaş, Newton and Newton-Krylov Methods for Solving Nonlinear Systems in $\mathbb{R}^{n}$, Ph.D. thesis, "Babes-Bolyai" University of Cluj-Napoca, Romania, 1999.
[4] E. Cătinaş, A note on the quadratic convergence of the inexact Newton methods, Rev. Anal. Numér. Théor. Approx., 29 (2000) no. 2, 129-133.
[5] E. Catinaş, Inexact perturbed Newton methods and applications to a class of Krylov solvers, J. Optim. Theory Appl., 108 (2001) no. 3, 543-570.
[6] E. Cătinaş, On the superlinear convergence of the successive approximations method, J. Optim. Theory Appl., 113 (2002) no. 3, 473-485.
[7] E. Cătinaş, The inexact, inexact perturbed and quasi-Newton methods are equivalent models, Math. Comp. 74 (2005) no. 249, 291-301.
[8] Dembo, R. S., Eisenstat, S. C., and Steihaug, T., Inexact Newton methods, SIAM J. Numer. Anal., 19 (1982), pp. 400-408.
[9] Deuflhard, P. and Heindl, G., Affine invariant convergence theorems for Newton’s method and extensions to related methods, SIAM J. Numer. Anal., 16 (1979), pp. 1-10.
[10] Deuflhard, P. and Potra, F. A., Asymptotic mesh independence of Newton-Galerkin methods via a refined Mysovskii theorem, SIAM J. Numer. Anal., 29 (1992), pp. 13951412.
[11] Ortega, J. M. and Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
[12] Walker, H. F., An approach to continuation using Krylov subspace methods, Computational Science in the 21st Century, M.-O. Bristeau, G. Etgen, W. Fitzgibbon, J. L. Lions, J. Periaux and M. F. Wheeler, eds., John Wiley and Sons, Ltd., 1997, pp. 72-82.
[13] Ypma, T. J., Local convergence of inexact Newton methods, SIAM J. Numer. Anal., 21 (1984), pp. 583-590.

Received by the editors: October 3, 2001.