Consider the system of nonlinear equations

where $F:\mathbb{R}^{N}\rightarrow\mathbb{R}^{N}$ is a nonlinear mapping and suppose that:
(C1) There exists $x^{*}\in\mathbb{R}^{N}$ such that $F\left(x^{*}\right)=0$.
A classical approach for approximating $x^{*}$ is the Newton method, which results in the following algorithm:
(NM) Choose an initial approximation $x_{0}\in\mathbb{R}^{N}$.
For $k=0,1,\ldots$ until convergence, do the following steps.
Step 1. Solve $F^{\prime}\left(x_{k}\right)s_{k}=-F\left(x_{k}\right)$.
Step 2. Set $x_{k+1}=x_{k}+s_{k}$.
At each iteration of the Newton method, a routine for solving the resulting linear system must be called. The direct methods for linear systems cannot offer always the exact solution when used in floating point arithmetic and they may be inefficient for large general systems. Usually, some of the iterative methods cannot offer the exact solution after a finite number of steps even in exact arithmetic. Another fact is that, when $x_{k}$ is far from $x^{*}$, it may be worthless to solve exactly the system. These reasons require a convergence analysis which takes into account some error terms.

Several Newton-type methods have been studied. Some sufficient conditions for different convergence orders have been given in Refs. 2-16 and references therein. A characterization of superlinear convergence and of convergence with orders $1+p,p\in(0,1]$, has been obtained by Dennis and Moré in Refs. 17-18 for sequences given by the following quasi-Newton method:

$\left(B_{k}\right)_{k\geq 0}\subset\mathbb{R}^{N\times N}$ being a sequence of invertible matrices.
A characterization of local superlinear convergence and local convergence with orders $1+p,p\in(0,1]$, of the Newton methods which take into account other error terms has been given by Dembo, Eisenstat, and Steihaug (Ref. 1). They considered in their paper the following inexact Newton method:
(INM) Choose an initial approximation $x_{0}\in\mathbb{R}^{N}$. For $k=0,1,\ldots$, until convergence, do the following steps.

Step 1. Find $s_{k}$ such that $F^{\prime}\left(x_{k}\right)s_{k}=-F\left(x_{k}\right)+r_{k}$.
Step 2. Set $x_{k+1}=x_{k}+s_{k}$.

The error terms (residuals) $r_{k}$ represent the amounts by which the solutions $s_{k}$, determined in an unspecified manner, fail to satisfy the exact systems (NM). Their magnitudes are determined by the relative residuals $\left\|r_{k}\right\|/\left\|F\left(x_{k}\right)\right\|$, supposed to be bounded by the forcing sequence $\left(\eta_{k}\right)_{k\geq 0}$,

The local convergence analysis given in Ref. 1 characterizes the convergence orders of $\left(x_{k}\right)_{k\geq 0}$ given by the (INM) in terms of the magnitudes of $r_{k}$; see also Refs. 19-20 for other convergence results. However, in this paper as well as in most other papers using these results, the error terms $r_{k}$ are considered to appear only because the exact Newton systems (NM) are solved approximately. But in many situations, it is hard to find the exact value of $F^{\prime}(x)$, and in some cases even of $F(x)$. On the other hand, $F^{\prime}(x)$ or its approximation and $F(x)$ are both altered when represented in floating point arithmetic.

The question that arises naturally is: What magnitudes can we allow in perturbing the matrices $F^{\prime}\left(x_{k}\right)$ and the vectors $-F\left(x_{k}\right)$ so that the convergence order of the resulting method does not decrease?

The Newton methods with perturbed linear systems have been considered by several authors (see for instance Refs. 9, 11, 21, and references therein), but these methods were not analyzed with respect to their convergence orders.

Martinez, Parada, and Tapia (Ref. 22) have analyzed the superlinear convergence of sequences given by the following damped and perturbed quasi-Newton method:

where $0<\alpha_{k}\leq 1,r_{k}\in\mathbb{R}^{N},k=0,1,\ldots$, and $x_{0}\in\mathbb{R}^{N}$; but their superlinear convergence was not characterized simultaneously in terms of $\alpha_{k},B_{k},r_{k}$.

