Error bounds for linear complementarity problems of DB-matrices

Error bounds for linear complementarity problems of DB-matrices

Linear Algebra and its Applications 434 (2011) 830–840 Contents lists available at ScienceDirect Linear Algebra and its Applications journal homepag...

183KB Sizes 3 Downloads 35 Views

Linear Algebra and its Applications 434 (2011) 830–840

Contents lists available at ScienceDirect

Linear Algebra and its Applications journal homepage: www.elsevier.com/locate/laa

Error bounds for linear complementarity problems of DB-matrices聻 Ping-Fan Dai Department of Mathematics and Computer Science, Sanming University, Sanming, Fujian 365004, PR China

A R T I C L E

I N F O

A B S T R A C T

Doubly B-matrices (DB-matrices), which properly contain B-matrices, are introduced by Peña (2003) [2]. In this paper we present error bounds for the linear complementarity problem when the matrix involved is a DB-matrix and a new bound for linear complementarity problem of a B-matrix. The numerical examples show that the bounds are sharp. © 2010 Elsevier Inc. All rights reserved.

Article history: Received 11 May 2010 Accepted 27 September 2010 Available online 2 November 2010 Submitted by M. Tsatsomeros Keywords: Error bounds Linear complementarity problem DB-matrix B-matrix H-matrix P-matrix

1. Introduction A real square matrix A is called a B-matrix if it is the matrix with positive row sums and all its off-diagonal elements bounded above by their corresponding row means (see [1]), i.e. for all i = 1, . . . , n, n  k =1

aik

> 0 and

A real matrix A aii 聻

n 1 

n k =1

aik

> aij ,

∀i = / j.

= (aij ) ∈ Rn×n with diagonal elements satisfying

> ri+ ∀i ∈ {1, . . . , n}

This work is supported by the Science Foundation of the Education Department of Fujian Province (JB09228) and the Science

Foundation of Sanming University (B0826/Q). E-mail address: [email protected] 0024-3795/$ - see front matter © 2010 Elsevier Inc. All rights reserved. doi:10.1016/j.laa.2010.09.049

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

831

is a doubly B-matrix (DB-matrix) if, for all i = / j (i, j ∈ {1, . . . , n}), ⎛ ⎞⎛ ⎞       +  + + + ajj − rj > ⎝ ri − aik ⎠ ⎝ rj − ajk ⎠ , aii − ri k= /i

k= /j

+

where ri = max{0, aij |∀j = / i} (see [2]). A real square matrix A is called a P-matrix if all its principal minors are positive. It is shown in [2] that a DB-matrix is a P-matrix. The linear complementarity problem, abbreviated LCP, is to find a vector z ∈ Rn such that z  0,

Mz

+ q  0, (Mz + q)T z = 0

(1.1) n× n

and q ∈ R . Many applications for or to show that no such vector z exists, where M = (mij ) ∈ R (1.1) can be found in [3–5], respectively. M is a P-matrix if and only if the LCP(M, q) has a unique solution for any q (see [4]). Error bounds for LCP have been given in [6–10,14]. Structured matrices can lead to nice properties of the corresponding linear complementarity problems. For instance, in [6], García-Esnaola et al. give error bounds for linear complementarity problem for B-matrices. Motivated by [6], in this paper, we present error bounds for DB-matrices linear complementarity problems. Since DB-matrices properly contain B-matrices, we get a generalization of [6] and obtain a new bound for LCP of a B-matrix (see Remark 3.2). The numerical examples show that the bounds are sharp. n

2. Preliminaries Let us introduce some basic notations. Let N := {1, . . . , n}. Given a set S, |S | denote the cardinal number of S. A Z-matrix is a matrix whose off-diagonal elements are nonpositive and a nonsingular Mmatrix is a Z-matrix with nonnegative inverse. Let A = (aij ), i, j ∈ N, be a real matrix. The comparison matrix A = (cij ) is defined by setting cii

= |aii |, cij = −|aij |, i = / j, i, j ∈ N .

If A is an M-matrix, then A is called an H-matrix. From now on, we shall use the following notation: for each i, j  |aij |. Ri (A) :=

∈ N,

i= /j

