幾類結(jié)構(gòu)矩陣線性互補問題解的誤差界

1、分類號024密級 公開UDC 編號碩士營菱也容儂論次題目幾類結(jié)構(gòu)矩陣線性互補問題解的誤差界Title Error bounds for the linear comDlementarity problems of some classes of structured matrices學(xué)院（所、中心）數(shù)學(xué)與統(tǒng)計學(xué)院專業(yè)名稱系統(tǒng)理論研究方向數(shù)值代數(shù)研究生姓名冶海姣 學(xué)號12016000983導(dǎo)師姓名李朝遷職稱 副教授2019年05月扉頁:論文獨創(chuàng)性聲明及使用授權(quán)本論文是作者在導(dǎo)師指導(dǎo)下取得的研究成果。除了文中特別加以標(biāo)注和致謝的地方 外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，不存在剽竊或抄

2、襲行為。與作 者一同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示了謝 意?，F(xiàn)就論文的使用對云南大學(xué)授權(quán)如下：學(xué)校有權(quán)保留本論文（含電子版），也可以 采用影印、縮印或其他復(fù)制手段保存論文；學(xué)校有權(quán)公布論文的全部或部分內(nèi)容，可以 將論文用于查閱或借閱服務(wù)：學(xué)校有權(quán)向有關(guān)機(jī)構(gòu)送交學(xué)位論文用于學(xué)術(shù)規(guī)范審查、社 會監(jiān)督或評獎；學(xué)校有權(quán)將學(xué)位論文的全部或部分內(nèi)容錄入有關(guān)數(shù)據(jù)庫用于檢索服務(wù)。（內(nèi)部或保密的論文在解密后應(yīng)遵循此規(guī)定）研究生簽名：左諭姣導(dǎo)師簽名：手曲遷日期：摘要線性互補問題LCP(M, q)在經(jīng)濟(jì)學(xué)、金融和線性規(guī)劃等領(lǐng)域有廣泛的應(yīng)用， 其解的存在性、唯一性、靈敏度以及求解算法

3、的收斂性都與矩陣M的結(jié)構(gòu)和性 質(zhì)有關(guān).本文研究了矩陣 Af 為 Dashnic-Zusmanovich (QZ)矩陣、Dashnic-Zusman- ovich-B (DZ-B)矩陣和雙嚴(yán)格對角占優(yōu)(/KDD)矩陣線性互補問題解的誤差界估 計問題，分別得到了只與矩陣的元素相關(guān)的上界，具體內(nèi)容如下.第二章研究了 OZ矩陣、DZ-與矩陣線性互補問題解的誤差界估計.利用Z)Z矩 陣的逆矩陣的無窮范數(shù)的上界及DZ矩陣的結(jié)構(gòu)和性質(zhì)，結(jié)合不等式的放縮方法， 得到了 OZ和。Z-8矩陣線性互補問題解的誤差估計式.同時，給出數(shù)值例子表明 結(jié)果的有效性.第三章研究了 QS加矩陣線性互補問題解的最優(yōu)誤差界.針對文

4、獻(xiàn)M. Garcia-Esnaola, J. M. Pena. A comparison of error bounds fbr linear complementarity problems of 77-matrices. Linear Algebra Appl, 2010. 433(5): 956-964提出的 H-短 陣線性互補問題誤差界的估計式，利用QS如矩陣的性質(zhì)和函數(shù)的單調(diào)性，得 到了 OSDD矩陣線性互補問題解的含有參數(shù)的誤差界的最優(yōu)值，最后用數(shù)值例 子驗證了所得結(jié)果.關(guān)鍵詞：線性互補問題；誤差界；H矩陣;刀Z矩陣；QZ也矩陣；雙嚴(yán)格對 角占優(yōu)陣AbstractLinear co

5、mplementarity problems LCP(M.q) are widely used in economics, finance, linear programming and other fields, the existence and uniqueness of the solution of LCP, sensitivity and the convergence of the algorithms are all related to the structures and properties of the matrix M. This thesis mainly stud

6、ies error bounds for the solutions for linear complementarity problems when the matrix M are Dashnic- Zusmaovich (Z)Z) matrices, Dashnic-Zusmanovich-B (DZ-B) matrices and double strictly diagonally dominant (DSDD) matrices, and we get some upper bounds which depend only on the elements of M. The spe

7、cific content is as follows.In Chapter 2. the error boundary estimation of linear complementary7 problems of DZ matrix and DZ-B matrix is studied. The new error estimation formula are obtained by using the upper bounds of the infinity norms of the inverse matrix of DZ matrices, the special structure

8、 and properties of DZ matrices and the monotonicity of functions. Some numerical examples are also given to show the validity of the results.In Chapter 3. the optimal error bounds fbr 比e linear complementarity problem of DSDD matrices are studied. For the error bound of the 77-matrix linear compleme

9、ntarity problem proposed in M. Garcfa-Esnaola, J. M. Pena. A comparison of error bound s for linear complementarity problems of 77-matrices. Linear Algebra Appl, 2010. 433 (5): 956-964. by using the properties of the DSDD matrix and the monotonicity of the function, the optimal value of the error bo

10、und with a parameter of linear complementarity problem of DSDD matrices is given. Finally, some numerical examples are given to verify the corresponding results.Key words: Linear complementarity problems; Error bounds; B-matrices;PZ-matrices; DZ-B-matrices; DSDD-matrices目錄 TOC o 1-5 h z HYPERLINK l