In Ref. 23, Ypma studied the case when the matrices $F^{\prime}\left(x_{k}\right)$ and the vectors $-F\left(x_{k}\right)$ are calculated approximately, the resulting linear systems being solved inexactly. However, the residuals were considered to be incorporated in those perturbed linear systems. Consequently, the obtained convergence results do not offer explicit formulas in terms of the magnitude of the perturbations and residuals. Recently, Cores and Tapia (Ref. 24) have considered the exact solving of perturbed linear systems, but they have obtained only sufficient conditions on the perturbations for different convergence orders to be attained.

We consider here the perturbations $\left(\Delta_{k}\right)_{k\geq 0}\subset\mathbb{R}^{N\times N}$ and $\left(\delta_{k}\right)_{k\geq 0}\subset\mathbb{R}^{N}$, being led to the study of the following inexact perturbed Newton method:

The terms $\hat{r}_{k}$ denote the residuals of the approximate solutions $s_{k}$ of the linear systems

When these systems are assumed to be solved exactly [i.e., $\hat{r}_{k}=0,k=0,1,\ldots$, in the (IPNM)], we call the resulting method a perturbed Newton method,

This frame will be useful for the study of some Newton-Krylov methods in connection with backward errors.

The paper is structured as follows. In Section 2, we give two convergence results for the (IPNM). In Section 3, we characterize the superlinear convergence and the convergence with orders $1+p,p\in(0,1]$, of the (IPNM), and we also provide some sufficient conditions. In Section 4, we analyze the Newton methods in which the linear systems from each step are solved by Gmres, Gmback, or Minpert. We verify the obtained theoretical results on numerical examples performed on two test problems (Section 5), and we end the paper with concluding remarks.

Throughout the paper, we consider the Euclidean norm (denoted by $\|\cdot\|_{2}$ ) and an arbitrary given norm on $\mathbb{R}^{N}$ (denoted by $\|\cdot\|$ ), together with their induced operator norms. We use also the Frobenius norm of a matrix $Z\in\mathbb{R}^{M\times N}$, defined as

We use the column notation for vectors; when we write vectors (or matrices) inside square brackets, we consider the matrix containing on columns those vectors (or the columns of those matrices). The same convention is used when joining rows. As usual, the vectors $e_{i},i=1,\ldots,n$, form the standard basis in $\mathbb{R}^{n},n$ being clear from the context.

The common conditions for the local convergence analysis of the Newton method are Condition (C1) and the following additional conditions:
(C2) The mapping $F$ is differentiable on a neighborhood of $x^{*}$ and $F^{\prime}$ is continuous at $x^{*}$.
(C3) The Jacobian $F^{\prime}\left(x^{*}\right)$ is nonsingular.
These conditions ensure that $x^{*}$ is a point of attraction for the Newton method; i.e., there exists $\epsilon>0$ such that $\left(x_{k}\right)_{k\geq 0}$ given by the Newton method converges to $x^{*}$ for any initial approximation $x_{0}\in\mathbb{R}^{N}$ with $\left\|x_{0}-x^{*}\right\|<\epsilon$.

Moreover, the convergence is $q$-superlinear ³; see Ref. 2, Theorem 10.2.2 and Ref. 10, Theorem 4.4.

In the convergence analysis of the (IPNM) iterations, we assume that:
(C4) The perturbations $\Delta_{k}$ are such that the matrices $F^{\prime}\left(x_{k}\right)+\Delta_{k}$ are nonsingular for $k=0,1,\ldots$.

Though different in notation, in fact this condition is similar to the one considered for the quasi-Newton iterates, which requires a sequence of invertible matrices $\left(B_{k}\right)_{k\geq 0}$.

The following sufficient condition for the convergence of the (INM) was proved by Dembo, Eisenstat, and Steihaug (Ref. 1).

Theorem 2.1. See Ref. 1. Assume Conditions (C1)-(C3) and $\eta_{k}\leq\eta_{\text{max }}<t<1,k=0,1,\ldots$. There exists $\boldsymbol{\epsilon}>0$ such that, if $\left\|x_{0}-x^{*}\right\|\leq\boldsymbol{\epsilon}$, then the sequence of the (INM) iterates $\left(x_{k}\right)_{k\geq 0}$ satisfying (2) converges to $x^{*}$. Moreover, the convergence is linear, in the sense that

