B-Nekrasov矩陣線性互補問題的最優(yōu)誤差界

甘夢婷, 楊紹蓉, 李朝遷

(云南大學 數(shù)學與統(tǒng)計學院, 昆明 650091)

1 引言與預備知識

線性互補問題在經(jīng)濟學、 對策論、 數(shù)學規(guī)劃等領域應用廣泛[1].

定義1[2]設M=(mij)∈n×n,q∈n, 尋找解x*∈n, 使其滿足

Mx+q≥0,x≥0,xT(Mx+q)=0

的問題稱為線性互補問題, 記為LCP(M,q).

LCP(M,q)解的存在性、 唯一性、 靈敏度以及求解算法的收斂性都與矩陣M的結構和性質有關. 當M為P-矩陣時, LCP(M,q)存在唯一解[2].

定義2[2]設M=(mij)∈n×n,x∈n, 若矩陣M滿足

?x≠0,

則稱矩陣M為P-矩陣.

定義3[9]設M=(mij)1≤i,j≤n∈n×n,mii≠0,i=1,2,…,n,

N={1,2,…,n}. 若|mii|>hi(M),i∈N, 則稱M為Nekrasov矩陣.

定義4[8]設A=(aij)1≤i,j≤n∈n×n, 將A分解為A=B++C的形式, 其中

定理1[8]設A=(aij)1≤i,j≤n∈n×n(n≥2)是B-Nekrasov矩陣, 并存在m>i, 使得如定義4中定義. 給定對角矩陣W=diag(w1,w2,…,wn), 其中

(1)

則

令

2 B-Nekrasov矩陣的線性互補問題誤差界的最優(yōu)值

對給定的滿足定理1中條件的B-Nekrasov矩陣A, 令

證明： 注意到

于是

進一步, 對式(1)進行分析. 不失一般性, 設

wi1≥wi2≥…≥win-1>0,ik∈{1,2,…,n-1},k=1,2,…,n-1,

(2)

所以

綜上可得式(2). 證畢.

例1給定B-Nekrasov矩陣

其中:

計算得

h1(B+)=2,h2(B+)=3,h3(B+)=10.666 7,h4(B+)=0.341 3,

w1=0.666 7,w2=0.75,w3=0.021 3,w4=0.170 7+ε,ε∈(0,0.829 3),

圖1 例1的誤差界及其最優(yōu)界Fig.1 Error bounds and their optimal bounds of example 1

[1] 李鳳. 線性互補問題及相關性質 [D]. 哈爾濱： 哈爾濱工業(yè)大學, 2007. (LI Feng. The Linear Complementarity Promblem and Related Properties [D]. Harbin： Harbin Institute of Technology, 2007.)

[2] CHEN Xiaojun, XIANG Shuhuang. Computation of Error Bounds forP-Matrix Linear Complementarity Problems [J]. Mathematical Programming, 2006, 106(3): 513-525.

[3] García-Esnaola M, Pea J M. Error Bounds for Linear Complementarity Problems forB-Matrices [J]. Applied Mathematics Letters, 2009, 22(7): 1071-1075.

[4] LI Chaoqian, GAN Mengting, YANG Shaorong. A New Error Bound for Linear Complementarity Problems forB-Matrices [J]. Electronic Journal of Linear Algebra, 2016, 31(1): 476-484.

[5] LI Chaoqian, LI Yaotang. Weakly Chained Diagonally DominantB-Matrices and Error Bounds for Linear Complementarity Problems [J]. Numerical Algorithms, 2016, 73(4): 985-998.

[6] DAI Pingfan. Error Bounds for Linear Complementarity Problems ofDB-Matrices [J]. Linear Algebra and Its Applications, 2011, 434(3): 830-840.

[7] DAI Pingfan, LI Yaotang, LU Changjing. Error Bounds for Linear Complementarity Problems forSB-Matrices [J]. Numerical Algorithms, 2012, 61(1): 121-139.

[8] García-Esnaola M, Pea J M.B-Nekrasov Matrices and Error Bound for Linear Complementarity Problems [J]. Numerical Algorithms, 2016, 72(2): 435-445.

[9] García-Esnaola M, Pea J M. Error Bounds for Linear Complementarity Problems of Nekrasov Matrices [J]. Numerical Algorithms, 2014, 67(3): 655-667.