Ostrowski-Brauer Sparse B (OBS-B)矩陣及其線性互補問題的誤差界

劉 毅，井 霞，高 磊

(寶雞文理學院 數學與信息科學學院，陜西 寶雞 721013)

P-矩陣是指所有主子式皆為正的矩陣，其廣泛應用于工程、經濟等領域的優化問題中. 眾所周知，優化領域的線性互補問題(如下)有唯一解當且僅當相關矩陣為P-矩陣，P-矩陣由此受到國內外學者的廣泛關注[1-5]. 給定矩陣M∈Rn×n和向量q∈Rn，線性互補問題 LCP(M,q)是指尋找x∈Rn滿足

或證明這樣的x∈Rn不存在. 進一步，當M為P-矩陣時，容易得到線性互補問題LCP(M,q) 的解存在且精確解x*與近似解x的誤差界[6]：

其中r(x)=min{x,Mx+q}表示對向量x與Mx+q對應位置分量取最小,D=diag(di),d=[d1,d2,···,dn]T(0≤di≤1). 然而，對于不具有特定結構且階數較大的P-矩陣，誤差界(1)中的計算是十分困難的. 注意到當矩陣具有特定結構時，上述問題將得到極大緩解[7-13]. 為此，尋找P-矩陣的具有特殊結構的子類并研究其線性互補問題的誤差界顯得尤為重要. 本文在OBS矩陣定義的基礎上，引入一類新的結構矩陣：OBS-B矩陣，證明該矩陣為P-矩陣，并討論該矩陣與其他P-矩陣子類如B-矩陣、DB-矩陣、B-Nekrasov矩陣、DZ-typeB矩陣之間的關系；進一步給出OBS-B矩陣線性互補問題的誤差界，證明所給誤差界優于現有的結果. 最后，給出數值算例闡明結果的有效性.

1 預備知識

令Rn×n(Cn×n)表示所有n階實矩陣(復矩陣)的集合，指標集N={1,2,···,n}.設矩陣，記下面給出本文所用到的定義和引理.

定義1[14]設矩陣. 若對任意的 i,j∈N ，i≠j，有

則稱A為雙嚴格對角占優矩陣，也稱為Ostrowski-Brauer矩陣.

2019年，Kolotilina[15]考慮到矩陣元素的稀疏性，在雙嚴格對角占優矩陣的基礎上，提出一類帶有稀疏結構的矩陣類，稱之為Ostrowski-Brauer Sparse矩陣.

定義2[15]設,n≥2. 若A無零行且對滿足的i,j∈N，有

則稱A為Ostrowski-Brauer Sparse矩陣，簡稱為OBS矩陣.

進一步，Kolotilina證明了OBS矩陣為非奇異H-矩陣，并給出其逆矩陣的無窮大范數估計式.

引理1[15]若A=[aij]∈Cn×n,n≥2是OBS矩陣，則A是非奇異H-矩陣.

引理2[15]設A=[aij]∈Cn×n,n≥2為OBS矩陣，則

下面給出P-矩陣的一些重要子類. 設矩陣. 則A可分裂為A=B++C，其中

2001年，Pe?a[1]提出一類重要的結構矩陣：B-矩陣，并證明了該矩陣為P-矩陣.

定義3[1]設，若對任意的i,j∈N且，有

則稱A為B-矩陣.

同時，Pe?a給出了B-矩陣的一個與嚴格對角占優矩陣密切相關的等價定義.

定義4[1]設且A=B++C，其中如(2)式所示. 矩陣A為B-矩陣當且僅當B+為具有正對角元的嚴格對角占優矩陣.

2009年，García-Esnaola等在文獻[16]中給出了B-矩陣線性互補問題的誤差界.

定理1[16]設是B-矩陣，如(2)式所示，則

此外，基于B-矩陣的等價定義，Pe?a在文獻[2]中提出了一類包含B-矩陣的結構矩陣類：DB-矩陣，該矩陣也為P-矩陣的重要子類.

定義5[2]設且A=B++C，其中如(2)式所示. 若矩陣B+為具有正對角元的雙嚴格對角占優矩陣，則稱A為DB-矩陣.

本節最后，我們羅列出下文證明中用到的一些技巧性引理.

引理3[2]若為非奇異M-矩陣，P是非負矩陣且秩為1，則A+P是P-矩陣.

引理4[7]設 γ＞0和 η≥0，則對任意的x∈[0,1]，有

引理5[8]設且則, 有

2 主要結果

下面結合OBS矩陣與B-矩陣的等價定義，給出OBS-B矩陣的定義，并證明OBS-B矩陣是P-矩陣的子類.

定義6設,n≥2，且A=B++C如(2)式所示. 若B+為主對角元為正的OBS矩陣，則稱A為OBS-B矩陣.

