# An Analysis on Local Convergence of Inexact Newton-Gauss Method for Solving Singular Systems of Equations

Authors: Fangqin Zhou
Journal: The Scientific World Journal
 (2014)

---

## Abstract

We study the local convergence properties of inexact Newton-Gauss method for singular systems of equations. Unified estimates of radius of convergence balls for one kind of singular systems of equations with constant rank derivatives are obtained. Application to the Smale point estimate theory is provided and some important known results are extended and/or improved.


---

## Body

## 1. Introduction

Consider the following system of nonlinear equations:(1)f(x)=0,
where f:D⊂ℝn→ℝm is a nonlinear operator with its Fréchet derivative denoted by f′ and D is open and convex. In the case when m=n and f′(x) is invertible for each x∈D, Newton’s method is a classical numerical method to find an approximation solution for such system. There are a lot of results that improve, generalize, or extend the convergence of Newton’s method for solving (1). We refer the reader to the works of Deuflhard and Heindl [1], Smale [2], Wang [3], Ferreira [4], Argyros et al. [5], and the references therein. If x0∈D is an approximation of a zero of this system, then Newton's method can be defined by the form as follows:
(2)xk+1=xk-f′(xk)-1f(xk),k=0,1,2,….
When f′(x) is not invertible, we choose its Moore-Penrose inverse f′(x)† instead of its classical inverse and call it Gauss-Newton's method given as follows:
(3)xk+1=xk-f′(xk)†f(xk),k=0,1,2,….LetA:ℝn→ℝm be a linear operator (or an m×n matrix). Recall that an operator (or n×m matrix) A†:ℝm→ℝn is the Moore-Penrose inverse of A, if it satisfies the following four equations:
(4)A†AA†=A†,AA†A=A;(AA†)*=AA†,(A†A)*=A†A,
where A* denotes the adjoint of A. Let ker⁡A and imA denote the kernel and image of A, respectively. For a subspace E of ℝn, we use ΠE to denote the projection onto E. Then, it is clear that
(5)A†A=Πker⁡A⊥,AA†=ΠimA.
In particular, in the case when A is full row rank (or, equivalently, when A is surjective), AA†=Iℝm; when A is full column rank (or equivalently, when A is injective), A†A=Iℝn.One of the disadvantages for Newton's method (2) is that it requires solving exactly the following linear equation at each step:
(6)f′(xk)(xk+1-xk)=-f(xk).
To overcome this disadvantage, Dembo et al. presented in [6] the following iterative processes called inexact Newton method (x0 is an initial guess):
(7)xk+1=xk+sk,f′(xk)sk=-f(xk)+rk,k=0,1,2,…,
where the residual control rk satisfies
(8)∥rk∥≤λk∥f(xk)∥,k=0,1,2,…,
and {λk} is a sequence of forcing terms such that 0≤λk<1. In [6], it was shown that if λk≤λ<1, then there exists r>0 such that, for any initial guess x0∈B(ζ,r), the sequence {xk} is well defined and converges to a solution ζ. Moreover, the rate of convergence of {xk} to ζ is characterized by the rate of convergence of {λk} to 0.Note that it is clear that the residual control (8) is not affine invariant (see [1] for more details about the affine invariant). To this end, Ypma used in [7] the affine invariant condition of residual control in the form
(9)∥f′(xk)-1rk∥≤λk∥f′(xk)-1f(xk)∥,k=0,1,2,…,
to study the local convergence of inexact Newton method (7). And the radius of convergent result is also obtained.To study the local convergence of inexact Newton method and inexact Newton-like method (called inexact methods for short below), Morini presented in [8] the following variation for the residual controls:
(10)∥Pkrk∥≤λk∥Pkf(xk)∥,k=0,1,2,…,
where {Pk} is a sequence of invertible operator from ℝn to ℝn and {λk} is the forcing term. If Pk=I and Pk=f′(xk) for each k, (10) reduces to (8) and (9), respectively. Both proposed inexact methods are linearly convergent under Lipschitz condition. It is worth noting that the residual controls (10) are used in iterative methods if preconditioning is applied and lead to a relaxation on the forcing terms. But we also note that the results obtained in [8] cannot make us clearly see how big the radius of the convergence ball is. To this end, Chen and Li [9] obtained the local convergence properties of inexact methods for (1) under weak Lipschitz condition, which was first introduced by Wang in [10] to study the local convergence behavior of Newton’s method (2). The results in [9] easily provide an estimate of convergence ball for the inexact methods. Furthermore, Ferreira and Gonçalves presented in [11] a new local convergence analysis for inexact Newton-like under so-called majorant condition, which is equivalent to the preceding weak Lipschitz condition.Under the assumption that the derivative of the operator satisfies the Hölder condition, the radius of convergence ball of the inexact Newton-like methods with a new type of residual control is estimated by Li and Shen [12]. And a superlinear convergence property is proved, which extends the corresponding result in [8]. In addition, as an application of the local convergence result, they presented a slight modification of the inexact Newton-like method of [13] for solving inverse eigenvalue problems and showed that it can be regarded equivalently as one of the inexact methods considered in [12].Recent attentions are focused on the study of finding zeros of singular nonlinear systems by Gauss-Newton’s method (3). For example, Shub and Smale extended in [14] the Smale point estimate theory (including α-theory and γ-theory) to Gauss-Newton's methods for underdetermined analytic systems with surjective derivatives. For overdetermined systems, Dedieu and Shub studied in [15] the local linear convergence properties of Gauss-Newton’s for analytic systems with injective derivatives and provided estimates of the radius of convergence balls for Gauss-Newton's method. Dedieu and Kim in [16] generalized both the results of the underdetermined case and the overdetermined case to such case where f′(x) is of constant rank (not necessarily full rank), which has been improved by Xu and Li in [17, 18], Ferreira et al. in [19], Argyros and Hilout in [20], and Gonçalves and Oliveira in [21].In the last years, some authors have studied the convergence behaviour of inexact versions of Gauss-Newton’s method for singular nonlinear systems. For example, Chen [22] employed the ideas of [9] to study the local convergence properties of several inexact Gauss-Newton type methods where a scaled relative residual control is performed at each iteration under weak Lipschitz conditions. Ferreira et al. presented in their recent paper [23] a local convergence analysis of an inexact version of Gauss-Newton's method for solving nonlinear least squares problems. Moreover, the radii of the convergence balls under the corresponding conditions were estimated in these two papers.In the present paper, we study the local convergence of inexact Newton-Gauss method for the singular systems with constant rank derivatives under the hypotheses that the derivatives satisfy Lipschitz conditions withL average and the residual satisfies several control conditions. Unified estimates for the radius of convergence balls of inexact Newton-Gauss method are obtained. As an application to Smale approximate zeros, we obtain a gamma-type theorem which gives an estimate of the size of convergence ball of inexact Newton-Gauss method about a zero.The rest of this paper is organized as follows. In Section2, we introduce some preliminary notions and properties of the majorizing function. The main results about the local convergence are stated in Section 3. And finally, in Section 4, we prove the local convergence results given in Section 3.