11、bookmark7 o Current Document 摘要I HYPERLINK l bookmark10 o Current Document AbstractII HYPERLINK l bookmark18 o Current Document 第一章緒論1 HYPERLINK l bookmark21 o Current Document 1.1研究背景1 HYPERLINK l bookmark24 o Current Document 2研究現(xiàn)狀2 HYPERLINK l bookmark34 o Current Document 1.3本文的主要工作 .7第二章 Dashni

12、c-Zusmanovich 矩陣和 Dashnic-ZusmanovichB 矩陣線性互補問題解的誤差界91。小記討湖矩陣線性互補問題解的誤差界估計10 HYPERLINK l bookmark50 o Current Document 2. 2 Dashnic-Zusmanovich-B矩陣線性互補問題解的誤差界估計13 HYPERLINK l bookmark62 o Current Document 第三章雙嚴(yán)格對角占優(yōu)矩陣線性互補問題的最優(yōu)誤差界23 HYPERLINK l bookmark68 o Current Document 3.1雙嚴(yán)格對角占優(yōu)矩陣線性互補問題誤差界的最優(yōu)值2

13、43.2數(shù)值例子29 HYPERLINK l bookmark77 o Current Document 第四章總結(jié)31 HYPERLINK l bookmark89 o Current Document 參考文獻(xiàn)33 HYPERLINK l bookmark132 o Current Document 攻讀碩士學(xué)位期間完成的科研成果36 HYPERLINK l bookmark138 o Current Document 致謝37第一章緒論本章首先介紹線性互補問題的概念、研究意義和應(yīng)用領(lǐng)域，再對近年來國內(nèi) 外學(xué)者關(guān)于線性互補問題誤差界的研究現(xiàn)狀進(jìn)行概述，最后對本文的內(nèi)容進(jìn)行簡 要闡述.1.1

14、研究背景給定F:R” tR”,求xeRn使其滿足如下條件0, F（x） 0, xTF（x） - 0.稱該問題為互補問題，記為CPCO；稱滿足上述不等式的X為互補問題的解當(dāng) F（X）是線性函數(shù)，即F（x）=Mx + q（Me 蔭”.養(yǎng) R”）時，上述問題稱為線性互補問題IF,記為LCP（M,/；否則為非線性互補問題, 記為 NCP（M,g）.互補問題可以分為非線性互補問題和線性互補問題，其中非線性互補問題在 交通平衡問題、流體彈性動態(tài)潤滑問題、接觸力學(xué)和經(jīng)濟(jì)等領(lǐng)域有著極其廣泛的 應(yīng)用EW4,己成為數(shù)學(xué)規(guī)劃中的一個研究熱點.經(jīng)過多年的發(fā)展，其數(shù)值算法、 理論體系和應(yīng)用領(lǐng)域己逐步拓展，并成為數(shù)學(xué)學(xué)科

15、的一個重要分支，眾多學(xué)者也 在這方面做了新的工作W9.然而，在解決實際問題中的函數(shù)F（X）并不一定為非 線性的，如彈性接觸問題、自由邊界問題、市場供需平衡問題、雙矩陣對策問題、 誤差界估計問題等Ng方面.這就是本文關(guān)心和研究的線性互補問題.1939年，線性互補問題的概念被Karush在研究連續(xù)性變量不等式約束 條件的優(yōu)化問題中最先提出，并對此類問題進(jìn)行了簡單研究“w. 1963年， Hobson和Lemke給出了線性互補的形式，并將其應(yīng)用在計算雙矩陣的納什均衡 點的問題上，利用互補點方法簡潔有效的解決了這個問題.隨后，氏凍印和 等在線性互補問題的理論與算法方面做了許多研究，并取得了巨大的成果

16、【si線性互補問題的研究初期，主要是側(cè)重于對線性互補問題解的存在性的研 究，一般很少涉及線性互補問題的數(shù)值算法和具體的應(yīng)用領(lǐng)域.1968年，Coule 和。奶左瀝g在求解二次規(guī)劃和雙矩陣模型研充中取得了重大突破心，6罰.此后， 這類線性互補問題的探討在各個學(xué)術(shù)領(lǐng)域引起了廣大學(xué)者的關(guān)注，國內(nèi)外學(xué)者都 致力于這一問題的研究，并取得了一系列的成果.目前，對線性互補問題研究主要集中在兩個方面：（1）理論方面研究了解的 存在性、唯一性、穩(wěn)定性和靈敏度分析；（2）算法方面主要探討求解互補問題的 有效算法和對算法作相應(yīng)的收斂性分析和誤差界的分析，即給出誤差界的最小 上界或解的近似解.在線性互補問題中涉及許多

17、特殊矩陣如P-矩陣、矩陣、 M矩陣等，它們廣泛應(yīng)用于數(shù)學(xué)物理、計算數(shù)學(xué)、運籌學(xué)與控制論、統(tǒng)計學(xué)和 經(jīng)濟(jì)數(shù)學(xué)等眾多領(lǐng)域方5,也它們的結(jié)構(gòu)和性質(zhì)與線性互補問題的解的存在性、 唯一性以及近似解的誤差分析都密切相關(guān).由于在研究中，不同的模型構(gòu)建方法 和不同的算法，得到的數(shù)值解與真實解之間存在誤差，因此，關(guān)于特殊矩陣線性 互補問題的誤差界的研究引起了許多學(xué)者的注意，從而使誤差變小這一問題便激 發(fā)了人們對線性互補問題誤差界估計的研究興趣g心9】，這也是本學(xué)位論文所關(guān) 心和研究的主要內(nèi)容.1.2研究現(xiàn)狀本節(jié)對線性互補問題誤差界的研究現(xiàn)狀做簡要敘述，為敘述方便，先給出文 章中所用到的符號及矩陣、矩陣、度矩陣相