where $\|y\|_{*}=\left\|F^{\prime}\left(x^{*}\right)y\right\|$.
Using this theorem, we obtain the following convergence results for the (IPNM).

Theorem 2.2. Assume Conditions (C1)-(C4) and $\eta_{k}\leq\eta_{\max}<t<1$, $k=0,1,\ldots$. There exists $\boldsymbol{\epsilon}>0$ such that, if $\left\|x_{0}-x^{*}\right\|\leq\epsilon$ and $\left\|\Delta_{k}\left[F^{\prime}\left(x_{k}\right)+\Delta_{k}\right]^{-1}F\left(x_{k}\right)+\left\{I-\Delta_{k}\left[F^{\prime}\left(x_{k}\right)+\Delta_{k}\right]^{-1}\right\}\left(\delta_{k}+\hat{r}_{k}\right)\right\|\leq\eta_{k}\left\|F\left(x_{k}\right)\right\|$, for $k=0,1,\ldots$, then the sequence of the (IPNM) iterates $\left(x_{k}\right)_{k\geq 0}$ converges to $x^{*}$, the convergence being linear,

Proof. The (IPNM) can be viewed as an (INM) with

Denoting

the conclusion follows from Theorem 2.1.

Corollary 2.1. Assume Conditions (C1)-(C4). There exists $\boldsymbol{\epsilon}>0$ such that, if $\left\|x_{0}-x^{*}\right\|\leq\epsilon$ and

then the sequence of the (IPNM) iterates $\left(x_{k}\right)_{k\geq 0}$ converges to $x^{*}$. Moreover, the convergence is linear,

where $t=q_{1}+q_{2}$.
Proof. The proof is obtained easily from the previous result making use of the hypotheses.

Remark 2.1. The idea of reducing certain perturbed Newton methods to (INM) iterations, which is used in the proof of Theorem 2.2, can be found in the work of several authors; see for example Refs. 9-10 and 26. The inexact secant methods considered by us in Ref. 27 are in fact instances of the (IPNM) model, but it was Ref. 28 that inspired us to consider the (IPNM).

Stronger conditions imposed on the continuity of $F^{\prime}$ at $x^{*}$ offer higher convergence orders for the Newton method. Namely, if $F^{\prime}$ is Hölder continuous at $x^{*}$ with exponent $p,p\in(0,1]$, i.e., if there exist $\epsilon>0$ and $L\geq 0$ such that

then the Newton method converges locally with $q$-order at least $1+p$; see Ref. 2, Theorem 10.2.2 and Ref. 10, Theorem 4.4.

For the inexact Newton methods, Dembo, Eisenstat, and Steihaug proved the following result.

Theorem 3.1. See Ref. 1. Assume that Conditions (C1)-(C3) hold and that the inexact Newton iterates $\left(x_{k}\right)_{k\geq 0}$ converge to $x^{*}$. Then, $x_{k}\rightarrow x^{*}q$-superlinearly if and only if

Moreover, if $F^{\prime}$ is Hölder continuous at $x^{*}$ with exponent $p,p\in(0,1]$, then $x_{k}\rightarrow x^{*}$ with $q$-order at least $1+p$ if and only if

We obtain the following result for the inexact perturbed Newton methods.

Theorem 3.2. Assume that Conditions (C1)-(C4) hold and that the iterates $\left(x_{k}\right)_{k\geq 0}$ given by the (IPNM) converge to $x^{*}$. Then, $x_{k}\rightarrow x^{*}q$-superlinearly if and only if
$\left\|\Delta_{k}\left[F^{\prime}\left(x_{k}\right)+\Delta_{k}\right]^{-1}F\left(x_{k}\right)+\left\{I-\Delta_{k}\left[F^{\prime}\left(x_{k}\right)+\Delta_{k}\right]^{-1}\right\}\left(\delta_{k}+\hat{r}_{k}\right)\right\|=o\left(\left\|F\left(x_{k}\right)\right\|\right)$, as $k\rightarrow\infty$. Moreover, if $F^{\prime}$ is Hölder continuous at $x^{*}$ with exponent $p$, then $x_{k}\rightarrow x^{*}$ with $q$-order at least $1+p$ if and only if
$\left\|\Delta_{k}\left[F^{\prime}\left(x_{k}\right)+\Delta_{k}\right]^{-1}F\left(x_{k}\right)+\left\{I-\Delta_{k}\left[F^{\prime}\left(x_{k}\right)+\Delta_{k}\right]^{-1}\right\}\left(\delta_{k}+\hat{r}_{k}\right)\right\|=O\left(\left\|F\left(x_{k}\right)\right\|^{1+p}\right)$, as $k\rightarrow\infty$.