## 2. Preliminaries

Forx∈ℝn and a positive number r, throughout the whole paper, we use B(x,r) to stand for the open ball with radius r and center x and let B(x,r)¯ denote its closure.Throughout this paper, we assume thatL is a positive nondecreasing function on [0,R), where R∈ℝ+. Let 0≤λ,θ<1 with 0≤λ+θ<1. The majorizing function hλ,θ:[0,R]→ℝ corresponding to (λ,θ,L) is defined by
(11)hλ,θ(t)=-(1+λ+θ)t+∫0t‍L(u)(t-u)du,t∈[0,R].
Note that, in the case when λ=θ=0, (11) reduces to
(12)h0,0(t)=-t+∫0t‍L(u)(t-u)du,t∈[0,R).
Obviously,
(13)hλ,θ′(t)=-(1+λ+θ)+∫0t‍L(u)du,t∈[0,R),hλ,θ′′(t)=L(t)fora.e.0≤t<R.
Moreover, we have hλ,θ(0)=0,hλ,θ′(0)=-(1+λ+θ) and hλ,θ′ is convex and strictly increasing. Set
(14)ξ≔sup⁡⁡{t∈[0,R):h0,0′(t)<0},(15)ρ≔sup⁡⁡{t∈[0,ξ):hλ,θ(t)h0,0′(t)-t<t},(16)σ≔sup⁡⁡{t∈[0,R):B(ζ,t)⊂D}.For the convergence analysis, we need the following useful lemma about elementary convex analysis.Lemma 1 (see [4]).
LetR>0. If g:[0,R]→ℝ is continuously differentiable and convex, then (i)
(g(t)-g(τt))/t≤(1-τ)g′(t), for all t∈(0,R) and τ∈[0,1],(ii)
(g(u)-g(τu))/u≤(g(v)-g(τv))/v, for all u,v∈[0,R),u<v, and 0≤τ≤1.The next two lemmas show that the constantsξ and ρ defined in (14) and (15), respectively, are positive.Lemma 2.
The constantξ defined in (14) is positive and t-(hλ,θ(t)/h0,0′(t))<0, for all t∈(0,ξ).Proof.
Sinceh0,0′(0)=-1, there exists δ>0 such that h0,0′(t)<0 for all t∈(0,δ). Then, we get ξ≥δ(>0). Because hλ,θ′ is strictly increasing, hλ,θ is strictly convex. It follows from Lemma 1(i) that
(17)hλ,θ(t)-hλ,θ(0)t≤hλ,θ′(t)≤h0,0′(t),t∈(0,R).
Note that hλ,θ(0)=0 and h0,0′(t)<0, for all t∈(0,ξ). Thus, the inequality t-(hλ,θ(t)/h0,0′(t))<0 follows.Lemma 3.
The constantρ defined in (15) is positive. As a consequence, |t-(hλ,θ(t)/h0,0′(t))|<t, for all t∈(0,ρ).Proof.
On one hand, by Lemma2, it is clear that (hλ,θ(t)/th0,0′(t))-1>0, for t∈(0,ξ). On the other hand, we can obtain from Lemma 1(i) that
(18)lim⁡t→0(hλ,θ(t)th0,0′(t)-1)=0.
Then, we conclude that there exists δ>0 such that
(19)0<hλ,θ(t)th0,0′(t)-1<1,t∈(0,ξ).
Therefore, ρ is positive.Let(20)r:=min⁡{ρ,σ},
where ρ and σ are given in (15) and (16), respectively. For any starting point x0∈B(ζ,r)∖{ζ}, let {tk} denote the sequence generated by
(21)t0=∥x0-ζ∥,tk+1=|tk-hλ,θ(tk)h0,0′(tk)|,k=0,1,2,….Lemma 4.
The sequence{tk} given by (21) is well defined, is strictly decreasing, is contained in (0,ρ), and converges to 0.Proof.
Since0<t0=∥x0-ζ∥<r≤ρ, using Lemma 3, one has that {tk} is well defined, strictly decreasing, and contained in [0,ρ). Thus, there exists t*∈[0,ρ) such that lim⁡k→∞⁡tk=t*; that is, we have
(22)0≤t*=hλ,θ(t*)h0,0′(t*)-t*<ρ.
If t*≠0, it follows from Lemma 3 that
(23)hλ,θ(t*)h0,0′(t*)-t*<t*.
This is a contradiction. So tk→0 as k→∞. This completes the proof.The notion of theL-average Lipschitz condition for semilocal convergence analysis was introduced by Li and Ng in [24], which is a modification of the one that was first introduced by Wang in [3], where the terminology of “the center Lipschitz condition in the inscribed sphere with L average” was used. This notion was used to study the semilocal convergence of Newton’s method (2) to solve singular systems of equation with constant rank derivatives by Xu and Li in [18] and Li et al. in [25]. As for the local convergence analysis, we can also introduce the similar definition.Definition 5.
Letr>0 be such that B(ζ,r)⊂D. Then, f′ is said to satisfy the L-average Lipschitz condition on B(ζ,r) if
(24)∥f′(ζ)†[f′(x)-f′(ζ+τ(x-ζ))]∥≤∫τ∥x-ζ∥∥x-ζ∥‍L(u)du,
for any x∈B(ζ,r) and τ∈[0,1].This definition is a modification of the one in [10], where the terminology of “the radius Lipschitz condition with the L average” was used. In the case when f′(ζ) is not surjective (see [15, 16]), the information on imf′(ζ)⊥ may be lost. To this end, we need to modify the above notion to suit the case when f′(ζ) is not surjective.Definition 6.
Letr>0 be such that B(ζ,r)⊂D. Then, f′ is said to satisfy the modified L-average Lipschitz condition on B(ζ,r) if
(25)∥f′(ζ)†∥∥f′(x)-f′(ζ+τ(x-ζ))∥≤∫τ∥x-ζ∥∥x-ζ∥‍L(u)du,
for any x∈B(ζ,r) and τ∈[0,1].The notion of theγ-condition for operators in Banach spaces was introduced in [26] by Wang and Han to study the Smale point estimate theory. Definition 7 about γ-condition and the related Lemma 8 are taken from [25].Definition 7 (see [25]).
Suppose thatγ>0 and f has continuous second derivative. Let 0<r≤1/γ be such that B(ζ,r)⊂D. f is said to satisfy the γ-condition (resp., the modified γ-condition) on B(ζ,r) if (26) (resp., (27)) holds as follows:
(26)∥f′(ζ)†f′′(x)∥≤2γ(1-γ∥x-ζ∥)3foreachx∈B(ζ,r),(27)∥f′(ζ)†∥∥f′′(x)∥≤2γ(1-γ∥x-ζ∥)3foreachx∈B(ζ,r).Lemma 8 (see [25]).
Suppose thatγ>0 and f has continuous second derivative. Let 0<r≤1/γ be such that B(ζ,r)⊂D. Then, f satisfies the γ-condition (resp., the modified γ-condition) on B(ζ,r) if and only if f′ satisfies the L-average Lipschitz condition (resp., the modified L-average Lipschitz condition) on B(ζ,r) with L(u)=2γ/(1-γu)3,u∈[0,1/γ).