18、關(guān)的定義.令表示所有階實矩陣（復(fù)矩陣）所成的集臺.指標(biāo)集 7V= 1,2,設(shè)M =頃準(zhǔn)R* ,對任意的沱記S SN-對于有限集S,用|S|表示集合S的勢.定義.1.2. 120設(shè)M =x R”.若max xf 0, Vx 工 0,則稱矩陣M為P-矩陣.定義1.2.2設(shè)力=（a.） g,稱（冷=驀）為刀的比較矩陣，其中團(tuán)i=j，若/20且3/0(SJ),則稱A為M-矩陣E；若,耘)，則稱刀為Z-矩陣；若3為非奇異的*矩陣，則稱.4為非奇異H-矩陣監(jiān).關(guān)于具有特殊結(jié)構(gòu)矩陣線性互補問題解的誤差界估計，國內(nèi)外學(xué)者做了許多 研究.當(dāng)矩陣M是R矩陣時,LCP(M, g)存在唯一解U。, 1990年,Mat

19、hias和Pang 給出如下P矩陣線性互補問題解的誤差界.定理1. 2. 1設(shè)M =為P-矩陣，q仕R”，其中x*為LCP(M, q)的唯一解，對任意的xeR,有m字鷺I(yè)其中= min如弩x,。衣吐r(x) = min(x. Mr + q)表示對向量x與Mxq對應(yīng)位置分量取最小.(1)式中當(dāng)矩陣肱的階數(shù)很大時，。(也的值很難求得.當(dāng)矩陣M是對角元為 正數(shù)的丑-矩陣時，Mathias和所想給出了計算c(M)下界的方法回， min A.inZ)c(M)max 脂 t=:c(b), PbeR,b0 ,其中崩是”的比較矩陣.上式中Mathias和戶奶g只給出了當(dāng)肱是對角元為正數(shù)的質(zhì)矩陣時計算以的 下界

20、的方法，但無法精確計算出c(的的值.2005年，Chen和Xiang在Mathias 和兒花研究的理論結(jié)果上利用區(qū)間法，得到了當(dāng)矩陣辨是P-矩陣時線性互補 問題解的誤差界.定理1.2.2設(shè)M = (%)*”為P-矩陣,則對任意的xeR”,有 HL，騷(1 -D + DM )- J (x 丸, 其中x*是LCP(M,g)的解，n-diag)(O l)正對角矩陣.定理1.2.2所給誤差估計式比(1)式更容易計算，且所得的精確度更高. 隨后，眾多國內(nèi)外學(xué)者對該問題進(jìn)行了研究，并給出了當(dāng)矩陣具有某些特殊 結(jié)構(gòu)時，線性互補問題解的誤差界的估計式.例如，2016年Garcia-Esnaola和 Pena給

21、出了當(dāng)矩陣M是B-ReAmsov矩陣時，線性互補問題的含有參數(shù)的誤差界.定義1.2. 3設(shè)M = (%)次”、，皿0,若其中/-I mn&W)：=|如仇(=W)+Z|%|,苦J=1 秫力J=/+l則稱矩陣Af為Nekrasov矩陣.定義 1.2. 423設(shè)MC二 M = 8*+C ,且叫,0,對任意的iuN,其中四一苛形2一亍叫一 TOC o 1-5 h z 4+*礦=廚=阻一尸2吼-上+Mm 一匕 ” 一匕，mnn-rn J# + +C= * 上4+4M & ，7廠:=max 0, % | J .若礦是主對角元為正數(shù)的Nekrasov矩陣，則稱汩為 B Nchasov 矩陣.定理 1.2.

22、3 迎設(shè)=(% L,Q c C”“， 2 2 為 B-Nekrasov 矩陣，并存在 左1,使得皿max0,% 13=f.令叫=4,7 = 1,2,./ 1,吧產(chǎn) 4- + g 0J-正對角矩陣砂-diag (叫,嗎,町)，叫 0,歹為定義1.2. 4所示，則房.=頃=&）皿戶為嚴(yán)格對角Z-矩陣，且瞬件。+。樹。|7；+,Vz G1V :Pjj-尸）伐們*）丫（灼其中廠:=max。，叫,IJ。，,則稱矩陣M為DB-矩陣.2011年，國內(nèi)學(xué)者?！敖o出了當(dāng)矩陣肱是D3矩陣時，其線性互補問題解的誤差界.定理1.2. 4網(wǎng)設(shè)以=為班-矩陣,且xmc.設(shè)B+ = &）Il0= / e N11婦 & （礦

23、）,扇 | - RJ侄）=min巾+）:=min侑0照一咒3）=|站|一與（礦），則下列結(jié)論成立cr、W-1)max + max*J(/-D-rDM)1max時0邛maxv、max. 服序瓦回兩s微）A（o| ；若M是3-矩陣，則麟（/-D +如尸 ILSt），其中1 = max+ max max -,A GO | ；若M不是昆矩陣，存在心-Q使得知&（礦），貝Umax |（Z-Z）+。心尸|L （一1）maxm,%,其中7 = max*max。,)I心+ max= max+ max冒朗上嚴(yán)而，特別地,max婦0,1|(/ - D + DM)_l J 0.特別地，如果矩陣M是Z-矩陣時，則叫