Proof. The proof is obtained from the previous theorem by using (3).

In the following result, we characterize the convergence orders of the (IPNM) iterates in terms of the rate of convergence to zero of residuals and perturbations.

Corollary 3.1. Assume that:
(a) Conditions (C1)-(C4) hold;
(b) $\Delta_{k}\rightarrow 0,\delta_{k}\rightarrow 0,\hat{r}_{k}\rightarrow 0$, as $k\rightarrow\infty$;
(c) the sequence $\left(x_{k}\right)_{k\geq 0}$ given by the (IPNM) converges to $x^{*}$.

In addition, if

then, $x_{k}\rightarrow x^{*}q$-superlinearly.

Under the same assumptions (a)-(c), if additionally $F^{\prime}$ is Hölder continuous at $x^{*}$ with exponent $p$, and if

then $x_{k}\rightarrow x^{*}$ with $q$-order at least $1+p$.
The corresponding results for the $r$-convergence orders of the (IPNM) iterates may be stated in a similar manner, taking into account the existing results for the (INM); see Ref. 1, Theorem 3.4 and Corollary 3.5.

Consider the nonsymmetric linear system

with $A\in\mathbb{R}^{N\times N}$ nonsingular and $b\in\mathbb{R}^{N}$. The Krylov methods for solving such a system when the dimension $N$ is large are based on the Krylov subspaces, defined for any initial approximation $x_{0}\in\mathbb{R}^{N}$ as

where

is the initial residual and $m\in\{1,\ldots,N\}$.
The normwise backward error of an approximate solution $\tilde{x}$ of (4) was introduced by Rigal and Gaches (Ref. 29) and is defined by

where the parameters $E\in\mathbb{R}^{N\times N}$ and $f\in\mathbb{R}^{N}$ are arbitrary. The value of $\Pi(\tilde{x})$ is

and the minimum is attained by the backward errors
$\Delta_{A}=\left[\|E\|_{F}\cdot\|\tilde{x}\|_{2}/\left(\|E\|_{F}\cdot\|\tilde{x}\|_{2}+\|f\|_{2}\right)\right](b-A\tilde{x})z^{t},\quad$ with $z=\left(1/\|\tilde{x}\|_{2}^{2}\right)\tilde{x}$,
$\Delta_{b}=-\left[\|f\|_{2}/\left(\|E\|_{F}\cdot\|\tilde{x}\|_{2}+\|f\|_{2}\right)\right](b-A\tilde{x})$.

We shall analyze the behavior of the following three Krylov solvers when used for the linear systems arising in the Newton methods: Gmres, Gmback, Minpert. Each of these solvers is based on backward error minimization properties, as we shall see.

In order to use some existing notations, we prefer to denote hereafter by $y^{*}$ the solution of the nonlinear system (1) and by $y_{k}$ the iterates from the Newton methods, using $x$ in the involved linear systems.
4.1. Newton-Gmres Method. Given an initial approximation $x_{0}\in\mathbb{R}^{N}$, the Gmres method of Saad and Schultz (Ref. 30) uses the Arnoldi process (see Ref. 31) to construct an orthonormal basis $\left\{v_{1},\ldots,v_{m}\right\}$ in the Krylov subspace $\mathscr{K}_{m}$. The approximation $x_{m}^{\mathrm{GM}}\in x_{0}+\mathscr{K}_{m}$ is then determined such that

Kasenally has noted in Ref. 32 that the minimizing property of $x_{m}^{\mathrm{GM}}$ may be expressed in terms of the backward errors, namely,

i.e, $x_{m}^{\mathrm{GM}}$ minimizes over $x_{0}+\mathscr{K}_{m}$ the backward error $\Delta_{b}$, assuming $\Delta_{A}=0$.

