# On Local Convergence Analysis of Inexact Newton Method for Singular Systems of Equations under Majorant Condition

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

---

## Abstract

We present a local convergence analysis of inexact Newton method for solving singular systems of equations. Under the hypothesis that the derivative of the function associated with the singular systems satisfies a majorant condition, we obtain that the method is well defined and converges. Our analysis provides a clear relationship between the majorant function and the function associated with the singular systems. It also allows us to obtain an estimate of convergence ball for inexact Newton method and some important special cases.


---

## Body

## 1. Introduction

Newton’s method and its variations, including the inexact Newton methods, are the most efficient methods known for solving the following nonlinear equation:(1)
F
(
x
)
=
0
,
where F
:
Ω
⊂
R
n
→
R
m is a nonlinear operator with its Fréchet derivative denoted by D
F; Ω is open and convex. In the case m
=
n, the inexact Newton method was introduced in [1] denoting any method which, given an initial point x
0, generates the sequence {
x
k
} as follows:
(2)
x
k
+
1
=
x
k
+
s
k
,
D
F
(
x
k
)
s
k
=
-
F
(
x
k
)
+
r
k
,
hhhhhhhhhhhhhhhhhhhhhhhh
k
=
0,1
,
2
,
…
,
where the residual control r
k satisfies
(3)
∥
r
k
∥
≤
λ
k
∥
F
(
x
k
)
∥
,
k
=
0,1
,
2
,
…
,
and {
λ
k
} is a sequence of forcing terms such that 0
≤
λ
k
<
1. Let ζ be a solution of (1) such that D
F
(
ζ
) is invertible. As shown in [1], if λ
k
≤
λ
<
1, then, there exists r
>
0 such that, for any initial guess x
0
∈
B
(
ζ
,
r
)
:
=
{
x
∈
R
n
:
∥
x
-
ζ
∥
<
r
}, the sequence {
x
k
} is well defined and converges to a solution ζ in the norm ∥
y
∥
*
:
=
∥
D
F
(
ζ
)
y
∥, where ∥
·
∥ is any norm in R
n. Moreover, the rate of convergence of {
x
k
} to ζ is characterized by the rate of convergence of {
λ
k
} to 0. It is worth noting that, in [1], no Lipschitz condition is assumed on the derivative D
F to prove that {
x
k
} is well defined and linearly converging. However, no estimate of the convergence radius r is provided. As pointed out by [2] the result of [1] is difficult to apply due to dependence of the norm ∥
·
∥
*, which is not computable.It is clear that the residual control (3) is not affine invariant (see [3] for more details about the affine invariant). To this end, Ypma used in [4] the affine invariant condition of residual control in the form
(4)
∥
D
F
(
x
k
)
-
1
r
k
∥
≤
λ
k
∥
D
F
(
x
k
)
-
1
F
(
x
k
)
∥
,
k
=
0,1
,
2
,
…
,
to study the local convergence of inexact Newton method (2). 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 [2] the following variation for the residual controls:
(5)
∥
P
k
r
k
∥
≤
λ
k
∥
P
k
F
(
x
k
)
∥
,
k
=
0,1
,
2
,
…
,
where {
P
k
} is a sequence of invertible operators from R
n to R
n and {
λ
k
} is the forcing term. If P
k
=
I and P
k
=
D
F
(
x
k
) for each k, (5) reduces to (3) and (4), respectively. Both proposed inexact methods are linearly convergent under Lipschitz condition. It is worth noting that the residual controls (5) are used in iterative methods if preconditioning is applied and lead to a relaxation on the forcing terms. And we also note that the results obtained in [2] cannot make us clearly see how big the radius of the convergence ball is. To this end, Chen and Li [5] obtained the local convergence properties of inexact methods for (1) under weak Lipschitz condition, which was first introduced by Wang in [6] to study the local convergence behavior of Newton’s method. The results in [5] easily provide an estimate of convergence ball for the inexact methods. Furthermore, Ferreira and Gonçalves presented in [7] a new local convergence analysis for inexact Newton-like method under the so-called majorant condition.Recent attentions are focused on the study of finding zeros of singular nonlinear systems by Gauss-Newton’s method, which is defined as follows. For a given initial pointx
0
∈
Ω, define
(6)
x
k
+
1
=
x
k
-
D
F
(
x
k
)
†
F
(
x
k
)
,
k
=
0,1
,
2
,
…
,
where D
F
(
x
k
)
† denotes the Moore-Penrose inverse of the linear operator (or matrix) D
F
(
x
k
). For example, Shub and Smale extended in [8] 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 [9] the local linear convergence properties of Gauss-Newton’s method for analytic systems with injective derivatives and provided estimates of the radius of convergence balls for Gauss-Newton’s method. Dedieu and Kim in [10] generalized the results of both the underdetermined case and the overdetermined case to such case where D
F
(
x
) is of constant rank (not necessarily full rank), which has been improved by some authors in [11–16].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 [17] employed the ideas of [5] 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 [18] 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 are interested in the local convergence analysis; that is, based on the information in a neighborhood of a solution of (1), we determine the convergence ball of the method. Following the ideas of [7, 14, 18–20], we will present a new local convergence analysis for inexact Newton’s method for solving singular systems with constant rank derivatives under majorant condition. The convergence analysis presented provides a clear relationship between the majorizing function, which relaxes the Lipschitz continuity of the derivative, and the function associated with the nonlinear operator equation. Besides, the results presented here have the conditions and the proof of convergence in quite a simple manner. Moreover, two unrelated previous results pertaining to inexact Newton method are unified, namely, the result for analytical functions and the classical one for functions with Lipschitz derivative.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. Notations and Auxiliary Results