24、0,再 0其中p = min-冊|& =吧盹*，=啰苔此外還有眾多國內(nèi)外學(xué)者對H-矩陣類矩陣線性互補問題誤差界估計式及最 優(yōu)誤差界做了許多研究，參見文獻(xiàn)32-35.1. 3本文的主要工作線性互補問題解的性質(zhì)主要與所定義的矩陣性質(zhì)有關(guān)，本文研究矩陣M為 刀Z矩陣，QZ-8矩陣，QSQZ）矩陣線性互補問題解的誤差界估計問題，并給出 相應(yīng)的誤差界估計式.第二章利用DZ矩陣的逆矩陣的無窮范數(shù)的上界，根據(jù)。Z矩陣和DZ-B矩 陣是汗矩陣的子類及H-矩陣的性質(zhì)，進(jìn)而得出具有正對角元的Z）Z矩陣和DZ-B 矩陣是P-矩陣的子類，得到當(dāng)矩陣M是OZ矩陣DZ-3矩陣時，線性互補問題解的誤差估計式:（1）當(dāng)M是O

25、Z矩陣時，根據(jù)DZ的逆的無窮范數(shù)的性質(zhì)，得到OZ矩陣線 性互補問題解的誤差界估計式.麟”-。+吐如密（颼V （以）,配炊 ），并用數(shù)值實例表明該誤差界對線性互補問題近似解的估計是有效的.（2）當(dāng)M是DZ-B矩陣時，首先將DZ-B矩陣M分解成M =礦+C ,其中B+ 是DZ矩陣同時也是Z矩陣且對角元為正數(shù)，C是秩為1的非負(fù)矩陣，然后構(gòu)造單調(diào)遞增函數(shù)，得到當(dāng)矩陣沮是矩陣時線性互補問題解的誤差界估計式,max姐0.1+0, 潤，則對任意的xeO,l,有1一才 +形 min/j + y 引理2.1.23?:設(shè)M =是OZ矩陣，則存在對角矩陣。使得郴是SDD矩陣.引理2.1.3助設(shè)M = S/CfDZ矩

26、陣.則MTL - max偵%（M）,尚洽 %（），其中聞, +網(wǎng)，Ji%()U福-(M)+隊| 肱|-|祖J曲)，%()=1J-冊)+hl!+血)l-喝曲)2. 1 Dashnic-Zusmanovich矩陣線性互補問題解的誤差界估計本節(jié)將研究F-矩陣的一個重要子類-原矩陣線性互補問題解的誤差界估計 問題.設(shè)矩陣” = (%)6C”“，記匕(M):w N /： (|w|- r；(M) pl J I% | ri(M) , i e N 由定義2.1.1,若矩陣M為DZ矩陣，則存在ieN,有max.忙為(M )=max阮 i - m”)|%| |呵 I。w) ,(l%l)| 灼 | Kh W) o.

27、定理2. 1. 1設(shè)M = (%.)C為DZ矩陣，且對任意的心，叫0.令M = /-D + DM = wJ其中正對角矩陣D = diag(d),0dj 1 .則max|(/-D + W)- max (max (也0,max其中S mm(minS廣().】 min%,(秫萬 一*(山)秫，一()io1 | 嘩)* 3廠匕證明 因為疚=1 一。+ OM，有 A-dl+dlmliJ = j,mh.= ,故對任意的Lj eN有阮1 = 12次,)F；W)g；(w).對任意的ij,i,jN,有阮-(脫)=阮|-7；(揚)+機(jī):/卜0/)+4帕|= d，3-q W)+|?J) |礦(療)|阿，卜伽If (

28、脫)+切阮I(lǐng)2 0叫-W)+41%| 加 J =4(%-匕 w)+M)MI 2* W)|%|.由QZ矩陣的定義知，舫是。Z矩陣.注意到Q-dj+d如-d/弓(A/ ) + CJ)(l -+婦)S (M ) njt |- 4 + + d,-d, + d產(chǎn)jj -電弓(M)+ 電%)(1-4+4%)1 -4 弓 W)4%(1 _ % + d煦日 一 djrj (M)+dJ勺J) (1 -.+ )1土min % - rt(A/) +mn(C)+KI)，min %1勺，7；W)(% 一。W)+|) w廣。W)+%S” + %機(jī)Jmin(以)+ r毗 1 mine(坦廠。()+帆 I)% | 叫 |%|