## 3. Local Convergence for Inexact Newton-Gauss Method

In this section, we state our main results of local convergence for inexact Newton-Gauss method (7). Recall that the system (1) is a surjective-underdetermined (resp., injective-overdetermined) system if the number of equations is less (resp., greater) than the number of unknowns and f′(x) is of full rank for each x∈D. Note that, for surjective-underdetermined systems, the fixed points of the Newton operator Nf(x):=x-f′(x)†f(x) are the zeros of f, while, for injective-overdetermined systems, the fixed points of Nf are the least square solutions of f(x)=0, which, in general, are not necessarily the zeros of f.Our first result concerned the local convergence properties of inexact Newton-Gauss method for general singular systems with constant rank derivatives.Theorem 9.
Letf:D⊂ℝn→ℝm be continuously Fréchet differentiable nonlinear operator, and D is open and convex. Suppose that f(ζ)=0, f′(ζ)≠0 and that f′ satisfies the modified L-average Lipschitz condition (25) on B(ζ,r), where r is given in (20). In addition, one assumes that rank⁡f′(x)≤rank⁡f′(ζ), for any x∈B(ζ,r), and that
(28)∥[Iℝn-f′(x)†f′(x)](x-ζ)∥≤θ∥x-ζ∥,x∈B(ζ,r),
where the constant θ satisfies 0≤θ<1. Let {xk} be sequence generated by inexact Newton-Gauss method with any initial point x0∈B(ζ,r)∖{ζ} and the conditions for the residual rk and the forcing term λk:
(29)∥rk∥≤λk∥f(xk)∥,0≤λkκ(f′(xk))≤λ,k=0,1,2,…,
where κ(A):=∥A†∥∥A∥ denotes the condition number of A∈ℝm×n. Then, {xk} converges to a zero ζ of f′(·)†f(·) in B(ζ,r)¯. Moreover, one has the following estimate:
(30)∥xk+1-ζ∥≤tk+1tk∥xk-ζ∥,k=0,1,2,…,
where the sequence {tk} is defined by (21).Remark 10.
If takingλ=0 (in this case, λk=0 and rk=0) in Theorem 9, we obtain the local convergence of Newton’s method for solving the singular systems, which has been studied by Dedieu and Kim in [16] for analytic singular systems with constant rank derivatives and Li et al. in [25] for some special singular systems with constant rank derivatives. Now, we obtain that the convergence ball r satisfies
(31)∫0r‍L(u)udur((1-θ)-∫0r‍L(u)du)≤1,θ∈[0,1).Iff′(x) is full column rank for every x∈B(ζ,r), then we have f′(x)†f′(x)=Iℝn. Thus,
(32)∥[Iℝn-f′(x)†f′(x)](x-ζ)∥=0;
that is, θ=0. We immediately have the following corollary.Corollary 11.
Suppose thatrank⁡f′(x)≤rank⁡f′(ζ) and that
(33)∥[Iℝn-f′(x)†f′(x)](x-ζ)∥=0,
for any x∈B(ζ,r). Suppose that f(ζ)=0,f′(ζ)≠0 and that f′ satisfies the modified L-average Lipschitz condition (25). Let {xk} be sequence generated by inexact Newton-Gauss method with any initial point x0∈B(ζ,r)∖{ζ} and the condition (29) for the residual rk and the forcing term λk. Then, {xk} converges to a zero ζ of f′(·)†f(·) in B(ζ,r)¯. Moreover, one has the following estimate:
(34)∥xk+1-ζ∥≤tk+1tk∥xk-ζ∥,k=0,1,2,…,
where the sequence {tk} is defined by (21) for θ=0.In the case whenf′(ζ) is full row rank, the modified L-average Lipschitz condition (25) can be replaced by the L-average Lipschitz condition (24).Theorem 12.
Suppose thatf(ζ)=0,f′(ζ) is full row rank, and f′ satisfies the L-average Lipschitz condition (24) on B(ζ,r), where r is given in (20). In addition, one assumes that rank⁡f′(x)≤rank⁡f′(ζ) for any x∈B(ζ,r) and that condition (28) holds. Let {xk} be sequence generated by inexact Newton-Gauss method with any initial point x0∈B(ζ,r)∖{ζ} and the conditions for the residual rk and the forcing term λk:
(35)∥f′(ζ)†rk∥≤λk∥f′(ζ)†f(xk)∥,0≤λkκ(f′(ζ)†f′(xk))≤λ,k=0,1,2,….
Then, {xk} converges to a zero ζ of f(·) in B(ζ,r)¯. Moreover, one has the following estimate:
(36)∥xk+1-ζ∥≤tk+1tk∥xk-ζ∥,k=0,1,2,…,
where the sequence {tk} is defined by (21).Theorem 13.
Suppose thatf(ζ)=0,f′(ζ) is full row rank, and f′ satisfies theL-average Lipschitz condition (24) on B(ζ,r), where r is given in (20). In addition, one assumes that rank⁡f′(x)≤rank⁡f′(ζ) for any x∈B(ζ,r) and that condition (28) holds. Let {xk} be sequence generated by inexact Newton-Gauss method with any initial point x0∈B(ζ,r)∖{ζ} and the conditions for the control residual rk and the forcing term λk:
(37)∥f′(xk)†rk∥≤λk∥f′(xk)†f(xk)∥,0≤λkκ(f′(xk))≤λ,222222222222222222222222222222222222k=0,1,2,….
Then, {xk} converges to a zero ζ of f(·) in B(ζ,r)¯. Moreover, one has the following estimate:
(38)∥xk+1-ζ∥≤tk+1tk∥xk-ζ∥,k=0,1,2,…,
where the sequence {tk} is defined by (21).Remark 14.
In the case whenf′(ζ) is invertible in Theorem 13, we obtain the local convergence results of inexact Newton-Gauss method for nonsingular systems, and the convergence ball r in this case satisfies
(39)∫0r‍L(u)udur((1-λ)-∫0r‍L(u)du)≤1,λ∈[0,1).
In particular, if takingλ=0, the convergence ball r determined in (39) reduces to the one given in [10] by Wang and the value r is the optimal radius of the convergence ball when the equality holds. Then, we can conclude that vanishing residuals, Theorem 13 merges into the theory of Newton’s method.The result below is an extension of the Smale approximate zeros. We first recall the notion of the approximate zero of an analytic operatorf from the domain D in a Banach space to another. In [2], Smale proposed two kinds of the notion: the first kind (in sense of ∥xk-xk-1∥) and the second kind (in sense of ∥xk-ζ∥) of an approximate zero. A more reasonable definition for the second kind was presented in [27]; see also [28]. The notion of the approximate zero in the sense of ∥f′(x0)-1f(xk)∥ was defined in [29], which is equivalent to the first kind (see [3]). The following unified definition is taken from [3].Definition 15 (see [3]).
Letx0∈D be such that the sequence {xk} generated by Newton's method (2) is well defined and satisfies
(40)e(xk)≤(12)2k-1e(xk-1),k=1,2,…,
where e(xk) denotes some measurement of the approximation degree between xk and the zero point ζ. Then, x0 is called an approximate zero of f in sense of e(xk).The concepts of an approximate zero for Gauss-Newton method (3) for solving singular systems of equations and inexact Newton method (7) for solving nonsingular systems of equations are proposed in [25, 30], respectively. We now extend the notion of approximate zeros to inexact Newton-Gauss method for solving singular systems of equations.Definition 16.
Letx0∈D be such that the sequence {xk} generated by inexact Newton-Gauss method (7) converges to a zero ζ of f′(·)†f(·) (resp., f) and satisfies (40). Then, x0 is called an INM-approximate solution (resp., approximate zero) of f in sense of e(xk).For the remainder of this subsection, letL be the function defined by
(41)L(u)=2γ(1-γu)3foreachuwith0≤u<1γ.
Then,
(42)hλ,θ(t)=-(1+λ+θ)t+γt21-γt,t∈[0,1γ),λ,θ∈[0,1)with0≤λ+θ<1,
and the constants ξ and ρ defined in (14) and (15), respectively, have the following concrete forms:
(43)ξ=2-22γ,(44)ρ=((5+2(λ+θ))2-4(1+λ+θ)(2+λ+θ)(5+2(λ+θ))-(5+2(λ+θ))2-4(1+λ+θ)(2+λ+θ))×(2(2+λ+θ)γ)-1.To state our gamma-type theorem for inexact Newton-Gauss method (7), we introduce some more notations. Let
(45)ϕ(t)=4γ2(λ+θ)t3-2γ(3λ+4θ+γ)t2+2(λ+θ+3γ)t-1,λ,θ∈[0,1),γ>0.
Since ϕ(0)=-1 and ϕ(ξ)=((3-22)λ+(2-2)γ)/γ>0, there exists one zero at least in (0,(2-2)/2γ). The smallest positive zero of ϕ in (0,(2-2)/2γ) is denoted by r^. Recall that r=min⁡{ρ,σ}; here ρ and σ are given in (44) and (16), respectively. Let
(46)r*=min⁡{r,r^,r~},
where r~ is given by
(47)r~=(4-3λ)-(4-3λ)2-8(1-λ)24γ(1-λ).Theorem 17.
Suppose thatf(ζ)=0,f′(ζ) is full row rank, and f satisfies the γ-condition (26) on B(ζ,r). Assume that rank⁡f′(x)≤rank⁡f′(ζ) and that
(48)∥[Iℝn-f′(x)†f′(x)](x-ζ)∥≤θ∥x-ζ∥2,
for any x∈B(ζ,r). Let {xk} be sequence generated by inexact Newton-Gauss method with any initial point x0∈B(ζ,r*)∖{ζ} and the conditions for the control residual rk and the forcing term λk:
(49)∥f′(xk)†rk∥≤(λk∥f′(xk)†f(xk)∥)2,0≤λkκ(f′(xk))≤λ,k=0,1,2,….
Then, {xk} converges to a zero ζ of f(·) in B(ζ,r)¯ and x0 is an approximate zero of f in sense of ∥xk-ζ∥.One typical and important class of examples satisfying theγ-conditions is the one of analytic functions. Following Smale’s idea in [2], Shub and Smale introduced in [14] the following invariant for analytic underdetermined systems with surjective f′(ζ):
(50)γ(f,ζ):=sup⁡k>1∥f′(ζ)†f(k)(ζ)k!∥1/(k-1).
For the case when f′(x) is not surjective, due to loss of the information on imf′(ζ)⊥, Dedieu and Shub introduce in [15] the following invariant for analytic overdetermined systems:
(51)γ1(f,ζ):=sup⁡k>1(∥f′(ζ)†∥∥f(k)(ζ)∥k!)1/(k-1).
By [25, Proposition 5.2], one has that an analytic operator satisfies the γ-condition and the modified γ-condition. So, the conclusions of Theorem 17 still hold when f is analytic.