Forx
∈
R
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.LetA
:
R
n
→
R
m be a linear operator (or an m
×
n matrix). Recall that an operator (or n
×
m matrix) A
†
:
R
m
→
R
n is the Moore-Penrose inverse of A if it satisfies the following four equations:
(7)
A
†
A
A
†
=
A
†
;
A
A
†
A
=
A
;
(
A
A
†
)
*
=
A
A
†
;
(
A
†
A
)
*
=
A
†
A
,
where A
* denotes the adjoint of A. Let ker
⁡
A and im
A denote the kernel and image of A, respectively. For a subspace E of R
n, we use Π
E to denote the projection onto E. Then, it is clear that
(8)
A
†
A
=
Π
ker
⁡
A
⊥
,
A
A
†
=
Π
im
A
.
In particular, in the case when A is full row rank (or equivalently, when A is surjective), A
A
†
=
I
R
m; when A is full column rank (or equivalently, when A is injective), A
†
A
=
I
R
n.The following lemma gives a perturbation bound for Moore-Penrose inverse, which is stated in [21].Lemma 1 (see [21], Corollary 7.1.1 and Corollary 7.1.2 ).
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
(9)
∥
B
†
∥
≤
∥
A
†
∥
1
-
∥
A
†
∥
∥
B
-
A
∥
.Also, we need the following useful lemma about elementary convex analysis.Lemma 2 (see [22], Proposition 1.3).
LetR
>
0. If g
:
[
0
,
R
]
→
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.For a positive realR
∈
R
+, let
(10)
f
:
[
0
,
R
]
×
[
0,1
)
×
[
0,1
)
⟶
R
be a continuously differentiable function of three of its arguments and satisfy the following properties:.(i)
f
(
0
,
λ
,
θ
)
=
0 and (
∂
/
∂
t
)
f
(
t
,
λ
,
θ
)
|
t
=
0
=
-
(
1
+
λ
+
θ
),
(ii)
(
∂
/
∂
t
)
f
(
t
,
λ
,
θ
) is convex and strictly increasing with respect to the argument t.For fixedλ
,
θ
∈
[
0,1
), we write h
λ
,
θ
(
t
)
≜
f
(
t
,
λ
,
θ
) for short below. Then the above two properties can be restated as follows:(iii)
h
λ
,
θ
(
0
)
=
0 and h
λ
,
θ
′
(
0
)
=
-
(
1
+
λ
+
θ
),
(iv)
h
λ
,
θ
′
(
t
) is convex and strictly increasing.Set(11)
ξ
∶
=
sup
⁡
{
t
∈
[
0
,
R
)
:
h
0,0
′
(
t
)
<
0
}
,
(12)
ρ
∶
=
sup
⁡
{
t
∈
[
0
,
ξ
)
:
h
λ
,
θ
(
t
)
h
0,0
′
(
t
)
-
t
<
t
}
,
(13)
σ
∶
=
sup
⁡
{
t
∈
[
0
,
R
)
:
B
(
ζ
,
t
)
⊂
Ω
}
.
The next two lemmas show that the constants ξ and ρ defined in (11) and (12), respectively, are positive.Lemma 3.
The constantξ defined in (11) is positive and t
-
h
λ
,
θ
(
t
)
/
h
0,0
′
(
t
)
<
0 for all t
∈
(
0
,
ξ
).Proof.
Sinceh
0,0
′
(
0
)
=
-
1, there exists δ
>
0 such that h
0,0
′
(
t
)
<
0 for all t
∈
(
0
,
δ
). Then, we get ξ
≥
δ
(
>
0
). It remains to show that t
-
h
λ
,
θ
(
t
)
/
h
0,0
′
(
t
)
<
0 for all t
∈
(
0
,
ξ
). Because h
λ
,
θ
′ is strictly increasing, h
λ
,
θ is strictly convex. It follows from Lemma 2 (i) that
(14)
h
λ
,
θ
(
t
)
-
h
λ
,
θ
(
0
)
t
<
h
λ
,
θ
′
(
t
)
≤
h
0,0
′
(
t
)
,
t
∈
(
0
,
R
)
.
Since h
λ
,
θ
(
0
)
=
0 and h
0,0
′
(
t
)
<
0 for all t
∈
(
0
,
ξ
), we obtain the desired inequality by (14).Lemma 4.
The constantρ defined in (12) is positive. As a consequence, |
t
-
h
λ
,
θ
(
t
)
/
h
0
,
0
′
(
t
)
|
<
t for all t
∈
(
0
,
ρ
).Proof.
On one hand, by Lemma3, it is clear that h
λ
,
θ
(
t
)
/
t
h
0
,
0
′
(
t
)
-
1
>
0 for t
∈
(
0
,
ξ
). On the other hand, we can obtain from Lemma 2 (i) that
(15)
lim
⁡
t
→
0
(
h
λ
,
θ
(
t
)
t
h
0,0
′
(
t
)
-
1
)
=
0
.
Then, we conclude that there exists a δ
>
0 such that
(16)
0
<
h
λ
,
θ
(
t
)
t
h
0,0
′
(
t
)
-
1
<
1
,
t
∈
(
0
,
ξ
)
.
Therefore, ρ is positive. This completes the proof.Let(17)
r
≔
min
⁡
⁡
{
ρ
,
σ
}
,
where ρ and σ are given in (12) and (13), respectively. For any starting point x
0
∈
B
(
ζ
,
r
)
∖
{
ζ
}, let {
t
k
} denote the sequence generated by
(18)
t
0
=
∥
x
0
-
ζ
∥
,
t
k
+
1
=
|
t
k
-
h
λ
,
θ
(
t
k
)
h
0,0
′
(
t
k
)
|
,
k
=
0,1
,
2
,
…
.Lemma 5.
The sequence{
t
k
} given by (18) is well defined, strictly decreasing, and contained in (
0
,
ρ
) and converges to 0.Proof.
Since0
<
t
0
=
∥
x
0
-
ζ
∥
<
r
≤
ρ, using Lemma 4, one has that {
t
k
} is well defined, strictly decreasing, and contained in [
0
,
ρ
). Thus, there exists t
*
∈
[
0
,
ρ
) such that lim
⁡
k
→
∞
t
k
=
t
*. That is to say, we have
(19)
0
≤
t
*
=
h
λ
,
θ
(
t
*
)
h
0,0
′
(
t
*
)
-
t
*
<
ρ
.
If t
*
≠
0, it follows from Lemma 4 that
(20)
h
λ
,
θ
(
t
*
)
h
0,0
′
(
t
*
)
-
t
*
<
t
*
.
This is a contradiction. So t
k
→
0 as k
→
∞. This completes the proof.Based on the researches in [7, 14, 18, 20] for the convergence of various Newton-type methods, we present the following modified majorant condition.Definition 6.
Letr
>
0 be such that B
(
ζ
,
r
)
⊂
Ω. Then, D
F is said to satisfy the majorant condition on B
(
ζ
,
r
) if
(21)
∥
D
F
(
ζ
)
†
[
D
F
(
x
)
-
D
F
(
ζ
+
τ
(
x
-
ζ
)
)
]
∥
≤
h
λ
,
θ
′
(
∥
x
-
ζ
∥
)
-
h
λ
,
θ
′
(
τ
∥
x
-
ζ
∥
)
for any x
∈
B
(
ζ
,
r
) and τ
∈
[
0,1
].In the case whenD
F
(
ζ
) is not surjective (see [9, 10]), the information on im
D
F
(
ζ
)
⊥ may be lost. To this end, we need to modify the above notion to suit the case when D
F
(
ζ
) is not surjective.Definition 7.
Letr
>
0 be such that B
(
ζ
,
r
)
⊂
Ω. Then, f
′ is said to satisfy the modified majorant condition on B
(
ζ
,
r
) if
(22)
∥
D
F
(
ζ
)
†
∥
∥
D
F
(
x
)
-
D
F
(
ζ
+
τ
(
x
-
ζ
)
)
∥
≤
h
λ
,
θ
′
(
∥
x
-
ζ
∥
)
-
h
λ
,
θ
′
(
τ
∥
x
-
ζ
∥
)
for any x
∈
B
(
ζ
,
r
) and τ
∈
[
0,1
].


## 3. Main Results