29、min- r, (M) + mti |, 1 j min w,/5lSi w )+W)甜J%min &rf (由),1 min %,13力 F(M)%T7,W)且a帶）一機(jī)E （脂）+ 1砌+以由）2（阮 I - 0 （府）+厄,I 阮 HM； F）=_dj.dmjL d 凸（歸）+ 均恤+ （歸）（1+d如一可（A/）+dJ）（l-+加,）一（M 網(wǎng)楫 jd + d廣n d：(M)十d(1 一。+ d,mjS - djj 偵4 ) + d,卜%)(12+皿)I-diriM)dj-勺+們叫廣電弓（M）+dj hJ）（l-d, +如）(M)p (1 _ 4 + 煩J (1 一 4 + dj%-

30、d凸(M)+dt mfi ) (1 一 苗 + d/% )1-min阮,1 何廣弓（M）+ f(min 阮,13廠0(M)+ %，)f%q (M)3廠。（庭）+勺)叫11匕W)min叫,1+ (秫力 (M)min%,lmn弓街）1 S 力T（M）扁,】2 +勺叫廣dp、()+4 |勺,|)。-4+4% )由引理2. L3得max&【curmaxmax 77, (MY max 爪M = I-D + DM =.%，max婦0”|(7-/)+Z)A/)1| maxl max 鞏(Af), max rj.證畢.當(dāng)矩陣沮具有某種特殊結(jié)構(gòu)時，即當(dāng)對任意的心，舟=1時，有定理2. 1.1簡化為下列結(jié)果.推論

31、2.1.1設(shè)=wC”為DZ矩陣，且對任意的iwN,陽.F.令其中正對角矩陣D=diag0）, 01,則，斕（2 + | max00其中1+1%若布萬一 rj W ) 1,（-匕（庭）秫”-阮,則mn+mu Kj(勺7 -冊) -勺,k W)功（M）=0 (“)=(勺廣尸；(沮)成+|勺J（成力一坦（M）仆）、擔(dān)力-尸伽）mJ 曲）.注 2. 1. 1 特別地，若 m /7 - (M ) 1 和 mtl 1 和 1 和 1 ,則門（M = SW）.1（仇廠】（肱） - ，（沮）,定理2. 1. 1給出了 QZ矩陣線性互補問題解的誤差界估計式，下面用數(shù)值算例討論結(jié)果的有效性.例2.1.1考慮。Z矩

32、陣0.4、0.6 .1 ）不難看出矩陣M不是良矩陣，故誤差界*爵一O +0.750.500.510.5不能由文獻(xiàn)250,其中矩陣8+和矩陣c如定義2. 2.1所示，則max |（7-n + DAf）_1| （ zz-I ）max （蜜x t（叮.g&-匕3）如小小佞）-1co下面給出的上界.因為月,是OZ矩陣，B+ = I-D + DB由定理2. 1. 1知萬+也是OZ矩陣，類似于定理2.1.1的證明可得, max00（眼y頃）膘礦）,其中（氣-小;）,+（礦）=min%Dl min,證明 因為M是DZ-B矩陣，M = B+ C如定義2.2. 1所定義，其中礦是DZ矩陣同時也是Z-矩陣且對角元

33、為正數(shù)，正對角矩陣D=diag（d）, 01, 有M I-D + DM =（I-D + DBDC = B rC .其中方+ =1 0 + 0礦，c = z）c.由文獻(xiàn)25的定理2得，其中1（加” 3*）板一穌 kW）1_ | ,，您）值+）二 min如,1 0廠r；伍+）min如,1max (n- )max I max 礦). max %兀a如7 證畢.推論2. 2.1設(shè)” = （%）wC”x”是OZ也矩陣，且對任意的ieN, %0.若矩陣M為Z-矩陣，則max婦o,】r(I-D + DM)0C罰食偵W（）,畔（,其中n（B+）, mS*）如定理2.2.1所示.注2. 2. 1特別地,若b廠r

34、；（B+）和如工1,則若bj廣而）1和九G,則（如”（礦）如+制代;混+）就Td礦）若-r；（5+）l和&,1,則hi +bH p p點）3廠匕（礦）如邛若；（8+）1和九1,則p-矩陣有各種亍類，如8-矩陣25, DB矩陣28, B-Nekiasov矩23, SB- 矩陣29, 30等.為了討論所提出的DZ必矩陣與上述這些矩陣類的關(guān)系，下面,給出上述矩陣的定義.設(shè)M = （m，wC*M = B+C,其中-和C如定義2. 2. 1所示.（1）若礦是SDQ矩陣且主對角元為正，則稱M矩陣為8-矩陣；（2）若歹是DSDD矩陣且主對角元為正，則稱必矩陣為08-矩陣；（3）若存在沖的非空真亍集S,使E*

35、為S-SDD矩陣且主對角元為正，則稱M矩陣為SB-矩陣.基于SDZ)矩陣，OZ矩陣,DSDD矩陣，S-S如矩陣和Nekrasov矩陣的關(guān) 系，可以得到相應(yīng)的3矩陣，矩陣，08-矩陣，SB-矩陣，B-Nekrasov矩陣 的關(guān)系，見圖2.1.文獻(xiàn)25中Garcia-Esnaola和Pefia給出了當(dāng)矩陣M是B-矩陣時,線性互補 問題的誤差界估計式.定理2.2.2如 設(shè)M = (mjECw,M = B*+C為B-矩陣，其中8和C如定 義2. 2.1所示，設(shè)& :=做)和P：= min但則max|l(Z-Z) + Z)A/)_lll/血沖化 min伊,1因為務(wù)矩陣是OZ-B矩陣，若當(dāng)矩陣M是身矩陣時