## 4. Proofs

In this section, we prove our main results of local convergence for inexact Newton-Gauss method (7) given in Section 3.


### 4.1. Proof of Theorem9

The following lemma gives a perturbation bound for Moore-Penrose inverse, which is stated in [31, Corollary 7.1.1 and Corollary 7.1.2].Lemma 18 (see [31]).
LetA and B be m×n matrices and let r≤min⁡{m,n}. Suppose that rank⁡A=r,1≤rank⁡B≤rank⁡A, and ∥A†∥∥B-A∥<1. Then, rank⁡B=r and
(52)∥B†∥≤∥A†∥1-∥A†∥∥B-A∥.Lemma 19.
Suppose thatf′ satisfies the modifiedL-average Lipschitz condition on B(ζ,r) and that ∥ζ-x∥<min⁡{ρ,ξ}, where r, ρ, and ξ are defined in (20), (15), and (14), respectively. Then, rank⁡f′(x)=rank⁡f′(ζ) and
(53)∥f′(x)†∥≤-∥f′(ζ)†∥h0,0′(∥x-ζ∥).Proof.
Sinceh0,0′(0)=-1, we have
(54)∥f′(ζ)†∥∥f′(x)-f′(ζ)∥≤∫0∥x-ζ∥‍L(u)du=h0,0′(∥x-ζ∥)-h0,0′(0)<-h0,0′(0)=1.
It follows from Lemma 18 that rank⁡f′(x)=rank⁡f′(ζ) and
(55)∥f′(x)†∥≤∥f′(ζ)†∥1-(h0,0′(∥x-ζ∥)-h0,0′(0))=-∥f′(ζ)†∥h0,0′(∥x-ζ∥).Proof of Theorem9.
We will prove by induction that{tk} is the majorizing sequence for {xk}; that is,
(56)∥ζ-xj∥≤tj∀j=0,1,2,….
Because t0=∥x0-ζ∥, thus (56) holds, for j=0. Now, we assume that ∥ζ-xj∥≤tj, for some j=k∈ℕ. For the case j=k+1, we first notice that
(57)xk+1-ζ=xk-ζ-f′(xk)†[f(xk)-f(ζ)]+f′(xk)†rk=f′(xk)†[f(ζ)-f(xk)-f′(xk)(ζ-xk)]+f′(xk)†rk+[Iℝn-f′(xk)†f′(xk)](xk-ζ)=f′(xk)†∫01[f′(xk)-f′(ζ+τ(xk-ζ))]‍(xk-ζ)dτ+f′(xk)†rk+[Iℝn-f′(xk)†f′(xk)](xk-ζ).
By using the modified L-average Lipschitz condition (25), Lemma 19, the inductive hypothesis (56), and Lemma 1, one has that
(58)∥f′(xk)†∫01‍[f′(xk)-f′(ζ+τ(xk-ζ))](xk-ζ)dτ∥≤-1h0,0′(∥xk-ζ∥)×∫01∥f′(ζ)†∥∥f′(xk)-f′(ζ+τ(xk-ζ))∥×∥xk-ζ∥dτ‍≤-1h0,0′(∥xk-ζ∥)∫01∫τ∥xk-ζ∥∥xk-ζ∥L(u)∥xk-ζ∥dudτ‍‍=-1h0,0′(∥xk-ζ∥)×∫01hλ,0′(∥xk-ζ∥)-hλ,0′(τ∥xk-ζ∥)∥xk-ζ∥dτ·∥xk-ζ∥2≤-1h0,0′(tk)∫01hλ,0′(tk)-hλ,0′(τtk)tkdτ·∥xk-ζ∥2‍=-1h0,0′(tk)(tkh′λ,0(tk)-hλ,0(tk))∥xk-ζ∥2tk2.
Thanks to (29),
(59)∥f′(xk)†rk∥≤∥f′(xk)†∥∥rk∥≤λk∥f′(xk)†∥∥f(xk)∥.
Since
(60)-f(xk)=f(ζ)-f(xk)-f′(xk)(ζ-xk)+f′(xk)(ζ-xk)=∫01‍[f′(xk)-f′(ζ+τ(xk-ζ))](xk-ζ)dτ+f′(xk)(ζ-xk),
combining Lemmas 1 and 19, the modified L-average Lipschitz condition (25), the inductive hypothesis (56), and the condition (29), we have
(61)λk∥f′(xk)†∥∥f(xk)∥≤λk∥f′(xk)†∥∫01∥f′(xk)-f′(ζ+τ(xk-ζ))∥‍×∥xk-ζ∥dτ+λk∥f′(xk)†∥∥f′(xk)∥∥xk-ζ∥≤-λ(h0,0′(tk))(tkhλ,0′(tk)-hλ,0(tk))∥xk-ζ∥2tk2+λtk·∥xk-ζ∥tk(62)≤λλtk+hλ,0(tk)h0,0′(tk)·∥xk-ζ∥tk.
Combining (28), (58), (59), and (62), we can obtain that
(63)∥xk+1-ζ∥≤[-tkhλ,0′(tk)-hλ,0(tk)h0,0′(tk)+λ·λtk+hλ,0(tk)h0,0′(tk)+θtk]×∥xk-ζ∥tk=[-tk+(1+λ)(λtkh0,0′(tk)+hλ,0(tk)h0,0′(tk))+θtk]×∥xk-ζ∥tk.
By the definition of hλ,0(t), we have hλ,0(t)≥-(1+λ)t. Then, we can obtain that
(64)(1+λ)(λtkh0,0′(tk)+hλ,0(tk)h0,0′(tk))≤hλ,0(tk)h0,0′(tk).
Note that -1<h0,0′(t)<0, for any t∈(0,ρ), and
(65)(1+λ)(λtkh0,0′(tk)+hλ,0(tk)h0,0′(tk))+θtk≤hλ,0(tk)h0,0′(tk)+θtk≤hλ,0(tk)-θtkh0,0′(tk)=hλ,θ(tk)h0,0′(tk).
Thus, in view of the definition of {tk} given in (21), one has that
(66)∥xk+1-ζ∥≤tk+1tk∥xk-ζ∥,
which implies ∥xk+1-ζ∥≤tk+1. Therefore, the proof by induction is complete. Since {tk} converges to 0 (by Lemma 4), it follows from (56) that {xk} converges to ζ and the estimate (30) holds for all k≥0. This completes the proof.


