Local convergence of a two-step Gauss-Newton Werner-type method for solving least squares problems

Let $i,j$ be natural numbers with $j\ge i.$ Let also $\mathrm{\Omega }$ be an open and convex subset of ${ℝ}^j.$ We are concerned with the solution $p$ of the least squares problem [4, 5, 6, 7, 8, 9]:

where $F:\mathrm{\Omega }⟶{ℝ}^j$ is a Fréchet-differentiable mapping. Numerous problems can be brought in the form (1.1) using Mathematical Modeling [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]. The closed form solutions can only be found in special cases. That explains why most solution methods for problem (1.1) are iterative. Let $x_0,y_0\in \mathrm{\Omega }$ and set $z=\frac{x_0+y_0}{2}.$ In the present study, we provide the local convergence analysis of GNWTM defined for each $n=0,1,2,\mathrm{\dots }$ by

where $A_n={[F^{\prime }{(z_n)}^T{F}^{\prime }(z_n)]}^{-1}{F}^{\prime }{(z_n)}^T.$ If $i=j,$ TGNWTM reduces to a Gauss-Newton-Werner type method [3, 8, 9]. Notice that in each iteration the inversion of ${[F^{\prime }{(z_n)}^T{F}^{\prime }(z_n)]}^{-1}$ is required only once. Therefore, the computational cost is essentially the same as in the Gauss- Newton method. The $L{L}^T$ decomposition of ${[F^{\prime }{(z_n)}^T{F}^{\prime }(z_n)]}^{-1}$ costs $O(n^3)$ floating-point operations (Flops) leading to the computation of $x_{n+1}.$ It then follows from the second substep of method (1) that $O(n^2)$ Flops are needed for the computation of $y_{n+1}.$

The local convergence analysis of method (1) was given in the elegant paper by Shakhno et.al. in [9] (see also related work in [3, 8]). Their convergence analysis uses average Lipschitz continuity condition as well as Lipschitz conditions.

Using the concept of the average Lipschitz continuity [12] and our new idea of restricted convergence domains, we present a local convergence analysis with the following advantages (A) over works using the similar information [3, 4, 8, 9, 11, 12, 13]:

1. (a)

   Larger radius of convergence;

2. (b)

   Tighter error bounds on the distances $\Vert x_n-p\Vert ;$

3. (c)

   An at least as precise information on the location of the solution $p.$

Achieving (a)-(c) is very important in computational sciences, since: (a)^′ We obtain a wider choice of initial guesses; (b)^′ Fewer iterates are required to obtain a desired error tolerance; (c)^′ Better information about the ball of convergence is obtained.

The rest of the paper is structured as follows: Section 2 contains the local convergence analysis of method (1) whereas special cases and the applications are presented in the concluding Section 3.

Set to be the open ball in ${ℝ}^j$ and by $\overline{U}(w,\rho )$ to denote its closure. Let $R>0.$ Define parameter $R_1$ by $R_1:=sup\{t\in [0,R]:\overline{U}(p,t)\subset \mathrm{\Omega }\}.$ The convergence analysis of numerous iterative methods has been given using the following concept due to Wang [12]:

It turns out that the convergence analysis of iterative methods based on the preceding notion can be improved as follows:

Clearly, we have that

and $\frac{L_0}{L_1}$ can be arbitrary small [2, 3, 4]. Let $\beta >0$ be a parameter. Suppose that equation

has positive solutions. Denote by $R_0$ the smallest such solution. Notice for example that $R_0$ exists, if

Indeed, function $g(t):=\beta {\int }_0^{t}L(u)𝑑u-1$ is such that and $g(R_1)=\beta L(R_1)R_1-1>0.$ The existence of $R_0$ follows from the intermediate value theorem.

We have that

since $R_0\le R_1.$ Throughout this paper, we suppose that

unless, otherwise stated. Otherwise, i.e., if

then the results that follow hold with $L_0$ replacing $L.$ Moreover, we need the definitions:

We have that

It is worth noticing that the definition of functions $L$ and $M$ (based on $L_0$ and $R_0$) was not possible in earlier studies using $L_1$ and $M_1.$ That is, $L=L(L_0,R_0,R_1),M=M(L_0,R_0,R_1),$ whereas $L_1=L_1(R_1)$ and $M_1=M_1(R_1).$ It turns out that $L_0$ can replace the less precise $L$ in the computation of the upper bounds on the inverses of the operators involved and $\overline{U}(p,R_0),L,M$ can replace $\overline{U}(p,R_1),L_1,M_1,$ respectively in the proofs of such results. Moreover, notice that the iterates $x_n$ lie in $\overline{U}(p,R_0)$ which is a more precise location than $\overline{U}(p,R_1)$ used in earlier studies [2, 3, 4, 8, 11, 12, 13]. We shall make the paper as self contained as possible by stating some standard auxiliary concepts and results.

Denote by ${ℝ}^{i\times j}$ the set of all $i\times j$ matrices. The Moore-Penrose pseudo-inverse is defined by $A^{†}={(A^{T}A)}^{-1}{A}^T$ for each full rank $A\in {ℝ}^{i\times j}$ [6].

As in [9], it is convenient for the local convergence analysis that follows to introduce some functions and parameters:

and

Notice that if $L_0=L=L_1$ and $M=M_1,$ then the preceding definitions reduce to the corresponding ones in [9].

The local convergence analysis is based on the conditions ($𝒞$):

1. (${𝒞}_1$)

   Mapping $F:\overline{U}(p,R_1)⟶{ℝ}^i$ is twice Fréchet-differentiable, $F^{\prime }(p)$ has full rank and $p$ solves problem (1.1).

2. (${𝒞}_2$)

   $F^{\prime }(x)$ satisfies: the center-Lipschitz condition with $L_0$ average on $\overline{U}(p,R_1)$ and the restricted Lipschitz condition with $L$ average on $\overline{U}(p,R_0);$ $F^{\prime \prime }(x)$ satisfies the restricted Lipschitz condition with $M$ average on $\overline{U}(p,R_0),$ where $L_0,L$ and $M$ are positive non-decreasing functions on $[0,\frac{3R_0}{2}].$

3. (${𝒞}_3$)

   Function $\mu$ has a minimal zero $R^{\ast }$ in $[0,R_0],$ which also satisfies

Then, we can show the following local convergence result for TGNWTM under the conditions ($𝒞$) and the preceding notation.

Proof. The proof follows the corresponding one in [9] but there are differences where we use ($L_0,L$), $M$ instead of $L_1,M_1,$ respectively used in [9]. We shall use mathematical induction to show that iterates $\{x_k\},$ $\{y_k\},\{z_k\}$ are well defined converge to $p$ and the error estimates (2.8)–(2.10) are satisfied. Using TGNWTM for $n=0,$ we can write

and

where

In view of the estimate

for $x=p$ and $y=x_0,$ we obtain in turn

and

By the central Lipschitz condition, we have that

Moreover, by 2.1 and 2.2 and (${𝒞}_1$), for all $x\in U(p,R^{\ast }),$ we get

and

By the monotonicity of $L(u)$ and $M(u)$ with 2.3 and 2.4, functions $\frac{1}{t}{\int }_0^{t}L(u)𝑑u$ and $\frac{1}{t^3}{\int }_0^{t}M(u){(t-u)}^2𝑑u$ are non-decreasing in $t.$ That is, by (${𝒞}_3$)

Thus, by 2.1–2.9 and condition (${𝒞}_2$), we have in turn

In an analogous way, we get in turn