The solution $x_{m}^{\mathrm{GM}}$ is determined roughly in the following way (see also Ref. 33):
(i) Arnoldi Process. Determine $V_{m}=\left[v_{1},\ldots,v_{m}\right]\in\mathbb{R}^{N\times m}$ and the upper Hessenberg matrix $\bar{H}_{m}\in\mathbb{R}^{(m+1)\times m}$.
(ii) Gmres Solution. Find the exact solution $y_{m}^{\mathrm{GM}}$ of the following least squares problem in $\mathbb{R}^{m}$ :

The Gmres method is used in an iterative fashion. Saad and Schultz proved that, at each step, the solution $x_{m}^{\text{GM }}$ is uniquely determined and that the algorithm breaks down in the Arnoldi method only if the exact solution has been reached. Moreover, the process terminates in at most $N$ steps. In the results presented below, we shall assume, as usually, that the Krylov methods do not continue after the exact solution has been determined.

First, we introduce some notations for the restarted Gmres iterations in order to express the relations which they satisfy.

Since only small values of $m$ are attractive in practice, an upper bound $\bar{m}\in\{1,\ldots,N-1\}$ is usually fixed for the subspace dimensions. If after $\bar{m}$ steps the computed solution does not have a sufficiently small residual, the Gmres method is restarted, taking for the initial approximation the last computed solution. We denote by $x_{m}^{\mathrm{GM}(0)},m\in\{1,\ldots,\bar{m}\}$, the first $\bar{m}$ solutions, by $x_{m}^{\mathrm{GM}(1)},m\in\{1,\ldots,\bar{m}\}$, the $\bar{m}$ solutions from the first restart, and so on. The value of the initial approximation $x_{0}$ will be clear from the context. For the nonrestarted version, we shall use the common notations $x_{m}^{\mathrm{GM}}$, while for a generic Gmres solution ⁴, we shall simply write $x^{\mathrm{GM}}$; the corresponding notations for the $k$ th correction from a Newton-Gmres method will be $s_{k,m}^{\mathrm{GM}}\left[\mathrm{resp}.s_{k}^{\mathrm{GM}}\right]$.

The choice $x_{0}=0$ in the Krylov solvers is a popular one when no better guess is known; see e.g. Refs. 26 and 34-35. With the above notation, the following result is obtained immediately from the properties of the Gmres solutions. Certain affirmations from this result are more or less explicitly stated in some papers dealing with Gmres; see for example Refs. 26 and 36-37.

Proposition 4.1. Consider the linear system (4) and the initial approximation $x_{0}=0$. Then, the following statements are true:
(i) For any $m\in\{1,\ldots,N\}$, the residual $r_{m}^{\mathrm{GM}}$ of the Gmres solution satisfies
$\left\|r_{m}^{\mathrm{GM}}\right\|_{2}\leq\|b\|_{2}$.
Moreover, the inequality is strict if and only if the solution $x_{m}^{\mathrm{GM}}$ is nonzero.
(ii) The residuals associated to the $N$ successive solutions satisfy
$0=\left\|r_{N}^{\mathrm{GM}}\right\|_{2}\leq\left\|r_{N-1}^{\mathrm{GM}}\right\|_{2}\leq\cdots\leq\left\|r_{1}^{\mathrm{GM}}\right\|_{2}\leq\|b\|_{2}$.
The inequality between the norms of two consecutive residuals is strict if and only if the corresponding Gmres solutions are distinct.
(iii) For any fixed upper bound $\bar{m}\in\{1,\ldots,N-1\}$, the residuals of the restarted Gmres method satisfy

The inequality between the norms of two consecutive residuals is strict if and only if the corresponding Gmres solutions are distinct; the residuals may eventually get to zero or may indefinitely stagnate, depending on the problem.

Considering the linear systems from the Newton method, we get easily the following proposition.

Proposition 4.2. Let $y\in D$ be an element for which the derivative $F^{\prime}(y)$ is nonsingular. Applying the Gmres method with $x_{0}=0$ to the linear system $F^{\prime}(y)s=-F(y)$, then for all $m\in\{1,\ldots,N\}$, the residual satisfies