In this section, we state our main results of local convergence for inexact Newton method (2). Recall that (1) is a surjective-underdetermined (resp., injective-overdetermined) system if the number of equations is less (resp., greater) than the number of unknowns and D
F
(
x
) is of full rank for each x
∈
Ω. Note that, for surjective-underdetermined systems, the fixed points of the Newton operator N
F
(
x
)
∶
=
x
-
D
F
(
x
)
†
F
(
x
) are the zeros of F, while for injective-overdetermined systems, the fixed points of N
F are the least square solutions of (1), which, in general, are not necessarily the zeros of F.Our first result concerns the local convergence properties of inexact Newton’s method for general singular systems with constant rank derivatives.Theorem 8.
LetF
:
Ω
⊂
R
n
→
R
m be continuously Fréchet differentiable nonlinear operator, where Ω is open and convex. Suppose that F
(
ζ
)
=
0, D
F
(
ζ
)
≠
0 and that D
F satisfies the modified majorant condition (22) on B
(
ζ
,
r
), where r is given in (17). In addition, we assume that rank
D
F
(
x
)
≤
rank
D
F
(
ζ
) for any x
∈
B
(
ζ
,
r
) and that
(23)
∥
[
I
R
n
-
D
F
(
x
)
†
D
F
(
x
)
]
(
x
-
ζ
)
∥
≤
θ
∥
x
-
ζ
∥
,
x
∈
B
(
ζ
,
r
)
,
where the constant θ satisfies 0
≤
θ
<
1. Let {
x
k
} be sequence generated by inexact Newton’s method with any initial point x
0
∈
B
(
ζ
,
r
)
∖
{
ζ
} and the conditions for the residual r
k and the forcing term λ
k:
(24)
∥
r
k
∥
≤
λ
k
∥
F
(
x
k
)
∥
,
0
≤
λ
k
κ
(
D
F
(
x
k
)
)
≤
λ
,
hhhhhhhhhhhhhhhhhhhhhhhhh
k
=
0,1
,
2
,
…
,
where κ
(
A
)
:
=
∥
A
†
∥
∥
A
∥ denotes the condition number of A
∈
R
m
×
n. Then, {
x
k
} converges to a zero ζ of D
F
(
·
)
†
F
(
·
) in B
(
ζ
,
r
)
¯. Moreover, we have the following estimate:
(25)
∥
x
k
+
1
-
ζ
∥
≤
t
k
+
1
t
k
∥
x
k
-
ζ
∥
,
k
=
0,1
,
2
,
…
,
where the sequence {
t
k
} is defined by (18).Remark 9.
Ifh
λ
,
θ
(
t
) is given by
(26)
h
λ
,
θ
(
t
)
=
-
(
1
+
λ
+
θ
)
t
+
∫
0
t
‍
L
(
u
)
(
t
-
u
)
d
u
,
t
∈
[
0
,
R
]
,
then the results obtained in Theorem 8 reduce to the one given in [19]. Moreover, if taking λ
=
0 (in this case λ
k
=
0 and r
k
=
0) in Theorem 8, we obtain the local convergence of Newton’s method for solving the singular systems, which has been studied by Dedieu and Kim in [10] for analytic singular systems with constant rank derivatives and Li et al. in [13] for some special singular systems with constant rank derivatives.IfD
F
(
x
) is full column rank for every x
∈
B
(
ζ
,
r
), then we have D
F
(
x
)
†
D
F
(
x
)
=
I
R
n. Thus,
(27)
∥
[
I
R
n
-
D
F
(
x
)
†
D
F
(
x
)
]
(
x
-
ζ
)
∥
=
0
.
That is, θ
=
0. We immediately have the following corollary.Corollary 10.
Suppose thatrank
D
F
(
x
)
≤
rank
D
F
(
ζ
) and that
(28)
∥
[
I
R
n
-
D
F
(
x
)
†
D
F
(
x
)
]
(
x
-
ζ
)
∥
=
0
for any x
∈
B
(
ζ
,
r
). Suppose that F
(
ζ
)
=
0, D
F
(
ζ
)
≠
0 and that D
F satisfies the modifed majorant condition (22). Let {
x
k
} be sequence generated by inexact Newton’s method with any initial point x
0
∈
B
(
ζ
,
r
)
∖
{
ζ
} and the condition (24) for the residual r
k and the forcing term λ
k. Then, {
x
k
} converges to a zero ζ of D
F
(
·
)
†
F
(
·
) in B
(
ζ
,
r
)
¯. Moreover, we have the following estimate:
(29)
∥
x
k
+
1
-
ζ
∥
≤
t
k
+
1
t
k
∥
x
k
-
ζ
∥
,
k
=
0,1
,
2
,
…
,
where the sequence {
t
k
} is defined by (18) for θ
=
0.In the case whenD
F
(
ζ
) is full row rank, the modified majorant condition (22) can be replaced by the majorant condition (21).Theorem 11.
Suppose thatF
(
ζ
)
=
0 and D
F
(
ζ
) is full row rank and that D
F satisfies the majorant condition (21) on B
(
ζ
,
r
), where r is given in (17). In addition, we assume that rank
D
F
(
x
)
≤
rank
D
F
(
ζ
) for any x
∈
B
(
ζ
,
r
) and that condition (23) holds. Let {
x
k
} be sequence generated by inexact Newton’s method with any initial point x
0
∈
B
(
ζ
,
r
)
∖
{
ζ
} and the conditions for the residual r
k and the forcing term λ
k:
(30)
∥
D
F
(
ζ
)
†
r
k
∥
≤
λ
k
∥
D
F
(
ζ
)
†
F
(
x
k
)
∥
,
0
≤
λ
k
κ
(
D
F
(
ζ
)
†
D
F
(
x
k
)
)
≤
λ
,
hhhhhhhhhhhhh
k
=
0,1
,
2
,
…
.
Then, {
x
k
} converges to a zero ζ of F
(
·
) in B
(
ζ
,
r
)
¯. Moreover, we have the following estimate:
(31)
∥
x
k
+
1
-
ζ
∥
≤
t
k
+
1
t
k
∥
x
k
-
ζ
∥
,
k
=
0,1
,
2
,
…
,
where the sequence {
t
k
} is defined by (18).Remark 12.
Whenh
λ
,
θ
(
t
) is given by (26), the results obtained in Theorem 11 reduce to the ones given in [19].Theorem 13.
Suppose thatF
(
ζ
)
=
0
,
D
F
(
ζ
) is full row rank and that D
F satisfies the majorant condition (21) on B
(
ζ
,
r
), where r is given in (17). In addition, we assume that rank
D
F
(
x
)
≤
rank
D
F
(
ζ
) for any x
∈
B
(
ζ
,
r
) and that condition (23) holds. Let {
x
k
} be sequence generated by inexact Newton method with any initial point x
0
∈
B
(
ζ
,
r
)
∖
{
ζ
} and the conditions for the control residual r
k and the forcing term λ
k:
(32)
∥
D
F
(
x
k
)
†
r
k
∥
≤
λ
k
∥
D
F
(
x
k
)
†
F
(
x
k
)
∥
,
0
≤
λ
k
κ
(
D
F
(
x
k
)
)
≤
λ
,
hhhhhhh
k
=
0,1
,
2
,
…
.
Then, {
x
k
} converges to a zero ζ of f
(
·
) in B
(
ζ
,
r
)
¯. Moreover, we have the following estimate:
(33)
∥
x
k
+
1
-
ζ
∥
≤
t
k
+
1
t
k
∥
x
k
-
ζ
∥
,
k
=
0,1
,
2
,
…
,
where the sequence {
t
k
} is defined by (18).Remark 14.
In the case whenD
F
(
ζ
) is invertible in Theorem 13 and h
λ
,
θ is given by (26), we obtain the local convergence results of inexact Newton method for nonsingular systems, and the convergence ball r in this case satisfies
(34)
∫
0
r
‍
L
(
u
)
u
d
u
r
(
(
1
-
λ
)
-
∫
0
r
‍
L
(
u
)
d
u
)
≤
1
,
λ
∈
[
0,1
)
.
In particular, if taking λ
=
0, the convergence ball r determined in (34) reduces to the one given in [6] by Wang and the value r is the optimal radius of the convergence ball when the equality holds. Now, Theorem 13 merges into the theory of Newton’s method obtained in [6].Example 15.
LetR
2 be endowed with the l
1-norm. Consider the operator F
:
R
2
→
R
2 defined by
(35)
F
(
x
)
∶
=
[
sin
(
x
1
-
x
2
)
-
1
2
cos
⁡
(
x
1
-
x
2
)
-
3
2
]
,
∀
x
=
[
x
1
x
2
]
∈
R
2
.
Then, F is analytic on R
2 and its derivative is given by
(36)
D
F
(
x
)
=
[
cos
⁡
⁡
(
x
1
-
x
2
)
-
cos
⁡
⁡
(
x
1
-
x
2
)
-
sin
⁡
(
x
1
-
x
2
)
sin
⁡
(
x
1
-
x
2
)
]
,
hhhhhhhhhhhhhhhhhhhhhh
∀
x
=
[
x
1
x
2
]
∈
R
2
.
Clearly, rank
⁡
(
D
F
(
x
)
)
=
1 and the Moore-Penrose inverse is
(37)
D
F
(
x
)
†
=
1
2
[
cos
⁡
⁡
(
x
1
-
x
2
)
-
sin
⁡
(
x
1
-
x
2
)
-
cos
⁡
⁡
(
x
1
-
x
2
)
sin
⁡
(
x
1
-
x
2
)
]
,
hhhhhhhhhhhhhhhhhhhhhhhh
∀
x
=
[
x
1
x
2
]
∈
R
2
.
Moreover, by mathematical induction, for k
=
1,2
,
…, we can obtain that
(38)
D
k
F
(
x
)
u
1
⋯
u
k
=
1
2
[
sin
(
x
1
-
x
2
+
k
π
2
)
cos
⁡
(
x
1
-
x
2
+
k
π
2
)
]
∏
i
=
1
k
‍
(
u
i
1
-
u
i
2
)
,
mmmmmm
u
i
=
[
u
i
1
u
i
2
]
∈
R
2
,
i
=
1
,
…
,
k
.
So, we have
(39)
∥
D
F
(
x
)
†
∥
=
max
⁡
{
|
cos
⁡
(
x
1
-
x
2
)
|
,
|
sin
(
x
1
-
x
2
)
|
}
,
∥
D
k
F
(
x
)
∥
=
|
cos
⁡
(
x
1
-
x
2
)
|
+
|
sin
(
x
1
-
x
2
)
|
.
Consequently,
(40)
γ
(
F
,
x
)
∶
=
sup
⁡
k
≥
2
(
∥
D
F
(
x
)
†
∥
∥
D
k
F
(
x
)
k
!
∥
)
1
/
(
k
-
1
)
=
|
cos
⁡
(
x
1
-
x
2
)
|
+
|
sin
(
x
1
-
x
2
)
|
2
×
max
⁡
{
|
cos
⁡
(
x
1
-
x
2
)
|
,
|
sin
(
x
1
-
x
2
)
|
}
.
Let
(41)
Ω
∶
=
{
(
x
1
,
x
2
)
T
:
π
5
<
x
1
<
3
π
10
,
0
<
x
2
<
π
10
}
⊂
R
2
.
Then, for any (
x
1
,
x
2
)
T
∈
Ω, we have
(42)
5
-
1
4
<
sin
(
x
1
-
x
2
)
<
5
+
1
4
,
5
8
-
5
8
<
cos
⁡
(
x
1
-
x
2
)
<
5
8
+
5
8
.
Consider the point ζ
=
(
13
π
/
60
,
π
/
20
)
T. Then, ζ
∈
Ω satisfies F
(
ζ
)
=
0 and
(43)
γ
∶
=
γ
(
F
,
ζ
)
=
3
+
3
8
.
Hence, we have
(44)
∥
[
I
R
n
-
D
F
(
x
)
†
D
F
(
x
)
]
(
x
-
ζ
)
∥
≤
(
5
8
+
5
8
)
∥
x
-
ζ
∥
,
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
x
∈
Ω
.
That is, (23) holds with θ
=
5
/
8
+
5
/
8
<
1. Furthermore, it is clear that
(45)
κ
(
D
F
(
x
k
)
)
=
∥
D
F
(
x
k
)
∥
∥
D
F
(
x
)
†
∥
=
2
(
5
8
+
5
8
)
.
So, we can choose the forcing term {
λ
k
} such that 0
≤
λ
k
≤
λ
max
⁡
=
1
/
2; see [23] for more details. Then (24) holds with λ
=
5
/
8
+
5
/
8. Now, the majorizing function h
λ
,
θ
(
t
) associated with the operator F defined by (35) reduces to
(46)
h
λ
,
θ
(
t
)
=
-
(
1
+
(
5
8
+
5
8
)
+
(
5
8
+
5
8
)
)
t
+
(
(
3
+
3
)
/
8
)
t
2
1
-
(
(
3
+
3
)
/
8
)
t
=
-
9
+
5
4
t
+
(
(
3
+
3
)
/
8
)
t
2
1
-
(
(
3
+
3
)
/
8
)
t
,
hhhhhhhhhhhhh
t
∈
[
0
,
4
(
3
-
3
)
3
)
.
Then we have the convergence radius r
=
0.0604146
…. Therefore, Theorem 8 is applicable to concluding that, for any x
0
∈
B
(
ζ
,
r
), the sequence {
x
k
} generated by inexact Newton method (2) with initial point x
0 converges to a zero of D
F
(
·
)
†
F
(
·
).