由引理3易證OBS-B矩陣為P-矩陣.

定理2若,n≥2 是OBS-B矩陣，則A是P-矩陣.

證明由A是OBS-B矩陣知，B+是主對角元為正的OBS矩陣且為Z-矩陣(所有非主對角元非正)，因此B+為具有正對角元的非奇異H-矩陣，從而為非奇異M-矩陣. 由(2)知C是非負矩陣且秩為1. 因此，由引理3可得A=B++C為P-矩陣. 證畢.

注1由定義1和定義2知雙嚴格對角占優矩陣為OBS矩陣，故由定義4、定義5和定義6易知下列關系成立：

此外，由文獻[17]知

因此，結合關系式(3)可得OBS-B矩陣不是B-Nekrasov和DZ-type-B矩陣的子類，即

進一步，下面的例子說明B-Nekrasov和DZ-type-B矩陣也不是OBS-B矩陣的子類，即

例1考慮如下矩陣：

由文獻[17]中例2知A1是DZ-typeB矩陣. 由|a22||a33|=304＜r2(A)r3(A)=440 知A不是OBS-B矩陣. 矩陣A2顯然是Z-矩陣，因此B+=A, 令計算可得

因此A2是B-Nekrasov矩陣. 由知A2不是OBS-B矩陣.

綜上所述，我們給出B-矩陣、DB-矩陣、OBS-B矩陣、B-Nekrasov矩陣及DZ-typeB矩陣之間的關系圖如圖1.

下面討論OBS-B矩陣線性互補問題的誤差界，首先給出一個重要引理.

引理6設為主對角元為正的OBS矩陣，且，其中D=diag(di)(0≤di≤1)，則仍為主對角元為正的OBS矩陣.

圖1 OBS-B矩陣與P-矩陣一些子類的關系Fig. 1 Relations between OBS-B matrices and some subclasses of P-matrices

證明由知

又因為A是主對角元為正的OBS矩陣且D=diag(di)(0≤di≤1)，故對任意的i∈N，有di+diaii＞0，且對滿足且的i,j∈N,i≠j,當dj≠0 時，有

當dj=0 時，有

因此，由定義2得是主對角元為正的OBS矩陣. 證畢.

利用引理2，引理4～6，下面給出OBS-B矩陣線性互補問題的誤差界.

定理3設為OBS-B矩陣，記A=B++C，其中B+=[bi j] 形如(2)式，則

其中：

證明令，則，其中DC. 因為B+是主對角元為正的OBS矩陣，故由引理6得也為主對角元為正的OBS矩陣，即為非奇異M-矩陣. 從而由文獻[16]中定理2.2的證明知

鴇鳥肅肅地扇著雙翼，停落在荊棘里。 王家的事沒了沒完，黍稷全不能種植。 父母拿什么做飯？遙遠的蒼天呀！何時才能終止？

注意到B+是主對角元為正的OBS矩陣且,i∈N. 因此，對每個i∈N有：

因此，

由(6)和(7)式知定理 3結論成立. 證畢.

由關系式(3)可知B-矩陣是OBS-B矩陣的一個子類，因此(4)式同樣可作為B-矩陣線性互補問題的誤差界. 為了說明誤差界(4)的優越性,下面我們給出一個比較定理.

定理4設A=[aij]∈Cn×n是B-矩陣，記A=B++C，其中矩陣B+=[bi j]如(2)式所示. 對滿足bij≠0 的任意i,j∈N,i≠j,若bii＜1,bjj＜1，則

若下列條件任意一條成立:

則

證明注意到和從而當ri(B+)=0時，有βi=bii. 因此

對滿足bi j≠0的任意i,j∈N,i≠j，若bii＜1，bjj＜1，顯然有

即

移項可得

即

移項可得

即

移項得

即有

3 數值算例

下面給出兩個數值算例對所得理論結果進行說明.

例2考慮矩陣

由矩陣A的分裂A=B++C，其中

得A為B-矩陣. 從而由定理1中的(3)式得

又因為B-矩陣也是DZ-type-B矩陣、B-Nekarsov矩陣、OBS-B矩陣(見圖1)，故由文獻[12]中B-Nekarsov矩陣線性互補誤差界得

由文獻[17]中DZ-type-B矩陣線性互補誤差界得

由定理3中OBS-B矩陣的線性互補誤差界(4)式得

上述結果顯示誤差界(4)優于文獻[12]和文獻[17]所給的誤差界.

例3考慮矩陣

顯然，矩陣A是Z-矩陣，因此，B+=A. 令B+=[bij],計算得

因此，A不是DB-矩陣、DZ-typeB矩陣和B-Nekrasov矩陣，從而無法用相應的誤差界估計然而，對滿足bi j≠0的任意i,j∈N,i≠j有

即A是OBS-B矩陣，從而由定理3得