Moreover, the above inequality is strict if and only if the correction $s_{m}^{\mathrm{GM}}$ is nonzero.

We have chosen to state the result corresponding only to part (i) of Proposition 4.1. The other results are similarly enounced.

Brown (Ref. 26) and Brown and Saad (Ref. 38) considered solving (1) by global minimization,

when $F:\mathbb{R}^{N}\rightarrow\mathbb{R}^{N}$. They obtained that any nonzero correction from a certain step of the Newton-Gmres method with $x_{0}=0$ in Gmres is a descent direction for the above minimization problem. Now, we are able to describe this positive behavior in terms of the distance to the solution.

Theorem 4.1. Assume that the mapping $F$ satisfies Conditions (C1)-(C3), and consider a current approximation $y_{c}\neq y^{*}$ for $y^{*}$. Let $s^{\text{GM }}$ be a nonzero approximate solution of the linear system $F^{\prime}\left(y_{c}\right)s=-F\left(y_{c}\right)$ provided by Gmres, assuming the initial guess $x_{0}=0$. Let $y_{+}=y_{c}+s^{\mathrm{GM}}$, denote $\eta=\left\|r^{\mathrm{GM}}\right\|_{2}/\left\|F\left(y_{c}\right)\right\|_{2}$, and take $t\in(\eta,1)$. If $y_{c}$ is sufficiently close to $y^{*}$, then

where $\|y\|_{*}=\left\|F^{\prime}\left(y^{*}\right)y\right\|_{2}$.
Proof. The thesis can be proved easily with slight modifications of the proof of Theorem 2.1, given in Ref. 1.

The above result says that, when using Gures (with $x_{0}=0$ ) in the Newton method, any nonzero correction improves the current outer
approximation, provided that the approximation is sufficiently good. Though this theorem guarantees a nonincreasing curve for the errors of the Newton-Gmres iterations starting from a sufficiently good approximation, the local convergence is not guaranteed. It is sufficient to notice that, considering a sequence obeying at each step the hypotheses of the above result, there may appear a situation when the set of forcing terms has 1 as accumulation point, in which case Theorem 2.1 cannot be applied.

The following theoretical example shows that, when the dimensions of the Krylov subspaces are smaller than $N$, the outer iterations may stagnate at the initial approximation $y_{0}\neq y^{*}$, no matter how close to $y^{*}$ we choose $y_{0}$.

Example 4.1. Consider

for which

The Newton method for solving $F(y)=0$ should yield the unique solution $y^{*}=0$ in one iteration for any $y_{0}\in\mathbb{R}^{N}$, whenever the corresponding linear system is solved exactly. However, when the correction is determined approximately, the situation changes, and we may use the (INM) setting.

Taking $y_{0}=-he_{N}$, for some arbitrarily small $h\neq 0$, we must solve

i.e.,

Applying $m\leq N-1$ steps of the Arnoldi process with $x_{0}=0$, we obtain $V_{m}=\left[e_{1},\ldots,e_{m}\right]\in\mathbb{R}^{N\times m}$ and $\bar{H}_{m}=\left[e_{2},\ldots,e_{m+1}\right]\in\mathbb{R}^{(m+1)\times m}$.

The Gmres solution is given by (see Refs. 36 and 39)

such that

and so

We also note that the restarting version of the Gmres yields the same result whenever $x_{0}=0$ and $\bar{m},m\leq N-1$.

This theoretical example shows that the dimension of the Krylov subspaces may sometimes be crucial for the efficiency of the Newton-Gmres method, and that the use of the restarted version of Gmres cannot overcome the difficulties. The stagnation of the Gmres algorithm was first reported in Ref. 36 (where $A$ was as above and $b$ stood for $e_{1}$ ), but we are not aware of any extension to a (non)linear mapping in order to show such stagnation of the Newton-Gmres method.
4.2. Newton-Gmback Method. The Gmback algorithm for solving the linear system (4) was introduced by Kasenally in Ref. 32. Given $x_{0}\in\mathbb{R}^{N}$, it computes a vector $x_{m}^{\mathrm{GB}}\in x_{0}+\mathscr{K}_{m}$ which minimizes the backward error in the matrix $A$, assuming $\Delta_{b}=0$,