## 4. Proofs

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


### 4.1. Proof of Theorem8

Lemma 16.
Suppose thatD
F satisfies the modified majorant condition on B
(
ζ
,
r
) and that ∥
ζ
-
x
∥
<
min
⁡
{
ρ
,
ξ
}, where r, ρ, and ξ are defined in (17), (12), and (11), respectively. Then, rank
D
F
(
x
)
=
rank
D
F
(
ζ
) and
(47)
∥
D
F
(
x
)
†
∥
≤
-
∥
D
F
(
ζ
)
†
∥
h
0,0
′
(
∥
x
-
ζ
∥
)
.Proof.
Sinceh
0,0
′
(
0
)
=
-
1, we have
(48)
∥
D
F
(
ζ
)
†
∥
∥
D
F
(
x
)
-
D
F
(
ζ
)
∥
≤
h
0,0
′
(
∥
x
-
ζ
∥
)
-
h
0,0
′
(
0
)
<
-
h
0,0
′
(
0
)
=
1
.
It follows from Lemma 1 that rank
⁡
D
F
(
x
)
=
rank
⁡
D
F
(
ζ
) and
(49)
∥
D
F
(
x
)
†
∥
≤
∥
D
F
(
ζ
)
†
∥
1
-
(
h
0,0
′
(
∥
x
-
ζ
∥
)
-
h
0,0
′
(
0
)
)
=
-
∥
D
F
(
ζ
)
†
∥
h
0,0
′
(
∥
x
-
ζ
∥
)
.
This completes the proof.Proof of Theorem8.
We will prove by induction that{
t
k
} is the majorizing sequence for {
x
k
}; that is,
(50)
∥
ζ
-
x
j
∥
≤
t
j
∀
j
=
0,1
,
2
,
…
.
Because t
0
=
∥
x
0
-
ζ
∥, (50) holds for j
=
0. Now, we assume that ∥
ζ
-
x
j
∥
≤
t
j for some j
=
k
∈
N. For the case j
=
k
+
1, we first notice that
(51)
x
k
+
1
-
ζ
=
x
k
-
ζ
-
D
F
(
x
k
)
†
[
F
(
x
k
)
-
F
(
ζ
)
]
+
D
F
(
x
k
)
†
r
k
=
D
F
(
x
k
)
†
[
F
(
ζ
)
-
F
(
x
k
)
-
D
F
(
x
k
)
(
ζ
-
x
k
)
]
+
D
F
(
x
k
)
†
r
k
+
[
I
R
n
-
D
F
(
x
k
)
†
D
F
(
x
k
)
]
(
x
k
-
ζ
)