A matrix A is strictly diagonally dominant if |aii | > Ri (A), i ∈ N and strictly doubly diagonally dominant if |aii ||ajj | > Ri (A)Rj (A), ∀ i = / j, i, j ∈ N. A strictly doubly diagonally dominant matrix is nonsingular (see Theorem 3.6.6 of [11]) and an H-matrix (see [12]). For each real square matrix M = (mij ), i, j ∈ N, let ri

= max{0, mij |∀j = / i},

we can write M as M

= B+ + C,

where B+



=

m11 − r1 ⎜m21 − r2 ⎜ ⎜ .. ⎝ . mn1

− rn

− r1 − r2 .. . mn2 − rn

m12 m22

··· ··· ..

.

···

− r1 ⎞ − r2 ⎟ ⎟ ⎟, .. ⎠ . mnn − rn



m1n m2n

C

=

r1 ⎜r2 ⎜ ⎜. ⎝ .. rn

··· ··· ..

.

···

⎞ r1 r2 ⎟ ⎟ . .. ⎟ .⎠

(2.1)

rn

Obviously, B+ is a Z-matrix and C is a nonnegative matrix of rank 1. We need the following auxiliary result. Lemma 2.1. Let M = (mij ) ∈ Rn×n , and let M = B+ + C, B+ , C be as in (2.1). If M is a DB-matrix, then B+ is a strictly doubly diagonally dominant matrix with positive diagonal elements and an M-matrix, too.

832

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

Proof. It follows from the definition of doubly B-matrix that B+ is a strictly doubly diagonally dominant matrix with positive diagonal elements. Taking into account that a strictly doubly diagonally dominant matrix is a nonsingular H-matrix, one can get that B+ is an H-matrix with positive diagonal elements. Since B+ is a Z-matrix, B+ is also a nonsingular M-matrix.  Pan and Chen give an upper bounds, which are used as proof of our main results, for the infinity norm of the inverse of strictly doubly diagonally dominant matrix in [13] as follows. Lemma 2.2. Let M = (mij ) ∈ Rn×n be a strictly doubly diagonally dominant matrix, Q := {i ∈ N ||mii | > Ri (M )}, |mj1 j1 | − Rj1 (M ) = mini∈Q {|mii | − Ri (M )}, J (M ) := {i ∈ Q ||mii | − Ri (M ) = |mj1 j1 | − Rj1 (M )},

|mjj | + Ri (M ) , i, j ∈ N, |mii ||mjj | − Ri (M )Rj (M ) then the following results hold. α(j, i) :=

(1) M −1 ∞  max j=/ i, α(j, i). i,j∈N

(2) If Q = N, i.e., M be a strictly diagonally dominant matrix, it holds that max α(j, i) j= / i, i,j∈N

= max α(j, j1 )  j= / j1 , j1 ,j∈N

1 minj∈N {|mjj | − Rj (M )}

,

equality holds if and only if one of the following conditions holds. a. |J (M )|  2; b. J (M ) = {j1 } and Rj1 (M )

= 0.

/ N, i.e., there exists i0 ∈ N − Q such that |ai0 i0 |  Ri0 (M ), then it follows that (3) If Q = max α(j, i) j= / i, i,j∈N

⎧ ⎨

⎫ ⎬

= max ⎩max α(j, i0 ), max α(j, j1 ) . j ∈Q

In particular, if |J (M )|  2, it holds that  max α(j, i) j= / i, i,j∈N



j= / j1 , j ∈Q

= max max α(j, i0 ), j ∈Q



1 minj∈Q {|mjj | − Rj (M )}

.

Since a DB-matrix M is a P-matrix, we can apply M to the third inequality of Theorem 2.3 of [8] and obtain

x − x∗ ∞  max n (I − D + DM )−1 ∞ r (x)∞ , d∈[0,1]

where x∗ is the solution of the LCP(M, q), r (x) := min{x, Mx + q}, D = diag(di ) with 0  di  1, and the min operator denotes the componentwise minimum of two vectors. 3. Main results In this section, we provide the bounds for maxd∈[0,1]n (I − D + DM )−1 ∞ when M is an n × n DB-matrix. The bounds can be calculated with O(n2 ) elementary operations. Theorem 3.1. On the assumption that M be as in (2.1). Let

β1 (j, i) =