36、，定理2.2.1同樣也能 給出的上界推論2. 2.2設(shè)M = S)eL”,M = B、C為B-矩陣，其中矩陣和矩陣C 如定義2.2.1所示.設(shè)有:=如-匕(礦)和歹=嗯1角 則式成立.且若對任意 的ieNt btif 則max( max % (丁), max n,(B+ 1,則max max 成）,max 礦、1心必們 /me 5 min （Al其中77（B+）,億（礦）如定理2. 2. 1所示.證明 因為E矩陣是DZ也矩陣，注意到8+是SOQ矩陣且主對角元為正,即（礦）4，其中/應(yīng)）= N，.若對任意的iwN, &且對任意的i，MN , E,有礦）（礦）如C,0 v如.一心（礦）1和0i,-

37、r/（B+）l.由注2. 2. 1得“（B，）=如I姐1 （如-礦）+6小書施+）另一方面，當(dāng)滿足上述情形下且min0,l=時，貝！J_ J_ I _1_1_mill伊,1 P 唧舟min 如-仆）吧乎如一二同 因為也 I 1,、 0廣川+）+如）如-|弓頃） 珈婦一演）， 若I礎(chǔ)F（礦冏醐（礦），將上述不等式兩邊同時乘以|如|0,則站-仙服I屯他W（礦膈I，即I九-匕（礦版|+|礎(chǔ)如冊（礦）%穌|財項礦服1-川+）時.化簡得（N+I&I）低 E（礦）k （時-尸；（礦）隔-。（礦）|&|,則九+|如I1（如一。）+&）&,穌k （日一限-由+）1 1另一方面，若隔F0+）邛（礦）和I砌=0,

38、 （7）式顯然成立,若時0,不等式兩邊同時乘以切0得|冊J -皈）時 |叫卜仁（礦）時,即切閾-小珈J+M如卜小珈邛砰-。（礦州+閾隔項礦）制,和I林項礦膈+RME（礦）隔 -，；例）IU+M砸-。3）隔，化簡得（如+時炯E（礦）（-尸；0*）服If（礦肉|，即 如 + |.n |匕 h -。（礦）+如邛，. k （礦廠時-弓供）1 1若對任意的jN, /3.=如-七3）,且對任意的i,jN,2N ,貝ljbjj 1+。（礦）,如 1和b廣1（）邊廠弓成）1由注2. 2. 1得“（3力-礦）+、）q 幅 k （礦） （bji _.（.+ ）+禺）如 + 九 （如-）+如）4- g k 但+）

39、滿足上述情形且min0,l=l,和=min 01 成立.綜上所述，對任意的i,心,2j ,則1切|侄）.同時（4）式也成立.同理 可得，對任意的KjeNJ手j,證畢.推論2. 2. 2表明，當(dāng)M是3-矩陣時，定理2. 2. 1給出了 3-矩陣線性互補問 題誤差界中的孺WIO D + D材尸L的新上界因此，一般來說，當(dāng)矩陣以是 8-矩陣時，可以取這兩上界中最小者估計3-矩陣線性互補問題解的誤差界，即 斕湖）*1）響扁鬲,max畔嘴例2. 2. 1考慮DZ-B矩陣=礦+。,其中不難看出矩陣M不是&矩陣，故誤差界*頓-D + DM）%不能由文獻(xiàn)25慶%。fM %為=。 -M,C =M X ML /

40、1 00017中的定理2.2和38的定理4的誤差估計式給出.另一方面，顯然礦是DZ矩 陣，則M是DZB矩陣，由定理2. 2. 1得 瞬孕.例2.2.2考慮OZ-E矩陣36 6 2 _3、3 18 一 98M =，+C-3 -15 21 -4、-1 6 2 21 ?易得到C=0, B+=M 不是SDD矩陣，QSDD矩陣，S-SDD矩陣，也不 是Nekraov-矩陣.因此，矩陣M不是3-矩陣，08-矩陣，SR矩陣，B-Nehaov 矩陣.故誤差界L不能由文獻(xiàn)25, 28, 29, 29, 23中的誤差估計給出.另一方面，顯然是QZ矩陣，則M是DZ-B矩陣，由定理2.2.1得max |(7 -D +

41、 DM ) | 且“22.若-閔匕(刀)，WeN,則稱刀為嚴(yán)格對角占優(yōu)矩陣，記作AeSDD.若是不可約的，aitrA), i&N,且至少有一個嚴(yán)格不等式成立，則稱為不可約對角占優(yōu)矩陣，記作.4住ZDD.若國|勾|*3)。( P Lj-N, f,則稱4為雙嚴(yán)格對角占優(yōu)矩陣，記作AeDSDD.記+3) = 苦 /；(),_() =件 N：|%| aC4).顯然一(4)U一(Z)= N.眾所周知，SDD矩陣是QSDD矩陣，也是非奇異矩陣，主對角元為正的 實H-矩陣是戶-矩陣.引理3. 1.1他 設(shè),4 = 0準(zhǔn)仗以”為叫。矩陣.則存在正對角矩陣 Z)=diag(d2，0j，d, 0,使得4?是SOD

42、矩陣，即A為H-矩陣.引理3. 1.2：龍設(shè)Z = （%）eC為SDD矩陣.則L氣機(jī)園引理3. 1.3U0設(shè)=（?。〦C為H-矩陣且主對角元全為正，即存在正對 角矩陣d = 6Z/ 0 對任意的，使得,4。是SDD矩陣，則max拓0邛由（8）式易知，正對角矩陣5的對角元,心）為參數(shù).然而，在實際計算 中并不實用.到目前為止，筆者沒有見到如何確定&的取值范圍的相關(guān)結(jié)果. 的取值問題及（8）式的最優(yōu)值問題將是本章的主要研究內(nèi)容，即當(dāng)矩陣刀是 DSDD矩陣時，d,在定理3. 2. 1中給定條件下，討論了（8）式的最優(yōu)值問題.3.1雙嚴(yán)格對角占優(yōu)矩陣線性互補問題誤差界的最優(yōu)值若一3）=。，即一3）=N

43、,矩陣A SDD占優(yōu)矩陣，則矩陣刀的線性互補 問題誤差界可以直接利用引理3. 1.2獲得.本節(jié)主要對 _（刀）。情況下的 DSDD矩陣的線性互補問題誤差界最優(yōu)值進(jìn)行研究.定理3. 1. 1設(shè)A = （a. ） e Cn0,且早缶 rvo I人牛肢,則存在正對角矩陣J = g（wPw2,.,w）,其中, j_（），XVS G1, 心一，使得附是SOD矩陣，且 max max在0邛其中餌=%嗎一幅時.證明 易證AW為SDD矩陣.進(jìn)一步，對所有的6/0.1有（7-D+ D.4）W =（研廣】+ D 稱啊廠 I + DAlir） W =（股 + DIV+DAW）印廠所以（I-D-DA） W也是SDD矩

44、陣且主對角元為正.由引理3. 1.2得max 0,1|(/-n+214)_| =k(甲一切皆 + 214 砂)一1lx-IkIL -DW + DAwYmax吧_ min(l- d,)叱 + dJPi) *i/記min(1 -dt)+ dlPi = (1 -)wf +d,& Nminw”& 2呻1 嗎.若一 (,4片0,則|一 (航=1,即只有一個使得|%。由。SDD矩陣定義得i氣3)hJ，b則/=5,且inf,nnn若農(nóng)1,且猝=其，S一(礦即m,in* =無，則件)專,且inf冉 min-t.阪| 土 R|、（時=- %min ；- g)min 1 x a,W)若方1,且萬，心_（刀）,即m