### 4.2. Proof of Theorem12

Lemma 20.
Suppose thatf(ζ)=0,f′(ζ) is full row rank, and f′ satisfies the L-average Lipschitz condition (24) on B(ζ,r). Then, for any x∈B(ζ,r), one has rank⁡f′(x)=rank⁡f′(ζ) and
(67)∥[Iℝn-f′(ζ)†(f′(ζ)-f′(x))]-1∥≤-1h0,0′(∥x-ζ∥).Proof.
Sinceh0,0′(0)=-1, we have
(68)∥f′(ζ)†[f′(x)-f′(ζ)]∥≤∫0∥x-ζ∥‍L(u)du=h0,0′(∥x-ζ∥)-h0,0′(0)<-h0,0′(0)=1.
It follows from Banach lemma that [Iℝn-f′(ζ)†(f′(ζ)-f′(x))]-1 exists and
(69)∥[Iℝn-f′(ζ)†(f′(ζ)-f′(x))]-1∥≤-1h0,0′(∥x-ζ∥).
Since f′(ζ) is full row rank, we have f′(ζ)f′(ζ)†=Iℝm and
(70)f′(x)=f′(ζ)[Iℝn-f′(ζ)†(f′(ζ)-f′(x))],
which implies that f′(x) is full row rank; that is, rank⁡f′(x)=rank⁡f′(ζ).Proof of Theorem12.
Letf^:B(ζ,r)→ℝm be defined by
(71)f^(x)=f′(ζ)†f(x),x∈B(ζ,r),
with residual r^k=f′(ζ)†rk. Since
(72)f^′(x)†=[f′(ζ)†f′(x)]†=f′(x)†f′(ζ),x∈B(ζ,r),
one has that {xk} coincides with the sequence generated by inexact Newton-Gauss method (7) for f^. In addition, we have
(73)f^′(ζ)†=(f′(ζ)†f′(ζ))†=f′(ζ)†f′(ζ),
and so
(74)∥f^′(ζ)†f^(ζ)∥=∥f′(ζ)†f′(ζ)f′(ζ)†f(ζ)∥=∥f′(ζ)†f(ζ)∥.
Because ∥f′(ζ)†f(ζ)∥=∥Πker⁡f′(ζ)⊥∥=1, thus, we have ∥f^′(ζ)†∥=∥f^′(ζ)†f^(ζ)∥=1. Therefore, by (24), we can obtain that
(75)∥f^′(ζ)†∥∥f^′(x)-f^′(ζ+τ(x-ζ))∥=∥f′(ζ)†(f′(x)-f′(ζ+τ(x-ζ)))∥≤∫τ∥x-ζ∥∥x-ζ∥L(u)du.
That is, f^ satisfies the modified L-average Lipschitz condition (25) on B(ζ,r). So, Theorem 9 is applicable and {xk} converges to ζ as follows. Note that f^′(·)†f^(·)=f′(·)†f(·) and f(·)=f′(·)f′(·)†f(·); it follows that ζ is a zero of f.


