
In this paper, we introduce a new subclass of P-matrices called Cvetković-Kostić-Varga type B-matrices (CKV-type B-matrices), which contains DZ-type-B-matrices as a special case, and present an infinity norm bound for the inverse of CKV-type B-matrices. Based on this bound, we also give an error bound for linear complementarity problems of CKV-type B-matrices. It is proved that the new error bound is better than that provided by Li et al. [
Citation: Xinnian Song, Lei Gao. CKV-type B-matrices and error bounds for linear complementarity problems[J]. AIMS Mathematics, 2021, 6(10): 10846-10860. doi: 10.3934/math.2021630
[1] | Yuanjie Geng, Deshu Sun . Error bounds for linear complementarity problems of strong $ SDD_{1} $ matrices and strong $ SDD_{1} $-$ B $ matrices. AIMS Mathematics, 2023, 8(11): 27052-27064. doi: 10.3934/math.20231384 |
[2] | Yingxia Zhao, Lanlan Liu, Feng Wang . Error bounds for linear complementarity problems of $ SD{{D}_{1}} $ matrices and $ SD{{D}_{1}} $-$ B $ matrices. AIMS Mathematics, 2022, 7(7): 11862-11878. doi: 10.3934/math.2022662 |
[3] | Dizhen Ao, Yan Liu, Feng Wang, Lanlan Liu . Schur complement-based infinity norm bounds for the inverse of $ S $-Sparse Ostrowski Brauer matrices. AIMS Mathematics, 2023, 8(11): 25815-25844. doi: 10.3934/math.20231317 |
[4] | Lanlan Liu, Pan Han, Feng Wang . New error bound for linear complementarity problem of $ S $-$ SDDS $-$ B $ matrices. AIMS Mathematics, 2022, 7(2): 3239-3249. doi: 10.3934/math.2022179 |
[5] | Hongmin Mo, Yingxue Dong . A new error bound for linear complementarity problems involving $ B- $matrices. AIMS Mathematics, 2023, 8(10): 23889-23899. doi: 10.3934/math.20231218 |
[6] | Lanlan Liu, Yuxue Zhu, Feng Wang, Yuanjie Geng . Infinity norm bounds for the inverse of $ SDD_1^{+} $ matrices with applications. AIMS Mathematics, 2024, 9(8): 21294-21320. doi: 10.3934/math.20241034 |
[7] | Deshu Sun . Note on error bounds for linear complementarity problems involving $ B^S $-matrices. AIMS Mathematics, 2022, 7(2): 1896-1906. doi: 10.3934/math.2022109 |
[8] | Maja Nedović, Dunja Arsić . New scaling criteria for $ H $-matrices and applications. AIMS Mathematics, 2025, 10(3): 5071-5094. doi: 10.3934/math.2025232 |
[9] | Xiaoyong Chen, Yating Li, Liang Liu, Yaqiang Wang . Infinity norm upper bounds for the inverse of $ SDD_1 $ matrices. AIMS Mathematics, 2022, 7(5): 8847-8860. doi: 10.3934/math.2022493 |
[10] | Xiaodong Wang, Feng Wang . Infinity norm upper bounds for the inverse of $ {SDD_k} $ matrices. AIMS Mathematics, 2023, 8(10): 24999-25016. doi: 10.3934/math.20231276 |
In this paper, we introduce a new subclass of P-matrices called Cvetković-Kostić-Varga type B-matrices (CKV-type B-matrices), which contains DZ-type-B-matrices as a special case, and present an infinity norm bound for the inverse of CKV-type B-matrices. Based on this bound, we also give an error bound for linear complementarity problems of CKV-type B-matrices. It is proved that the new error bound is better than that provided by Li et al. [
Given an n×n real matrix A and a vector q∈Rn, the linear complementarity problem is to find a vector x∈Rn satisfying
x≥0,Ax+q≥0,(Ax+q)Tx=0 | (1.1) |
or to show that no such vector x exists. We denote the problem (1.1) and its solution by LCP(A,q) and x∗, respectively. The LCP(A,q), as one of the fundamental problems in optimization and mathematical programming, has various applications in the quadratic programming, the optimal stopping, the Nash equilibrium point of a bimatrix game, the network equilibrium problem, the contact problem, and the free boundary problem for journal bearing, for details, see [1,2,26].
It is well known that the LCP(A,q) has a unique solution x∗ for any q∈Rn if and only if A is a P-matrix [2]. Here, a real square matrix A is called a P-matrix if all its principal minors are positive. For this case, an important topic in the study of the LCP(A,q) concerns the bound of ||x−x∗||∞, since it can be used as termination criteria for iterative algorithms and can be used to measure the sensitivity of the solution of LCP(A,q) in response to a small perturbation, e.g., [18,19,28,34]. When the matrix A is a P-matrix, Chen and Xiang [3] gave the following error bound for the LCP(A,q):
||x−x∗||∞≤maxd∈[0,1]n||(I−D+DA)−1||∞||r(x)||∞, | (1.2) |
where D=diag(di) with 0≤di≤1 for each i∈N:={1,…,n}, d=(d1,d2,…,dn)T∈[0,1]n, and r(x)=min{x,Ax+q} in which the min operator denotes the componentwise minimum of two vectors. Furthermore, to avoid the high-cost computations of the inverse matrix in (1.2), some easily computable bounds for the LCP(A,q) were derived for the different subclass of P-matrices, such as, B-matrices [10,20], doubly B-matrices [6], SB-matrices [7,8], MB-matrices [4], B-Nekrasov matrices [11,21], weakly chained diagonally dominant B-matrices [22,32,35], BRπ-matrices [12,13,27], and so on [9,14,15,16,17,23,36].
Recently, Li et al. [24] presented a new subclass of P-matrices called Dashnic-Zusmanovich type B-matrices (DZ-type-B-matrices), and provided an error bound for the LCP(A,q) when A is a DZ-type-B-matrix.
Definition 1.1. [33] A matrix A=[aij]∈Cn×n, with n≥2, is a DZ-type matrix if for each i∈N, there exists j∈N,j≠i such that
(|aii|−rji(A))|ajj|>|aij|rj(A), |
where rji(A)=ri(A)−|aij| and ri(A)=∑j∈N∖{i}|aij|.
Definition 1.2. [24] Let A=[aij]∈Cn×n be written in the form
A=B++C, | (1.3) |
where
B+=[bij]=[a11−r+1⋯a1n−r+1⋮⋱⋮an1−r+n⋯ann−r+n],C=[r+1⋯r+1⋮⋱⋮r+n⋯r+n], |
and r+i:=max{0,aij|j≠i}. Then, A is called a DZ-type-B-matrix if B+ is a DZ-type matrix with all positive diagonal entries.
Theorem 1.1. [24,Theorem 6] Let A=[aij]∈Rn×n be a DZ-type-B-matrix, and B+=[bij] be the matrix of (1.3). Then,
maxd∈[0,1]n||(I−D+DA)−1||∞≤(n−1)⋅maxi∈Nminj∈γi(B+)ζij(B+), | (1.4) |
where
γi(B+):={j∈N∖{i}:(|bii|−rji(B+))|bjj|>|bij|rj(B+)}, |
and
ζij(B+):=(bii−rji(B+))bjjmax{1bii−rji(B+),1}+bjj|bij|max{1bjj,1}(bii−rji(B+))bjj−|bij|rj(B+). |
Very recently, Cvetković et al. [5] proposed a new subclass of H-matrices called CKV-type matrices, which generalizes CKV matrices (also known as Σ-SDD matrices in the literature) and DZ-type matrices.
Definition 1.3. [5] A matrix A=[aij]∈Cn×n, with n≥2, is called a CKV-type matrix if NA=∅ or S⋆i(A) is not empty for all i∈NA, where NA:={i∈N:|aii|≤ri(A)} and
S⋆i(A):={S∈Σ(i):|aii|>rSi(A),andforallj∈¯S(|aii|−rSi(A))(|ajj|−r¯Sj(A))>r¯Si(A)rSj(A)} |
with Σ(i):={S⊊N:i∈S} and rSi(A):=∑j∈S∖{i}|aij|.
Motivated by the definition of DZ-type-B-matrices, two meaningful questions naturally arise: can we get a more general subclass of P-matrices using CKV-type matrices, and can we obtain a sharper error bound than the bound (1.4) for the linear complementarity problem of DZ-type-B-matrices? To answer these questions, in Section 2, we present a new class of matrices: CKV-type B-matrices, and prove that it is a subclass of P-matrices containing DZ-type-B-matrices and SB-matrices. Meanwhile, we give an upper bound for the infinity norm for the inverse of CKV-type B-matrices. In Section 3, we give an error bound for the LCP(A,q) when A is a CKV-type B-matrix, consequently, for the LCP(A,q) when A is a DZ-type-B-matrix, and some comparisons with other results are also discussed. Finally, in Section 4, numerical examples are given to illustrate the corresponding theoretical results.
Using CKV-type matrices, we first give the definition of CKV-type B-matrices.
Definition 2.1. A matrix A∈Rn×n is called a CKV-type B-matrix if B+ given by (1.3) is a CKV-type matrix with positive diagonal entries.
To show that a CKV-type B-matrix is a P-matrix, we recall the following results.
Lemma 2.1. [5,Theorem 6] Every CKV-type matrix is a nonsingular H-matrix.
Lemma 2.2. [29,Corollary 2.4] If A is a real nonsingular M-matrix and P is a nonnegative matrix with rank(P) = 1, then A+P is a P-matrix.
Proposition 2.1. If A is a CKV-type B-matrix, then A is a P-matrix.
Proof. Let A be written in the form A=B++C as shown in (1.3). It follows from (1.3) and Definition 2.1 that B+ is a Z-matrix (all non-diagonal entries are non-positive [1]) with positive diagonal entries and C is a nonnegative matrix of rank 1. By Lemma 2.1, we know that B+ is a nonsingular H-matrix, and thus the conclusion follows from Lemma 2.2.
As shown in [5,33], the relations of strictly diagonally dominant (SDD) matrices, doubly strictly diagonally dominant (DSDD) matrices, S-strictly diagonally dominant (S-SDD) matrices, DZ-type matrices, and CKV-type matrices are:
● {SDD}⊆{DSDD}⊆{DZ}⊆{S−SDD} and {SDD}⊆{DZ-type};
● {DSDD}⊈{DZ-type} and {DZ-type} ⊈ {DSDD};
● {DZ}⊈{DZ-type} and {DZ-type} ⊈ {DZ};
● {S-SDD}⊆{CKV -type} and {DZ-type} ⊆ { CKV-type}.
According to [24] and the above relations, we give a figure to illustrate the relations among B-matrices, DZ-type-B-matrices, DB-matrices, SB-matrices, CKV-type B-matrices. Here, the notions of B-matrices, DB-matrices, and of SB-matrices are listed as follows. Let A=B++C∈Rn×n, where B+ is defined by (1.3). Then, A is called
● a B-matrix if B+ is SDD with all positive diagonal entries [30];
● a DB-matrix if B+ is DSDD with all positive diagonal entries [29];
● a SB-matrix if B+ is S-SDD with all positive diagonal entries for a given non-empty proper subset S of N [25].
Next, we give a sufficient and necessary condition for a CKV-type B-matrix. Before that, a lemma is needed.
Lemma 2.3. [5,Remark 9] A matrix A=[aij]∈Cn×n, with n≥2, is called a CKV-type matrix if S⋆i(A) given by Definition 1.3 is not empty for all i∈N. Especially, if A is an SDD matrix, then for all i∈N, all proper subsets S containing i belong to S⋆i(A).
Proposition 2.2. Given any diagonal matrix D=diag(d1,d2,…,dn) with di∈[0,1] for all i∈N, and let I be the identity matrix, then A is a CKV-type B-matrix if and only if I−D+DA is a CKV-type B-matrix.
Proof. Sufficiency is clearly established. We next show the necessity. Suppose A=[aij]∈Rn×n is a CKV-type B-matrix. Then, A=B++C, where B+ is the matrix of (1.3). Let ¯A:=I−D+DA=[ˉaij] and ¯A:=I−D+DA=¯B++¯C, where
¯B+=[ˉa11−ˉr+1⋯ˉa1n−ˉr+1⋮⋱⋮ˉan1−ˉr+n⋯ˉann−ˉr+n],¯C=[ˉr+1⋯ˉr+1⋮⋱⋮ˉr+n⋯ˉr+n], |
and ˉr+i:=max{0,ˉaij|j≠i}.
Note that
ˉaij={1−di+diaii,i=j,diaij,i≠j. |
It follows that
ˉr+i:=max{0,ˉaij|j≠i}=max{0,diaij|j≠i}=dimax{0,aij|j≠i}=dir+i, | (2.1) |
and
ˉaij−ˉr+i={1−di+di(aii−r+i)i=j,di(aij−r+i),i≠j. | (2.2) |
Since A=B++C, it holds that
¯A=I−D+DA=I−D+D(B++C)=(I−D+DB+)+DC. |
Note that B+=[bij] and bij=aij−r+i. Hence, from (2.1) and (2.2), we easily obtain that
¯B+=I−D+DB+and¯C=DC. |
Let ¯B+=[ˉbij]. Then,
ˉbij={1−di+dibii,i=j,dibij,i≠j. |
Since A is a CKV-type B-matrix, then B+=[bij] is a CKV-type matrix with positive diagonal entries. Thus, by Lemma 2.3, it follows that for each i∈N, there exists S∈S⋆i(B+), which implies that
{|bii|>rSi(B+),(|bii|−rSi(B+))(|bjj|−r¯Sj(B+))>r¯Si(B+)rSj(B+)forallj∈¯S. | (2.3) |
Hence, for each i∈N, it follows from (2.3) that
ˉbii−rSi(¯B+)=1−di+di(bii−rSi(B+))>0, |
and that for all j∈¯S, if di≠0 and dj≠0, then
(|ˉbii|−rSi(¯B+))(|ˉbjj|−r¯Sj(¯B+))=[1−di+di(bii−rSi(B+))][1−dj+dj(bjj−r¯Sj(B+))]≥di(bii−rSi(B+))dj(bjj−r¯Sj(B+))>dir¯Si(B+)djrSj(B+)=r¯Si(¯B+)rSj(¯B+), |
and if di=0 or dj=0, then
(|ˉbii|−rSi(¯B+))(|ˉbjj|−r¯Sj(¯B+))=[1−di+di(bii−rSi(B+))][1−dj+dj(bjj−r¯Sj(B+))]>0=r¯Si(¯B+)rSj(¯B+). |
These mean that S∈S⋆i(¯B+) for each i∈N. Therefore, from Definition 1.3, ¯B+ is a CKV-type matrix with positive diagonal entries, and consequently, ¯A=I−D+DA is a CKV-type B-matrix from Definition 2.1.
In the following, we give an infinity norm bound for the inverse of CKV-type B-matrices. First, two lemmas are listed.
Lemma 2.4. [5] Let A=[aij]∈Cn×n,n≥2, be a CKV-type matrix. Then
||A−1||∞≤maxi∈NminS∈S⋆i(A)maxj∈¯SβSij(A), |
where S⋆i(A) is given by Definition 1.3, and
βSij(A)=|ajj|−r¯Sj(A)+r¯Si(A)(|aii|−rSi(A))(|ajj|−r¯Sj(A))−r¯Si(A)rSj(A). |
Lemma 2.5. [11] Suppose P=(p1,…,pn)Te, where e=(1,…,1) and pi≥0 for all i∈N, then
||(I+P)−1||∞≤n−1. |
Theorem 2.1. Let A=[aij]∈Rn×n,n≥2, be a CKV-type B-matrix, and B+=[bij] be the matrix of (1.3). Then
||A−1||∞≤(n−1)⋅maxi∈NminS∈S⋆i(B+)maxj∈¯SβSij(B+), |
where S⋆i(B+) is defined as in Definition 1.3, and
βSij(B+)=|bjj|−r¯Sj(B+)+r¯Si(B+)(|bii|−rSi(B+))(|bjj|−r¯Sj(B+))−r¯Si(B+)rSj(B+). |
Proof. Since A is a CKV-type B-matrix, so B+ is a CKV-type matrix with positive diagonal entries and also a Z-matrix. By Corollary 4 of [31], we know that B+ is an M-matrix and thus (B+)−1 is nonnegative. Hence, from A=B++C in which B+ and C are given by (1.3), we have
A−1=(B+(I+(B+)−1C))−1=(I+(B+)−1C)−1(B+)−1, |
which implies that
||A−1||∞≤||(I+(B+)−1C)−1||∞⋅||(B+)−1||∞. | (2.4) |
Note that C=(r+1,…,r+n)Te is nonnegative. Therefore, (B+)−1C can be written as (p1,…,pn)Te, where pi≥0 for all i∈N. By Lemma 2.5, we get
||(I+(B+)−1C)−1||∞≤n−1. | (2.5) |
Since B+ is a CKV-type matrix, it follows from Lemma 2.4 that
||(B+)−1||∞≤maxi∈NminS∈S⋆i(B+)maxj∈¯SβSij(B+). | (2.6) |
Hence, from (2.4), (2.5), and (2.6), the conclusion follows.
Based on Theorem 2.1, we give in this section an upper bound of maxd∈[0,1]n||(I−D+DA)−1||∞ when A is a CKV-type B-matrix, and give some comparisons with other results. Before that, a useful lemma is needed.
Lemma 3.1. [20,Lemma 3] Let γ>0 and η≥0. Then for any x ∈[0,1],
11−x+γx≤1min{γ,1} |
and
ηx1−x+γx≤ηγ. |
Theorem 3.1. Let A=[aij]∈Rn×n,n≥2, be a CKV-type B-matrix, and B+=[bij] be the matrix of (1.3). Then
maxd∈[0,1]n||(I−D+DA)−1||∞≤(n−1)⋅maxi∈NminS∈S⋆i(B+)maxj∈¯SαSij(B+), | (3.1) |
where S⋆i(B+) is defined as in Definition 1.3, and
αSij(B+)=(bii−rSi(B+))(bjj−r¯Sj(B+))max{1bii−rSi(B+),1}+(bjj−r¯Sj(B+))r¯Si(B+)max{1bjj−r¯Sj(B+),1}(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+). |
Proof. Since A is a CKV-type B-matrix, by Proposition 2.2, it follows that I−D+DA is also a CKV-type B-matrix. Taking into account that A=B++C in which B+ and C are defined as (1.3), then
I−D+DA=I−D+D(B++C)=I−D+DB++DC. |
Denote ¯B+:=I−D+DB+=[¯bij] and ¯C=DC. Then, from Theorem 2.1, we have
||(I−D+DA)−1||∞≤(n−1)⋅maxi∈NminS∈S⋆i(¯B+)maxj∈¯SβSij(¯B+). | (3.2) |
By Lemma 3.1, it follows that for all i∈N,j∈¯S,
βSij(¯B+)=|ˉbjj|−r¯Sj(¯B+)+r¯Si(¯B+)(|ˉbii|−rSi(¯B+))(|ˉbjj|−r¯Sj(¯B+))−r¯Si(¯B+)rSj(¯B+)=1−dj+dj(bjj−r¯Sj(B+))+dir¯Si(B+)[1−di+di(bii−rSi(B+))][1−dj+dj(bjj−r¯Sj(B+))]−dir¯Si(B+)djrSj(B+)=11−di+di(bii−rSi(B+))+dir¯Si(B+)[1−di+di(bii−rSi(B+))][1−dj+dj(bjj−r¯Sj(B+))]1−dir¯Si(B+)djrSj(B+)[1−di+di(bii−rSi(B+))][1−dj+dj(bjj−r¯Sj(B+))]≤max{1bii−rSi(B+),1}+max{1bjj−r¯Sj(B+),1}r¯Si(B+)bii−rSi(B+)1−r¯Si(B+)bii−rSi(B+)rSj(B+)bjj−r¯Sj(B+)=(bii−rSi(B+))(bjj−r¯Sj(B+))max{1bii−rSi(B+),1}+(bjj−r¯Sj(B+))r¯Si(B+)max{1bjj−r¯Sj(B+),1}(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+)=:αSij(B+). |
Furthermore, by the proof of Proposition 2.2, S⋆i(B+)⊆S⋆i(¯B+) for each i∈N. Thus,
maxi∈NminS∈S⋆i(¯B+)maxj∈¯SβSij(¯B+)≤maxi∈NminS∈S⋆i(B+)maxj∈¯SαSij(B+). | (3.3) |
Hence, the conclusion follows from (3.2) and (3.3).
Remark 3.1. Note that, if bii−rSi(B+)≤1 and bjj−r¯Sj(B+)≤1, then
αSij(B+)=bjj−r¯Sj(B+)+r¯Si(B+)(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+); |
If bii−rSi(B+)>1 and bjj−r¯Sj(B+)≤1, then
αSij(B+)=(bii−rSi(B+))(bjj−r¯Sj(B+))+r¯Si(B+)(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+); |
If bii−rSi(B+)≤1 and bjj−r¯Sj(B+)>1, then
αSij(B+)=bjj−r¯Sj(B+)+(bjj−r¯Sj(B+))r¯Si(B+)(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+); |
If bii−rSi(B+)>1 and bjj−r¯Sj(B+)>1, then
αSij(B+)=(bii−rSi(B+))(bjj−r¯Sj(B+))+(bjj−r¯Sj(B+))r¯Si(B+)(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+). |
Since a DZ-type-B-matrix is a CKV-type B-matrix, the bound (3.1) can also be used to estimate maxd∈[0,1]n||(I−D+DA)−1||∞ when A is a DZ-type-B-matrix. The following theorem provides that the bound (3.1) is better than the bound (1.4) in Theorem 1.1 (Theorem 6 of [24]).
Theorem 3.2. Let A=[aij]∈Rn×n be a DZ-type-B-matrix, and B+=[bij] be the matrix of (1.3). Then (3.1) holds. Furthermore,
maxi∈NminS∈S⋆i(B+)maxj∈¯SαSij(B+)≤maxi∈Nminj∈γi(B+)ζij(B+), |
where γi(B+) and ζij(B+) are given by Theorem 1.1, S⋆i(B+) and αSij(B+) are defined in Theorem 3.1.
Proof. For each i∈N, note that
γi(B+):={j∈N∖{i}:(|bii|−rji(B+))|bjj|>|bij|rj(B+)}, |
and
S⋆i(B+):={S∈Σ(i):|bii|>rSi(B+),andforallj∈¯S,(|bii|−rSi(B+))(|bjj|−r¯Sj(B+))>r¯Si(B+)rSj(B+)} |
with Σ(i):={S⊊N:i∈S}. Take S=N∖{j}, ¯S={j}, j≠i, then
rSi(B+)=rji(B+),r¯Si(B+)=|bij|,rSj(B+)=rj(B+),r¯Sj(B+)=0, |
which leads to
αSij(B+)=(bii−rSi(B+))(bjj−r¯Sj(B+))max{1bii−rSi(B+),1}+(bjj−r¯Sj(B+))r¯Si(B+)max{1bjj−r¯Sj(B+),1}(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+)=(bii−rji(B+))bjjmax{1bii−rji(B+),1}+bjj|bij|max{1bjj,1}(bii−rji(B+))bjj−|bij|rj(B+)=ζij(B+). |
It is easy to see that j∈γi(B+) is equivalent to S=N∖{j}∈S⋆i(B+). Therefore, for each i∈N,
minS∈S⋆i(B+)maxj∈¯SαSij(B+)=min{minS=N∖{j}∈S⋆i(B+)maxj∈¯SαSij(B+),minS∈S⋆i(B+)∖(N∖{j})maxj∈¯SαSij(B+)}=min{minj∈γi(B+)ζij(B+),minS∈S⋆i(B+)∖(N∖{j})maxj∈¯SαSij(B+)}≤minj∈γi(B+)ζij(B+). |
This completes the proof.
Particularly, for B-matrices, as an important subclass of CKV-type B-matrices, we next show that the bound (3.1) is better than that given by García-Esnaola and Peña in [10] in some cases.
Theorem 3.3. [10,Theorem 2.3] Let A∈Rn×n be a B-matrix, and B+=[bij] be the matrix of (1.3). Let βi:=bii−ri(B+) and β:=mini∈N{βi}. Then
maxd∈[0,1]n||(I−D+DA)−1||∞≤(n−1)⋅1min{β,1}. | (3.4) |
Theorem 3.4. Let A=[aij]∈Rn×n be a B-matrix, and B+=[bij] be the matrix of (1.3). Let βi:=bii−ri(B+), β:=mini∈N{βi}, and S be a nonempty proper subset of N. Then (3.1) holds. Furthermore, if bii−rSi(B+)≤1 for all i∈N and bjj−r¯Sj(B+)≤1 for all j∈¯S, then,
maxi∈NminS∈S⋆i(B+)maxj∈¯SαSij(B+)≤1min{β,1}, | (3.5) |
and if βi>1 for each i∈N, then
maxi∈NminS∈S⋆i(B+)maxj∈¯SαSij(B+)≥1min{β,1}, | (3.6) |
where αSij(B+) is defined as in Theorem 3.1.
Proof. By the fact that a B-matrix is a CKV-type B-matrix, we know that (3.1) holds directly. We now prove that (3.5) and (3.6) hold. For each i∈N, S∈S⋆i(B+), and j∈¯S, if bii−rSi(B+)≤1 and bjj−r¯Sj(B+)≤1, then from Remark 3.1 that
αSij(B+)=bjj−r¯Sj(B+)+r¯Si(B+)(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+). |
If bjj−rj(B+)<bii−ri(B+), then
(bjj−r¯Sj(B+))−rSj(B+)<(bii−rSi(B+))−r¯Si(B+), |
which implies that
(bjj−r¯Sj(B+))2−(bjj−r¯Sj(B+))rSj(B+)+r¯Si(B+)(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+)<(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+), |
i.e.
[(bjj−r¯Sj(B+))−rSj(B+)][(bjj−r¯Sj(B+))+r¯Si(B+)]<(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+). |
It follows that
(bjj−r¯Sj(B+))+r¯Si(B+)(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+)<1(bjj−r¯Sj(B+))−rSj(B+)=1bjj−rj(B+)=max{1bii−ri(B+),1bjj−rj(B+)}≤1min{β,1}. | (3.7) |
If bjj−rj(B+)≥bii−ri(B+), then
(bjj−r¯Sj(B+))−rSj(B+)≥(bii−rSi(B+))−r¯Si(B+), |
implying that
(bii−rSi(B+))(bjj−r¯Sj(B+))−(bjj−r¯Sj(B+))r¯Si(B+)+(bii−rSi(B+))r¯Si(B+)−(r¯Si(B+))2≤(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+), |
i.e.
[(bii−rSi(B+))−r¯Si(B+)]⋅[(bjj−r¯Sj(B+))+r¯Si(B+)]≤(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+). |
It holds that
(bjj−r¯Sj(B+))+r¯Si(B+)(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+)≤1(bii−rSi(B+))−r¯Si(B+)=1bii−ri(B+)=max{1bii−ri(B+),1bjj−rj(B+)}≤1min{β,1}. | (3.8) |
Hence, (3.5) follows from (3.7) and (3.8).
If βi:=bii−ri(B+)>1 for each i∈N, then
bii−rSi(B+)≥bii−ri(B+)>1andbjj−r¯Sj(B+)≥bjj−rj(B+)>1. |
By Remark 3.1, we can see that
αSij(B+)=(bii−rSi(B+))(bjj−r¯Sj(B+))+(bjj−r¯Sj(B+))r¯Si(B+)(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+)≥(bii−rSi(B+))(bjj−r¯Sj(B+))+rSj(B+)r¯Si(B+)(bii−rSi(B+))(bjj−r¯Sj(B+))−r¯Si(B+)rSj(B+)≥1. |
Therefore,
maxi∈NminS∈S⋆i(B+)maxj∈¯SαSij(B+)≥1=1min{β,1}. |
The proof is complete.
Remark from Theorem 3.4 that we can take the minimum of bounds (3.1) and (3.4) to estimate the error bound for the LCP(A,q) with A being a B-matrix, that is,
maxd∈[0,1]n||(I−D+DA)−1||∞≤(n−1)⋅min{1min{β,1},maxi∈NminS∈S⋆i(B+)maxj∈¯SαSij(B+)}. |
In this section, three examples are given to show the advantage of the bound (3.1) in Theorem 3.1.
Example 4.1. Consider the following matrix
A=[40−2−203−2−2−1−16−2−1−1−26]. |
Obviously, B+=A and C=0. It is easy to verify that B+ is not a DZ-type matrix and an S-SDD matrix, consequently, not a SDD matrix and a DSDD matrix. Hence, A is not a DZ-type-B-matrix and an SB-matrix, and thus not a B-matrix and a DB-matrix. So we cannot use the error bounds in [6,7,8,10,20,24] to estimate maxd∈[0,1]4||(I−D+DA)−1||∞. However, by calculations, one has that B+ is a CKV-type matrix with positive diagonal entries, and thus A is a CKV-type B-matrix. So by the bound (3.1) in Theorem 3.1, we get
maxd∈[0,1]4||(I−D+DA)−1||∞≤21. |
Example 4.2. Consider the following matrix
A=[30−2−203−2−2−1−160−1−106]. |
Note that r+i:=max{0,aij|j≠i}=0 for i=1,2,3,4. Hence, B+=A and C=0. By calculations, we have that A is a DZ-type-B-matrix, and thus it is a CKV-type B-matrix. By the bound (3.1) in Theorem 3.1, we have
maxd∈[0,1]4||(I−D+DA)−1||∞≤12.6, |
while by the bound (1.4) in Theorem 1.1, it holds that
maxd∈[0,1]4||(I−D+DA)−1||∞≤27. |
Obviously, the bound (3.1) is sharper than bound (1.4) in Theorem 1.1 (Theorem 6 of [24]).
Example 4.3. Consider the B-matrix
A=[3−1−1−12−13−1−12−1−13−120001]. |
Note that B+=A, C=0. Then, by the bound (3.4) in Theorem 3.3, we have
maxd∈[0,1]4||(I−D+DA)−1||∞≤6. |
In addition, A is also a CKV-type B-matrix. By calculations, for i=1,2,3, take S={1,2,3} and ¯S={4}, it follows that bii−rSi(B+)≤1 for all i∈{1,2,3,4} and b44−r¯S4(B+)≤1; and for i=4, take S={4} and ¯S={1,2,3}, it follows that bii−rSi(B+)≤1 for all i∈{1,2,3,4} and bjj−r¯Sj(B+)≤1 for all j∈¯S, which satisfy the hypothesis of Theorem 3.4. Therefore, by Theorem 3.4, we get
maxd∈[0,1]4||(I−D+DA)−1||∞≤4.5, |
which is smaller than the bound (3.4) in Theorem 3.3 (Theorem 2.3 of [10]).
In this paper, on the basis of the class of CKV-type matrices, a new subclass of P-matrices: CKV-type B-matrices, containing B-matrices, DB-matrices, SB-matrices as well as DZ-type-B-matrices, is introduced, and an upper bound for the infinity norm for the inverse of CKV-type B-matrices is provided. Then, by this bound, an error bound for the corresponding LCP(A,q) is given. We also proved that the new error bound is sharper than those of [10] and [24] in some cases, and give numerical examples to show the advantage of our results.
The authors sincerely thank the editors and anonymous reviewers for their valuable suggestions and helpful comments, which greatly improved the quality of the paper. This work was supported by National Natural Science Foundation of China (31600299), Young Talent fund of University Association for Science and Technology in Shaanxi, China (20160234), the Natural Science Foundations of Shaanxi province, China (2017JQ3020, 2020JM-622), the Scientific Research Program Funded by Shaanxi Provincial Education Department (18JK0044), and the Key Project of Baoji University of Arts and Sciences (ZK2017021).
The authors declare no conflict of interest.
[1] | A. Berman, R. J. Plemmons, Nonnegative Matrix in the Mathematical Sciences, Philadelphia: SIAM Publisher, 1994. |
[2] | R. W. Cottle, J. S. Pang, R. E. Stone, The Linear Complementarity Problem, San Diego: Academic Press, 1992. |
[3] |
X. J. Chen, S. H. Xiang, Computation of error bounds for P-matrix linear complementarity problems, Math. Program, Ser., 106 (2006), 513–525. doi: 10.1007/s10107-005-0645-9
![]() |
[4] |
T. T. Chen, W. Li, X. Wu, S. Vong, Error bounds for linear complementarity problems of MB-matrices, Numer. Algorithms, 70 (2015), 341–356. doi: 10.1007/s11075-014-9950-9
![]() |
[5] |
D. Lj. Cvetković, L. Cvetković, C. Q. Li, CKV-type matrices with applications, Linear Algebra Appl., 608 (2021), 158–184. doi: 10.1016/j.laa.2020.08.028
![]() |
[6] | P. F. Dai, Error bounds for linear complementarity problem of DB-matrices Linear Algebra Appl., 434 (2011), 830–840. |
[7] |
P. F. Dai, Y. T. Li, C. J. Lu, Error bounds for the linear complementarity problem for SB-matrices, Numer. Algorithms, 61 (2012), 121–139. doi: 10.1007/s11075-012-9533-6
![]() |
[8] |
P. F. Dai, C. J. Lu, Y. T. Li, New error bounds for the linear complementarity problem for SB-matrix, Numer. Algorithms, 64 (2013), 741–757. doi: 10.1007/s11075-012-9691-6
![]() |
[9] |
P. F. Dai, J. C. Li, Y. T. Li, C. Y. Zhang, Error bounds for linear complementarity problem of QN-matrices, Calcolo, 53 (2016), 647–657. doi: 10.1007/s10092-015-0167-7
![]() |
[10] |
M. García-Esnaola, J. M. Peña, Error bounds for the linear complementarity problem for B-matrices, Appl. Math. Lett., 22 (2009), 1071–1075. doi: 10.1016/j.aml.2008.09.001
![]() |
[11] |
M. García-Esnaola, J. M. Peña, B-Nekrasov matrices and error bounds for the linear complementarity problems, Numer. Algorithms, 72 (2016), 435–445. doi: 10.1007/s11075-015-0054-y
![]() |
[12] |
M. García-Esnaola, J. M. Peña, BRπ-matrices and error bounds for linear complementarity problems, Calcolo, 54 (2017), 813–822. doi: 10.1007/s10092-016-0209-9
![]() |
[13] |
L. Gao, C. Q. Li, Y. T. Li, Parameterized error bounds for linear complementarity problems of BRπ-matrices and their optimal values, Calcolo, 56 (2019), 31. doi: 10.1007/s10092-019-0328-1
![]() |
[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. doi: 10.1016/j.laa.2010.04.024
![]() |
[15] |
L. Gao, Y. Q. Wang, C. Q. Li, Y. T. Li, Error bounds for linear complementarity problems of S-Nekrasov matrices and B-S-Nekrasov matrices, J. Comput. Appl. Math., 336 (2018), 147–159. doi: 10.1016/j.cam.2017.12.032
![]() |
[16] | L. Gao, C. Q. Li, New error bounds for linear complementarity problem of QN-matrices, Numer. Algorithms, 80 (2018), 229–242. |
[17] |
M. García-Esnaola, J. M. Peña, On the asymptotic of error bounds for some linear complementarity problems, Numer. Algorithms, 80 (2019), 521–532. doi: 10.1007/s11075-018-0495-1
![]() |
[18] |
Z. Q. Luo, P. Tseng, Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem, SIAM J. Optimiz., 2 (1992), 43–54. doi: 10.1137/0802004
![]() |
[19] |
Z. Q. Luo, P. Tseng, On the linear convergence of descent methods for convex essentially smooth minimization, SIAM J. Control Optim., 30 (1992), 408–425. doi: 10.1137/0330025
![]() |
[20] |
C. Q. Li, Y. T. Li, Note on error bounds for linear complementarity problems of B-matrices, Appl. Math. Lett., 57 (2016), 108–113 doi: 10.1016/j.aml.2016.01.013
![]() |
[21] |
C. Q. Li, P. F. Dai, Y. T. Li, New error bounds for linear complementarity problems of Nekrasov matrices and B-Nekrasov matrices, Numer. Algorithms, 74 (2017), 997–1009. doi: 10.1007/s11075-016-0181-0
![]() |
[22] |
C. Q. Li, Y. T. Li, Weakly chained diagonally dominant B-matrices and error bounds for linear complementarity problems, Numer. Algorithms, 73 (2016), 985–998. doi: 10.1007/s11075-016-0125-8
![]() |
[23] |
W. Li, H. Zhang, Some new error bounds for linear complementarity problems of H-matrices, Numer. Algorithums, 67 (2014), 257–269. doi: 10.1007/s11075-013-9786-8
![]() |
[24] |
C. Q. Li, L. Cvetković, Y. Wei, J. X. Zhao, An infinity norm bound for the inverse of Dashnic-Zusmanovich type matrices with applications, Linear Algebra Appl., 565 (2019), 99–122. doi: 10.1016/j.laa.2018.12.013
![]() |
[25] |
H. B. Li, T. Z. Huang, H. Li, On some subclasses of P-matrices, Numer. Linear Algebra Appl., 14 (2007), 391–405. doi: 10.1002/nla.524
![]() |
[26] | K. G. Murty, Linear Complementarity, Linear and Nonlinear Programming, Berlin: Heldermann Verlag, 1988. |
[27] |
H. Orera, J. M. Peña, Error bounds for linear complementarity problems of BRπ-matrices, Comp. Appl. Math., 40 (2021), 94. doi: 10.1007/s40314-021-01491-w
![]() |
[28] |
J. S. Pang, A posteriori error bounds for the linearly-constrained variational inequality problem, Math. Oper. Res., 12 (1987), 474–484. doi: 10.1287/moor.12.3.474
![]() |
[29] |
J. M. Peña, On an alternative to Geršchgorin circle and ovals of Cassini, Numer. Math., 95 (2003), 337–345. doi: 10.1007/s00211-002-0427-8
![]() |
[30] |
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. doi: 10.1137/S0895479800370342
![]() |
[31] |
P. N. Shivakumar, K. H. Chew, A sufficient condition for nonvanishing of determinants, Proc. Amer. Math. Soc., 43 (1974), 63–66. doi: 10.1090/S0002-9939-1974-0332820-0
![]() |
[32] |
C. L. Sang, Z. Chen, A new error bound for linear complementarity problems of weakly chained diagonally dominant B-matrices, Linear Multilinear A., 69 (2021), 1909–1921. doi: 10.1080/03081087.2019.1649995
![]() |
[33] |
J. X. Zhao, Q. L. Liu, C. Q. Li, Y. T. Li, Dashnic-Zusmanovich type matrices: A new subclass of nonsingular H-matrices, Linear Algebra Appl., 552 (2018), 277–287. doi: 10.1016/j.laa.2018.04.028
![]() |
[34] |
R. J. Zhao, B. Zheng, M. L. Liang, A new error bound for linear complementarity problems with weakly chained diagonally dominant B-matrices, Appl. Math. Compt., 367 (2020), 124788. doi: 10.1016/j.amc.2019.124788
![]() |
[35] | F. Wang, D. S. Sun, New error bound for linear complementarity problems for B-matrices, Linear Multilinear A., 66 (2018), 2154–2167. |
[36] |
Z. F. Wang, C. Q. Li, Y. T. Li, Infimum of error bounds for linear complementarity problems of Σ-SDD and Σ1-SSD matrices, Linear Algebra Appl., 581 (2019), 285–303. doi: 10.1016/j.laa.2019.07.020
![]() |
1. | Yingxia Zhao, Lanlan Liu, Feng Wang, Error bounds for linear complementarity problems of $ SD{{D}_{1}} $ matrices and $ SD{{D}_{1}} $-$ B $ matrices, 2022, 7, 2473-6988, 11862, 10.3934/math.2022662 | |
2. | Dunja Arsic, Maja Nedovic, On π−nekrasov matrices, 2023, 37, 0354-5180, 4335, 10.2298/FIL2313335A | |
3. | Yuanjie Geng, Deshu Sun, Error bounds for linear complementarity problems of strong $ SDD_{1} $ matrices and strong $ SDD_{1} $-$ B $ matrices, 2023, 8, 2473-6988, 27052, 10.3934/math.20231384 | |
4. | Liang Yan, Feng Wang, Global error bounds for the extended vertical linear complementarity problems of CKV-type matrices and CKV-type B-matrices, 2024, 41, 0916-7005, 129, 10.1007/s13160-023-00591-w | |
5. | Lei Gao, Xiudan Jia, Xia Jing, Yi Liu, Global Error Bounds for the Extended Vertical Linear Complementarity Problems of CKV-Type Matrices and CKV-Type $B$-Matrices, 2024, 190, 0167-8019, 10.1007/s10440-024-00644-3 | |
6. | Lanlan Liu, Yuxue Zhu, Feng Wang, Yuanjie Geng, Infinity norm bounds for the inverse of $ SDD_1^{+} $ matrices with applications, 2024, 9, 2473-6988, 21294, 10.3934/math.20241034 | |
7. | Maja Nedovic, Ernest Sanca, Partition-Nekrasov type matrices: A new subclass of nonsingular H-matrices and applications, 2024, 38, 0354-5180, 5083, 10.2298/FIL2414083N | |
8. | Yuxue Zhu, Yuanjie Geng, Feng Wang, Lanlan Liu, Infinity norm bounds for the inverse of extended $$SDD_1$$ matrices with applications, 2025, 0916-7005, 10.1007/s13160-025-00702-9 |