45、in女 = &,則/（）= *，且E)inf /（,）= T勇I、.春如專yl%S r 3）+用）j證明由定理3. 1.1得f()= max 若療21,則仲）=6 ,且（遙（2）若萬1,且萬=無，3_（4）,即叫in伊=其，且 A 8%-展4)，因為fG）o,則_/0）在區(qū)間上為單調(diào)遞減函數(shù)，于是inf 、|。扁,皿如）, 一%,-E)min-N_ 。(/) min也若療1,且E = R,任一（力，即mjn物=度,則 0, -，；（，） 一 （。1）幅因為/何)0, /()在區(qū)間上為單調(diào)遞增函數(shù)，貝U W)1 K)=|氣,如|(?！?匕3)+|%|陣證畢.maxf/efO.ir(ID + DA

46、ymax co推論3.1.1若|A_()| = 0,即是SDD矩陣，取正對角矩陣W=1,則證明 若|_(,4)| = 0,即4為SDD矩陣，取破寸,唱X = =1,仙叫=0.maxre0,ln(7-Z)+ DA) max-oc= max,m,in 攜證畢.3. 2數(shù)值例子例3. 1. 1考慮Z)SZ)Z)矩陣 TOC o 1-5 h z 422.50、=】4 I0.5 0.5 5 I、0.4 0.617,由引理3. 1.3得,正對角矩陣B=diQg(0.7414,0.5061,0.3814,0.2831),故應(yīng)用式 得max2.6188(io)而由定理3.1.1得麟IS2,考慮、DSDD占優(yōu)矩

47、陣2k -k-2R + 3 k /由引理3. 1.3得，正對角矩陣Ddiag2kT M-3 F,故應(yīng)用(8)式得max 4.000(12)而由推論3.1.1得(13)I 2.000進(jìn)一步，應(yīng)用 MATLAB 代碼 for i=l: 1000;D=diag（rand（4,l）;end” 隨機(jī)取 1000個矩陣并計算+ L的值，參見圖3. 2.圖3.2例3.1.2隨機(jī)取1000個矩陣Z）下的最優(yōu)值圖3.2中“表示，取1-1000時所對應(yīng)（7-D + Z）M）_1j的值，顯然（13）式比（12）式更精確.綜上，本章在_（）/情況下，對正對角矩陣咋花叫,可2,羽），且叫取滿足定理3. 1. 1中的條件

48、下的時的DSQD矩陣線性補問題解的誤差界進(jìn)行研究，得到了/（時,的最優(yōu)值，這個值是存在的并且是可計算的.第四章總結(jié)第四章總結(jié)本文主要討論了 QZ矩陣、DZ-3矩陣和DSDD矩陣線性互補問題的誤差界 估計問題，從特殊矩陣的結(jié)構(gòu)和性質(zhì)入手，構(gòu)造具有參數(shù)的正對角矩陣，應(yīng)用不 等式放縮和函數(shù)單調(diào)性，得到線性互補問題誤差界新的估計式.本文所得結(jié)果總結(jié)如下:（1）給出了當(dāng)矩陣是OZ矩陣時，線性互補問題解的誤差界估計式|（。+5孔即虬略（肱）,蜉華（叫max | II其中花廠r；（M）叫,（團(tuán)1 理）77（X）= min柵急（電-/Q/Dmin叫,11（2）給出了當(dāng)矩陣M是DZ-B矩陣時，線性互補問題解的誤