### 4.3. Proof of Theorem13

Lemma 21.
Suppose thatf(ζ)=0,f′(ζ) is full row rank, and f′ satisfies theL-average Lipschitz condition (24) on B(ζ,r). Then, one has
(76)∥f′(x)†f′(ζ)∥≤-1h0,0′(∥x-ζ∥),x∈B(ζ,r).Proof.
Sincef′(ζ) is full row rank, we have f′(ζ)f′(ζ)†=Iℝm. It follows that
(77)f′(x)†f′(ζ)(Iℝn-f′(ζ)†(f′(ζ)-f′(x)))=f′(x)†f′(x),x∈B(ζ,r).
By Lemma 20, Iℝn-f′(ζ)†(f′(ζ)-f′(x)) is invertible for any x∈B(ζ,r). Thus, in view of the equality A†A=Πker⁡A⊥, for any m×n matrix A, one has that
(78)f′(x)†f′(ζ)=Πker⁡f′(x)⊥[Iℝn-f′(ζ)†(f′(ζ)-f′(x))]-1.
Therefore, Lemma 20 is applicable to conclude that
(79)∥f′(x)†f′(ζ)∥≤∥Πker⁡f′(x)⊥∥∥[Iℝn-f′(ζ)†(f′(ζ)-f′(x))]-1∥≤-1h0,0′(∥x-ζ∥).Proof of Theorem13.
Using Lemma21, L-average condition (24), and the residual condition (35), respectively, instead of Lemma 19, modified L-average condition (25), and condition (29), one can complete the proof of Theorem 13 as the same line of proof in Theorem 9.


### 4.4. Proof of Theorem17

Proof.
Recall that the majorizing sequence{tk} is defined by (21) and the majorizing function hλ,θ(t) is defined by (42). By Lemma 4, {tk} is strictly decreasing and converges to 0. We first note that (57) gives
(80)xk-ζ=f′(xk)†∫01‍[f′(xk)-f′(ζ+τ(xk-ζ))]×(xk-ζ)dτ+f′(xk)†rk+[Iℝn-f′(xk)†f′(xk)](xk-ζ).
Using Lemma 8, the γ-condition (26), and Lemma 21, one has that
(81)∥f′(xk)†∫01‍[f′(xk)-f′(ζ+τ(xk-ζ))](xk-ζ)dτ∥≤γtk21-4γtk+2γ2tk2·∥xk-ζ∥tk2.
Thanks to (60), we use the γ-condition (26), Lemma 21, and the condition (49) to obtain that
(82)λk∥f′(xk)†f(xk)∥≤λ(2γ2tk2-3γtk+1)tk2γ2tk2-4γtk+1·∥xk-ζ∥tk.
Note that
(83)λ(1-3γt+2γ2t2)1-4γt+2γ2t2<1forany0≤t<(4-3λ)-(4-3λ)2-8(1-λ)24γ(1-λ).
Then, it follows from (49) and (82) that
(84)∥f′(xk)†rk∥≤(λk∥f′(xk)†f(xk)∥)2≤λ(2γ2tk2-3γtk+1)tk22γ2tk2-4γtk+1·∥xk-ζ∥2tk2.
Thus, we can obtain by combining (81), (84), and (48) that
(85)∥xk+1-ζ∥≤(γtk21-4γtk+2γ2tk2+λ(2γ2tk2-3γtk+1)tk21-4γtk+2γ2tk2+θtk2)×∥xk-ζ∥2tk2.
It is clear that the function
(86)ψ(t):=λ(1-3γt+2γ2t2)1-4γt+2γ2t2+γ1-4γt+2γ2t2+θ
is increasing monotonically with respect to t in [0,(2-2)/2γ). Hence, we have
(87)∥xk-ζ∥≤(γt021-4γt0+2γ2t02+λ(2γ2t02-3γt0+1)t021-4γt0+2γ2t02+θt02)×∥xk-1-ζ∥2t02≤(ψ(t0)t0)2k-1∥x0-ζ∥.
Consequently, to show that x0 is an approximate zero of f, it suffices to prove ψ(t0)t0≤1/2. In fact, in view of the definition of r* given in (46), for any t∈[0,t^], we have -1≤ϕ(t)≤0. Consequently, we get that
(88)4γ2(λ+θ)t3-2γ(3λ+4θ)t2+2(λ+θ+γ)t1-4γt+2γ2t2≤1,
which is equivalent to tψ(t)≤1/2,t∈[0,t^]. The proof is complete.


## 4.1. Proof of Theorem9