bjj bii bjj

− Ri (B+ )Rj (B+ )

,

= (mij ) is an n × n DB-matrix and let B+ =: (bij ), i, j ∈ N, C β2 (i) =

Ri (B+ ) bii

,

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

833

:= {i ∈ N ||bii | > Ri (B+ )}, |bj1 j1 | − Rj1 (B+ ) = mini∈Q {|bii | − Ri (B+ )}, − Ri (B+ ) = |bj1 j1 | − Rj1 (B+ )}. Then the following results hold.

J (B+ )

Q

:= {i ∈ Q | |bii |

(1) It holds that max

d∈[0,1]n

(I − D + DM )−1 ∞ ⎛

⎧ ⎨

⎫ ⎬

⎧ ⎨

⎫⎞

⎬ β2 (i) (n − 1) ⎝max max β1 (j, i), 1 + max max , max β2 (i) ⎠ . ⎩ j=/ i, ⎭ ⎩ j=/ i, bjj − β2 (i)Rj (B+ ) i∈N ⎭ i,j∈N i,j∈N

(2) If M is a B-matrix, then it follows that max

d∈[0,1]n

where

(I − D + DM )−1 ∞ (n − 1)η, ⎧ ⎨

⎧ ⎨

⎫ ⎬



⎬ β2 (j1 ) η = max ⎩max β1 (j, j1 ), 1 + max max , β2 (j1 ) . + ⎩ ⎭ ⎭ j= / j1 , j= / j1 , b − β (j )R (B ) jj 2 1 j j ∈N j ∈N

(3) If M is not a B-matrix, there exists i0 ∈ N − Q such that bi0 i0  Ri0 (B+ ), and then it holds that max

d∈[0,1]n

(I − D + DM )−1 ∞ (n − 1) max{η1 , η2 },

where 





⎧ ⎨

⎫ ⎬

⎧ ⎨



β2 (i0 ) η1 = max max β1 (j, i0 ), 1 + max max , β2 (i0 ) , j ∈Q j∈Q bjj − β2 (i0 )Rj (B+ ) ⎫

⎬ β2 (j1 ) η2 = max ⎩max β1 (j, j1 ), 1 + max ⎩max , β2 (j1 ) . ⎭ ⎭ j= / j1 , j= / j1 , b − β (j )R (B+ ) jj 2 1 j j ∈Q j ∈Q In particular, if |J (B+ )|  2, it holds that max

d∈[0,1]n

−1

(I − D + DM )



∞ (n − 1) max η1 ,



1

 min minj∈Q {bjj



− Rj (B+ )}, 1

.

 := I − D + DM is a DB-matrix for Proof. We firstly verify (1). It is straightforward to check that M each diagonal matrix D = diag(di ) with 0  di  1. Note that M = B+ + C , with B+ and C given in (2.1), then we can write  M

= I − D + DM = I − D + D(B+ + C ) = (I − D + DB+ ) + DC .

(3.1)

It follows from Lemma 2.1 that B+ is a strictly doubly diagonally dominant matrix with positive diagonal

elements. Then it is straightforward to check that  B = (bˆ ij ) := I − D + DB+ is also a strictly doubly  = diagonally dominant matrix with positive diagonal elements. Due to (3.1), M B+ C, where  C := DC, and as  B is nonsingular, we can write  −1 M

C ))−1 = (I +  C )−1 B(I +  B −1  B −1  B −1 = (

and thus  −1 ∞  (I +  M C )−1 ∞  B −1  B−1 ∞ .

(3.2)

Now, we first consider the upper bound for  B−1 ∞ . Since  B is a strictly doubly diagonally dominant matrix with positive diagonal elements, then by Lemma 2.2, we have

834

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

 B−1 ∞  max j= / i, i,j∈N

i.e., for di , dj

bˆ jj bˆ ii bˆ jj

+ Ri ( B)

− Ri ( B)Rj ( B)

,

∈ [0, 1],

 B−1 ∞  max j= / i, i,j∈N

where

+ dj bjj + di Ri (B+ ) = max γ (j, i), j= / i, (1 − di + di bii )(1 − dj + dj bjj ) − di Ri (B+ )dj Rj (B+ ) i,j∈N 1 − dj

(3.3)

+ dj bjj + di Ri (B+ ) , i, j ∈ N . (1 − di + di bii )(1 − dj + dj bjj ) − di Ri (B+ )dj Rj (B+ ) 1 − dj

γ (j, i) :=

∈ N be such that γ (j∗ , i∗ ) = max γ (j, i).

Let i∗ , j∗

(3.4)

j= / i, i,j∈N

Then

+ dj∗ bj∗ j∗ + di∗ Ri∗ (B+ ) (1 − di∗ + di∗ bi∗ i∗ )(1 − dj∗ + dj∗ bj∗ j∗ ) − di∗ Ri∗ (B+ )dj∗ Rj∗ (B+ ) 1 − d j∗ + d j ∗ b j∗ j∗ = (1 − di∗ + di∗ bi∗ i∗ )(1 − dj∗ + dj∗ bj∗ j∗ ) − di∗ Ri∗ (B+ )dj∗ Rj∗ (B+ ) di∗ Ri∗ (B+ ) + (1 − di∗ + di∗ bi∗ i∗ )(1 − dj∗ + dj∗ bj∗ j∗ ) − di∗ Ri∗ (B+ )dj∗ Rj∗ (B+ ) = f (dj∗ , di∗ ) + g (di∗ , dj∗ ), 1 − d j∗

γ (j∗ , i∗ ) =

where di∗ , dj∗

∈ [0, 1],

+ d j∗ b j∗ j∗ , (1 − di∗ + di∗ bi∗ i∗ )(1 − dj∗ + dj∗ bj∗ j∗ ) − di∗ Ri∗ (B+ )dj∗ Rj∗ (B+ ) di∗ Ri∗ (B+ ) . g (di∗ , dj∗ ) = (1 − di∗ + di∗ bi∗ i∗ )(1 − dj∗ + dj∗ bj∗ j∗ ) − di∗ Ri∗ (B+ )dj∗ Rj∗ (B+ ) f (dj∗ , di∗ )

1 − dj∗

=

Observe that f (dj∗ , di∗ )  max f (dj , di∗ ) dj ∈[0,1]

= max

dj ∈[0,1]

=

1 d

(1 − di∗ + di∗ bi∗ i∗ ) − di∗ Ri∗ (B+ ) 1−dj +dj j bj

∗ j∗

1

(1 − di∗ + di∗ bi∗ i∗ ) − di∗ Ri∗ (B+ ) bj 1j Rj∗ (B+ ) ∗∗

=

1 − di∗

 max

di ∈[0,1]

1





+ di∗ bi∗ i∗ − Ri∗ (B+ ) bj 1j Rj∗ (B+ ) ∗∗

1 − di



1

.

+ di bi∗ i∗ − Ri∗ (B+ ) bj 1j Rj∗ (B+ ) ∗∗

For 1 − di



1

,

+ di bi∗ i∗ − Ri∗ (B+ ) bj 1j Rj∗ (B+ ) ∗∗

Rj∗ (B+ )

(3.5)

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

835

we consider the function

ϕ(x) = For x

1 1 − x + xa

,

a

> 0.

(3.6)

∈ [0, 1], ϕ(x) > 0, and ϕ (x)  0 if a < 1 otherwise ϕ (x)  0. Thus we get 

max

x∈[0,1]

ϕ(x) =

a < 1; a  1.

1 , a

1,

(3.7)

This, together with B+ being strictly doubly diagonally dominant matrix with positive diagonal entries, implies f (dj∗ , di∗ )  max

di ∈[0,1]



1 − di

= max

1





+ di bi∗ i∗ − Ri∗ (B+ ) bj 1j Rj∗ (B+ ) ∗∗



b j ∗ j∗

b i∗ i ∗ b j∗ j∗

− Ri∗ (B+ )Rj∗ (B+ )

,1

.

(3.8)

On the other hand, g (di∗ , dj∗ )  max g (di , dj∗ ) di ∈[0,1]

= max

di ∈[0,1]

di Ri∗ (B+ )

(1 − di + di bi∗ i∗ )(1 − dj∗ + dj∗ bj∗ j∗ ) − di Ri∗ (B+ )dj∗ Rj∗ (B+ ) Ri∗ (B+ )

= max  1 di ∈[0,1]

=

di



− 1 + bi∗ i∗ (1 − dj∗ + dj∗ bj∗ j∗ ) − Ri∗ (B+ )dj∗ Rj∗ (B+ ) Ri∗ (B+ )

+ dj∗ bj∗ j∗ ) − Ri∗ (B+ )dj∗ Rj∗ (B+ ) Ri∗ (B+ )  max dj ∈[0,1] bi i (1 − dj + dj bj j ) − Ri (B+ )dj Rj (B+ ) ∗∗ ∗∗ ∗ ∗ bi∗ i∗ (1 − dj∗

= max

dj ∈[0,1]

1 − dj



Ri∗ (B+ ) bi∗ i∗

.

R i∗ ( B + ) Rj∗ (B+ ) bi∗ i∗

+ d j b j∗ j∗ −

By (3.6), (3.7) and B+ being strictly doubly diagonally dominant matrix with positive diagonal entries, this implies g (di∗ , dj∗ )  max

dj ∈[0,1]



= max

1 − dj



Ri∗ (B+ ) bi∗ i∗

+ d j b j∗ j∗ − Ri∗ (B+ )

b i ∗ i∗ b j∗ j∗



Ri∗ (B+ ) Rj∗ (B+ ) bi∗ i∗

− Ri∗ (B+ )Rj∗ (B+ )

,

Ri∗ (B+ )



b i∗ i∗

Therefore, it follows from (3.5), (3.8), (3.9) and i∗ , j∗ ∈ N that   b j ∗ j∗ γ (j∗ , i∗ )  max ,1 bi∗ i∗ bj∗ j∗ − Ri∗ (B+ )Rj∗ (B+ )   Ri∗ (B+ ) Ri∗ (B+ ) + max , bi∗ i∗ bj∗ j∗ − Ri∗ (B+ )Rj∗ (B+ ) b i∗ i∗

.

(3.9)

836

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

 max

⎧ ⎨ max



j= / i, i,j∈N

⎫ ⎬

bjj

,1 − Ri (B+ )Rj (B+ ) ⎭

bii bjj

(3.10)

⎫ Ri (B+ ) ⎬ + max ⎩max , max . j= / i, b b − R (B+ )R (B+ ) i∈N bii ⎭ ii jj i j ⎧ ⎨

Ri (B+ )

i,j∈N

B−1 ∞ as follows: Hence, by (3.3), (3.4) and (3.10) we have an upper bound for  ⎧ ⎫ ⎨ ⎬ bjj  B−1 ∞  max max ,1 ⎩ j=/ i, bii bjj − Ri (B+ )Rj (B+ ) ⎭ i,j∈N

⎧ ⎨ + max ⎩max j= / i, b b ii jj i,j∈N

⎫ Ri (B+ ) ⎬ . , max − Ri (B+ )Rj (B+ ) i∈N bii ⎭ Ri (B+ )

(3.11)

We can get the following formula: C )−1 ∞  n − 1, B −1  (I + 

(3.12)

whose proof is similar to that of Theorem 2.2 of [6]. For completeness, we give the proof as follows. B is also an nonsingular Notice that the matrix B+ of (3.1) is an nonsingular M-matrix and so  M-matrix by Theorem 2.3 of Chapter 6 of [3]. Thus  B−1 =: (b˜ )ij  0 for all i, j ∈ N. Observe that C is a nonnegative matrix of rank 1, we deduce that it also holds for  C = DC and we can write it as  C = (c1 , . . . , cn )T e, where e = (1, . . . , 1) and ci = di ri  0. Then we can write ⎛ ⎞ w1 ··· w1 1 + w1 ⎜ w2 1 + w2 ··· w2 ⎟ ⎜ ⎟ I + C =⎜ B −1  .. .. ⎟ .. .. ⎝ . . . ⎠ . wn wn · · · 1 + wn and



1 − 1+n1 w i =1 i

B −1  (I +  C )−1 =

where wi

:=

⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝

w

− 1+wn2 wi i =1 .. . − 1+wnn wi i =1

n

˜ j=1 bij cj  0, i

− 1+wn1

i =1

wi

1 − 1+n2 w i =1 i w

− 1+

.. .

wn  n

i =1

wi

··· ··· ..

.

···

− 1+wn1



i =1

wi

⎟ ⎟

− 1+wn2 wi ⎟ ⎟ ⎟, i =1 ⎟ .. ⎟ ⎠ . w n 1 − 1 + n w i i =1

∈ N. Therefore, we can conclude that

(I +  C )−1 ∞ = 1 + B −1 

(n − 2) maxi wi  1 + ( n − 2 ) = n − 1.  1 + ni=1 wi

Hence, by (3.1), (3.2), (3.11) and (3.12) the result (1) holds. Now, we consider (2). If M is a B-matrix, then B+ is a strictly diagonally dominant matrix with positive diagonal entries and so  B is also a strictly diagonally dominant matrix with positive diagonal entries, that is, Q = N, it follows from (2) of Lemma 2.2 and (3.3) that B−1 ∞  max  j= / j1 , j1 ,j∈N

+ dj bjj + dj1 Rj1 (B+ ) = max γ (j, j1 ), j= / j1 , (1 − dj1 + dj1 bj1 j1 )(1 − dj + dj bjj ) − dj1 Rj1 (B+ )dj Rj (B+ ) j ,j∈N 1 − dj

By the same principle of (3.4)–(3.12) it is not difficult to obtain that max

d∈[0,1]n

(I − D + DM )−1 ∞ (n − 1)η,

1

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

837

where ⎧ ⎨

η = max max ⎩ j= / j1 , j ∈N

⎧ ⎨

⎫ ⎬

bjj

bj1 j1 bjj

,1 − Rj1 (B+ )Rj (B+ ) ⎭

⎫ Rj1 (B+ ) ⎬ + max ⎩max , . + + j= / j1 , b b j1 j 1 ⎭ j1 j1 bjj − Rj1 (B )Rj (B ) Rj1 (B+ )

j ∈N

Thus the result (2) follows. Next, we turn to (3). If M is a DB-matrix but not a B-matrix, by Proposition 2.1 in [6], B+ is a strictly doubly diagonally dominant matrix with positive diagonal entries but not a strictly diagonally dominant matrix with positive diagonal entries, that is, Q = / N and there exists i0 ∈ N − Q such that bi0 i0  Ri0 (B+ ), then according to (3) of Lemma 2.2 and (3.3) we have that ⎫ ⎧ ⎬ ⎨ − 1 B ∞  max max γ (j, i0 ), max γ (j, j1 ) .  ⎭ ⎩ j ∈Q j= / j1 , j ∈Q

Then by the same principle of (3.1)–(3.12) it is not difficult to obtain that max

d∈[0,1]n

(I − D + DM )−1 ∞ (n − 1) max{η1 , η2 },

where 







η1 = max max β1 (j, i0 ), 1 + max max ⎧ ⎨

j ∈Q

j ∈Q

⎧ ⎨

⎫ ⎬

β2 (i0 ) , β2 (i0 ) , bjj − β2 (i0 )Rj (B+ )

(3.13)



⎬ β2 (j1 ) η2 = max ⎩max β1 (j, j1 ), 1 + max max , β (j ) . ⎩ j=/ j1 , bjj − β2 (j1 )Rj (B+ ) 2 1 ⎭ ⎭ j= / j1 , j ∈Q j ∈Q In particular, if |J (B+ )|  2, it is not difficult to get by (3) of Lemma 2.2, (3.13) and the bound of Theorem 2.2 of [6] that   1   . max (I − D + DM )−1 ∞ (n − 1) max η1 , d∈[0,1]n min minj∈Q {bjj − Rj (B+ )}, 1 We complete the proof.



Remark 3.2. For the case that M is a B-matrix, the bound of the result (2) is smaller than the bound of Theorem 2.2 of [6] in some cases. For instance, Example 4.3. Hence, according to the result (2) and the bound of Theorem 2.2 of [6], a new bound for the case that M is a B-matrix is as follows:   n−1 −1   , max (I − D + DM ) ∞  min (n − 1)η, d∈[0,1]n min minj∈N {bjj − Rj (B+ )}, 1 where

⎧ ⎨

⎫ ⎬



⎧ ⎨

⎬ β2 (j1 ) η = max ⎩max β1 (j, j1 ), 1⎭ + max ⎩max , β2 (j1 ) . ⎭ j= / j1 , j= / j1 , b − β (j )R (B+ ) jj 2 1 j j ∈N j ∈N Remark 3.3. If M is also a Z-matrix, that is, B+ max

d∈[0,1]n

−1

(I − D + DM )

−1

∞ = B

= M and C is the null matrix, by (3.1) one can obtain

∞ .

838

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

Thus the bounds of Theorem 3.1 transform into the lower bounds (n  3), which do not contain the factor n − 1, corresponding to Theorem 3.1 as follows. (1) It holds that max

d∈[0,1]n



(I − D + DM )−1 ∞ ⎧ ⎨

⎫ ⎬

⎧ ⎨

⎫⎞

⎬ β2 (i)  ⎝max max β1 (j, i), 1 + max max , max β2 (i) ⎠ . + ⎩ j=/ i, ⎭ ⎩ j=/ i, bjj − β2 (i)Rj (B ) i∈N ⎭ i,j∈N i,j∈N (2) It follows that max

d∈[0,1]n

(I − D + DM )−1 ∞  η,

where

⎧ ⎨

⎫ ⎬



⎧ ⎨

⎬ β2 (j1 ) η = max ⎩max β1 (j, j1 ), 1⎭ + max ⎩max , β2 (j1 ) . ⎭ j= / j1 , j= / j1 , b − β (j )R (B+ ) 2 1 j jj j ∈N j ∈N (3) It follows that max

d∈[0,1]n

(I − D + DM )−1 ∞  max{η1 , η2 },

where 





⎧ ⎨

⎫ ⎬

⎧ ⎨



β2 (i0 ) η1 = max max β1 (j, i0 ), 1 + max max , β2 (i0 ) , j ∈Q j∈Q bjj − β2 (i0 )Rj (B+ ) ⎫

⎬ β2 (j1 ) η2 = max ⎩max β1 (j, j1 ), 1⎭ + max ⎩max , β2 (j1 ) . ⎭ j= / j1 , j= / j1 , b − β (j )R (B+ ) jj 2 1 j j ∈Q j ∈Q In particular, if |J (B+ )|  2, it holds that max

d∈[0,1]



(I − D + DM )−1 ∞  max η1 , n





1

min minj∈Q {bjj

− Rj (B+ )}, 1



.

4. Numerical examples In this section we give some examples that are used to illustrate our theoretical results. The norm

 · ∞ in Example 4.2 is obtained by using Matlab 7.1.

Example 4.1. Let us first consider the following P-matrix from [5,8,7]   1 −4 M1 = . 5 7 +

We write M1 as M1 = B1 + C1 , where     1 −4 0 0 + , , C1 = B1 = 5 5 0 2 +

B1 is a strictly doubly diagonally dominant matrix with positive diagonal entries and so M1 is a DB-matrix but neither a B-matrix nor an H-matrix. By simple computations, we obtain that

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

max

j= / i, i,j∈{1,2}

β1 (j, i) = 1,

max

i∈{1,2}

β2 (i) = 4,

max

j= / i, i,j∈{1,2}

bjj

839

β2 (i) = 2, − β2 (i)Rj (B1+ )

and thus the upper bound (1) of Theorem 3.1 is 5. Example 3.1 of [8] by solving an optimization problem show max

d∈[0,1]n

(I − D + DM1 )−1 ∞ = 5.

Hence, this indicates that the upper bound of Theorem 3.1 is sharp for this example and is obtained with small computational cost. Final remarks in [7] cited the LCP (M1 , q) and the error bounds (2.9) of [7] for the LCP (M, q) with M being P-matrix but not H-matrix with positive diagonal entries have not been obtained so far by solving a system of linear equations. Example 4.2. Let us now consider the matrix ⎛ ⎞ 10 −4 −6 ⎝ 12 2 ⎠, M2 = −7 −8 1 11 which is simultaneously a DB-matrix and an H-matrix but not a B-matrix. Now, we use the upper + bound of Theorem 3.1 to estimate maxd∈[0,1]n (I − D + DM2 )−1 ∞ . We write M2 as M2 = B2 + C2 , where ⎛ ⎛ ⎞ ⎞ 10 0 0 0 −4 −6 + 10 0 ⎠ , C2 = ⎝2 2 2⎠ . B2 = ⎝−9 1 1 1 −9 0 10 It follows from some simple calculations that max

j∈{2,3}

β1 (j, 1) = 1, β2 (1) = 1,

β2 (1) 1   = 1. = 1, + + j∈{2,3} bjj − β2 (1)Rj (B ) min minj∈{2,3} {bjj − Rj (B2 )}, 1 2 max

So the upper bound (3) of Theorem 3.1 is 4, which is considerably smaller than the bound ⎛ ⎞⎛ ⎞  0.4194 0.1613 0.2581 10 0 0    −1  ⎝ ⎠ ⎝ 0 12 0 ⎠ M2  max(∧, I )∞ =  0.3000 0.2000 0.2000  = 8.9677  0.3323 0.1355 0.2968 0 0 11 ∞ for H-matrices given by formula (2.4) of [8]. Example 4.3. Let us assume that k   k − ka . M3 = 0 k +

> 0, a > 1 and

+

+

We write M3 as M3 = B3 + C3 , where B3 = M3 and C3 is the null matrix, Obviously, B3 is a strictly diagonally dominant matrix with positive diagonal entries and so M3 is a B-matrix and an H-matrix. By simple computations, we get the result (2) of Theorem 3.1 given by     1 1 1 η = max , 1 + max , k ak a and the bound of Theorem 2.2 of [6] is max{ (a−a1)k , 1}. It is not difficult to verify that when 0 a2

a 2 −1

, 

η < max

a

(a − 1)k

 ,1 ,


840

P.-F. Dai / Linear Algebra and its Applications 434 (2011) 830–840

that is, the result (2) of Theorem 3.1 is smaller than the bound of Theorem 2.2 of [6] in this case. Furthermore, it is interesting that for all k > 0, the bounds of the result (2) of Remark 3.3 is equal to the bound (2.3) of [14].

Acknowledgments The author wish to thank the referees for their corrections and suggestions on an earlier version of the manuscript.

References [1] J.M. Peña, A class of P-matrices with applications to the localization of the eigenvalues of a real matrix, SIAM J. Matrix Anal. Appl. 22 (2001) 1027–1037. [2] J.M. Peña, On an alternative to Gershgorin circles and ovals of Cassini, Numer. Math. 95 (2003) 337–345. [3] A. Berman, R. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York, 1979. [4] Cottle, J.S. Pang, R.E. Stone, The Linear Complementarity Problem, Academic Press, San Diego, 1992. [5] U. Schäer, A linear complementarity problem with a P-matrix, SIAM Rev. 46 (2004) 189–201. [6] M. García-Esnaola, J.M. Peña, Error bounds for linear complementarity problems for B-matrices, Appl. Math. Lett. 22 (2009) 1071–1075. [7] Z.Y. Wang, Y.X. Yuan, Componentwise error bounds for linear complementarity problems, IMA J. Numer. Anal. 4 (2009) 1–10. [8] X.J. Chen, S.H. Xiang, Computation of error bounds for P-matrix linear complementarity problems, Math. Program. Ser. A 106 (2006) 513–525. [9] X.J. Chen, S.H. Xiang, Perturbation bounds of P-matrix linear complementarity problems, SIAM J. Optim. 18 (2007) 1250– 1265. [10] R. Mathias, J.S. Pang, Error bounds for the linear complementarity problem with a P-matrix, Linear Algebra Appl. 132 (1990) 123–136. [11] R. Brualdi, H. Ryser, Combinatorial Matrix Theory, Encyclopedia of Mathematics and Its Applications, vol. 39, Cambridge University Press, 1991. [12] B. Li, M. Tsatsomeros, Doubly diagonally dominant matrices, Linear Algebra Appl. 261 (1997) 221–235. [13] S.Z. Pan, S.C. Chen, An upper bound for A−1  of strictly doubly diagonally dominant matrices, J. Fuzhou Univ. Nat. Sci. Ed. 36 (2008) 639–642. (in Chinese). [14] M. García-Esnaola, J.M. Peña, A comparison of error bounds for linear complementarity problems of H-matrices, Linear Algebra Appl. 433 (2010) 956–964.