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

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

2、襲行為。與作 者一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示了謝 意?，F(xiàn)就論文的使用對(duì)云南大學(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ī)范審查、社 會(huì)監(jiān)督或評(píng)獎(jiǎng)；學(xué)校有權(quán)將學(xué)位論文的全部或部分內(nèi)容錄入有關(guān)數(shù)據(jù)庫(kù)用于檢索服務(wù)。（內(nèi)部或保密的論文在解密后應(yīng)遵循此規(guī)定）研究生簽名：左諭姣導(dǎo)師簽名：手曲遷日期：摘要線性互補(bǔ)問(wèn)題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)格對(duì)角占優(yōu)(/KDD)矩陣線性互補(bǔ)問(wèn)題解的誤差界估 計(jì)問(wèn)題，分別得到了只與矩陣的元素相關(guān)的上界，具體內(nèi)容如下.第二章研究了 OZ矩陣、DZ-與矩陣線性互補(bǔ)問(wèn)題解的誤差界估計(jì).利用Z)Z矩 陣的逆矩陣的無(wú)窮范數(shù)的上界及DZ矩陣的結(jié)構(gòu)和性質(zhì)，結(jié)合不等式的放縮方法， 得到了 OZ和。Z-8矩陣線性互補(bǔ)問(wèn)題解的誤差估計(jì)式.同時(shí)，給出數(shù)值例子表明 結(jié)果的有效性.第三章研究了 QS加矩陣線性互補(bǔ)問(wèn)題解的最優(yōu)誤差界.針對(duì)文

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-短 陣線性互補(bǔ)問(wèn)題誤差界的估計(jì)式，利用QS如矩陣的性質(zhì)和函數(shù)的單調(diào)性，得 到了 OSDD矩陣線性互補(bǔ)問(wèn)題解的含有參數(shù)的誤差界的最優(yōu)值，最后用數(shù)值例 子驗(yàn)證了所得結(jié)果.關(guān)鍵詞：線性互補(bǔ)問(wèn)題；誤差界；H矩陣;刀Z矩陣；QZ也矩陣；雙嚴(yán)格對(duì) 角占優(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 矩陣線性互補(bǔ)問(wèn)題解的誤差界91。小記討湖矩陣線性互補(bǔ)問(wèn)題解的誤差界估計(jì)10 HYPERLINK l bookmark50 o Current Document 2. 2 Dashnic-Zusmanovich-B矩陣線性互補(bǔ)問(wèn)題解的誤差界估計(jì)13 HYPERLINK l bookmark62 o Current Document 第三章雙嚴(yán)格對(duì)角占優(yōu)矩陣線性互補(bǔ)問(wèn)題的最優(yōu)誤差界23 HYPERLINK l bookmark68 o Current Document 3.1雙嚴(yán)格對(duì)角占優(yōu)矩陣線性互補(bǔ)問(wèn)題誤差界的最優(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第一章緒論本章首先介紹線性互補(bǔ)問(wèn)題的概念、研究意義和應(yīng)用領(lǐng)域，再對(duì)近年來(lái)國(guó)內(nèi) 外學(xué)者關(guān)于線性互補(bǔ)問(wèn)題誤差界的研究現(xiàn)狀進(jìn)行概述，最后對(duì)本文的內(nèi)容進(jìn)行簡(jiǎn) 要闡述.1.1

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

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

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

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

18、關(guān)的定義.令表示所有階實(shí)矩陣（復(fù)矩陣）所成的集臺(tái).指標(biāo)集 7V= 1,2,設(shè)M =頃準(zhǔn)R* ,對(duì)任意的沱記S SN-對(duì)于有限集S,用|S|表示集合S的勢(shì).定義.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)矩陣線性互補(bǔ)問(wèn)題解的誤差界估計(jì)，國(guó)內(nèi)外學(xué)者做了許多 研究.當(dāng)矩陣M是R矩陣時(shí),LCP(M, g)存在唯一解U。, 1990年,Mat

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

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

21、出了當(dāng)矩陣M是B-ReAmsov矩陣時(shí)，線性互補(bǔ)問(wèn)題的含有參數(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,對(duì)任意的iuN,其中四一苛形2一亍叫一 TOC o 1-5 h z 4+*礦=廚=阻一尸2吼-上+Mm 一匕 ” 一匕，mnn-rn J# + +C= * 上4+4M & ，7廠:=max 0, % | J .若礦是主對(duì)角元為正數(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-正對(duì)角矩陣砂-diag (叫,嗎,町)，叫 0,歹為定義1.2. 4所示，則房.=頃=&）皿戶為嚴(yán)格對(duì)角Z-矩陣，且瞬件。+。樹(shù)。|7；+,Vz G1V :Pjj-尸）伐們*）丫（灼其中廠:=max。，叫,IJ。，,則稱矩陣M為DB-矩陣.2011年，國(guó)內(nèi)學(xué)者?！敖o出了當(dāng)矩陣肱是D3矩陣時(shí)，其線性互補(bǔ)問(wèn)題解的誤差界.定理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時(shí)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-矩陣時(shí)，則叫

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

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

26、陣.則MTL - max偵%（M）,尚洽 %（），其中聞, +網(wǎng)，Ji%()U福-(M)+隊(duì)| 肱|-|祖J曲)，%()=1J-冊(cè))+hl!+血)l-喝曲)2. 1 Dashnic-Zusmanovich矩陣線性互補(bǔ)問(wèn)題解的誤差界估計(jì)本節(jié)將研究F-矩陣的一個(gè)重要子類-原矩陣線性互補(bǔ)問(wèn)題解的誤差界估計(jì) 問(wèn)題.設(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矩陣，且對(duì)任意的心，叫0.令M = /-D + DM = wJ其中正對(duì)角矩陣D = diag(d),0dj 1 .則max|(/-D + W)- max (max (也0,max其中S mm(minS廣().】 min%,(秫萬(wàn) 一*(山)秫，一()io1 | 嘩)* 3廠匕證明 因?yàn)榫?1 一。+ OM，有 A-dl+dlmliJ = j,mh.= ,故對(duì)任意的Lj eN有阮1 = 12次,)F；W)g；(w).對(duì)任意的ij,i,jN,有阮-(脫)=阮|-7；(揚(yáng))+機(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)時(shí)，即當(dāng)對(duì)任意的心，舟=1時(shí)，有定理2. 1.1簡(jiǎn)化為下列結(jié)果.推論

31、2.1.1設(shè)=wC”為DZ矩陣，且對(duì)任意的iwN,陽(yáng).F.令其中正對(duì)角矩陣D=diag0）, 01,則，斕（2 + | max00其中1+1%若布萬(wàn)一 rj W ) 1,（-匕（庭）秫”-阮,則mn+mu Kj(勺7 -冊(cè)) -勺,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矩陣線性互補(bǔ)問(wèn)題解的誤差界估計(jì)式，下面用數(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下面給出的上界.因?yàn)樵?是OZ矩陣，B+ = I-D + DB由定理2. 1. 1知萬(wàn)+也是OZ矩陣，類似于定理2.1.1的證明可得, max00（眼y頃）膘礦）,其中（氣-小;）,+（礦）=min%Dl min,證明 因?yàn)镸是DZ-B矩陣，M = B+ C如定義2.2. 1所定義，其中礦是DZ矩陣同時(shí)也是Z-矩陣且對(duì)角元