=

D
F
(
x
k
)
†
∫
0
1
‍
[
D
F
(
x
k
)
-
D
F
(
ζ
+
τ
(
x
k
-
ζ
)
)
]
(
x
k
-
ζ
)
d
τ
+
D
F
(
x
k
)
†
r
k
+
[
I
R
n
-
D
F
(
x
k
)
†
D
F
(
x
k
)
]
(
x
k
-
ζ
)
.
By using the modified majorant condition (22), Lemma 16, the inductive hypothesis (50), and Lemma 2, one has that
(52)
∥
D
F
(
x
k
)
†
∫
0
1
‍
[
D
F
(
x
k
)
-
D
F
(
ζ
+
τ
(
x
k
-
ζ
)
)
]
(
x
k
-
ζ
)
d
τ
∥
≤
-
1
h
0,0
′
(
∥
x
k
-
ζ
∥
)
∫
0
1
‍
∥
D
F
(
ζ
)
†
∥
×
∥
D
F
(
x
k
)
-
D
F
(
ζ
+
τ
(
x
k
-
ζ
)
)
∥
×
∥
x
k
-
ζ
∥
d
τ
=
-
1
h
0,0
′
(
∥
x
k
-
ζ
∥
)
×
∫
0
1
‍
h
λ
,
0
′
(
∥
x
k
-
ζ
∥
)
-
h
λ
,
0
′
(
τ
∥
x
k
-
ζ
∥
)
∥
x
k
-
ζ
∥
d
τ
·
∥
x
k
-
ζ
∥
2
≤
-
1
h
0,0
′
(
t
k
)
∫
0
1
‍
h
λ
,
0
′
(
t
k
)
-
h
λ
,
0
′
(
τ
t
k
)
t
k
d
τ
·
∥
x
k
-
ζ
∥
2
=
-
1
h
0,0
′
(
t
k
)
(
t
k
h
λ
,
0
′
(
t
k
)
-
h
λ
,
0
(
t
k
)
)
∥
x
k
-
ζ
∥
2
t
k
2
.
Thanks to (24),
(53)
∥
D
F
(
x
k
)
†
r
k
∥
≤
∥
D
F
(
x
k
)
†
∥
∥
r
k
∥
≤
λ
k
∥
D
F
(
x
k
)
†
∥
∥
F
(
x
k
)
∥
.
Since
(54)
-
F
(
x
k
)
=
F
(
ζ
)
-
F
(
x
k
)
-
D
F
(
x
k
)
(
ζ
-
x
k
)
+
D
F
(
x
k
)
(
ζ
-
x
k
)
=
∫
0
1
‍
[
D
F
(
x
k
)
-
D
F
(
ζ
+
τ
(
x
k
-
ζ
)
)
]
(
x
k
-
ζ
)
d
τ
+
D
F
(
x
k
)
(
ζ
-
x
k
)
,
combining Lemma 2, Lemma 16, the modified majorant condition (22), the inductive hypothesis (50), and the condition (24), we have
(55)
λ
k
∥
D
F
(
x
k
)
†
∥
∥
F
(
x
k
)
∥
≤
λ
k
∥
D
F
(
x
k
)
†
∥
×
∫
0
1
‍
∥
D
F
(
x
k
)
-
D
F
(
ζ
+
τ
(
x
k
-
ζ
)
)
∥
×
∥
x
k
-
ζ
∥
d
τ
+
λ
k
∥
D
F
(
x
k
)
†
∥
∥
D
F
(
x
k
)
∥
∥
x
k
-
ζ
∥
≤
-
λ
h
0,0
′
(
t
k
)
(
t
k
h
λ
,
0
′
(
t
k
)
-
h
λ
,
0
(
t
k
)
)
∥
x
k
-
ζ
∥
2
t
k
2
+
λ
t
k
·
∥
x
k
-
ζ
∥
t
k
≤
λ
λ
t
k
+
h
λ
,
0
(
t
k
)
h
0,0
′
(
t
k
)
·
∥
x
k
-
ζ
∥
t
k
.
Combining (23), (52), (53), and (55), we can obtain that
(56)
∥
x
k
+
1
-
ζ
∥
≤
[
-
t
k
h
λ
,
0
′
(
t
k
)
-
h
λ
,
0
(
t
k
)
h
0,0
′
(
t
k
)
mmm
+
λ
·
λ
t
k
+
h
λ
,
0
(
t
k
)
h
0,0
′
(
t
k
)
+
θ
t
k
]
∥
x
k
-
ζ
∥
t
k
=
[
-
t
k
+
(
1
+
λ
)
(
λ
t
k
h
0,0
′
(
t
k
)
+
h
λ
,
0
(
t
k
)
h
0,0
′
(
t
k
)
)
+
θ
t
k
]
∥
x
k
-
ζ
∥
t
k
.
Note that -
1
<
h
0,0
′
(
t
)
<
0 for any t
∈
(
0
,
ρ
),
(57)
(
1
+
λ
)
(
λ
t
k
h
0,0
′
(
t
k
)
+
h
λ
,
0
(
t
k
)
h
0,0
′
(
t
k
)
)
+
θ
t
k
≤
h
λ
,
0
(
t
k
)
h
0,0
′
(
t
k
)
+
θ
t
k
≤
h
λ
,
0
(
t
k
)
-
θ
t
k
h
0,0
′
(
t
k
)
=
h
λ
,
θ
(
t
k
)
h
0,0
′
(
t
k
)
.
Thus, in view of the definition of {
t
k
} given in (18), one has that
(58)
∥
x
k
+
1
-
ζ
∥
≤
t
k
+
1
t
k
∥
x
k
-
ζ
∥
,
which implies that ∥
x
k
+
1
-
ζ
∥
≤
t
k
+
1. Therefore, the proof by induction is complete. Since {
t
k
} converges to 0 (by Lemma 5), it follows from (50) that {
x
k
} converges to ζ and the estimate (25) holds for all k
≥
0. This completes the proof.