The following lemma gives a perturbation bound for Moore-Penrose inverse, which is stated in [31, Corollary 7.1.1 and Corollary 7.1.2].Lemma 18 (see [31]).
LetA and B be m×n matrices and let r≤min⁡{m,n}. Suppose that rank⁡A=r,1≤rank⁡B≤rank⁡A, and ∥A†∥∥B-A∥<1. Then, rank⁡B=r and
(52)∥B†∥≤∥A†∥1-∥A†∥∥B-A∥.Lemma 19.
Suppose thatf′ satisfies the modifiedL-average Lipschitz condition on B(ζ,r) and that ∥ζ-x∥<min⁡{ρ,ξ}, where r, ρ, and ξ are defined in (20), (15), and (14), respectively. Then, rank⁡f′(x)=rank⁡f′(ζ) and
(53)∥f′(x)†∥≤-∥f′(ζ)†∥h0,0′(∥x-ζ∥).Proof.
Sinceh0,0′(0)=-1, we have
(54)∥f′(ζ)†∥∥f′(x)-f′(ζ)∥≤∫0∥x-ζ∥‍L(u)du=h0,0′(∥x-ζ∥)-h0,0′(0)<-h0,0′(0)=1.
It follows from Lemma 18 that rank⁡f′(x)=rank⁡f′(ζ) and
(55)∥f′(x)†∥≤∥f′(ζ)†∥1-(h0,0′(∥x-ζ∥)-h0,0′(0))=-∥f′(ζ)†∥h0,0′(∥x-ζ∥).Proof of Theorem9.
We will prove by induction that{tk} is the majorizing sequence for {xk}; that is,
(56)∥ζ-xj∥≤tj∀j=0,1,2,….
Because t0=∥x0-ζ∥, thus (56) holds, for j=0. Now, we assume that ∥ζ-xj∥≤tj, for some j=k∈ℕ. For the case j=k+1, we first notice that
(57)xk+1-ζ=xk-ζ-f′(xk)†[f(xk)-f(ζ)]+f′(xk)†rk=f′(xk)†[f(ζ)-f(xk)-f′(xk)(ζ-xk)]+f′(xk)†rk+[Iℝn-f′(xk)†f′(xk)](xk-ζ)=f′(xk)†∫01[f′(xk)-f′(ζ+τ(xk-ζ))]‍(xk-ζ)dτ+f′(xk)†rk+[Iℝn-f′(xk)†f′(xk)](xk-ζ).
By using the modified L-average Lipschitz condition (25), Lemma 19, the inductive hypothesis (56), and Lemma 1, one has that
(58)∥f′(xk)†∫01‍[f′(xk)-f′(ζ+τ(xk-ζ))](xk-ζ)dτ∥≤-1h0,0′(∥xk-ζ∥)×∫01∥f′(ζ)†∥∥f′(xk)-f′(ζ+τ(xk-ζ))∥×∥xk-ζ∥dτ‍≤-1h0,0′(∥xk-ζ∥)∫01∫τ∥xk-ζ∥∥xk-ζ∥L(u)∥xk-ζ∥dudτ‍‍=-1h0,0′(∥xk-ζ∥)×∫01hλ,0′(∥xk-ζ∥)-hλ,0′(τ∥xk-ζ∥)∥xk-ζ∥dτ·∥xk-ζ∥2≤-1h0,0′(tk)∫01hλ,0′(tk)-hλ,0′(τtk)tkdτ·∥xk-ζ∥2‍=-1h0,0′(tk)(tkh′λ,0(tk)-hλ,0(tk))∥xk-ζ∥2tk2.
Thanks to (29),
(59)∥f′(xk)†rk∥≤∥f′(xk)†∥∥rk∥≤λk∥f′(xk)†∥∥f(xk)∥.
Since
(60)-f(xk)=f(ζ)-f(xk)-f′(xk)(ζ-xk)+f′(xk)(ζ-xk)=∫01‍[f′(xk)-f′(ζ+τ(xk-ζ))](xk-ζ)dτ+f′(xk)(ζ-xk),
combining Lemmas 1 and 19, the modified L-average Lipschitz condition (25), the inductive hypothesis (56), and the condition (29), we have
(61)λk∥f′(xk)†∥∥f(xk)∥≤λk∥f′(xk)†∥∫01∥f′(xk)-f′(ζ+τ(xk-ζ))∥‍×∥xk-ζ∥dτ+λk∥f′(xk)†∥∥f′(xk)∥∥xk-ζ∥≤-λ(h0,0′(tk))(tkhλ,0′(tk)-hλ,0(tk))∥xk-ζ∥2tk2+λtk·∥xk-ζ∥tk(62)≤λλtk+hλ,0(tk)h0,0′(tk)·∥xk-ζ∥tk.
Combining (28), (58), (59), and (62), we can obtain that
(63)∥xk+1-ζ∥≤[-tkhλ,0′(tk)-hλ,0(tk)h0,0′(tk)+λ·λtk+hλ,0(tk)h0,0′(tk)+θtk]×∥xk-ζ∥tk=[-tk+(1+λ)(λtkh0,0′(tk)+hλ,0(tk)h0,0′(tk))+θtk]×∥xk-ζ∥tk.
By the definition of hλ,0(t), we have hλ,0(t)≥-(1+λ)t. Then, we can obtain that
(64)(1+λ)(λtkh0,0′(tk)+hλ,0(tk)h0,0′(tk))≤hλ,0(tk)h0,0′(tk).
Note that -1<h0,0′(t)<0, for any t∈(0,ρ), and
(65)(1+λ)(λtkh0,0′(tk)+hλ,0(tk)h0,0′(tk))+θtk≤hλ,0(tk)h0,0′(tk)+θtk≤hλ,0(tk)-θtkh0,0′(tk)=hλ,θ(tk)h0,0′(tk).
Thus, in view of the definition of {tk} given in (21), one has that
(66)∥xk+1-ζ∥≤tk+1tk∥xk-ζ∥,
which implies ∥xk+1-ζ∥≤tk+1. Therefore, the proof by induction is complete. Since {tk} converges to 0 (by Lemma 4), it follows from (56) that {xk} converges to ζ and the estimate (30) holds for all k≥0. This completes the proof.


## 4.2. Proof of Theorem12

