# A New Upper Bound on the Infinity Norm of the Inverse of Nekrasov Matrices

Authors: Lei Gao; Chaoqian Li; Yaotang Li
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

A new upper bound which involves a parameter for the infinity norm of the inverse of Nekrasov matrices is given. And we determine the optimal value of the parameter such that the bound improves the results of Kolotilina, 2013. Numerical examples are given to illustrate the corresponding results.


---

## Body

## 1. Introduction

The class of Nekrasov matrices is a subclass ofH-matrices. Estimating the infinity norm of the inverse of Nekrasov matrices can be used to prove the convergence of matrix splitting and matrix multisplitting iteration methods for solving large sparse systems of linear equations; see [1–4]. Here, we call a matrix A
=
(
a
i
j
)
∈
C
n
,
n an H-matrix if its comparison matrix 〈
A
〉
=
[
m
i
j
] defined by
(1)
〈
A
〉
=
[
m
i
j
]
∈
C
n
,
n
,
m
i
j
=
{
|
a
i
i
|
,
i
=
j
-
|
a
i
j
|
,
i
≠
j
,
is an M-matrix; that is, 〈
A
〉
-
1
≥
0 [1, 5, 6], and a matrix A
=
[
a
i
j
]
∈
C
n
,
n is called a Nekrasov matrix if for each i
∈
N,
(2)
|
a
i
i
|
>
h
i
(
A
)
,
where h
1
(
A
)
=
∑
j
≠
1
|
a
1
j
| and h
i
(
A
)
=
∑
j
=
1
i
-
1
(
|
a
i
j
|
/
|
a
j
j
|
)
h
j
(
A
)
+
∑
j
=
i
+
1
n
|
a
i
j
|, i
=
2,3
,
…
,
n [2, 6].In 1975, Varah [7] provided the following upper bound for strictly diagonally dominant (SDD) matrices as one most important subclass of Nekrasov matrices, consequently, H-matrices [2, 6, 8]. Here a matrix A
=
[
a
i
j
]
∈
C
n
,
n is called SDD if for each i
∈
N
=
{
1,2
,
…
,
n
},
(3)
|
a
i
i
|
>
r
i
(
A
)
,
where r
i
(
A
)
=
∑
j
≠
i
|
a
i
j
|.Theorem 1 (see [7]).
LetA
=
[
a
i
j
]
∈
C
n
,
n be SDD. Then
(4)
∥
A
-
1
∥
∞
≤
1
min
⁡
i
∈
N
⁡
(
|
a
i
i
|
-
r
i
(
A
)
)
.We call the bound in Theorem1 the Varah’s bound. As Cvetković et al. [2] said, Varah’s bound works only for SDD matrices and even then it is not always good enough. To obtain new upper bounds for the infinity norm of the inverse of a wider class of matrices which sometimes works better in the SDD case, Cvetković et al. [2] give the following bound of Nekrasov matrices.Theorem 2 (see [2, Theorem  2]).
LetA
=
[
a
i
j
]
∈
C
n
,
n be a Nekrasov matrix. Then
(5)
∥
A
-
1
∥
∞
≤
max
⁡
i
∈
N
⁡
(
z
i
(
A
)
/
|
a
i
i
|
)
1
-
max
⁡
i
∈
N
⁡
(
h
i
(
A
)
/
|
a
i
i
|
)
,
(6)
∥
A
-
1
∥
∞
≤
max
⁡
i
∈
N
⁡
z
i
(
A
)
min
⁡
i
∈
N
⁡
|
a
i
i
|
-
h
i
(
A
)
,
where z
1
(
A
)
=
1 and z
i
(
A
)
=
∑
j
=
1
i
-
1
(
|
a
i
j
|
/
|
a
j
j
|
)
z
j
(
A
)
+
1
,
i
=
2,3
…
,
n.In [9, Theorems  2.2 and  2.3], Kolotilina gave an improvement of these upper bounds in Theorem 2 (see Theorems 3 and 4).Theorem 3 (see [9, Theorem  2.2]).
LetA
=
[
a
i
j
]
∈
C
n
,
n be a Nekrasov matrix. Then
(7)
∥
A
-
1
∥
∞
≤
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.Theorem 4 (see [9, Theorem  2.3]).
LetA
=
[
a
i
j
]
∈
C
n
,
n be a Nekrasov matrix. Then
(8)
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
≤
max
⁡
i
∈
N
⁡
(
z
i
(
A
)
/
|
a
i
i
|
)
1
-
max
⁡
i
∈
N
(
h
i
(
A
)
/
|
a
i
i
|
)
,
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
≤
max
⁡
i
∈
N
z
i
(
A
)
min
⁡
i
∈
N
|
a
i
i
|
-
h
i
(
A
)
.In this paper, we also focus on the estimation problem of the infinity norm of the inverse of Nekrasov matrices and give an improvement of the bound in Theorem3 (Theorem  2.2 in [9]). Numerical example is given to illustrate the corresponding results.


## 2. Bounds for the Infinity Norm of the Inverse of Nekrasov Matrices

In order to obtain a new bound, we start with the following lemmas and notations. Given a matrixA
=
[
a
i
j
], by A
=
D
-
L
-
U we denote the standard splitting of A into its diagonal (
D
), strictly lower (
-
L
), and strictly upper (
-
U
) triangular parts. And by [
A
]
i
j denote the (
i
,
j
)-entry of A; that is, [
A
]
i
j
=
a
i
j. Furthermore, we denote |
A
|
=
[
|
a
i
j
|
].Lemma 5 (see [10]).
LetA
=
[
a
i
j
]
∈
C
n
,
n be a nonsingular H-matrix. Then
(9)
|
A
-
1
|
≤
〈
A
〉
-
1
.Lemma 6 (see [11]).
Given any matrixA
=
[
a
i
j
]
∈
C
n
,
n, n
≥
2, with a
i
i
≠
0 for all i
∈
N, then
(10)
h
i
(
A
)
=
|
a
i
i
|
[
(
|
D
|
-
|
L
|
)
-
1
|
U
|
e
]
i
,
where e
∈
C
n
,
n is the vector with all components equal to 1.Lemma 7 (see [12]).
A matrixA
=
[
a
i
j
]
∈
C
n
,
n, n
≥
2, is a Nekrasov matrix if and only if
(11)
(
|
D
|
-
|
L
|
)
-
1
|
U
|
e
<
e
,
that is, if and only if E
-
(
|
D
|
-
|
L
|
)
-
1
|
U
| is an SDD matrix, where E is the identity matrix.LetC
=
E
-
(
|
D
|
-
|
L
|
)
-
1
|
U
|
=
[
c
i
j
]. Then from Lemma 7, C is SDD when A is a Nekrasov matrix. Note that c
11
=
1, c
k
1
=
0, k
=
2,3
,
…
,
n, and c
1
k
=
-
|
a
1
k
|
/
|
a
11
|, k
=
2,3
,
…
,
n, which leads to the following lemma.Lemma 8.
LetA
=
[
a
i
j
]
∈
C
n
,
n be a Nekrasov matrix and
(12)
C
(
μ
)
=
C
D
(
μ
)
=
[
E
-
(
|
D
|
-
|
L
|
)
-
1
|
U
|
]
D
(
μ
)
,
where D
(
μ
)
=
diag
⁡
(
μ
,
1
,
…
,
1
) and μ
>
r
1
(
A
)
/
|
a
11
|. Then C
(
μ
) is SDD.Proof.
It is not difficult from (12) to see that [
C
(
μ
)
]
k
1
=
μ
c
k
1 for all k
∈
N and [
C
(
μ
)
]
k
j
=
c
k
j for all k
∈
N and j
≠
1. Hence
(13)
[
C
(
μ
)
]
11
=
μ
,
r
1
(
C
(
μ
)
)
=
r
1
(
C
)
=
r
1
(
A
)
|
a
i
i
|
and for i
=
2
,
…
,
n,
(14)
[
C
(
μ
)
]
i
i
=
c
i
i
,
r
i
(
C
(
μ
)
)
=
r
i
(
C
)
.
From the fact that C is SDD and μ
>
r
1
(
A
)
/
|
a
11
|, we have that C
(
μ
) is SDD. The proof is completed.The main result of this paper is the following theorem.Theorem 9.
LetA
=
[
a
i
j
]
∈
C
n
,
n be a Nekrasov matrix. Then for μ
>
r
1
(
A
)
/
|
a
11
|,
(15)
∥
A
-
1
∥
∞
≤
max
⁡
⁡
{
μ
,
1
}
max
⁡
{
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
1
μ
|
a
11
|
-
h
1
(
A
)
,
f
f
f
f
f
f
i
i
f
f
f
f
f
f
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
.Proof.
LetC
(
μ
)
=
C
D
(
μ
)
=
(
E
-
(
|
D
|
-
|
L
|
)
-
1
|
U
|
)
D
(
μ
), where D
(
μ
)
=
diag
⁡
(
μ
,
1
,
…
,
1
). From (12), we have
(16)
C
(
μ
)
=
(
|
D
|
-
|
L
|
)
-
1
〈
A
〉
D
(
μ
)
,
which implies that
(17)
〈
A
〉
=
(
|
D
|
-
|
L
|
)
C
(
μ
)
D
(
μ
)
-
1
=
(
|
D
|
-
|
L
|
)
Δ
·
Δ
-
1
C
(
μ
)
D
(
μ
)
-
1
,
where
(18)
Δ
=
diag
⁡
(
δ
1
,
δ
2
,
…
,
δ
n
)
,
δ
i
>
0
,
i
=
1,2
,
…
,
n
.
Furthermore, since a Nekrasov matrix is an H-matrix, we have, from Lemma 5,
(19)
∥
A
-
1
∥
∞
≤
∥
〈
A
〉
-
1
∥
∞
≤
∥
D
(
μ
)
∥
∞
·
∥
C
(
μ
)
-
1
Δ
∥
∞
·
∥
[
(
|
D
|
-
|
L
|
)
Δ
]
-
1
∥
∞
.
First, we estimate∥
[
(
|
D
|
-
|
L
|
)
Δ
]
-
1
∥
∞. Since (
|
D
|
-
|
L
|
)
Δ is an M-matrix and there exists a positive diagonal matrix Δ such that (
|
D
|
-
|
L
|
)
Δ
e
=
e, see [9], we get
(20)
∥
[
(
|
D
|
-
|
L
|
)
Δ
]
-
1
∥
∞
=
∥
[
(
|
D
|
-
|
L
|
)
Δ
]
-
1
e
∥
∞
=
1
.
Secondly, we estimate∥
C
(
μ
)
-
1
Δ
∥
∞. From Lemma 8, C
(
μ
) is SDD. Obviously, multiplying the left-hand side of C
(
μ
) by diagonal matrix Δ
-
1 does not change SDD property, so Δ
-
1
C
(
μ
) is also SDD. Thus, Varah’s bound (4) can be applied as follows:
(21)
∥
C
(
μ
)
-
1
Δ
∥
∞
≤
max
⁡
i
∈
N
⁡
1
[
Δ
-
1
C
(
μ
)
e
]
i
=
max
⁡
i
∈
N
δ
i
[
C
(
μ
)
e
]
i
=
max
⁡
{
δ
1
[
C
(
μ
)
e
]
1
,
max
⁡
i
≠
1
δ
i
[
C
(
μ
)
e
]
i
}
=
max
⁡
{
δ
1
|
a
11
|
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
δ
i
|
a
i
i
|
|
a
i
i
|
-
h
i
(
A
)
}
.
In addition, since z
(
A
)
=
[
z
1
(
A
)
,
…
,
z
n
(
A
)
]
T
=
|
D
|
(
|
D
|
-
|
L
|
)
-
1
e and (
|
D
|
-
|
L
|
)
Δ
e
=
e, see [9, 13], we have
(22)
δ
i
|
a
i
i
|
=
z
i
(
A
)
,
i
=
1,2
,
…
,
n
.
Substituting (22) into (21), we get that
(23)
∥
C
(
μ
)
-
1
Δ
∥
∞
≤
max
⁡
{
z
1
(
A
)
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
.
Finally, from (20), (23), z
1
(
A
)
=
1, and the fact that ∥
D
(
μ
)
∥
∞
=
max
⁡
{
μ
,
1
}, we have
(24)
∥
A
-
1
∥
∞
≤
max
⁡
⁡
{
μ
,
1
}
×
max
⁡
{
z
1
(
A
)
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
=
max
⁡
{
μ
,
1
}
×
max
⁡
{
1
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
.
The conclusions follow.Example 10.
Consider the Nekrasov matrixA
1 in [2, 9], where
(25)
A
1
=
[
-
7
1
-
0.2
2
7
88
2
-
3
2
0.5
13
-
2
0.5
3.0
1
6
]
.
By computation, h
1
(
A
)
=
3.2000, h
2
(
A
)
=
8.2000, h
3
(
A
)
=
2.9609, h
4
(
A
)
=
0.7359, z
1
(
A
)
=
1, z
2
(
A
)
=
2, z
3
(
A
)
=
1.2971, and z
4
(
A
)
=
1.2394. By the bound of Theorem 3 (the bound of Theorem  2.2 in [9]), we have
(26)
∥
A
1
-
1
∥
∞
≤
0.2632
.
By Theorem 9, we have
(27)
∥
A
1
-
1
∥
∞
≤
0.3226
(
Taking
μ
=
0.90
)
,
∥
A
1
-
1
∥
∞
≤
0.2786
(
Taking
μ
=
0.97
)
,
∥
A
1
-
1
∥
∞
≤
0.2549
(
Taking
μ
=
1.04
)
,
∥
A
1
-
1
∥
∞
≤
0.2590
(
Taking
μ
=
1.10
)
,
∥
A
1
-
1
∥
∞
≤
0.2708
(
Taking
μ
=
1.15
)
.
In fact, ∥
A
1
-
1
∥
∞
=
0.1921.Remark 11.
Example10 shows that by choosing the value of μ, the bound in Theorem 9 is better than that in Theorem 3 in some cases. We further observe the bound in Theorem 9 by Figure 1 and find that there is an interval such that for any μ in this interval, the bound in Theorem 9 for the matrix A
1 is always smaller than that in Theorem 3. An interesting problem arises: whether there is an interval of μ such that the bound in Theorem 9 for any Nekrasov matrix is smaller than that in Theorem 3. In the following section, we will study this problem.Figure 1
The bounds in Theorems9 and 3.


## 3. The Choice ofμ

In this section, we determine the value ofμ such that the bound for ∥
A
-
1
∥
∞ in Theorem 9 is less than or equal to that in [9]. First, we consider the Nekrasov matrix A
=
[
a
i
j
]
∈
C
n
,
n with
(28)
1
|
a
11
|
-
h
1
(
A
)
>
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
,
and give the following lemma.Lemma 12.
Leta, b, and c be positive real numbers, and 0
<
a
(
b
-
c
)
<
1. Then
(29)
1
<
1
+
a
c
a
b
<
1
a
(
b
-
c
)
.Proof.
We only need to prove that(
1
+
a
c
)
/
a
b
-
1
>
0 and 1
/
a
(
b
-
c
)
-
(
1
+
a
c
)
/
a
b
>
0. In fact,
(30)
1
+
a
c
a
b
-
1
=
1
-
a
(
b
-
c
)
a
b
>
0
,
1
a
(
b
-
c
)
-
1
+
a
c
a
b
=
c
(
1
-
a
(
b
-
c
)
)
a
b
(
b
-
c
)
>
0
.
The proof is completed.Lemma 13.
LetA
=
[
a
i
j
]
∈
C
n
,
n be a Nekrasov matrix with
(31)
1
|
a
11
|
-
h
1
(
A
)
>
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Then
(32)
1
<
1
+
max
⁡
i
≠
1
⁡
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
<
1
/
(
|
a
11
|
-
h
1
(
A
)
)
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
.Proof.
Leta
=
max
⁡
i
≠
1
⁡
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
), b
=
|
a
11
|, and c
=
h
1
(
A
). From (28), we get 0
<
a
(
b
-
c
)
<
1. Then from Lemma 12, the first and second inequalities in (32) hold.We now give an interval ofμ such that the bound in Theorem 9 is less than that in Theorem 3.Lemma 14.
LetA
=
[
a
i
j
]
∈
C
n
,
n be a Nekrasov matrix with
(33)
1
|
a
11
|
-
h
1
(
A
)
>
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Then for each μ
∈
(
1
,
(
1
/
(
|
a
11
|
-
h
1
(
A
)
)
)
/
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
),
(34)
∥
A
-
1
∥
∞
≤
max
⁡
⁡
{
μ
,
1
}
×
max
⁡
{
1
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
<
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.Proof.
From Lemma13, we have
(35)
μ
∈
(
1
,
1
+
max
⁡
i
≠
1
⁡
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
]
⋃
‍
[
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
,
f
f
f
f
1
/
(
|
a
11
|
-
h
1
(
A
)
)
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
and max
⁡
{
μ
,
1
}
=
μ.
(
I
) For μ
∈
(
1
,
(
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
)
/
(
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
], then
(36)
μ
|
a
11
|
-
h
1
(
A
)
≤
1
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
;
that is,
(37)
1
μ
|
a
11
|
-
h
1
(
A
)
≥
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Therefore,
(38)
max
⁡
{
μ
,
1
}
max
⁡
{
1
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
=
μ
μ
|
a
11
|
-
h
1
(
A
)
.
Consider the function f
(
x
)
=
x
/
(
x
|
a
11
|
-
h
1
(
A
)
), x
∈
[
1
,
(
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
)
/
(
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
]. It is easy to prove that f
(
x
) is a monotonically decreasing function of x. Hence, for any μ
∈
(
1
,
(
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
)
/
(
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
],
(39)
f
(
μ
)
<
f
(
1
)
;
that is,
(40)
μ
μ
|
a
11
|
-
h
1
(
A
)
<
1
|
a
11
|
-
h
1
(
A
)
=
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Hence,
(41)
max
⁡
{
μ
,
1
}
max
⁡
{
1
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
<
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
(
II
) For ∈
[
(
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
)
/
(
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
), (
1
/
(
|
a
11
|
-
h
1
(
A
)
)
)
/
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
), then
(42)
μ
|
a
11
|
-
h
1
(
A
)
≥
1
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
;
that is,
(43)
1
μ
|
a
11
|
-
h
1
(
A
)
≤
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Therefore,
(44)
max
⁡
{
μ
,
1
}
max
⁡
{
1
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
=
μ
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Consider the function
(45)
g
(
x
)
=
x
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
,
x
∈
[
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
,
f
f
i
1
/
(
|
a
11
|
-
h
1
(
A
)
)
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
]
.
Obviously, g
(
x
) is a monotonically increasing function of x. Hence, for any μ
∈
[
(
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
)
/
(
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
), (
1
/
(
|
a
11
|
-
h
1
(
A
)
)
)
/
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
),
(46)
g
(
μ
)
<
g
(
(
1
/
(
|
a
11
|
-
h
1
(
A
)
)
)
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
;
that is,
(47)
μ
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
<
1
|
a
11
|
-
h
1
(
A
)
=
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Hence,
(48)
max
⁡
{
μ
,
1
}
max
⁡
{
1
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
<
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
The conclusion follows from (
I
) and (
II
).Lemma14 provides an interval of μ such that the bound in Theorem 9 is better than the bound in Theorem 3 (the bound in [9]). Moreover, we can determine the optimal value of μ by the following theorem.Theorem 15.
LetA
=
[
a
i
j
]
∈
C
n
,
n be a Nekrasov matrix with
(49)
1
|
a
11
|
-
h
1
(
A
)
>
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Then
(50)
min
⁡
{
(
1
,
1
/
(
|
a
11
|
-
h
1
(
A
)
)
max
⁡
i
≠
1
⁡
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
max
⁡
{
μ
,
1
}
fffifffff
×
max
⁡
{
1
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
:
fffifffff
μ
∈
(
1
,
1
/
(
|
a
11
|
-
h
1
(
A
)
)
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
}
.
=
z
1
(
A
)
|
a
11
|
+
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
·
h
1
(
A
)
|
a
11
|
.
Furthermore,
(51)
∥
A
-
1
∥
∞
≤
max
⁡
{
μ
,
1
}
(
z
1
(
A
)
|
a
11
|
+
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
·
h
1
(
A
)
|
a
11
|
)
<
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.Proof.
From the proof of Lemma14, we have that
(52)
f
(
x
)
=
x
x
|
a
11
|
-
h
1
(
A
)
,
x
∈
[
1
,
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
]
is decreasing and that
(53)
g
(
x
)
=
x
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
,
x
∈
[
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
,
f
f
1
/
(
|
a
11
|
-
h
1
(
A
)
)
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
]
is increasing. Therefore, the minimum of f
(
x
) and g
(
x
) is
(54)
f
(
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
=
g
(
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
=
z
1
(
A
)
|
a
11
|
+
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
·
h
1
(
A
)
|
a
11
|
,
which implies that (50) holds. Again by Lemma 14, (51) follows easily.Remark 16.
Theorem15 provides a method to determine the optimal value of μ for a Nekrasov matrix A
=
[
a
i
j
]
∈
C
n
,
n with
(55)
1
|
a
11
|
-
h
1
(
A
)
>
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Also consider the matrix A
1 in Example 10. By computation, we get
(56)
1
|
a
11
|
-
h
1
(
A
)
=
0.2632
>
0.2354
=
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Hence, by Theorem 15, we can obtain that the bound in Theorem 9 reaches its minimum
(57)
z
1
(
A
)
|
a
11
|
+
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
·
h
1
(
A
)
|
a
11
|
=
0.2505
at μ
=
(
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
)
/
(
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
=
1.0639 (also see Figure 1).Next, we study the bound in Theorem9 for the Nekrasov matrix A
=
[
a
i
j
]
∈
C
n
,
n with
(58)
1
|
a
11
|
-
h
1
(
A
)
≤
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.Theorem 17.
LetA
=
[
a
i
j
]
∈
C
n
,
n be a Nekrasov matrix with
(59)
1
|
a
11
|
-
h
1
(
A
)
≤
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Then we can take μ
∈
[
(
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
)
/
(
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
,
1
] such that
(60)
∥
A
-
1
∥
∞
≤
max
⁡
{
μ
,
1
}
×
max
⁡
{
1
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
=
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.Proof.
From (59), we get (
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
)
/
(
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
≤
1. Then, for μ
>
r
1
(
A
)
/
|
a
11
|
=
h
1
(
A
)
/
|
a
11
|, we have
(61)
μ
∈
(
h
1
(
A
)
|
a
11
|
,
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
⋃
‍
[
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
,
1
]
⋃
‍
(
1
,
+
∞
)
.
(
I
) For μ
∈
(
h
1
(
A
)
/
|
a
11
|
,
(
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
)
/
(
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
), then max
⁡
{
μ
,
1
}
=
1 and
(62)
μ
<
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
;
that is,
(63)
1
μ
|
a
11
|
-
h
1
(
A
)
>
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Therefore,
(64)
max
⁡
{
μ
,
1
}
max
⁡
{
1
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
=
1
μ
|
a
11
|
-
h
1
(
A
)
>
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
=
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
(
II
) For μ
∈
[
(
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
)
/
(
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
)
,
1
], then max
⁡
{
μ
,
1
}
=
1 and
(65)
μ
≥
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
;
that is,
(66)
1
μ
|
a
11
|
-
h
1
(
A
)
≤
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Therefore,
(67)
max
⁡
{
μ
,
1
}
max
⁡
{
1
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
=
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
=
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
(
III
) For μ
∈
(
1
,
+
∞
), then max
⁡
{
μ
,
1
}
=
μ and
(68)
1
μ
|
a
11
|
-
h
1
(
A
)
≤
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
Therefore,
(69)
max
⁡
{
μ
,
1
}
max
⁡
{
1
μ
|
a
11
|
-
h
1
(
A
)
,
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
}
=
μ
·
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
>
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
=
max
⁡
i
∈
N
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
.
The conclusion follows from (I), (II), and (III).Remark 18.
Theorems15 and 17 provide the value of μ; that is,
(70)
μ
=
1
+
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
·
h
1
(
A
)
|
a
11
|
·
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
|
-
h
i
(
A
)
)
)
such that the bound in Theorem 9 is not worse than that in Theorem 3 for a Nekrasov matrix A
=
[
a
i
j
]
∈
C
n
,
n. In particular, for the Nekrasov matrix A with 1
/
(
|
a
11
|
-
h
1
(
A
)
)
>
max
⁡
i
≠
1
(
z
i
(
A
)
/
(
|
a
i
i
-
h
i
(
A
)
|
)
), the bound in Theorem 9 is better than that in Theorem 3.Example 19.
Consider the following five Nekrasov matrices in [2, 9]:
(71)
A
2
=
[
8
1
-
0.2
3.3
7
13
2
-
3
-
1.3
6.7
13
-
2
0.5
3
1
6
]
,
A
3
=
[
21
-
9.1
-
4.2
-
2.1
-
0.7
9.1
-
4.2
-
2.1
-
0.7
-
0.7
4.9
-
2.1
-
0.7
-
0.7
-
0.7
2.8
]
,
A
4
=
[
5
1
0.2
2
1
21
1
-
3
2
0.5
6.4
-
2
0.5
-
1
1
9
]
,
A
5
=
[
6
-
3
-
2
-
1
11
-
8
-
7
-
3
10
]
,
A
6
=
[
8
-
0.5
-
0.5
-
0.5
-
9
16
-
5
-
5
-
6
-
4
15
-
3
-
4.9
-
0.9
-
0.9
6
]
.
Obviously, A
2, A
3, and A
4 are SDD. And it is not difficult to verify that A
4 satisfies the conditions in Theorem 15 and A
2, A
3, A
5, and A
6 satisfy the conditions in Theorem 17. We compute by Matlab 7.0 the upper bounds for the infinity norm of the inverse of A
i, i
=
2
,
…
,
6, which are shown in Table 1. It is easy to see from Table 1 that this example illustrates Theorems 15 and 17.Table 1
The upper bounds for|
|
A
i
-
1
|
|
∞, i
=
2
,
…
,
6.
Matrix
A
2
A
3
A
4
A
5
A
6
Exact|
|
A
-
1
|
|
∞
0.2390
0.8759
0.2707
1.1519
0.4474
Varah (4)
1
1.4286
0.5556
—
—
Cvetković et al. (5)
0.8848
1.8076
0.6200
1.4909
1.1557
Cvetković et al. (6)
0.6885
0.9676
0.7937
2.4848
0.5702
Kolotilina (7)
0.5365
0.9676
0.5556
1.4138
0.4928
Theorem9
0.5365
0.9676
0.5038
1.4138
0.4928


## 4. Conclusions

In this paper, we give an improvement on the infinity norm bound for the inverse of a Nekrasov matrix in [9]. In particular, for the Nekrasov matrix A
=
[
a
i
j
]
∈
C
n
,
n with
(72)
1
|
a
11
|
-
h
1
(
A
)
>
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
,
we prove that new bound is better than that in [9]. However, for the Nekrasov matrix A with
(73)
1
|
a
11
|
-
h
1
(
A
)
≤
max
⁡
i
≠
1
z
i
(
A
)
|
a
i
i
|
-
h
i
(
A
)
,
we only obtain that new bound is equal to that in [9]. For this case, we try to found some better bounds in future. On the other hand, our bound only considers one parameter μ, that is, D
(
μ
)
=
diag
⁡
(
μ
,
1
,
…
,
1
), which poses an interesting problem: whether we further improve this bound by introducing more parameters. In future, we will research this problem.



---

*Source: 708128-2014-06-12.xml*