### 4.2.  Proof of Theorem11

Lemma 17.
Suppose thatF
(
ζ
)
=
0
,
D
F
(
ζ
) is full row rank, and D
F satisfies the majorant condition (21) on B
(
ζ
,
r
). Then, for any x
∈
B
(
ζ
,
r
), we have rank
D
F
(
x
)
=
rank
D
F
(
ζ
) and
(59)
∥
[
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
]
-
1
∥
≤
-
1
h
0,0
′
(
∥
x
-
ζ
∥
)
.Proof.
Sinceh
0,0
′
(
0
)
=
-
1, we have
(60)
∥
D
F
(
ζ
)
†
[
D
F
(
x
)
-
D
F
(
ζ
)
]
∥
≤
h
0,0
′
(
∥
x
-
ζ
∥
)
-
h
0,0
′
(
0
)
<
-
h
0,0
′
(
0
)
=
1
.
It follows from Banach lemma that [
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
]
-
1 exists and
(61)
∥
[
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
]
-
1
∥
≤
-
1
h
0,0
′
(
∥
x
-
ζ
∥
)
.
Since D
F
(
ζ
) is full row rank, we have D
F
(
ζ
)
D
F
(
ζ
)
†
=
I
R
m and
(62)
D
F
(
x
)
=
D
F
(
ζ
)
[
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
]
,
which implies that D
F
(
x
) is full row rank; that is, rank
⁡
D
F
(
x
)
=
rank
⁡
D
F
(
ζ
). The proof is complete.Proof of Theorem11.
LetF
^
:
B
(
ζ
,
r
)
→
R
m be defined by
(63)
F
^
(
x
)
=
D
F
(
ζ
)
†
F
(
x
)
,
x
∈
B
(
ζ
,
r
)
,
with residual r
^
k
=
D
F
(
ζ
)
†
r
k. Since
(64)
D
F
^
(
x
)
†
=
[
D
F
(
ζ
)
†
D
F
(
x
)
]
†
=
D
F
(
x
)
†
D
F
(
ζ
)
,
hhhhhhhhhhhhhhhhhhhhhhhh
x
∈
B
(
ζ
,
r
)
,
one has that {
x
k
} coincides with the sequence generated by inexact Newton’s method (2) for F
^. In addition, we have
(65)
D
F
^
(
ζ
)
†
=
(
D
F
(
ζ
)
†
D
F
(
ζ
)
)
†
=
D
F
(
ζ
)
†
D
F
(
ζ
)
,
and so
(66)
∥
D
F
^
(
ζ
)
†
D
F
^
(
ζ
)
∥
=
∥
D
F
(
ζ
)
†
D
F
(
ζ
)
D
F
(
ζ
)
†
F
(
ζ
)
∥
=
∥
D
F
(
ζ
)
†
F
(
ζ
)
∥
.
Because ∥
D
F
(
ζ
)
†
F
(
ζ
)
∥
=
∥
Π
ker
⁡
D
F
(
ζ
)
⊥
∥
=
1, we have
(67)
∥
D
F
^
(
ζ
)
†
∥
=
∥
D
F
^
(
ζ
)
†
D
F
^
(
ζ
)
∥
=
1
.
Therefore, by (21), we can obtain that
(68)
∥
D
F
^
(
ζ
)
†
∥
∥
D
F
^
(
x
)
-
D
F
^
(
ζ
+
τ
(
x
-
ζ
)
)
∥
=
∥
D
F
(
ζ
)
†
(
D
F
(
x
)
-
D
F
(
ζ
+
τ
(
x
-
ζ
)
)
)
∥
≤
h
λ
,
θ
′
(
∥
x
-
ζ
∥
)
-
h
λ
,
θ
′
(
τ
∥
x
-
ζ
∥
)
.
That is, F
^ satisfies the modified majorant condition (22) on B
(
ζ
,
r
). So, Theorem 8 is applicable and {
x
k
} converges to ζ follows. Note that D
F
^
(
·
)
†
F
^
(
·
)
=
D
F
(
·
)
†
F
(
·
) and F
(
·
)
=
D
F
(
·
)
D
F
(
·
)
†
F
(
·
); it follows that ζ is a zero of F.


### 4.3.  Proof of Theorem13

Lemma 18.
Suppose thatF
(
ζ
)
=
0, D
F
(
ζ
) is full row rank, and D
F satisfies the majorant condition (21) on B
(
ζ
,
r
). Then we have
(69)
∥
D
F
(
x
)
†
D
F
(
ζ
)
∥
≤
-
1
h
0,0
′
(
∥
x
-
ζ
∥
)
,
x
∈
B
(
ζ
,
r
)
.Proof.
SinceD
F
(
ζ
) is full row rank, we have D
F
(
ζ
)
D
F
(
ζ
)
†
=
I
R
m. It follows that
(70)
D
F
(
x
)
†
D
F
(
ζ
)
(
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
)
=
D
F
(
x
)
†
D
F
(
x
)
,
x
∈
B
(
ζ
,
r
)
.
By Lemma 17, I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
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
(71)
D
F
(
x
)
†
D
F
(
ζ
)
=
Π
ker
⁡
D
F
(
x
)
⊥
[
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
]
-
1
.
Therefore, Lemma 17 is applicable to conclude that
(72)
∥
D
F
(
x
)
†
D
F
(
ζ
)
∥
≤
∥
Π
ker
⁡
D
F
(
x
)
⊥
∥
∥
[
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
]
-
1
∥
≤
-
1
h
0,0
′
(
∥
x
-
ζ
∥
)
.
The proof is complete.Proof of Theorem13.
Using Lemma18, majorant condition (21), and the residual condition (32), respectively, instead of Lemma 16, modified majorant condition (22), and condition (24), one can complete the proof of Theorem 13 as the same line of proof in Theorem 8.


## 4.1. Proof of Theorem8