Lemma 20.
Suppose thatf(ζ)=0,f′(ζ) is full row rank, and f′ satisfies the L-average Lipschitz condition (24) on B(ζ,r). Then, for any x∈B(ζ,r), one has rank⁡f′(x)=rank⁡f′(ζ) and
(67)∥[Iℝn-f′(ζ)†(f′(ζ)-f′(x))]-1∥≤-1h0,0′(∥x-ζ∥).Proof.
Sinceh0,0′(0)=-1, we have
(68)∥f′(ζ)†[f′(x)-f′(ζ)]∥≤∫0∥x-ζ∥‍L(u)du=h0,0′(∥x-ζ∥)-h0,0′(0)<-h0,0′(0)=1.
It follows from Banach lemma that [Iℝn-f′(ζ)†(f′(ζ)-f′(x))]-1 exists and
(69)∥[Iℝn-f′(ζ)†(f′(ζ)-f′(x))]-1∥≤-1h0,0′(∥x-ζ∥).
Since f′(ζ) is full row rank, we have f′(ζ)f′(ζ)†=Iℝm and
(70)f′(x)=f′(ζ)[Iℝn-f′(ζ)†(f′(ζ)-f′(x))],
which implies that f′(x) is full row rank; that is, rank⁡f′(x)=rank⁡f′(ζ).Proof of Theorem12.
Letf^:B(ζ,r)→ℝm be defined by
(71)f^(x)=f′(ζ)†f(x),x∈B(ζ,r),
with residual r^k=f′(ζ)†rk. Since
(72)f^′(x)†=[f′(ζ)†f′(x)]†=f′(x)†f′(ζ),x∈B(ζ,r),
one has that {xk} coincides with the sequence generated by inexact Newton-Gauss method (7) for f^. In addition, we have
(73)f^′(ζ)†=(f′(ζ)†f′(ζ))†=f′(ζ)†f′(ζ),
and so
(74)∥f^′(ζ)†f^(ζ)∥=∥f′(ζ)†f′(ζ)f′(ζ)†f(ζ)∥=∥f′(ζ)†f(ζ)∥.
Because ∥f′(ζ)†f(ζ)∥=∥Πker⁡f′(ζ)⊥∥=1, thus, we have ∥f^′(ζ)†∥=∥f^′(ζ)†f^(ζ)∥=1. Therefore, by (24), we can obtain that
(75)∥f^′(ζ)†∥∥f^′(x)-f^′(ζ+τ(x-ζ))∥=∥f′(ζ)†(f′(x)-f′(ζ+τ(x-ζ)))∥≤∫τ∥x-ζ∥∥x-ζ∥L(u)du.
That is, f^ satisfies the modified L-average Lipschitz condition (25) on B(ζ,r). So, Theorem 9 is applicable and {xk} converges to ζ as follows. Note that f^′(·)†f^(·)=f′(·)†f(·) and f(·)=f′(·)f′(·)†f(·); it follows that ζ is a zero of f.


## 4.3. Proof of Theorem13

Lemma 21.
Suppose thatf(ζ)=0,f′(ζ) is full row rank, and f′ satisfies theL-average Lipschitz condition (24) on B(ζ,r). Then, one has
(76)∥f′(x)†f′(ζ)∥≤-1h0,0′(∥x-ζ∥),x∈B(ζ,r).Proof.
Sincef′(ζ) is full row rank, we have f′(ζ)f′(ζ)†=Iℝm. It follows that
(77)f′(x)†f′(ζ)(Iℝn-f′(ζ)†(f′(ζ)-f′(x)))=f′(x)†f′(x),x∈B(ζ,r).
By Lemma 20, Iℝn-f′(ζ)†(f′(ζ)-f′(x)) is invertible for any x∈B(ζ,r). Thus, in view of the equality A†A=Πker⁡A⊥, for any m×n matrix A, one has that
(78)f′(x)†f′(ζ)=Πker⁡f′(x)⊥[Iℝn-f′(ζ)†(f′(ζ)-f′(x))]-1.
Therefore, Lemma 20 is applicable to conclude that
(79)∥f′(x)†f′(ζ)∥≤∥Πker⁡f′(x)⊥∥∥[Iℝn-f′(ζ)†(f′(ζ)-f′(x))]-1∥≤-1h0,0′(∥x-ζ∥).Proof of Theorem13.
Using Lemma21, L-average condition (24), and the residual condition (35), respectively, instead of Lemma 19, modified L-average condition (25), and condition (29), one can complete the proof of Theorem 13 as the same line of proof in Theorem 9.


## 4.4. Proof of Theorem17

Proof.
Recall that the majorizing sequence{tk} is defined by (21) and the majorizing function hλ,θ(t) is defined by (42). By Lemma 4, {tk} is strictly decreasing and converges to 0. We first note that (57) gives
(80)xk-ζ=f′(xk)†∫01‍[f′(xk)-f′(ζ+τ(xk-ζ))]×(xk-ζ)dτ+f′(xk)†rk+[Iℝn-f′(xk)†f′(xk)](xk-ζ).
Using Lemma 8, the γ-condition (26), and Lemma 21, one has that
(81)∥f′(xk)†∫01‍[f′(xk)-f′(ζ+τ(xk-ζ))](xk-ζ)dτ∥≤γtk21-4γtk+2γ2tk2·∥xk-ζ∥tk2.
Thanks to (60), we use the γ-condition (26), Lemma 21, and the condition (49) to obtain that
(82)λk∥f′(xk)†f(xk)∥≤λ(2γ2tk2-3γtk+1)tk2γ2tk2-4γtk+1·∥xk-ζ∥tk.
Note that
(83)λ(1-3γt+2γ2t2)1-4γt+2γ2t2<1forany0≤t<(4-3λ)-(4-3λ)2-8(1-λ)24γ(1-λ).
Then, it follows from (49) and (82) that
(84)∥f′(xk)†rk∥≤(λk∥f′(xk)†f(xk)∥)2≤λ(2γ2tk2-3γtk+1)tk22γ2tk2-4γtk+1·∥xk-ζ∥2tk2.
Thus, we can obtain by combining (81), (84), and (48) that
(85)∥xk+1-ζ∥≤(γtk21-4γtk+2γ2tk2+λ(2γ2tk2-3γtk+1)tk21-4γtk+2γ2tk2+θtk2)×∥xk-ζ∥2tk2.
It is clear that the function
(86)ψ(t):=λ(1-3γt+2γ2t2)1-4γt+2γ2t2+γ1-4γt+2γ2t2+θ
is increasing monotonically with respect to t in [0,(2-2)/2γ). Hence, we have
(87)∥xk-ζ∥≤(γt021-4γt0+2γ2t02+λ(2γ2t02-3γt0+1)t021-4γt0+2γ2t02+θt02)×∥xk-1-ζ∥2t02≤(ψ(t0)t0)2k-1∥x0-ζ∥.
Consequently, to show that x0 is an approximate zero of f, it suffices to prove ψ(t0)t0≤1/2. In fact, in view of the definition of r* given in (46), for any t∈[0,t^], we have -1≤ϕ(t)≤0. Consequently, we get that
(88)4γ2(λ+θ)t3-2γ(3λ+4θ)t2+2(λ+θ+γ)t1-4γt+2γ2t2≤1,
which is equivalent to tψ(t)≤1/2,t∈[0,t^]. The proof is complete.



---

*Source: 752673-2014-03-26.xml*