49、差界估計式 |（/+5此（婦）順 %（質(zhì)）嘴部2頃），maxdwg,】其中S” ;. _ min如-匕(7T)1廠 min如,1,如-如 M礦）_ _+ _虬何+）二 min如,1 0廣0+）而話如,1I她（碩九 給出了當(dāng)矩陣電是DSQQ矩陣時，線性互補問題解的誤差界的最優(yōu)值maxCCcmin 丹其中:=與 叫- 圳L.j0再對（3）式進(jìn)行討論得到最優(yōu)解凡：=% -E），A n3）-（T）|%J，B： = mjn極.（1）若在21,則/（）= ,且inf若B1,且療=其，樨）,即mjn0 =凡，則/（）= *，且inf 、 方理min上I 少。rAAf （牛min 會M）inf f（）=I K

50、 。（巧fl若B1，且月=丹，心_（以），即min岳 = 0”則（）= *且 E）氣（。（，）+幅）-。0虹I ,參考文獻(xiàn)彭凌.幾類特殊矩陣線性互補問題的誤差界D.吉首大學(xué)，2015.M. Jansen. Equilibrium points ofbimatrix games J. Journal of the Society fbr Industrial &Applied Mathematices, 1964, 12(4)： 778-780.何素艷.互補問題算法研究及其在力學(xué)中的應(yīng)用D.大連理工大學(xué)，2003.苗新河.Hilbert空間中Lorentz錐線性互補問題的理論研究D.天津大學(xué)，2

51、010.吳軍榮.非線性互補問題的水平值估計算法D.上海大學(xué)，2010.M. C. Ferris. J. S. Pang. Engineering and economic applications of problemsJ. SIAMReview, 1997,39(4):669-713.J. S. Pang. Complementerity problems:vij. Kluwer Academic Pulishers, Boston, 1994.A. M. Al-Fahed. G. E. Stavroulakis and P. D.Panagiotopoulos. A linear comp

52、lementarityapproach to the friction less gripper problemfJ. Internetional Journal of Robotics Research, 1992. 11: 112-122.K. G. Murry. Linear complementarity, linear and Nonlinear programiningM. Heldermann,1988.R. W. Cottle, J. S. Pang, R. E. Stone. The Linear Complementarity ProblemsM. New York: Ac

53、ademic Press, 1992.M. M. Kostreva. M. M.Wiecek. Linear complementarity problems and multiple objective programmingf J. Mathematical Programming, 1993,60(1-3): 349-359.Z. Z. Bai. On the convergence of the multisplitting methods fbr the linear Complementarity probIeniJ. SIAM Journal on Matrix Analysis

54、 And Applications, 1999, 21 ：67-78.J. S. Pang. Error bounds in the mathematical programmingJ. Mathematical Programming. 1997, 79:299-332.N. Xiu, J. Zhang. A characteristic quantity of 尸-matrices J. Applied Mathematices Letters, 2002,15:41-46.J. C. D Bremaecker. M. C. Ferris. D. Railph. Compressional

55、 fractures considered as contact problems and mixed complementarity problems J. Engineering Fracture Mechanics. 2000. 66(3): 287-303.f 16 O. L. Mangasnricm, T. H. Shiau. Error bounds for monotone linear complementarityproblems J. Mathematical Programming, 1994, 36: 81-89.Z. Q. Luo, O. L. Mangasarian

56、, J. Ren, and M. V, Solodov . New error bounds fbr linear complementarity problemsfJ. Mathematics of Operations Research, 1994, 19: 880-892.O. L. Mangasari an. Error bounds fbr monotone linear complementarity problems J. Mathematical Programming. 1990,48: 437-445.O. L. Mangasarian, J. Ren. New impro

57、ved error bounds fbr linear complementarity problems. Mathematics of Operations Research, 1994,66:241-255.R. Mathias. J. S. Pang. Error bounds fbr linear complementarity problems with a P-matrixJ. Linear Algebra App, 1990, 132: 123-136.X. J. Chen, S. H. Xiang. Perturbation bounds of P-matrix linear

58、complementarity problemJ. SIAM Journal on Optimization, 2007, 18: 1250-1265.M. Garcia-Esnaola. J. M. Pena. Error bounds for linear complementarity problems of Nekrasov matrices. Numerical Algorithms. 2014, 67(3): 655-667.M. Garcia-Esnaola, J. M. Pena. B-Nekrasov matrices and error bounds for linear

59、complementarity prob!emsJ. Numerical Algorithms, 2016, 72(2): 435T45.J. M. Pena. A class of P-matrices with applications to the localization of the eigenvalues of areal matrix J. SIAM Journal on Matrix Analysis and Applications, 2001. 22(4): 1027-1037.M. Garcia-Esnaola, J. M. Pena. Error bounds for

60、linear cornplementarity problems fbr S-matrices J. Applied Mathematices Letters, 2009. 22: 1071-1075.M. Garcia-Esnaola, J. M. Pena. Error bounds fbr linear complementarity problems involving B -matrices J. Applied Mathematices Letters, 2012. 25: 1379-1383.M. Garcia-Esnaola, J. M. Pena. Error bounds