Lemma 16.
Suppose thatD
F satisfies the modified majorant condition on B
(
ζ
,
r
) and that ∥
ζ
-
x
∥
<
min
⁡
{
ρ
,
ξ
}, where r, ρ, and ξ are defined in (17), (12), and (11), respectively. Then, rank
D
F
(
x
)
=
rank
D
F
(
ζ
) and
(47)
∥
D
F
(
x
)
†
∥
≤
-
∥
D
F
(
ζ
)
†
∥
h
0,0
′
(
∥
x
-
ζ
∥
)
.Proof.
Sinceh
0,0
′
(
0
)
=
-
1, we have
(48)
∥
D
F
(
ζ
)
†
∥
∥
D
F
(
x
)
-
D
F
(
ζ
)
∥
≤
h
0,0
′
(
∥
x
-
ζ
∥
)
-
h
0,0
′
(
0
)
<
-
h
0,0
′
(
0
)
=
1
.
It follows from Lemma 1 that rank
⁡
D
F
(
x
)
=
rank
⁡
D
F
(
ζ
) and
(49)
∥
D
F
(
x
)
†
∥
≤
∥
D
F
(
ζ
)
†
∥
1
-
(
h
0,0
′
(
∥
x
-
ζ
∥
)
-
h
0,0
′
(
0
)
)
=
-
∥
D
F
(
ζ
)
†
∥
h
0,0
′
(
∥
x
-
ζ
∥
)
.
This completes the proof.Proof of Theorem8.
We will prove by induction that{
t
k
} is the majorizing sequence for {
x
k
}; that is,
(50)
∥
ζ
-
x
j
∥
≤
t
j
∀
j
=
0,1
,
2
,
…
.
Because t
0
=
∥
x
0
-
ζ
∥, (50) holds for j
=
0. Now, we assume that ∥
ζ
-
x
j
∥
≤
t
j for some j
=
k
∈
N. For the case j
=
k
+
1, we first notice that
(51)
x
k
+
1
-
ζ
=
x
k
-
ζ
-
D
F
(
x
k
)
†
[
F
(
x
k
)
-
F
(
ζ
)
]
+
D
F
(
x
k
)
†
r
k
=
D
F
(
x
k
)
†
[
F
(
ζ
)
-
F
(
x
k
)
-
D
F
(
x
k
)
(
ζ
-
x
k
)
]
+
D
F
(
x
k
)
†
r
k
+
[
I
R
n
-
D
F
(
x
k
)
†
D
F
(
x
k
)
]
(
x
k
-
ζ
)

=

D
F
(
x
k
)
†
∫
0
1
‍
[
D
F
(
x
k
)
-
D
F
(
ζ
+
τ
(
x
k
-
ζ
)
)
]
(
x
k
-
ζ
)
d
τ
+
D
F
(
x
k
)
†
r
k
+
[
I
R
n
-
D
F
(
x
k
)
†
D
F
(
x
k
)
]
(
x
k
-
ζ
)
.
By using the modified majorant condition (22), Lemma 16, the inductive hypothesis (50), and Lemma 2, one has that
(52)
∥
D
F
(
x
k
)
†
∫
0
1
‍
[
D
F
(
x
k
)
-
D
F
(
ζ
+
τ
(
x
k
-
ζ
)
)
]
(
x
k
-
ζ
)
d
τ
∥
≤
-
1
h
0,0
′
(
∥
x
k
-
ζ
∥
)
∫
0
1
‍
∥
D
F
(
ζ
)
†
∥
×
∥
D
F
(
x
k
)
-
D
F
(
ζ
+
τ
(
x
k
-
ζ
)
)
∥
×
∥
x
k
-
ζ
∥
d
τ
=
-
1
h
0,0
′
(
∥
x
k
-
ζ
∥
)
×
∫
0
1
‍
h
λ
,
0
′
(
∥
x
k
-
ζ
∥
)
-
h
λ
,
0
′
(
τ
∥
x
k
-
ζ
∥
)
∥
x
k
-
ζ
∥
d
τ
·
∥
x
k
-
ζ
∥
2
≤
-
1
h
0,0
′
(
t
k
)
∫
0
1
‍
h
λ
,
0
′
(
t
k
)
-
h
λ
,
0
′
(
τ
t
k
)
t
k
d
τ
·
∥
x
k
-
ζ
∥
2
=
-
1
h
0,0
′
(
t
k
)
(
t
k
h
λ
,
0
′
(
t
k
)
-
h
λ
,
0
(
t
k
)
)
∥
x
k
-
ζ
∥
2
t
k
2
.
Thanks to (24),
(53)
∥
D
F
(
x
k
)
†
r
k
∥
≤
∥
D
F
(
x
k
)
†
∥
∥
r
k
∥
≤
λ
k
∥
D
F
(
x
k
)
†
∥
∥
F
(
x
k
)
∥
.
Since
(54)
-
F
(
x
k
)
=
F
(
ζ
)
-
F
(
x
k
)
-
D
F
(
x
k
)
(
ζ
-
x
k
)
+
D
F
(
x
k
)
(
ζ
-
x
k
)
=
∫
0
1
‍
[
D
F
(
x
k
)
-
D
F
(
ζ
+
τ
(
x
k
-
ζ
)
)
]
(
x
k
-
ζ
)
d
τ
+
D
F
(
x
k
)
(
ζ
-
x
k
)
,
combining Lemma 2, Lemma 16, the modified majorant condition (22), the inductive hypothesis (50), and the condition (24), we have
(55)
λ
k
∥
D
F
(
x
k
)
†
∥
∥
F
(
x
k
)
∥
≤
λ
k
∥
D
F
(
x
k
)
†
∥
×
∫
0
1
‍
∥
D
F
(
x
k
)
-
D
F
(
ζ
+
τ
(
x
k
-
ζ
)
)
∥
×
∥
x
k
-
ζ
∥
d
τ
+
λ
k
∥
D
F
(
x
k
)
†
∥
∥
D
F
(
x
k
)
∥
∥
x
k
-
ζ
∥
≤
-
λ
h
0,0
′
(
t
k
)
(
t
k
h
λ
,
0
′
(
t
k
)
-
h
λ
,
0
(
t
k
)
)
∥
x
k
-
ζ
∥
2
t
k
2
+
λ
t
k
·
∥
x
k
-
ζ
∥
t
k
≤
λ
λ
t
k
+
h
λ
,
0
(
t
k
)
h
0,0
′
(
t
k
)
·
∥
x
k
-
ζ
∥
t
k
.
Combining (23), (52), (53), and (55), we can obtain that
(56)
∥
x
k
+
1
-
ζ
∥
≤
[
-
t
k
h
λ
,
0
′
(
t
k
)
-
h
λ
,
0
(
t
k
)
h
0,0
′
(
t
k
)
mmm
+
λ
·
λ
t
k
+
h
λ
,
0
(
t
k
)
h
0,0
′
(
t
k
)
+
θ
t
k
]
∥
x
k
-
ζ
∥
t
k
=
[
-
t
k
+
(
1
+
λ
)
(
λ
t
k
h
0,0
′
(
t
k
)
+
h
λ
,
0
(
t
k
)
h
0,0
′
(
t
k
)
)
+
θ
t
k
]
∥
x
k
-
ζ
∥
t
k
.
Note that -
1
<
h
0,0
′
(
t
)
<
0 for any t
∈
(
0
,
ρ
),
(57)
(
1
+
λ
)
(
λ
t
k
h
0,0
′
(
t
k
)
+
h
λ
,
0
(
t
k
)
h
0,0
′
(
t
k
)
)
+
θ
t
k
≤
h
λ
,
0
(
t
k
)
h
0,0
′
(
t
k
)
+
θ
t
k
≤
h
λ
,
0
(
t
k
)
-
θ
t
k
h
0,0
′
(
t
k
)
=
h
λ
,
θ
(
t
k
)
h
0,0
′
(
t
k
)
.
Thus, in view of the definition of {
t
k
} given in (18), one has that
(58)
∥
x
k
+
1
-
ζ
∥
≤
t
k
+
1
t
k
∥
x
k
-
ζ
∥
,
which implies that ∥
x
k
+
1
-
ζ
∥
≤
t
k
+
1. Therefore, the proof by induction is complete. Since {
t
k
} converges to 0 (by Lemma 5), it follows from (50) that {
x
k
} converges to ζ and the estimate (25) holds for all k
≥
0. This completes the proof.