33、為正數(shù)，正對(duì)角矩陣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也矩陣，且對(duì)任意的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點(diǎn)）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矩陣且主對(duì)角元為正，則稱M矩陣為8-矩陣；（2）若歹是DSDD矩陣且主對(duì)角元為正，則稱必矩陣為08-矩陣；（3）若存在沖的非空真亍集S,使E*

35、為S-SDD矩陣且主對(duì)角元為正，則稱M矩陣為SB-矩陣.基于SDZ)矩陣，OZ矩陣,DSDD矩陣，S-S如矩陣和Nekrasov矩陣的關(guān) 系，可以得到相應(yīng)的3矩陣，矩陣，08-矩陣，SB-矩陣，B-Nekrasov矩陣 的關(guān)系，見(jiàn)圖2.1.文獻(xiàn)25中Garcia-Esnaola和Pefia給出了當(dāng)矩陣M是B-矩陣時(shí),線性互補(bǔ) 問(wèn)題的誤差界估計(jì)式.定理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因?yàn)閯?wù)矩陣是OZ-B矩陣，若當(dāng)矩陣M是身矩陣時(shí)

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

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

38、 （7）式顯然成立,若時(shí)0,不等式兩邊同時(shí)乘以切0得|冊(cè)J -皈）時(shí) |叫卜仁（礦）時(shí),即切閾-小珈J+M如卜小珈邛砰-。（礦州+閾隔項(xiàng)礦）制,和I林項(xiàng)礦膈+RME（礦）隔 -，；例）IU+M砸-。3）隔，化簡(jiǎn)得（如+時(shí)炯E（礦）（-尸；0*）服If（礦肉|，即 如 + |.n |匕 h -。（礦）+如邛，. k （礦廠時(shí)-弓供）1 1若對(duì)任意的jN, /3.=如-七3）,且對(duì)任意的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 成立.綜上所述，對(duì)任意的i,心,2j ,則1切|侄）.同時(shí)（4）式也成立.同理 可得，對(duì)任意的KjeNJ手j,證畢.推論2. 2. 2表明，當(dāng)M是3-矩陣時(shí)，定理2. 2. 1給出了 3-矩陣線性互補(bǔ)問(wèn) 題誤差界中的孺WIO D + D材尸L的新上界因此，一般來(lái)說(shuō)，當(dāng)矩陣以是 8-矩陣時(shí)，可以取這兩上界中最小者估計(jì)3-矩陣線性互補(bǔ)問(wèn)題解的誤差界，即 斕湖）*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的誤差估計(jì)式給出.另一方面，顯然礦是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中的誤差估計(jì)給出.另一方面，顯然是QZ矩陣，則M是DZ-B矩陣，由定理2.2.1得max |(7 -D +

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

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

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

44、陣且主對(duì)角元為正.由引理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,即只有一個(gè)使得|%。由。SDD矩陣定義得i氣3)hJ，b則/=5,且inf,nnn若農(nóng)1,且猝=其，S一(礦即m,in* =無(wú)，則件)專,且inf冉 min-t.阪| 土 R|、（時(shí)=- %min ；- g)min 1 x a,W)若方1,且萬(wàn)，心_（刀）,即m

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

46、ymax co推論3.1.1若|A_()| = 0,即是SDD矩陣，取正對(duì)角矩陣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得,正對(duì)角矩陣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得，正對(duì)角矩陣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個(gè)矩陣并計(jì)算+ L的值，參見(jiàn)圖3. 2.圖3.2例3.1.2隨機(jī)取1000個(gè)矩陣Z）下的最優(yōu)值圖3.2中“表示，取1-1000時(shí)所對(duì)應(yīng)（7-D + Z）M）_1j的值，顯然（13）式比（12）式更精確.綜上，本章在_（）/情況下，對(duì)正對(duì)角矩陣咋花叫,可2,羽），且叫取滿足定理3. 1. 1中的條件

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

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

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

51、010.吳軍榮.非線性互補(bǔ)問(wèn)題的水平值估計(jì)算法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