Let $F(x)=0$$F(x)=0$F(x)=0F(x)=0$F(x)=0$ be a nonlinear system, with $F:D\subseteq {\mathbb{R}}^n\to {\mathbb{R}}^n$$F:D\subseteq {\mathbb{R}}^n\to {\mathbb{R}}^n$F:D subeR^(n)rarrR^(n)F: D \subseteq \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$F:D\subseteq {\mathbb{R}}^n\to {\mathbb{R}}^n$. The local convergence of the Newton iterates

is studied under the following usual conditions (which will be implicitly assumed hereafter):

Given a norm $\Vert \cdot \Vert$$\Vert \cdot \Vert$||*||\|\cdot\|$\Vert \cdot \Vert$ on ${\mathbb{R}}^n$${\mathbb{R}}^n$R^(n)\mathbb{R}^{n}${\mathbb{R}}^n$, these hypotheses assure the existence of a radius $r>0$$r>0$r > 0r>0$r>0$ such that the Newton iterates converge $q$$q$qq$q$-superlinearly to $x^{\ast }$$x^{\ast }$x^(**)x^{*}$x^{\ast }$ for any initial approximation $x_0$$x_0$x_(0)x_{0}$x_0$ with $\Vert x_0-x^{\ast }\Vert <r$$‖x_0-x^{\ast }‖<r$||x_(0)-x^(**)|| < r\left\|x_{0}-x^{*}\right\|<r$\Vert x_0-x^{\ast }\Vert <r$ [8, Th.10.2.2] (see also [10, Th.4.4]):

also denoted by $\Vert x_{k+1}-x^{\ast }\Vert =o\left(\Vert x_k-x^{\ast }\Vert \right)$$‖x_{k+1}-x^{\ast }‖=o\left(‖x_k-x^{\ast }‖\right)$||x_(k+1)-x^(**)||=o(||x_(k)-x^(**)||)\left\|x_{k+1}-x^{*}\right\|=o\left(\left\|x_{k}-x^{*}\right\|\right)$\Vert x_{k+1}-x^{\ast }\Vert =o\left(\Vert x_k-x^{\ast }\Vert \right)$, as $k\to \mathrm{\infty }$$k\to \mathrm{\infty }$k rarr ook \rightarrow \infty$k\to \mathrm{\infty }$.
In the practical applications, there are used mainly two models of perturbed Newton iterates: the quasi-Newton (QN) and the inexact Newton (IN) method

The first model assumes the use of perturbed Jacobians, while the second assumes that at each step the correction $s_k$$s_k$s_(k)s_{k}$s_k$ is only approximately determined (i.e., having nonzero residual $r_k$$r_k$r_(k)r_{k}$r_k$ ). The superlinear convergence (as well as the $q$$q$qq$q$-orders $p\in (1,2]$$p\in (1,2]$p in(1,2]p \in(1,2]$p\in (1,2]$ ) of these methods was characterized by Dennis and Moré, respectively Dembo, Eisenstat and Steihaug.

Theorem 1.1 ([4]) Consider a sequence ${\left(B_k\right)}_{k\ge 0}\subset {\mathbb{R}}^{n\times n}$${\left(B_k\right)}_{k\ge 0}\subset {\mathbb{R}}^{n\times n}$(B_(k))_(k >= 0)subR^(n xx n)\left(B_{k}\right)_{k \geq 0} \subset \mathbb{R}^{n \times n}${\left(B_k\right)}_{k\ge 0}\subset {\mathbb{R}}^{n\times n}$ of invertible matrices and an initial approximation $x_0\in D$$x_0\in D$x_(0)in Dx_{0} \in D$x_0\in D$. If the QN iterates converge to $x^{\ast }$$x^{\ast }$x^(**)x^{*}$x^{\ast }$, then they converge superlinearly iff

Theorem 1.2 ([3]) If the IN iterates converge to $x^{\ast }$$x^{\ast }$x^(**)x^{*}$x^{\ast }$, then the convergence is superlinear iff

Denoting ${\mathrm{\Delta }}_k=B_k-F^{\prime }\left(x_k\right)$${\mathrm{\Delta }}_k=B_k-F^{\prime }\left(x_k\right)$Delta_(k)=B_(k)-F^(')(x_(k))\Delta_{k}=B_{k}-F^{\prime}\left(x_{k}\right)${\mathrm{\Delta }}_k=B_k-F^{\prime }\left(x_k\right)$, the quasi-Newton iterates are transcribed as (QN'):

The following two results show the connection between the conditions for the superlinear convergence of the two methods.
Theorem 1.3 ([2]) If the QN ' iterates are written as IN iterates,

then the (DES) condition for these resulted iterates is equivalent to the (DM) condition for the initial QN' iterates.

Let $\Vert \cdot {\Vert }_2$$\Vert \cdot {\Vert }_2$||*||_(2)\|\cdot\|_{2}$\Vert \cdot {\Vert }_2$ denote the Euclidean norm.
Theorem 1.4 ([2]) If the IN are written as QN ' iterates,

then the (DM) condition for these resulted iterates is equivalent to the (DES) condition for the initial IN iterates.

In [1] we have considered the inexact perturbed Newton (IPN) method and characterized its superlinear convergence:

Previous results contained only sufficient conditions. The elements ${\mathrm{\Delta }}_k\in {\mathbb{R}}^{n\times n}$${\mathrm{\Delta }}_k\in {\mathbb{R}}^{n\times n}$Delta_(k)inR^(n xx n)\Delta_{k} \in \mathbb{R}^{n \times n}${\mathrm{\Delta }}_k\in {\mathbb{R}}^{n\times n}$ represent perturbations to the Jacobians, ${\delta }_k\in {\mathbb{R}}^n$${\delta }_k\in {\mathbb{R}}^n$delta_(k)inR^(n)\delta_{k} \in \mathbb{R}^{n}${\delta }_k\in {\mathbb{R}}^n$ perturbations to the function evaluations, while ${\hat{r}}_k\in {\mathbb{R}}^n$${\widehat{r}}_k\in {\mathbb{R}}^n$hat(r)_(k)inR^(n)\hat{r}_{k} \in \mathbb{R}^{n}${\hat{r}}_k\in {\mathbb{R}}^n$ are the residuals of the approximate solutions $s_k$$s_k$s_(k)s_{k}$s_k$ of the resulted perturbed linear systems. The perturbation terms may contain errors resulted from floating point representation/arithmetical operations, so this model may be conceived to contain all sources of perturbations. In [1] we have assumed that the perturbed Jacobians are invertible. This condition may be relaxed, and one can assume just that the perturbed linear systems are compatible (i.e., the iterations are well defined):

Theorem 2.1 ([2]) If the IPN iterates are well defined and converge to $x^{\ast }$$x^{\ast }$x^(**)x^{*}$x^{\ast }$, then the convergence is superlinear iff

As shown in [2], the (DM) and (DES) conditions may be retrieved from the above one; on the other hand, the IPN iterates may be regarded as IN iterates, so it follows that the conditions characterizing the high convergence orders of the QN, IN and IPN methods are equivalent.

The above result can be successfully applied to characterize the convergence of some Newton-Krylov methods. Let

and consider an initial approximation $u_0$$u_0$u_(0)u_{0}$u_0$ to the exact solution $u^{\ast }=A^{-1}b$$u^{\ast }=A^{-1}b$u^(**)=A^(-1)bu^{*}=A^{-1} b$u^{\ast }=A^{-1}b$. Denote ${\mathcal{K}}_m:=\mathrm{span}\{r_0,A{r}_0,\dots ,A^{m-1}{r}_0\}$${\mathcal{K}}_m:=\mathrm{span}\left\{r_0,A{r}_0,\dots ,A^{m-1}{r}_0\right\}$K_(m):=span{r_(0),Ar_(0),dots,A^(m-1)r_(0)}\mathcal{K}_{m}:=\operatorname{span}\left\{r_{0}, A r_{0}, \ldots, A^{m-1} r_{0}\right\}${\mathcal{K}}_m:=\mathrm{span}\{r_0,A{r}_0,\dots ,A^{m-1}{r}_0\}$, $1\le m\le n$$1\le m\le n$1 <= m <= n1 \leq m \leq n$1\le m\le n$, where $r_0:=b-A{u}_0$$r_0:=b-A{u}_0$r_(0):=b-Au_(0)r_{0}:=b-A u_{0}$r_0:=b-A{u}_0$.

The GMBACK algorithm [5] finds $u_m^{GB}\in u_0+{\mathcal{K}}_m$$u_m^{GB}\in u_0+{\mathcal{K}}_m$u_(m)^(GB)inu_(0)+K_(m)u_{m}^{G B} \in u_{0}+\mathcal{K}_{m}$u_m^{GB}\in u_0+{\mathcal{K}}_m$ as argmin for (i.e., minimizes the backward error in $A$$A$AA$A$ )

where $\Vert \cdot {\Vert }_F$$\Vert \cdot {\Vert }_F$||*||_(F)\|\cdot\|_{F}$\Vert \cdot {\Vert }_F$ denotes the Frobenius norm. Depending on the parameters, the above problem may have a unique, several ones, or no solution at all. Therefore, Theorem 1.1 is not the best choice (whereas Theorem 2.1 is) for characterizing the superlinear convergence of the Newton-GMBACK iterates, when written in the QN form

The same holds for the MINPERT method [6] which finds $u_m^{MP}$$u_m^{MP}$u_(m)^(MP)u_{m}^{M P}$u_m^{MP}$ as argmin for (i.e., minimizes the joint backward error)

Acknowledgements I would like to express my gratitude to the organizers, who made possible my participation to the conference.

[1] E. Cătinaş, Inexact perturbed Newton methods and applications to a class of Krylov solvers, J. Optim. Theory Appl. 108 (2001), 543-570.
[2] E. Cătinaş, The inexact, inexact perturbed and quasi-Newton methods are equivalent models, Math. Comp., 74 (2005) no. 249, pp. 291-301.
[3] R. S. Dembo, S. C. Eisenstat and T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 19 (1982), 400-408.
[4] J. E. Dennis, Jr. and J. J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp. 28 (1974), 549-560.
[5] E. M. Kasenally, GMBACK: a generalised minimum backward error algorithm for nonsymmetric linear systems, SIAM J. Sci. Comput. 16 (1995), 698-719.
[6] E. M. Kasenally and V. Simoncini, Analysis of a minimum perturbation algorithm for nonsymmetric linear systems, SIAM J. Numer. Anal. 34 (1997), 48-66.
[7] C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, Philadelphia, 1995.
[8] J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
[9] F. A. Potra, $Q$$Q$QQ$Q$-superlinear convergence of the iterates in primal-dual interior-point methods, Math. Progr., 91 no. 1, Ser. A, pp. 99-115, 2001.
[10] W. C. Rheinboldt, Methods for Solving Systems of Nonlinear Equations, Second ed., SIAM, Philadelphia, PA, 1998.