## 4.2.  Proof of Theorem11

Lemma 17.
Suppose thatF
(
ζ
)
=
0
,
D
F
(
ζ
) is full row rank, and D
F satisfies the majorant condition (21) on B
(
ζ
,
r
). Then, for any x
∈
B
(
ζ
,
r
), we have rank
D
F
(
x
)
=
rank
D
F
(
ζ
) and
(59)
∥
[
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
]
-
1
∥
≤
-
1
h
0,0
′
(
∥
x
-
ζ
∥
)
.Proof.
Sinceh
0,0
′
(
0
)
=
-
1, we have
(60)
∥
D
F
(
ζ
)
†
[
D
F
(
x
)
-
D
F
(
ζ
)
]
∥
≤
h
0,0
′
(
∥
x
-
ζ
∥
)
-
h
0,0
′
(
0
)
<
-
h
0,0
′
(
0
)
=
1
.
It follows from Banach lemma that [
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
]
-
1 exists and
(61)
∥
[
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
]
-
1
∥
≤
-
1
h
0,0
′
(
∥
x
-
ζ
∥
)
.
Since D
F
(
ζ
) is full row rank, we have D
F
(
ζ
)
D
F
(
ζ
)
†
=
I
R
m and
(62)
D
F
(
x
)
=
D
F
(
ζ
)
[
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
]
,
which implies that D
F
(
x
) is full row rank; that is, rank
⁡
D
F
(
x
)
=
rank
⁡
D
F
(
ζ
). The proof is complete.Proof of Theorem11.
LetF
^
:
B
(
ζ
,
r
)
→
R
m be defined by
(63)
F
^
(
x
)
=
D
F
(
ζ
)
†
F
(
x
)
,
x
∈
B
(
ζ
,
r
)
,
with residual r
^
k
=
D
F
(
ζ
)
†
r
k. Since
(64)
D
F
^
(
x
)
†
=
[
D
F
(
ζ
)
†
D
F
(
x
)
]
†
=
D
F
(
x
)
†
D
F
(
ζ
)
,
hhhhhhhhhhhhhhhhhhhhhhhh
x
∈
B
(
ζ
,
r
)
,
one has that {
x
k
} coincides with the sequence generated by inexact Newton’s method (2) for F
^. In addition, we have
(65)
D
F
^
(
ζ
)
†
=
(
D
F
(
ζ
)
†
D
F
(
ζ
)
)
†
=
D
F
(
ζ
)
†
D
F
(
ζ
)
,
and so
(66)
∥
D
F
^
(
ζ
)
†
D
F
^
(
ζ
)
∥
=
∥
D
F
(
ζ
)
†
D
F
(
ζ
)
D
F
(
ζ
)
†
F
(
ζ
)
∥
=
∥
D
F
(
ζ
)
†
F
(
ζ
)
∥
.
Because ∥
D
F
(
ζ
)
†
F
(
ζ
)
∥
=
∥
Π
ker
⁡
D
F
(
ζ
)
⊥
∥
=
1, we have
(67)
∥
D
F
^
(
ζ
)
†
∥
=
∥
D
F
^
(
ζ
)
†
D
F
^
(
ζ
)
∥
=
1
.
Therefore, by (21), we can obtain that
(68)
∥
D
F
^
(
ζ
)
†
∥
∥
D
F
^
(
x
)
-
D
F
^
(
ζ
+
τ
(
x
-
ζ
)
)
∥
=
∥
D
F
(
ζ
)
†
(
D
F
(
x
)
-
D
F
(
ζ
+
τ
(
x
-
ζ
)
)
)
∥
≤
h
λ
,
θ
′
(
∥
x
-
ζ
∥
)
-
h
λ
,
θ
′
(
τ
∥
x
-
ζ
∥
)
.
That is, F
^ satisfies the modified majorant condition (22) on B
(
ζ
,
r
). So, Theorem 8 is applicable and {
x
k
} converges to ζ follows. Note that D
F
^
(
·
)
†
F
^
(
·
)
=
D
F
(
·
)
†
F
(
·
) and F
(
·
)
=
D
F
(
·
)
D
F
(
·
)
†
F
(
·
); it follows that ζ is a zero of F.


## 4.3.  Proof of Theorem13

Lemma 18.
Suppose thatF
(
ζ
)
=
0, D
F
(
ζ
) is full row rank, and D
F satisfies the majorant condition (21) on B
(
ζ
,
r
). Then we have
(69)
∥
D
F
(
x
)
†
D
F
(
ζ
)
∥
≤
-
1
h
0,0
′
(
∥
x
-
ζ
∥
)
,
x
∈
B
(
ζ
,
r
)
.Proof.
SinceD
F
(
ζ
) is full row rank, we have D
F
(
ζ
)
D
F
(
ζ
)
†
=
I
R
m. It follows that
(70)
D
F
(
x
)
†
D
F
(
ζ
)
(
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
)
=
D
F
(
x
)
†
D
F
(
x
)
,
x
∈
B
(
ζ
,
r
)
.
By Lemma 17, I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
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
(71)
D
F
(
x
)
†
D
F
(
ζ
)
=
Π
ker
⁡
D
F
(
x
)
⊥
[
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
]
-
1
.
Therefore, Lemma 17 is applicable to conclude that
(72)
∥
D
F
(
x
)
†
D
F
(
ζ
)
∥
≤
∥
Π
ker
⁡
D
F
(
x
)
⊥
∥
∥
[
I
R
n
-
D
F
(
ζ
)
†
(
D
F
(
ζ
)
-
D
F
(
x
)
)
]
-
1
∥
≤
-
1
h
0,0
′
(
∥
x
-
ζ
∥
)
.
The proof is complete.Proof of Theorem13.
Using Lemma18, majorant condition (21), and the residual condition (32), respectively, instead of Lemma 16, modified majorant condition (22), and condition (24), one can complete the proof of Theorem 13 as the same line of proof in Theorem 8.



---

*Source: 498016-2014-08-28.xml*