# Global Convergence of Schubert’s Method for Solving Sparse Nonlinear Equations

Authors: Huiping Cao
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Schubert’s method is an extension of Broyden’s method for solving sparse nonlinear equations, which can preserve the zero-nonzero structure defined by the sparse Jacobian matrix and can retain many good properties of Broyden’s method. In particular, Schubert’s method has been proved to be locally andq-superlinearly convergent. In this paper, we globalize Schubert’s method by using a nonmonotone line search. Under appropriate conditions, we show that the proposed algorithm converges globally and superlinearly. Some preliminary numerical experiments are presented, which demonstrate that our algorithm is effective for large-scale problems.


---

## Body

## 1. Introduction

In this paper, we consider the quasi-Newton method [1] for solving the general nonlinear equation
(1)
F
(
x
)
=
0
,
where the function F
:
R
n
→
R
n is continuously differentiable. The ordinary quasi-Newton method for solving (1) generates a sequence {
x
k
} by the following iterative scheme:
(2)
x
k
+
1
=
x
k
+
d
k
,
where the quasi-Newton direction d
k is obtained by solving the system of linear equations
(3)
B
k
d
+
F
(
x
k
)
=
0
.
Here the matrix B
k is an approximation to the Jacobian matrix of F at x
k which usually satisfies the quasi-Newton condition (i.e., the secant condition):
(4)
B
k
+
1
s
k
=
y
k
,
where s
k
=
x
k
+
1
-
x
k and y
k
=
F
(
x
k
+
1
)
-
F
(
x
k
). The matrix B
k can be updated by different quasi-Newton update formulae. However, quasi-Newton method is not applicable for solving large-scale problems due to the density of B
k. Fortunately, a large-scale problem usually has the property of sparsity, and then it is natural to extend some known quasi-Newton methods based on this property. Early in 1970, Schubert [2] modified Broyden’s method and proposed a sparse Broyden’s method, that is, the Schubert’s method [3] with B
k defined in the following way:
(5)
B
k
+
1
=
B
k
+
∑
i
=
1
,
s
(
i
)
k
≠
0
n
‍
e
i
e
i
T
(
y
k
-
B
k
s
k
)
s
(
i
)
k
T
s
(
i
)
k
T
s
(
i
)
k
,
where
(6)
s
(
i
)
k
(
j
)
=
{
0
,
if
(
i
,
j
)
∈
E
,
s
k
(
j
)
,
if
(
i
,
j
)
∈
J
,
where E and J are the sparsity patterns of the Jacobian matrix F
′
(
x
) and e
i denotes the ith column of the n
×
n identity matrix. It has been proved by Broyden [4] that the Schubert’s method is locally convergent when the Jacobian satisfies a Lipschitz condition. Lam [5] further showed the local and superlinear convergence of Schubert’s method in the special case when s
(
i
)
k
≠
0, i
=
1,2
,
…
,
n at each iteration. As an improvement, Marwil considered the following updated formula:
(7)
B
k
+
1
=
B
k
+
∑
i
=
1
n
‍
(
s
(
i
)
k
T
s
(
i
)
k
)
+
e
i
T
(
y
k
-
B
k
s
k
)
e
i
s
(
i
)
k
T
,
where, for a scalar α
∈
R,
(8)
α
+
=
{
α
-
1
,
if
α
≠
0
,
0
,
if
α
=
0
.
Marwil established stronger local and superlinear convergence, which contains the results in [5] as a special case.Note that the updated formula (7) is not symmetric; therefore, its use is restricted to problems where the symmetry of the updated matrix is not important. The sparse and symmetric quasi-Newton update has attracted much attention [6–8]. Toint [6] and Fletcher [8] previously proposed symmetric updates which met the sparsity and secant conditions simultaneously. Yamashita [9] proposed a new sparse quasi-Newton update, called Matrix Completion Quasi-Newton (MCQN) [10], which exploited the sparsity of the Hessian and guaranteed positive definiteness.So far, most studies in the convergence of sparse quasi-Newton methods have focused on their local behaviors. Seldom studies are concerned with the global convergence of those methods. It is a relatively more difficult research topic than optimization. To the author’s knowledge, the main work related to the general global convergence of sparse quasi-Newton methods is based on the work [10–12]. The purpose of this paper is to study the global and superlinear convergence of the Schubert’s method.The remainder of this paper is organized as follows. In Section2, we review some properties of Schubert’s method. In Section 3, by using a nonmonotone line search [13], we globalize the Schubert’s method and prove its global and superlinear convergence under appropriate conditions. In particular, we will show that after finitely many iterations, the unit step length will be accepted. In Section 4, some preliminary numerical results are presented. Finally, we provide some remarks in Section 5.


## 2. Schubert’s Update

In this section, we present some useful properties of the Schubert’s update. For the sake of convenience, we introduce some notations.(1)
The subspaceZ
i
⊂
R
n that identifies the sparsity structure of the ith row of Jacobian matrix F
′
(
x
) is defined as Z
i
=
{
v
∈
R
n
∣
v
T
F
′
(
x
)
e
i
=
0
,
∀
x
∈
D
};
(2)
Z
⊂
R
n
×
R
n denotes the sparsity structure of the Jacobian matrix F
′
(
x
) and it is defined as Z
=
{
A
∈
R
n
×
n
∣
A
T
e
i
∈
Z
i
,
i
=
1,2
,
…
,
n
};
(3)
the projection operatorsS
i, i
=
1,2
,
…
,
n project vectors onto the subspaces Z
i, i
=
1,2
,
…
,
n, which particularly makes S
i
s
k
=
s
(
i
)
k;
(4)
Q
(
y
,
s
)
=
{
B
∈
R
n
×
n
∣
B
s
=
y
}.Schubert’s update (7) is the unique solution to the following minimization problem [3]:
(9)
min
⁡
{
∥
B
^
-
B
∥
F
:
B
^
∈
Q
(
y
,
s
)
∩
Z
}
.
Specifically, the following inequality [3] holds for any J
∈
Z, y
,
s
∈
R
n with s
≠
0:
(10)
∥
B
k
+
1
-
J
∥
F
2
≤
∥
B
k
-
J
∥
F
2
-
∥
(
B
k
-
J
)
s
k
∥
2
2
∥
s
k
∥
2
2
+
∑
i
=
1
n
‍
(
s
(
i
)
k
T
s
(
i
)
k
)
+
(
e
i
T
(
y
k
-
J
s
k
)
)
2
.The following theorem states the local and superlinear convergence of Schubert’s method, which has been proved by Marwil [3].Theorem 1.
Suppose thatF
:
R
n
→
R
n satisfies the following conditions. (1)
F is continuously differentiable in an open convex set D
0.
(2)
There exists anx
*
∈
D
0 such that F
(
x
*
)
=
0 and F
′
(
x
*
) is nonsingular.
(3)
There existsK
=
(
k
1
,
k
2
,
…
,
k
n
)
T
∈
R
n with k
i
≥
0 for i
=
1,2
,
…
,
n, such that
(11)
∥
e
i
T
(
F
′
(
x
)
-
F
′
(
y
)
)
∥
2
≤
k
i
∥
x
-
y
∥
2
,
∀
x
,
y
∈
D
0
.Then there exist constants ϵ, δ
>
0 and a nonsingular matrix B
0 such that if x
0
∈
D
0 satisfies ∥
x
0
-
x
*
∥
2
<
ϵ and ∥
B
0
-
F
′
(
x
*
)
∥
F
<
δ, then (i)
Schubert’s method generates{
B
k
} with B
k nonsingular for all k
≥
0;
(ii)
the sequence{
x
k
} converges to x
*;
(iii)
the convergence is superlinear.It is noticed that the matrixB
k
+
1 determined by (7) may be singular even if B
k is nonsingular. To overcome such a difficulty, Marwil [3] proposed a nonsingular schubert’s method by using
(12)
B
¯
=
B
+
∑
i
=
1
n
‍
θ
i
(
s
(
i
)
T
s
(
i
)
)
+
e
i
T
(
y
-
B
s
)
e
i
s
(
i
)
T
.
Here, we have omitted the subscript k and used B
¯ to represent B
k
+
1 and B to represent B
k. The parameters θ
i are chosen so that B
¯ is nonsingular when B is nonsingular and the details are given below.SetC
0
=
B and define for i
=
1,2
,
…
,
n as follows:
(13)
C
i
=
C
0
+
∑
j
=
1
i
‍
θ
j
(
s
(
j
)
T
s
(
j
)
)
+
e
j
T
(
y
-
B
s
)
e
j
s
(
j
)
T
=
C
i
-
1
+
θ
i
(
s
(
i
)
T
s
(
i
)
)
+
e
i
T
(
y
-
B
s
)
e
i
s
(
i
)
T
.
Note that e
i
T
C
0
=
e
i
T
C
1
=
⋯
=
e
i
T
C
i
-
1, and then
(14)
C
i
=
C
i
-
1
+
θ
i
(
s
(
i
)
T
s
(
i
)
)
+
e
i
T
(
y
-
C
i
-
1
s
)
e
i
s
(
i
)
T
.
For a scalar α
∈
(
0,1
), θ
i can be chosen to satisfy
(15)
|
det
⁡
C
i
|
≥
α
n
|
det
⁡
C
i
-
1
|
,
θ
i
∈
[
1
-
α
n
1
+
α
n
,
1
]
.
Therefore, |
det
⁡
(
B
¯
)
|
≥
α
|
det
⁡
B
|, and θ
i can be chosen so that
(16)
B
¯
is
nonsigular
,
|
θ
i
-
1
|
≤
θ
^
<
1
.The dependence ofθ
i on the iteration k is suppressed, but θ
^ is independent of k [3].


## 3. The Algorithm

In this section, we will globalize Schubert’s method. To this end, we introduce a derivative-free line search proposed by Li and Fukushima [13] to determine a step length α
k.Algorithm 2.
Given constantsσ
1
>
0 and β
∈
(
0,1
). Let α
k
=
β
i
k, where i
k is the smallest nonnegative integer such that
(17)
∥
F
(
x
k
+
β
i
k
d
k
)
∥
≤
∥
F
(
x
k
)
∥
-
σ
1
∥
β
i
k
d
k
∥
2
+
ε
k
∥
F
(
x
k
)
∥
,
and {
ε
k
} is a given positive sequence satisfying
(18)
∑
k
=
0
∞
‍
ε
k
≤
ε
<
∞
.
It is not difficult to see that Algorithm2 is well defined. Moreover, for each k, we have
(19)
∥
F
(
x
k
+
α
k
d
k
)
∥
≤
(
1
+
ε
k
)
∥
F
(
x
k
)
∥
.
By using Algorithm 2, we give our algorithm as follows.Algorithm 3.
Consider the following.
Step
0. Given constants ρ
,
β
,
θ
¯
∈
(
0,1
), σ
1
,
σ
2
>
0, select a positive sequence {
ε
k
} satisfying (18). Then choose an initial point x
0
∈
R
n and a nonsingular matrix B
0
∈
R
n
×
n. Let k
:
=
0.
Step
1. Stop if F
(
x
k
)
=
0. Otherwise, solve the following system of linear equations
(20)
B
k
d
+
F
(
x
k
)
=
0
to get d
k.
Step
2. If
(21)
∥
F
(
x
k
+
d
k
)
∥
≤
ρ
∥
F
(
x
k
)
∥
-
σ
2
∥
d
k
∥
2
,
then let α
k
:
=
1 and go to Step 4. Else, go to Step 3.
Step
3. Let α
k be determined by Algorithm 2.
Step
4. Set x
k
+
1
:
=
x
k
+
α
k
d
k.
Step
5. Compute B
k
+
1 by (12).
Step
6. Set k
:
=
k
+
1. Go to Step 1.
We then show some useful properties of Algorithm3.Lemma 4.
Let the level setΩ
=
{
x
∈
R
n
∣
∥
F
(
x
)
∥
≤
e
ε
∥
F
(
x
0
)
∥
} be bounded and let {
x
k
} be generated by Algorithm 3. Then {
x
k
} is contained in Ω. Moreover, it holds that
(22)
∑
k
=
0
∞
‍
∥
s
k
∥
2
<
∞
.Proof.
By the line search (17), we have for any k
(23)
∥
F
(
x
k
+
1
)
∥
≤
(
1
+
ε
k
)
∥
F
(
x
k
)
∥
1
⋮
≤
∥
F
(
x
0
)
∥
[
∏
j
=
0
k
(
1
+
ε
j
)
]
≤
∥
F
(
x
0
)
∥
[
1
k
+
1
∑
j
=
0
k
‍
(
1
+
ε
j
)
]
k
+
1
=
∥
F
(
x
0
)
∥
[
1
+
1
k
+
1
∑
j
=
0
k
‍
ε
j
]
k
+
1
≤
∥
F
(
x
0
)
∥
[
(
1
+
ε
k
+
1
)
(
k
+
1
)
/
ε
]
ε
≤
e
ε
∥
F
(
x
0
)
∥
.
This implies that the sequence {
x
k
} generated by Algorithm 3 is contained in Ω and the sequence {
∥
F
(
x
k
)
∥
} is bounded. Moreover, combined with (17) and (21), we can get for each k
(24)
σ
0
∥
s
k
∥
2
=
σ
0
∥
x
k
+
1
-
x
k
∥
2
≤
∥
F
(
x
k
)
∥
-
∥
F
(
x
k
+
1
)
∥
+
ε
k
∥
F
k
∥
,
where σ
0
=
min
⁡
{
σ
1
,
σ
2
}. Making summation on both sides for k from 0 to ∞, we obtain (22).Similar to Lemma 2.4 in [13], we have the following result.Lemma 5.
Let the level setΩ be bounded and let {
x
k
} be generated by Algorithm 3. Then the sequence {
∥
F
(
x
k
)
∥
} is convergent.In order to establish the global convergence of Algorithm3, we need the following assumptions.Assumption 6.
(i) The level setΩ defined in Lemma 4 is bounded.
(ii)F
(
x
) is continuously differentiable in an open set D
⊆
Ω, and there exists an x
*
∈
Ω such that F
(
x
*
)
=
0 and F
′
(
x
*
) is nonsingular.
(iii)F
′
(
x
) is Lipschitz continuous on Ω; that is, there exists an L
>
0 such that
(25)
∥
F
′
(
x
)
-
F
′
(
y
)
∥
≤
L
∥
x
-
y
∥
,
∀
x
,
y
∈
Ω
.
(iv)F
′
(
x
) is nonsingular for any x
∈
Ω.Assumption6 (iv) is the same as that in [13], which is not as strong as the assumption adopted in [14], where the uniform nonsingularity of F
′
(
x
) is assumed.We first introduce some notations. Define(26)
A
k
+
1
=
∫
0
1
‍
F
′
(
x
k
+
t
s
k
)
d
t
,
and then we have y
k
=
A
k
+
1
s
k. Let
(27)
η
k
=
∥
∑
i
=
1
n
‍
(
s
(
i
)
k
T
s
(
i
)
k
)
+
e
i
T
(
y
k
-
B
k
s
k
)
e
i
s
(
i
)
k
T
∥
,
δ
k
=
∥
y
k
-
B
k
s
k
∥
∥
s
k
∥
=
∥
(
A
k
+
1
-
B
k
)
s
k
∥
∥
s
k
∥
=
1
∥
s
k
∥
∥
∑
i
=
1
n
‍
(
s
(
i
)
k
T
s
(
i
)
k
)
+
e
i
T
(
y
k
-
B
k
s
k
)
e
i
s
(
i
)
k
T
s
k
∥
.The following lemma is an extension of Lemma 2.5 in [13].Lemma 7.
Let the sequence{
x
k
} be generated by Algorithm 3. Suppose that the conditions (i)–(iii) in Assumption 6 hold. If
(28)
∑
k
=
0
∞
‍
∥
s
k
∥
2
<
∞
,
then one has
(29)
lim
⁡
l
→
∞
1
l
∑
k
=
0
l
-
1
‍
δ
k
2
=
0
.
In particular, there is a subsequence of {
δ
k
} tending to zero. If
(30)
∑
k
=
0
∞
‍
∥
s
k
∥
<
∞
,
then one has
(31)
∑
k
=
0
∞
‍
δ
k
2
<
∞
.
In particular, the whole sequence {
δ
k
} converges to zero.Proof.
By the Lipschitz continuity ofF
′, we have
(32)
∥
A
k
+
1
-
A
k
∥
≤
1
2
L
(
∥
s
k
∥
+
∥
s
k
-
1
∥
)
.
Denote
(33)
a
k
=
∥
B
k
-
A
k
∥
F
,
b
k
=
∥
A
k
+
1
-
A
k
∥
F
.
According to the updated (12), we have
(34)
e
i
T
B
k
+
1
=
e
i
T
B
k
+
(
s
(
i
)
k
T
s
(
i
)
k
)
+
θ
k
i
e
i
T
(
y
k
-
B
k
s
k
)
s
(
i
)
k
T
.
Subtracting e
i
T
A
k
+
1 from both sides of the above equality gives
(35)
e
i
T
(
B
k
+
1
-
A
k
+
1
)
=
e
i
T
(
B
k
-
A
k
+
1
)
+
θ
k
i
e
i
T
(
s
(
i
)
k
T
s
(
i
)
k
)
+
(
y
k
-
B
k
s
k
)
s
(
i
)
k
T
=
e
i
T
(
B
k
-
A
k
+
1
)
(
I
-
θ
k
i
(
s
(
i
)
k
T
s
(
i
)
k
)
+
s
(
i
)
k
s
(
i
)
k
T
)
.
Taking norms yields
(36)
∥
e
i
T
(
B
k
+
1
-
A
k
+
1
)
∥
2
=
∥
e
i
T
(
B
k
-
A
k
+
1
)
(
I
-
θ
k
i
(
s
(
i
)
k
T
s
(
i
)
k
)
+
s
(
i
)
k
s
(
i
)
k
T
)
∥
2
=
∥
e
i
T
(
B
k
-
A
k
+
1
)
∥
2
11
-
θ
k
i
(
2
-
θ
k
i
)
(
s
(
i
)
k
T
s
(
i
)
k
)
+
∥
e
i
T
(
B
k
-
A
k
+
1
)
s
(
i
)
k
s
(
i
)
k
T
∥
2
.
Making summation on both sides, i
=
1
,
…
,
n, yields
(37)
∥
B
k
+
1
-
A
k
+
1
∥
F
2
=
∑
i
=
1
n
‍
∥
e
i
T
(
B
k
+
1
-
A
k
+
1
)
∥
2
=
∑
i
=
1
n
‍
∥
e
i
T
(
B
k
-
A
k
+
1
)
∥
2
11
-
∑
i
=
1
n
‍
θ
k
i
(
2
-
θ
k
i
)
(
s
(
i
)
k
T
s
(
i
)
k
)
+
11
×
∥
e
i
T
(
B
k
-
A
k
+
1
)
s
(
i
)
k
s
(
i
)
k
T
∥
2
=
∥
(
B
k
-
A
k
+
1
)
∥
F
2
11
-
∥
∑
i
=
1
n
‍
θ
k
i
(
2
-
θ
k
i
)
e
i
e
i
T
(
s
(
i
)
k
T
s
(
i
)
k
)
+
111111
×
(
y
k
-
B
k
s
k
)
s
(
i
)
k
T
∑
i
=
1
n
‍
θ
k
i
(
2
-
θ
k
i
)
e
i
e
i
T
(
s
(
i
)
k
T
s
(
i
)
k
)
+
∥
2
≤
∥
(
B
k
-
A
k
+
1
)
∥
F
2
-
(
1
-
θ
^
2
)
11
×
∥
∑
i
=
1
n
‍
e
i
e
i
T
(
s
(
i
)
k
T
s
(
i
)
k
)
+
(
y
k
-
B
k
s
k
)
s
(
i
)
k
T
∥
2
=
∥
(
B
k
-
A
k
+
1
)
∥
F
2
-
(
1
-
θ
^
2
)
η
k
2
.
Then it follows that
(38)
(
1
-
θ
^
2
)
η
k
2
≤
∥
B
k
-
A
k
+
1
∥
F
2
-
a
k
+
1
2
≤
(
a
k
+
b
k
)
2
-
a
k
+
1
2
=
a
k
2
-
a
k
+
1
2
+
2
a
k
b
k
+
b
k
2
,
a
k
+
1
2
≤
(
a
k
+
b
k
)
2
-
(
1
-
θ
^
2
)
η
k
2
.
According to Lemma 2.5 of [13], we get
(39)
lim
⁡
l
→
∞
1
l
∑
k
=
0
l
-
1
‍
η
k
2
=
0
,
∑
k
=
0
∞
‍
η
k
2
<
∞
.
Moreover, for each k we have
(40)
δ
k
=
1
∥
s
k
∥
∥
∑
i
=
1
n
‍
(
s
(
i
)
k
T
s
(
i
)
k
)
+
e
i
T
(
y
k
-
B
k
s
k
)
e
i
s
(
i
)
k
T
s
k
∥
≤
∥
∑
i
=
1
n
‍
(
s
(
i
)
k
T
s
(
i
)
k
)
+
e
i
T
(
y
k
-
B
k
s
k
)
e
i
s
(
i
)
k
T
∥
=
η
k
.
This completes the proof.According to Algorithm3, we have the following lemma.Lemma 8.
Let{
x
k
} be generated by Algorithm 3. If there are finitely many k for which α
k is determined by (21), then one has
(41)
lim
⁡
t
→
∞
1
t
∑
k
=
0
t
‍
∑
i
=
1
m
‍
δ
k
2
=
0
.
In particular, there is an infinity index set K such that, for each i
=
1,2
,
…
,
m, the subsequence {
δ
k
}
k
∈
K converges to zero.Proof.
Since there are finitely manyk for which α
k is determined by (21), we can know that there exists an index k
^ such that, for k
>
k
^,
(42)
∥
F
(
x
k
+
ρ
i
d
k
)
∥
≤
∥
F
(
x
k
)
∥
-
σ
1
∥
ρ
i
d
k
∥
2
+
ϵ
k
∥
F
(
x
k
)
∥
.
This implies
(43)
∑
k
=
k
^
∞
‍
∥
s
k
∥
2
=
∑
k
=
k
^
∞
‍
∥
x
k
+
1
-
x
k
∥
2
=
∑
k
=
k
^
∞
‍
∥
α
k
d
k
∥
2
<
∞
.
According to Lemma 7, we can easily prove the result.Lemma 9.
Suppose that∑
k
=
1
∞
‍
∥
s
k
∥
2
<
∞ and that there is an accumulation point x
* of {
x
k
}
k
∈
K at which F
′
(
x
*
) is nonsingular. Then there exists a constant M
1
>
0 such that the following inequality holds for all k
∈
K sufficiently large:
(44)
∥
d
k
∥
≤
M
1
∥
F
(
x
k
)
∥
.Proof.
Without loss of generality, we suppose{
x
k
}
K
→
x
*. Since ∑
k
=
1
∞
‍
∥
s
k
∥
2
<
∞, it is clear that when k
∈
K is sufficiently large, A
k
+
1 is nonsingular. Moreover, there is a constant C
1
>
0 such that the inequality ∥
A
k
+
1
-
1
∥
≤
C
1 holds for all k
∈
K sufficiently large. It then follows from Lemma 8 that {
δ
k
}
K
→
0. Therefore, there exists an index N
>
0 such that the inequality δ
k
≤
1
/
(
2
C
1
) holds for all k
∈
K with k
≥
N. Consequently, we get from the definition of δ
k that for all k
∈
K with k
>
N sufficiently large
(45)
∥
d
k
∥
≤
∥
A
k
+
1
-
1
∥
(
∥
A
k
+
1
d
k
+
g
(
x
k
)
∥
+
∥
g
(
x
k
)
∥
)
≤
C
1
(
∥
g
(
x
k
)
∥
+
δ
k
∥
d
k
∥
)
≤
C
1
(
∥
g
(
x
k
)
∥
+
1
2
C
1
∥
d
k
∥
)
≤
C
1
∥
g
(
x
k
)
∥
+
1
2
∥
d
k
∥
.
The last inequality implies (44) with M
1
=
2
C
1.We show the global convergence of Algorithm3 in the following section.Theorem 10.
Let Assumption6 hold and let index set K be specified by Lemma 8. Then the sequence {
x
k
} converges to the unique solution x
* of (1).Proof.
We first verify(46)
lim
⁡
k
→
∞
inf
⁡
∥
F
(
x
k
)
∥
=
0
.
If there are infinitely many k for which α
k is determined by (21), then ∥
F
(
x
k
+
1
)
∥
≤
ρ
∥
F
(
x
k
)
∥ holds for infinitely many k. Let I be the index set for which (21) holds and let i
k be the number of index j, where j
≤
k and j
∈
I. Then we can know that i
k
→
∞, when k
→
∞. For each k
∉
I, we have ∥
F
(
x
k
+
1
)
∥
≤
(
1
+
ϵ
k
)
∥
F
(
x
k
)
∥, and then for all sufficiently large k we have
(47)
∥
F
(
x
k
+
1
)
∥
≤
(
ρ
)
i
k
+
1
∏
i
=
0
k
‍
(
1
+
ϵ
i
)
∥
F
(
x
0
)
∥
≤
ρ
i
k
+
1
e
ϵ
∥
F
(
x
0
)
∥
,
where ρ
∈
(
0,1
). This implies liminf
⁡
k
→
∞
∥
F
(
x
k
)
∥
=
0, and hence the conclusion is true.
If there are finitely manyk for which α
k is determined by (21), by Lemma 8, there exists a subsequence {
δ
k
}
k
∈
K that converges to zero. Similar to the proof of Lemma 9, it is not difficult to show that (44) holds for all k
∈
K
¯ sufficiently large, where K
¯ denotes the index set of k
>
k
^, k
∈
K. In particular, the subsequence {
d
k
}
K
¯ is bounded. Without loss of generality, we suppose that {
d
k
}
K
¯ converges to some d
*.
Denoteα
¯
=
limsup
⁡
k
→
∞
α
k. It is clear that α
¯
≥
0. If α
¯
>
0, then d
*
=
0, and hence it follows from (20) that F
(
x
*
)
=
0. Suppose α
¯
=
0, or equivalently lim
⁡
k
→
∞
α
k
=
0. By the line search rule, when k
∈
K
¯ is sufficiently large, α
k
<
1 and hence
(48)
∥
F
(
x
k
+
ρ
-
1
α
k
d
k
)
∥
-
∥
F
(
x
k
)
∥
>
-
σ
1
∥
ρ
-
1
α
k
d
k
∥
2
.
Multiplying both sides by (
∥
F
(
x
k
+
ρ
-
1
α
k
d
k
)
∥
+
∥
F
(
x
k
)
∥
)
/
(
ρ
-
1
α
k
) and then taking limit as k
→
∞ with k
∈
K
¯, we obtain
(49)
F
(
x
*
)
T
F
′
(
x
*
)
d
*
≥
0
.
On the other hand, taking the limit in (20) as k
→
∞ with k
∈
K
¯ yields
(50)
F
′
(
x
*
)
d
*
+
F
(
x
*
)
=
0
.
This together with (49) implies F
(
x
*
)
=
0.In the latter part of this section, we give the superlinear convergence of Algorithm3.Theorem 11.
Let the conditions in Theorem10 hold. Then there exist a constant δ
>
0 and an index k
¯ such that α
k
=
1 whenever δ
k
≤
δ and k
≥
k
¯, the inequality
(51)
∥
F
(
x
k
+
d
k
)
∥
≤
ρ
∥
F
(
x
k
)
∥
-
σ
1
∥
d
k
∥
2
<
ρ
∥
F
(
x
k
)
∥
holds for all k
≥
k
¯ and δ
k
≤
δ.Proof.
By Theorem10, {
x
k
} converges to the solution of (1), say, x
*, and there exists a constant C
2
>
0 such that ∥
A
k
+
1
-
1
∥
≤
C
2 for all k sufficiently large. Similar to the proof of Lemma 9, when k is large enough we can show that
(52)
∥
d
k
∥
≤
M
2
∥
F
(
x
k
)
∥
.
And from (20) we have
(53)
A
k
+
1
(
x
k
+
d
k
-
x
*
)
=
A
k
+
1
(
x
k
-
x
*
)
+
(
A
k
+
1
-
B
k
)
d
k
-
F
(
x
k
)
=
(
A
k
+
1
-
F
′
(
x
*
)
)
(
x
k
-
x
*
)
+
(
A
k
+
1
-
B
k
)
d
k
11111
-
F
(
x
k
)
+
F
(
x
*
)
+
F
′
(
x
*
)
(
x
k
-
x
*
)
,
and this implies
(54)
∥
x
k
+
d
k
-
x
*
∥
≤
∥
A
k
+
1
-
1
∥
×
(
∥
A
k
+
1
-
F
′
(
x
*
)
∥
11
111111
×
∥
x
k
-
x
*
∥
+
∥
(
A
k
+
1
-
B
k
)
d
k
∥
11
111111
+
∥
F
′
F
(
x
k
)
-
F
(
x
*
)
11111111111
+
F
′
(
x
*
)
(
x
k
-
x
*
)
∥
)
≤
C
2
(
o
∥
x
k
-
x
*
∥
2
+
δ
k
∥
d
k
∥
)
≤
C
2
(
o
∥
x
k
-
x
*
∥
111111
+
M
2
δ
k
∥
F
(
x
k
)
-
F
(
x
*
)
∥
)
≤
C
2
(
o
∥
x
k
-
x
*
∥
+
M
2
M
δ
k
∥
x
k
-
x
*
∥
)
,
where M is an upper bound of F
′
(
x
) in Ω. The second and third inequalities follow from the definition of δ
k and (52), respectively. It then follows that
(55)
∥
F
(
x
k
+
d
k
)
∥
=
∥
F
(
x
k
+
d
k
)
-
F
(
x
*
)
∥
≤
M
∥
x
k
+
d
k
-
x
*
∥
≤
M
C
2
(
o
∥
x
k
-
x
*
∥
+
M
2
M
δ
k
∥
x
k
-
x
*
∥
)
.
On the other hand, by the nonsingularity of F
′
(
x
*
) and the fact that x
k
→
x
*, there is a constant m
>
0 such that
(56)
∥
F
(
x
k
)
∥
=
∥
F
(
x
k
)
-
F
(
x
*
)
∥
≥
m
∥
x
k
-
x
*
∥
holds for all k sufficiently large. Therefore, we deduce from (52) and (56) that when δ
k
≤
δ
′
(57)
∥
F
(
x
k
+
1
)
∥
-
ρ
∥
F
(
x
k
)
∥
+
σ
2
∥
d
k
∥
2
≤
M
C
2
(
o
∥
x
k
-
x
*
∥
+
M
2
M
δ
k
∥
x
k
-
x
*
∥
)
11
-
ρ
m
∥
x
k
-
x
*
∥
+
σ
2
M
2
2
∥
F
(
x
k
)
∥
2
≤
(
M
2
C
2
M
2
δ
k
-
ρ
m
)
∥
x
k
-
x
*
∥
11
+
o
(
∥
x
k
-
x
*
∥
)
+
σ
2
M
2
2
M
2
∥
x
k
-
x
*
∥
2
≤
-
(
ρ
m
-
M
2
C
2
M
2
δ
k
)
∥
x
k
-
x
*
∥
11
+
o
(
∥
x
k
-
x
*
∥
)
.
Letδ
=
min
⁡
{
δ
′
,
(
1
/
2
)
ρ
m
(
M
2
C
2
M
2
)
-
1
}. Then we know that when δ
k
<
δ, (51) holds for all k sufficient large.The following theorem establishes the superlinear convergence of Algorithm3.Theorem 12.
Let the conditions in Theorem10 hold. Then the sequence {
x
k
} generated by Algorithm 3 converges to the unique solution x
* of (1) superlinearly.Proof.
By Theorem11, it suffices to show {
δ
k
}
→
0 as k
→
∞.
Letδ and k
¯ be as specified by Theorem 11. It follows from Lemma 8 that there is an index k
~ such that the following inequality holds for all k
≥
k
~:
(58)
1
k
∑
j
=
0
k
-
1
‍
δ
j
2
≤
1
2
δ
2
.
This shows that, for any k
≥
k
~, there are at least ⌈
k
/
2
⌉ many indices j
≤
k such that δ
j
≤
δ. Let k
′
=
max
⁡
{
k
¯
,
k
~
}. By Theorem 11, for any k
≥
2
k
′, there are at least ⌈
k
/
2
⌉
-
k
′ many indices j
≤
k such that α
j
=
1 and
(59)
∥
F
(
x
j
+
1
)
∥
=
∥
F
(
x
j
+
d
k
)
∥
≤
ρ
∥
F
(
x
j
)
∥
.
Let J
k be the set of indices for which (21) holds and let j
k be the number of elements in J
k. Then j
k
≥
(
k
/
2
)
-
k
′
-
1. On the other hand, for each j
∈
J
k, we have
(60)
∥
F
(
x
j
+
1
)
∥
≤
(
1
+
ε
k
)
∥
F
(
x
j
)
∥
.
Multiplying inequalities (21) with j
∈
J
k and (60) with j
∉
J
k, we can obtain for any k
>
2
k
′
(61)
∥
F
(
x
k
+
1
)
∥
≤
(
ρ
)
j
k
∥
F
(
x
k
′
)
∥
[
∏
j
=
k
′
k
(
1
+
ε
j
)
]
≤
∥
F
(
x
k
′
)
∥
ρ
(
1
/
2
)
k
-
k
′
-
1
e
ε
,
or equivalently
(62)
∥
F
(
x
k
+
1
)
∥
≤
∥
F
(
x
k
′
)
∥
ρ
(
1
/
2
)
k
-
k
′
-
1
e
ε
.
So, we have
(63)
∑
k
=
0
∞
‍
∥
F
(
x
k
)
∥
<
∞
.
This together with (56) implies
(64)
∑
k
=
0
∞
‍
∥
s
k
∥
<
∞
.
It then follows from Lemma 7 that {
δ
k
}
→
0 as k
→
∞. The proof is completed.


## 4. Numerical Experiments

In this section, we will present some numerical results to show the efficiency of Algorithm3 for a class of sparse nonlinear equations.In each experiment, we employ the following termination criterion:(65)
∥
F
(
x
k
)
∥
2
≤
1
0
-
5
.
The parameters in Algorithm 3 are specified as follows:
(66)
ρ
=
0.9
,
σ
1
=
σ
2
=
0.001
,
β
=
0.45
,
η
k
=
1
(
k
+
1
)
2
,see [13].The numerical experiments are done by using MATLAB version 7.10 on a Core (TM) 2 PC with Windows XP. The details of the problems are given as follows, wherex
0 denotes the initial point.Problem 1 (Broyden tridiagonal function [15]).
The elements ofF
(
x
) are
(67)
F
1
(
x
)
=
-
(
3
-
0.5
x
1
)
x
1
+
2
x
2
-
1
,
F
i
(
x
)
=
x
i
-
1
-
(
3
-
0.5
x
i
)
x
i
+
2
x
i
+
1
-
1
,
11111111111
i
=
2,3
,
…
,
n
-
1
,
F
n
(
x
)
=
x
n
-
1
-
(
3
-
0.5
x
n
)
x
n
-
1
,
x
0
=
(
-
3
,
-
3
,
…
,
-
3
)
T
.Problem 2 (Trigexp function [16]).
The elements ofF
(
x
) are
(68)
F
1
(
x
)
=
3
x
1
2
+
2
x
2
-
5
+
sin
(
x
1
-
x
2
)
sin
(
x
1
+
x
2
)
,
F
i
(
x
)
=
3
x
i
2
+
2
x
i
+
1
-
5
+
sin
⁡
(
x
i
-
x
i
+
1
)
×
sin
(
x
i
+
x
i
+
1
)
+
4
x
i
-
x
i
-
1
exp
⁡
⁡
(
x
i
-
1
)
-
x
i
-
3
,
1111111111
i
=
2,3
,
…
,
n
-
1
,
F
n
(
x
)
=
4
x
n
-
x
n
-
1
exp
⁡
(
x
n
-
1
-
x
n
)
-
3
,
x
0
=
(
-
2
,
-
2
,
…
,
-
2
)
T
.Problem 3 (tridiagonal exponential problem [17]).
The elements ofF
(
x
) are
(69)
F
1
(
x
)
=
x
1
-
exp
⁡
(
cos
⁡
(
h
(
x
1
+
x
2
)
)
)
,
F
i
(
x
)
=
x
i
-
exp
⁡
(
cos
⁡
(
h
(
x
i
-
1
+
x
i
+
x
i
+
1
)
)
)
,
111111111111111
i
=
2,3
,
…
,
n
-
1
,
F
n
(
x
)
=
x
n
-
exp
⁡
(
cos
⁡
(
h
(
x
n
-
1
+
x
n
)
)
)
,
h
=
1
(
n
+
1
)
,
x
0
=
(
1.5,1.5
,
…
,
1.5
)
T
.Problem 4 (discrete boundary value problem [18]).
The elements ofF
(
x
) are
(70)
F
1
(
x
)
=
2
x
1
+
0.5
h
2
(
x
1
+
h
)
3
-
x
2
,
F
i
(
x
)
=
2
x
i
+
0.5
h
2
(
x
i
+
h
i
)
3
-
x
i
-
1
+
x
i
+
1
,
111111111111
i
=
2,3
,
…
,
n
-
1
,
F
n
(
x
)
=
2
x
n
+
0.5
h
2
(
x
n
+
h
n
)
3
-
x
n
-
1
,
h
=
1
n
+
1
,
x
0
=
(
h
(
h
-
1
)
,
h
(
2
h
-
1
)
,
…
,
h
(
n
h
-
1
)
)
T
.Problem 5 (exponentional problem 1 [19]).
The elements ofF
(
x
) are
(71)
F
1
(
x
)
=
exp
⁡
(
x
1
-
1
)
-
1
,
F
i
(
x
)
=
i
(
exp
⁡
(
x
i
-
1
)
-
x
i
)
,
i
=
2,3
,
…
,
n
,
x
0
=
(
n
n
-
1
,
…
,
n
n
-
1
)
T
.Problem 6 (exponentional problem 2 [19]).
The elements ofF
(
x
) are
(72)
F
1
(
x
)
=
exp
⁡
(
x
1
)
-
1
,
F
i
(
x
)
=
i
10
(
exp
⁡
(
x
i
)
+
x
i
-
1
-
1
)
,
i
=
2,3
,
…
,
n
,
x
0
=
(
1
n
2
,
…
,
1
n
2
)
T
.Problem 7 ( penalty I function [19]).
The elements ofF
(
x
) are
(73)
F
i
(
x
)
=
1
0
-
5
(
x
i
-
1
)
,
i
=
1
,
…
,
n
-
1
,
F
n
(
x
)
=
1
4
n
∑
j
=
1
n
‍
x
j
2
-
1
4
,
x
0
=
(
1
3
,
…
,
1
3
)
T
.Problem 8 (exponential function [19]).
The elements ofF
(
x
) are
(74)
F
i
(
x
)
=
i
10
(
1
-
x
i
2
-
exp
⁡
(
-
x
i
2
)
)
,
i
=
1,2
,
…
,
n
-
1
,
F
n
(
x
)
=
n
10
(
1
-
exp
⁡
(
-
x
n
2
)
)
,
x
0
=
(
1
4
n
2
,
2
4
n
2
,
…
,
n
4
n
2
)
T
.Problem 9 (minimal function [19]).
The elements ofF
(
x
) are
(75)
F
i
(
x
)
=
(
ln
⁡
x
i
-
exp
⁡
⁡
(
x
i
)
)
-
(
ln
⁡
x
i
-
exp
⁡
⁡
(
x
i
)
)
2
+
1
0
-
10
2
,
111111111111111111111111111111
i
=
1
,
…
,
n
,
x
0
=
(
1,1
,
…
,
1
)
T
.Problem 10 (extended Rosenbrock function (n is even) [20]).
The elements ofF
(
x
) are
(76)
F
2
i
-
1
(
x
)
=
10
(
x
2
i
-
x
2
i
-
1
2
)
,
F
2
i
(
x
)
=
1
-
x
2
i
-
1
,
i
=
1,2
,
…
,
n
2
,
x
0
=
(
5,1
,
5,1
,
…
,
5,1
)
T
.Problem 11 (logarithmic function [19]).
The elements ofF
(
x
) are
(77)
F
i
(
x
)
=
ln
⁡
(
x
i
+
1
)
-
x
i
n
,
i
=
1,2
,
…
,
n
,
x
0
=
(
1,1
,
…
,
1
)
T
.Problem 12 (strictly convex function 1 [21]).
F
(
x
) is the gradient of f
(
x
)
=
∑
i
=
1
n
(
exp
⁡
(
x
1
)
-
x
i
). The elements of F
(
x
) are
(78)
F
i
(
x
)
=
exp
⁡
(
x
i
)
-
1
,
i
=
1,2
,
…
,
n
.
x
0
=
(
1
n
,
2
n
,
…
,
1
)
T
.Problem 13 (tridimensional valley function (n is a multiple of 3) [22]).
The elements ofF
(
x
) are
(79)
F
3
i
-
2
(
x
)
=
(
c
2
x
3
i
-
2
3
+
c
1
x
3
i
-
2
)
exp
⁡
(
-
x
3
i
-
2
2
100
)
-
1
,
F
3
i
-
1
(
x
)
=
10
(
sin
(
x
3
i
-
2
-
x
3
i
-
1
)
)
,
F
3
i
(
x
)
=
10
(
cos
⁡
(
x
3
i
-
2
-
x
3
i
)
)
,
i
=
1,2
,
…
,
n
3
,
and then denote
(80)
c
1
=
1.003344481605351
,
c
2
=
-
3.344481605351171
×
1
0
-
3
,
x
0
=
(
2,1
,
2,1
,
2
,
…
,
1
)
T
.Problem 14 (extended Freudenstein and Roth function (n is even) [17]).
The elements ofF
(
x
) are
(81)
F
2
i
-
1
(
x
)
=
x
2
i
-
1
+
(
(
5
-
x
2
i
)
x
2
i
-
2
)
x
2
i
-
13
,
F
2
i
(
x
)
=
x
2
i
-
1
+
(
(
x
2
i
+
1
)
x
2
i
-
14
)
x
2
i
-
29
,
1111111111111111
i
=
1,2
,
…
,
n
2
,
x
0
=
(
6,3
,
6,3
,
…
,
6,3
)
T
.The sparsity patterns of most of the problems are tridiagonal and the dimension of problems varies from 50 to 20000. The results are given in Tables1 and 2, and each column is specified as follows:Pro: the problem;
n: the dimension of the problem;
∥
F
(
x
0
)
∥: the initial Euclidean norms of F
(
x
);
∥
F
(
x
k
)
∥: the final Euclidean norms of F
(
x
);
Iter: the total number of iterations;
Times: the CPU time in second.Table 1
Results of Algorithm3 for Problems 1–7.
Pro
n
∥
F
(
x
0
)
∥
B
0
=
I
B
0
=
F
′
(
x
0
)
∥
F
(
x
k
)
∥
Iter
Time (s)
∥
F
(
x
k
)
∥
Iter
Time (s)
1
50
26.8421
4.2686e  − 06
17
0.0000
3.0281e  − 06
12
0.0000
100
36.5103
6.6863
e  − 06
17
0.0000
3.0284e  − 06
12
0.0000
200
50.5767
3.4126e  − 06
19
0.0313
3.0284e  − 06
12
0.0313
500
78.9494
3.5829e  − 06
19
0.0313
3.0284e  − 06
12
0.0313
1000
111.1665
6.7616e  − 06
20
0.0938
3.0284e  − 06
12
0.0625
3000
156.8247
4.6028e  − 06
21
0.1780
3.0284e  − 06
12
0.1563
5000
247.7055
5.0272e  − 06
22
0.2063
3.0284e  − 06
12
0.2031
10000
256.8910
5.6234e  − 06
25
0.2028
3.0284e  − 06
12
0.3125
20000
289.2351
5.4512e  − 06
25
0.3276
3.0284e  − 06
12
0.6563
2
50
6.9282
1.3431e  − 06
10
0.0000
1.0235e  − 06
4
0.0000
100
9.8995
1.8437e  − 06
11
0.0000
1.0235e  − 06
4
0.0000
200
14.0712
6.2185e  − 06
11
0.0313
1.0235e  − 06
4
0.0000
500
22.3159
2.6805e  − 06
12
0.0313
1.0235e  − 06
4
0.0000
1000
31.5911
7.8148e  − 06
11
0.0625
1.0235e  − 06
4
0.0313
3000
54.7540
8.5561e  − 06
18
0.7188
1.0235e  − 06
4
0.0625
5000
70.6965
8.3005e  − 06
12
0.2500
1.0235e  − 06
4
0.0938
10000
75.0126
8.2145e  − 06
14
0.2808
1.0235e  − 06
4
0.1406
20000
81.2659
8.5179e  − 06
14
0.5304
1.0235e  − 06
4
0.2500
3
50
8.5416
8.7650e  − 08
3
0.0000
1.1795e  − 07
5
0.0000
100
12.1562
6.8406e  − 10
3
0.0000
5.3904e  − 06
4
0.0000
200
17.2195
8.0105e  − 06
2
0.0000
3.6741e  − 07
3
0.0000
500
27.2392
3.3130e  − 07
2
0.0000
1.2337e  − 06
3
0.0000
1000
38.5246
2.9461e  − 08
2
0.0000
1.5498e  − 07
3
0.0313
3000
66.7279
6.3233e  − 10
3
0.0313
3.0014e  − 06
2
0.0313
5000
86.1455
1.0586e  − 10
2
0.0313
1.0804e  − 06
2
0.0625
10000
121.8282
9.3691e  − 12
2
0.0938
2.7008e  − 07
2
0.0938
20000
172.2911
8.7919e  − 13
2
0.1563
6.7517e  − 08
2
0.1719
4
50
0.1511
8.7479e  − 06
19
0.0000
2.4065e  − 06
13
0.0000
100
0.1111
8.4206e  − 06
16
0.0000
5.7592e  − 06
12
0.0000
200
0.0801
9.4752e  − 06
18
0.0313
9.6492e  − 06
10
0.0313
500
0.0512
8.2454e  − 06
14
0.0313
9.0492e  − 06
10
0.0313
1000
0.0364
7.7380e  − 06
13
0.0625
4.0496e  − 06
10
0.0625
3000
0.0211
7.6951e  − 06
13
0.1719
9.7135e  − 06
8
0.1250
5000
0.0163
9.8163e  − 06
10
0.1875
8.4494e  − 06
7
0.1563
10000
0.0115
8.4212e  − 06
10
0.3125
4.1718e  − 06
7
0.2344
20000
0.0082
6.9072e  − 06
4
0.2656
2.0897e  − 06
7
0.3906
5
50
0.0481
7.6492e  − 06
9
0.0000
5.5212e  − 06
9
0.0000
100
0.0315
5.3122e  − 06
9
0.0000
9.8754e  − 06
8
0.0000
200
0.0213
9.7441e  − 06
8
0.0000
6.8642e  − 06
8
0.0000
500
0.0131
6.1289e  − 06
8
0.0000
4.2970e  − 06
8
0.0000
1000
0.0092
4.3258e  − 06
8
0.0000
7.9238e  − 06
7
0.0000
3000
0.0053
6.5316e  − 06
7
0.0000
4.5644e  − 06
7
0.0000
5000
0.0041
5.0582e  − 06
7
0.0000
9.2636e  − 06
6
0.0000
10000
0.0029
9.3577e  − 06
6
0.0000
6.5482e  − 06
6
0.0313
20000
0.0020
6.6163e  − 06
6
0.0313
4.6295e  − 06
6
0.0313
6
50
0.0166
6.6166e  − 06
7
0.0000
6.5364e  − 06
5
0.0000
100
0.0116
7.5062e  − 06
6
0.0000
8.5483e  − 06
2
0.0000
200
0.0082
9.4436e  − 06
4
0.0000
2.1372e  − 06
2
0.0000
500
0.0052
9.8417e  − 06
18
0.0406
5.2204e  − 06
1
0.0000
1000
0.0037
9.6163e  − 06
24
0.0313
3.6586e  − 06
3
0.0313
3000
0.0021
8.3375e  − 06
17
0.0625
2.1088e  − 06
3
0.0313
5000
0.0016
9.7458e  − 06
15
0.0938
1.6333e  − 06
3
0.0313
10000
0.0012
9.9565e  − 06
11
0.1563
1.1548e  − 06
3
0.0313
20000
0.0082
8.8706e  − 06
9
0.2031
8.1653e  − 06
2
0.0625
7
50
0.2271
1.4914e  − 14
2
0.0000
5.9494e  − 06
53
0.1250
100
0.2319
1.4792e  − 14
2
0.0000
5.6147e  − 06
58
0.0938
200
0.2413
1.4960e  − 14
2
0.0000
6.6486e  − 06
77
0.2031
500
0.2675
1.5760e  − 14
2
0.0000
7.4199e  − 06
70
0.7500
1000
0.3062
0
2
0.0313
8.2082e  − 06
35
0.3906
3000
0.4274
0
4
0.0625
5.7188e  − 06
53
10.5469
5000
0.5211
0
7
2.5000
6.7092e  − 06
41
19.0625
10000
0.7027
0
9
10.3125
6.8420e  − 06
45
25.0156
20000
0.9686
0
11
43.7500
7.1086e  − 06
51
30.0156Table 2
Results of Algorithm3 for Problems 8–14.
Pro
n
∥
F
(
x
0
)
∥
B
0
=
I
B
0
=
F
′
(
x
0
)
∥
F
(
x
k
)
∥
Iter
Time (s)
∥
F
(
x
k
)
∥
Iter
Time (s)
8
52
1.2019e  − 04
4.7426e  − 06
4
0.0000
4.8145e  − 06
6
0.0000
100
6.2500e  − 05
6.8402e  − 06
3
0.0000
6.9537e  − 06
4
0.0000
200
3.1250e  − 05
7.7243e  − 06
2
0.0000
7.8200e  − 06
2
0.0000
500
1.2500e  − 05
9.8751e  − 06
11
0.0000
3.1279e  − 06
2
0.0000
1000
6.2500e  − 06
6.2500e  − 06
0
0.0000
6.2500e  − 06
0
0.0000
3000
2.0833e  − 06
2.0833e  − 06
0
0.0000
2.0833e  − 06
0
0.0000
5000
1.2500e  − 06
1.2500e  − 06
0
0.0000
1.2500e  − 06
0
0.0000
10000
6.2500e  − 07
6.2500e  − 07
0
0.0000
6.2500e  − 07
0
0.0000
20000
3.1250e  − 07
3.1250e  − 07
0
0.0000
3.1250e  − 07
0
0.0000
9
50
19.2212
4.7930e  − 11
4
0.0000
4.3678e  − 11
2
0.0000
100
27.1828
6.7783e  − 11
4
0.0000
6.1770e  − 11
2
0.0000
200
38.4423
9.5860e  − 11
4
0.0000
9.8689e  − 11
2
0.0000
500
60.7826
1.5157e  − 10
4
0.0000
1.5604e  − 10
2
0.0000
1000
85.9596
2.1435e  − 10
4
0.0313
2.2068e  − 10
2
0.0000
3000
148.8864
4.1536e  − 10
4
0.0313
3.8222e  − 10
2
0.0313
5000
192.2116
5.3623e  − 10
4
0.0625
4.9345e  − 10
2
0.0625
10000
271.8282
7.5834e  − 10
4
0.1250
7.7298e  − 10
2
0.0938
20000
384.4231
1.0725e  − 09
4
0.2500
1.0932e  − 09
2
0.1563
10
50
1200
8.3426e  − 06
33
0.0000
4.2841e  − 09
19
0.0000
100
1697.1
2.2053e  − 07
34
0.0000
6.0586e  − 09
19
0.0000
200
2400
2.4538e  − 07
34
0.0000
3.5281e  − 06
23
0.0000
500
3794.7
1.3524e  − 06
35
0.0313
5.5783e  − 06
23
0.0000
1000
5366.6
1.0785e  − 06
33
0.0313
7.8890e  − 06
23
0.0000
3000
9295.2
2.3859e  − 07
33
0.0625
1.1640e  − 07
24
0.0313
5000
12000
3.0801e  − 07
33
0.0938
1.5028e  − 07
24
0.0625
10000
16971
4.1301e  − 06
29
0.1563
2.1252e  − 07
24
0.1250
20000
24000
5.3904e  − 06
25
0.2813
1.4378e  − 07
24
0.2500
11
50
4.7599
1.2153e  − 07
6
0.0000
1.4006e  − 06
6
0.0000
100
6.8315
1.1647e  − 07
6
0.0000
1.4743e  − 06
6
0.0000
200
9.7319
1.3534e  − 07
6
0.0000
1.8019e  − 06
6
0.0000
500
15.4545
1.9008e  − 07
6
0.0000
2.6117e  − 06
6
0.0000
1000
21.8876
2.5837e  − 07
6
0.0000
3.5883e  − 06
6
0.0000
3000
37.9470
4.3584e  − 07
6
0.0000
6.0967e  − 06
6
0.0000
5000
48.9988
5.5970e  − 07
6
0.0000
2.6853e  − 06
6
0.0000
10000
69.3047
7.8840e  − 07
6
0.0313
3.7947e  − 06
6
0.0313
20000
98.0187
1.1128e  − 06
6
0.0313
5.3645e  − 06
6
0.0469
12
50
6.2761
1.5871e  − 08
7
0.0000
2.7576e  − 08
6
0.0000
100
8.7909
1.9036e  − 08
7
0.0000
3.6023e  − 08
6
0.0000
200
12.3723
2.4543e  − 08
7
0.0000
4.8866e  − 08
6
0.0000
500
19.5054
3.6586e  − 08
7
0.0000
7.5309e  − 08
6
0.0000
1000
27.5580
5.0705e  − 08
7
0.0000
1.0559e  − 07
6
0.0000
3000
47.7008
8.6635e  − 08
7
0.0000
1.8182e  − 07
6
0.0000
5000
61.5735
1.1154e  − 07
7
0.0000
2.3446e  − 07
6
0.0000
10000
87.0696
1.5742e  − 07
7
0.0000
3.3129e  − 07
6
0.0000
20000
123.1291
2.2239e  − 07
7
0.0313
4.6831e  − 07
6
0.0313
13
51
771.2349
8.4607e  − 09
10
0.0000
1.6413e  − 08
9
0.0000
99
1089.8
1.1644e  − 08
10
0.0000
2.3210e  − 08
9
0.0000
201
1564.5
1.6479e  − 08
10
0.0000
3.3331e  − 08
9
0.0000
501
2480.5
2.5914e  − 08
10
0.0000
5.2860e  − 08
9
0.0000
999
3507.7
3.6544e  − 08
10
0.0000
7.4754e  − 08
9
0.0000
3000
6087.3
6.3242e  − 08
10
0.0313
1.2974e  − 07
9
0.0000
5001
7857.2
8.1675e  − 08
10
0.0625
1.6746e  − 07
9
0.0313
9999
11112
1.1547e  − 07
10
0.0938
2.3682e  − 07
9
0.0625
20001
15717
1.6330e  − 07
10
0.1563
3.3496e  − 07
9
0.1563
14
50
147.1394
2.8039e  − 06
7
0.0000
1.4943e  − 06
8
0.0000
100
208.0865
3.9654e  − 06
7
0.0000
2.1133e  − 06
8
0.0000
200
294.2788
5.6079e  − 06
7
0.0000
2.9887e  − 06
8
0.0313
500
465.2956
8.8669e  − 06
7
0.0313
4.7255e  − 06
8
0.0625
1000
658.0274
3.5104e  − 07
8
0.0625
6.6829e  − 06
8
0.1250
3000
1139.7
6.0803e  − 07
8
0.1250
3.1348e  − 08
9
0.3438
5000
1471.4
7.8496e  − 07
8
0.2969
4.0470e  − 08
9
0.4219
10000
2080.9
1.1101e  − 06
8
0.3594
5.7234e  − 08
9
0.8438
20000
2942.8
1.5699e  − 06
8
0.7656
8.0941e  − 08
9
1.5000It can be seen from the tables that, for all tested problems, Algorithm3 terminated successfully. The numerical results show that Algorithm 3 becomes increasingly desirable as n increases.In Tables1 and 2, we list the results of Algorithm 3 for solving Problems 1 to 14 with B
0
=
I. Because B
0 is very important for the performance of Broyden’s method, we also present the results with B
0
=
F
′
(
x
0
). We can see that Algorithm 3 can be applied to solve a class of nonlinear equations, where the dimension of which can be up to 20000. Since the Schubert’s update formula (7) can maintain the sparsity pattern of Jacobian matrix exactly, so Algorithm 3 is especially effective for solving large-scale nonlinear equations with sparse Jacobian matrix, such as tridiagonal or block diagonal Jacobian matrix.


## 5. Remarks

In this paper, based on the work of Schubert, Broyden, and Marwil, we have globalized Schubert’s method and proposed a global algorithm by using a nonmonotone line search. We have established the global and superlinear convergence. Numerical results showed that the algorithm is especially effective for large-scale problems.



---

*Source: 251587-2014-10-14.xml*