The following steps are performed for determining $x_{m}^{\mathrm{GB}}$.
(i) Arnoldi Process. Compute the matrices $V_{m}$ and $\bar{H}_{m}$.
(ii) Gmback Solution. Execute Steps (a), (b), (c), (d) below.
(a) Let $\beta=\left\|r_{0}\right\|_{2}$,

(b) Determine an eigenvector $u_{m+1}$ corresponding to the smallest eigenvalue $\lambda_{m+1}^{\mathrm{GB}}$ of the generalized eigenproblem $\mathrm{Pu}=\lambda Qu$.
(c) If the first component $u_{m+1}^{(1)}$ is nonzero, compute the vector $y_{m}^{\mathrm{GB}}\in\mathbb{R}^{m}$ by scaling $u_{m+1}$ such that

(d) Set $x_{m}^{\mathrm{GB}}=x_{0}+V_{m}y_{m}^{\mathrm{GB}}$.

This algorithm may lead to two possible breakdowns, either in the Arnoldi method or in the scaling of $u_{m+1}$. As in the case of Gmres, the
first breakdown is a happy breakdown, because the solution may be determined exactly using $\bar{H}_{m}$ and $V_{m}$. The second breakdown appears when all the eigenvectors associated to $\lambda_{m+1}^{\mathrm{GB}}$ have the first component zero, the inevitable divisions by zero leading to uncircumventible breakdowns. In such case, either $m$ is increased or the algorithm is restarted with a different initial approximation $x_{0}$. We shall assume in the following analysis that $x_{m}^{\mathrm{GB}}$ exists.

Kasenally proved that, for any $x_{0}\in\mathbb{R}^{N}$ and $m\in\{1,\ldots,N\}$, the backward error $\Delta_{A,m}^{\mathrm{GB}}$ corresponding to the Gmback solution satisfies

The Newton-Gmback iterates may be written in two equivalent ways, taking into account the properties of the Krylov solutions,

$k=0,1,\ldots,y_{0}\in D$, where we considered

There are three results which may be applied to characterize the high convergence orders of these sequences (the corresponding statements are left to the reader): Theorem 2.1 of Dembo, Eisenstat, and Steihaug; the results of Dennis and Moré for the quasi-Newton methods (see Refs. 17-18); and Theorem 2.2 for the (IPNM) iterates, in which we must take $\delta_{k}=\hat{r}_{k}=0$, $k=0,1,\ldots$. Naturally, these results must be equivalent, but here we do not analyze this aspect.

Concerning the sufficient conditions, the convergence orders of the Newton-Gmback method may be controlled by the computed eigenvalues $\lambda_{k}^{\mathrm{GB}}$ from Gmback.

Theorem 4.2. Consider the sequence of Newton-Gmback iterates $y_{k+1}=y_{k}+s_{k}^{\mathrm{GB}}$, where $s_{k}^{\mathrm{GB}}$ satisfies

Assume the following:
(a) Conditions (C1)-(C4) hold.
(b) The derivative $F^{\prime}$ is Hölder continuous with exponent $p$ at $y^{*}$.
(c) The sequence $\left(y_{k}\right)_{k\geq 0}$ converges to $y^{*}$.

Moreover, if

then the Newton-Gmback iterates converge with $q$-order at least $1+p$.

Proof. The proof follows from Corollary 3.1, taking into account formula (6), the inequality $\|Z\|_{2}\leq\|Z\|_{F}$, true for all $Z\in\mathbb{R}^{N\times N}$, and the fact that all the norms are equivalent on a finite-dimensional normed space.

We are interested now if the curve of the Newton-Gmback errors is nonincreasing when starting with a sufficiently good approximation. In the following, we shall construct an example which shows that, unlike the Newton-Gmres case, this property is not generally shared by the NewtonGmback method when Gmback is used in the nonrestarted version.

Example 4.2. Consider the system $F(y)=0$, with

having the unique solution $y^{*}=0$. For all $y\in\mathbb{R}^{N}$, the derivative of $F$ is given by

Taking $y_{0}=-he_{N}$ with arbitrarily small $h\neq 0$, we must solve

or equivalently,

Applying $m\leq N-1$ steps of the Arnoldi process with $x_{0}=0$, we obtain successively