几类结构矩阵线性互补问题解的误差界

1、分类号024密级 公开UDC 编号硕士营菱也容侬论次题目几类结构矩阵线性互补问题解的误差界Title Error bounds for the linear comDlementarity problems of some classes of structured matrices学院（所、中心）数学与统计学院专业名称系统理论研究方向数值代数研究生姓名冶海姣 学号12016000983导师姓名李朝迁职称 副教授2019年05月扉页:论文独创性声明及使用授权本论文是作者在导师指导下取得的研究成果。除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，不存在剽窃或抄

2、袭行为。与作 者一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。现就论文的使用对云南大学授权如下：学校有权保留本论文（含电子版），也可以 采用影印、缩印或其他复制手段保存论文；学校有权公布论文的全部或部分内容，可以 将论文用于查阅或借阅服务：学校有权向有关机构送交学位论文用于学术规范审查、社 会监督或评奖；学校有权将学位论文的全部或部分内容录入有关数据库用于检索服务。（内部或保密的论文在解密后应遵循此规定）研究生签名：左谕姣导师签名：手曲迁日期：摘要线性互补问题LCP(M, q)在经济学、金融和线性规划等领域有广泛的应用， 其解的存在性、唯一性、灵敏度以及求解算法

3、的收敛性都与矩阵M的结构和性 质有关.本文研究了矩阵 Af 为 Dashnic-Zusmanovich (QZ)矩阵、Dashnic-Zusman- ovich-B (DZ-B)矩阵和双严格对角占优(/KDD)矩阵线性互补问题解的误差界估 计问题，分别得到了只与矩阵的元素相关的上界，具体内容如下.第二章研究了 OZ矩阵、DZ-与矩阵线性互补问题解的误差界估计.利用Z)Z矩 阵的逆矩阵的无穷范数的上界及DZ矩阵的结构和性质，结合不等式的放缩方法， 得到了 OZ和。Z-8矩阵线性互补问题解的误差估计式.同时，给出数值例子表明 结果的有效性.第三章研究了 QS加矩阵线性互补问题解的最优误差界.针对文

4、献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如矩阵的性质和函数的单调性，得 到了 OSDD矩阵线性互补问题解的含有参数的误差界的最优值，最后用数值例 子验证了所得结果.关键词：线性互补问题；误差界；H矩阵;刀Z矩阵；QZ也矩阵；双严格对 角占优阵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研究现状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 第三章双严格对角占优矩阵线性互补问题的最优误差界23 HYPERLINK l bookmark68 o Current Document 3.1双严格对角占优矩阵线性互补问题误差界的最优值2

13、43.2数值例子29 HYPERLINK l bookmark77 o Current Document 第四章总结31 HYPERLINK l bookmark89 o Current Document 参考文献33 HYPERLINK l bookmark132 o Current Document 攻读硕士学位期间完成的科研成果36 HYPERLINK l bookmark138 o Current Document 致谢37第一章绪论本章首先介绍线性互补问题的概念、研究意义和应用领域，再对近年来国内 外学者关于线性互补问题误差界的研究现状进行概述，最后对本文的内容进行简 要阐述.1.1

14、研究背景给定F:R” tR”,求xeRn使其满足如下条件0, F（x） 0, xTF（x） - 0.称该问题为互补问题，记为CPCO；称满足上述不等式的X为互补问题的解当 F（X）是线性函数，即F（x）=Mx + q（Me 荫”.养 R”）时，上述问题称为线性互补问题IF,记为LCP（M,/；否则为非线性互补问题, 记为 NCP（M,g）.互补问题可以分为非线性互补问题和线性互补问题，其中非线性互补问题在 交通平衡问题、流体弹性动态润滑问题、接触力学和经济等领域有着极其广泛的 应用EW4,己成为数学规划中的一个研究热点.经过多年的发展，其数值算法、 理论体系和应用领域己逐步拓展，并成为数学学科

15、的一个重要分支，众多学者也 在这方面做了新的工作W9.然而，在解决实际问题中的函数F（X）并不一定为非 线性的，如弹性接触问题、自由边界问题、市场供需平衡问题、双矩阵对策问题、 误差界估计问题等Ng方面.这就是本文关心和研究的线性互补问题.1939年，线性互补问题的概念被Karush在研究连续性变量不等式约束 条件的优化问题中最先提出，并对此类问题进行了简单研究“w. 1963年， Hobson和Lemke给出了线性互补的形式，并将其应用在计算双矩阵的纳什均衡 点的问题上，利用互补点方法简洁有效的解决了这个问题.随后，氏冻印和 等在线性互补问题的理论与算法方面做了许多研究，并取得了巨大的成果

16、【si线性互补问题的研究初期，主要是侧重于对线性互补问题解的存在性的研 究，一般很少涉及线性互补问题的数值算法和具体的应用领域.1968年，Coule 和。奶左沥g在求解二次规划和双矩阵模型研充中取得了重大突破心，6罚.此后， 这类线性互补问题的探讨在各个学术领域引起了广大学者的关注，国内外学者都 致力于这一问题的研究，并取得了一系列的成果.目前，对线性互补问题研究主要集中在两个方面：（1）理论方面研究了解的 存在性、唯一性、稳定性和灵敏度分析；（2）算法方面主要探讨求解互补问题的 有效算法和对算法作相应的收敛性分析和误差界的分析，即给出误差界的最小 上界或解的近似解.在线性互补问题中涉及许多

17、特殊矩阵如P-矩阵、矩阵、 M矩阵等，它们广泛应用于数学物理、计算数学、运筹学与控制论、统计学和 经济数学等众多领域方5,也它们的结构和性质与线性互补问题的解的存在性、 唯一性以及近似解的误差分析都密切相关.由于在研究中，不同的模型构建方法 和不同的算法，得到的数值解与真实解之间存在误差，因此，关于特殊矩阵线性 互补问题的误差界的研究引起了许多学者的注意，从而使误差变小这一问题便激 发了人们对线性互补问题误差界估计的研究兴趣g心9】，这也是本学位论文所关 心和研究的主要内容.1.2研究现状本节对线性互补问题误差界的研究现状做简要叙述，为叙述方便，先给出文 章中所用到的符号及矩阵、矩阵、度矩阵相

18、关的定义.令表示所有阶实矩阵（复矩阵）所成的集台.指标集 7V= 1,2,设M =顷准R* ,对任意的沱记S SN-对于有限集S,用|S|表示集合S的势.定义.1.2. 120设M =x R”.若max xf 0, Vx 工 0,则称矩阵M为P-矩阵.定义1.2.2设力=（a.） g,称（冷=蓦）为刀的比较矩阵，其中团i=j，若/20且3/0(SJ),则称A为M-矩阵E；若,耘)，则称刀为Z-矩阵；若3为非奇异的*矩阵，则称.4为非奇异H-矩阵监.关于具有特殊结构矩阵线性互补问题解的误差界估计，国内外学者做了许多 研究.当矩阵M是R矩阵时,LCP(M, g)存在唯一解U。, 1990年,Mat

19、hias和Pang 给出如下P矩阵线性互补问题解的误差界.定理1. 2. 1设M =为P-矩阵，q仕R”，其中x*为LCP(M, q)的唯一解，对任意的xeR,有m字鹭I其中= min如弩x,。衣吐r(x) = min(x. Mr + q)表示对向量x与Mxq对应位置分量取最小.(1)式中当矩阵肱的阶数很大时，。(也的值很难求得.当矩阵M是对角元为 正数的丑-矩阵时，Mathias和所想给出了计算c(M)下界的方法回， min A.inZ)c(M)max 脂 t=:c(b), PbeR,b0 ,其中崩是”的比较矩阵.上式中Mathias和户奶g只给出了当肱是对角元为正数的质矩阵时计算以的 下界

20、的方法，但无法精确计算出c(的的值.2005年，Chen和Xiang在Mathias 和儿花研究的理论结果上利用区间法，得到了当矩阵辨是P-矩阵时线性互补 问题解的误差界.定理1.2.2设M = (%)*”为P-矩阵,则对任意的xeR”,有 HL，骚(1 -D + DM )- J (x 丸, 其中x*是LCP(M,g)的解，n-diag)(O l)正对角矩阵.定理1.2.2所给误差估计式比(1)式更容易计算，且所得的精确度更高. 随后，众多国内外学者对该问题进行了研究，并给出了当矩阵具有某些特殊 结构时，线性互补问题解的误差界的估计式.例如，2016年Garcia-Esnaola和 Pena给

21、出了当矩阵M是B-ReAmsov矩阵时，线性互补问题的含有参数的误差界.定义1.2. 3设M = (%)次”、，皿0,若其中/-I mn&W)：=|如仇(=W)+Z|%|,苦J=1 秫力J=/+l则称矩阵Af为Nekrasov矩阵.定义 1.2. 423设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 .若矿是主对角元为正数的Nekrasov矩阵，则称汩为 B Nchasov 矩阵.定理 1.2.

22、3 迎设=(% L,Q c C”“， 2 2 为 B-Nekrasov 矩阵，并存在 左1,使得皿max0,% 13=f.令叫=4,7 = 1,2,./ 1,吧产 4- + g 0J-正对角矩阵砂-diag (叫,吗,町)，叫 0,歹为定义1.2. 4所示，则房.=顷=&）皿户为严格对角Z-矩阵，且瞬件。+。树。|7；+,Vz G1V :Pjj-尸）伐们*）丫（灼其中厂:=max。，叫,IJ。，,则称矩阵M为DB-矩阵.2011年，国内学者。“给出了当矩阵肱是D3矩阵时，其线性互补问题解的误差界.定理1.2. 4网设以=为班-矩阵,且xmc.设B+ = &）Il0= / e N11妇 & （矿

23、）,扇 | - RJ侄）=min巾+）:=min侑0照一咒3）=|站|一与（矿），则下列结论成立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冒朗上严而，特别地,max妇0,1|(/ - D + DM)_l J 0.特别地，如果矩阵M是Z-矩阵时，则叫

24、0,再 0其中p = min-册|& =吧盹*，=啰苔此外还有众多国内外学者对H-矩阵类矩阵线性互补问题误差界估计式及最 优误差界做了许多研究，参见文献32-35.1. 3本文的主要工作线性互补问题解的性质主要与所定义的矩阵性质有关，本文研究矩阵M为 刀Z矩阵，QZ-8矩阵，QSQZ）矩阵线性互补问题解的误差界估计问题，并给出 相应的误差界估计式.第二章利用DZ矩阵的逆矩阵的无穷范数的上界，根据。Z矩阵和DZ-B矩 阵是汗矩阵的子类及H-矩阵的性质，进而得出具有正对角元的Z）Z矩阵和DZ-B 矩阵是P-矩阵的子类，得到当矩阵M是OZ矩阵DZ-3矩阵时，线性互补问题解的误差估计式:（1）当M是O

25、Z矩阵时，根据DZ的逆的无穷范数的性质，得到OZ矩阵线 性互补问题解的误差界估计式.麟”-。+吐如密（飕V （以）,配炊 ），并用数值实例表明该误差界对线性互补问题近似解的估计是有效的.（2）当M是DZ-B矩阵时，首先将DZ-B矩阵M分解成M =矿+C ,其中B+ 是DZ矩阵同时也是Z矩阵且对角元为正数，C是秩为1的非负矩阵，然后构造单调递增函数，得到当矩阵沮是矩阵时线性互补问题解的误差界估计式,max姐0.1+0, 润，则对任意的xeO,l,有1一才 +形 min/j + y 引理2.1.23?:设M =是OZ矩阵，则存在对角矩阵。使得郴是SDD矩阵.引理2.1.3助设M = S/CfDZ矩

26、阵.则MTL - max侦%（M）,尚洽 %（），其中闻, +网，Ji%()U福-(M)+队| 肱|-|祖J曲)，%()=1J-册)+hl!+血)l-喝曲)2. 1 Dashnic-Zusmanovich矩阵线性互补问题解的误差界估计本节将研究F-矩阵的一个重要子类-原矩阵线性互补问题解的误差界估计 问题.设矩阵” = (%)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设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；(扬)+机:/卜0/)+4帕|= d，3-q W)+|?J) |矿(疗)|阿，卜伽If (

28、脱)+切阮I2 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产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” + %机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带）一机E （脂）+ 1砌+以由）2（阮 I - 0 （府）+厄,I 阮 HM； F）=_dj.dmjL d 凸（归）+ 均恤+ （归）（1+d如一可（A/）+dJ）（l-+加,）一（M 网楫 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.证毕.当矩阵沮具有某种特殊结构时，即当对任意的心，舟=1时，有定理2. 1.1简化为下列结果.推论

31、2.1.1设=wC”为DZ矩阵，且对任意的iwN,阳.F.令其中正对角矩阵D=diag0）, 01,则，斓（2 + | max00其中1+1%若布万一 rj W ) 1,（-匕（庭）秫”-阮,则mn+mu Kj(勺7 -册) -勺,k W)功（M）=0 (“)=(勺广尸；(沮)成+|勺J（成力一坦（M）仆）、担力-尸伽）mJ 曲）.注 2. 1. 1 特别地，若 m /7 - (M ) 1 和 mtl 1 和 1 和 1 ,则门（M = SW）.1（仇厂】（肱） - ，（沮）,定理2. 1. 1给出了 QZ矩阵线性互补问题解的误差界估计式，下面用数值算例讨论结果的有效性.例2.1.1考虑。Z矩

32、阵0.4、0.6 .1 ）不难看出矩阵M不是良矩阵，故误差界*爵一O +0.750.500.510.5不能由文献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、为正数，正对角矩阵D=diag（d）, 01, 有M I-D + DM =（I-D + DBDC = B rC .其中方+ =1 0 + 0矿，c = z）c.由文献25的定理2得，其中1（加” 3*）板一稣 kW）1_ | ,，您）值+）二 min如,1 0厂r；伍+）min如,1max (n- )max I max 矿). max %兀a如7 证毕.推论2. 2.1设” = （%）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必矩阵与上述这些矩阵类的关系，下面,给出上述矩阵的定义.设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矩阵的关 系，可以得到相应的3矩阵，矩阵，08-矩阵，SB-矩阵，B-Nekrasov矩阵 的关系，见图2.1.文献25中Garcia-Esnaola和Pefia给出了当矩阵M是B-矩阵时,线性互补 问题的误差界估计式.定理2.2.2如 设M = (mjECw,M = B*+C为B-矩阵，其中8和C如定 义2. 2.1所示，设& :=做)和P：= min但则max|l(Z-Z) + Z)A/)_lll/血冲化 min伊,1因为务矩阵是OZ-B矩阵，若当矩阵M是身矩阵时

36、，定理2.2.1同样也能 给出的上界推论2. 2.2设M = S)eL”,M = B、C为B-矩阵，其中矩阵和矩阵C 如定义2.2.1所示.设有:=如-匕(矿)和歹=嗯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，其中/应）= N，.若对任意的iwN, &且对任意的i，MN , E,有矿）（矿）如C,0 v如.一心（矿）1和0i,-

37、r/（B+）l.由注2. 2. 1得“（B，）=如I姐1 （如-矿）+6小书施+）另一方面，当满足上述情形下且min0,l=时，贝！J_ J_ I _1_1_mill伊,1 P 唧舟min 如-仆）吧乎如一二同 因为也 I 1,、 0广川+）+如）如-|弓顷） 珈妇一演）， 若I础F（矿冏醐（矿），将上述不等式两边同时乘以|如|0,则站-仙服I屯他W（矿膈I，即I九-匕（矿版|+|础如册（矿）%稣|财项矿服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表明，当M是3-矩阵时，定理2. 2. 1给出了 3-矩阵线性互补问 题误差界中的孺WIO D + D材尸L的新上界因此，一般来说，当矩阵以是 8-矩阵时，可以取这两上界中最小者估计3-矩阵线性互补问题解的误差界，即 斓湖）*1）响扁鬲,max畔嘴例2. 2. 1考虑DZ-B矩阵=矿+。,其中不难看出矩阵M不是&矩阵，故误差界*顿-D + DM）%不能由文献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不能由文献25, 28, 29, 29, 23中的误差估计给出.另一方面，显然是QZ矩阵，则M是DZ-B矩阵，由定理2.2.1得max |(7 -D +

41、 DM ) | 且“22.若-闵匕(刀)，WeN,则称刀为严格对角占优矩阵，记作AeSDD.若是不可约的，aitrA), i&N,且至少有一个严格不等式成立，则称为不可约对角占优矩阵，记作.4住ZDD.若国|勾|*3)。( P Lj-N, f,则称4为双严格对角占优矩阵，记作AeDSDD.记+3) = 苦 /；(),_() =件 N：|%| aC4).显然一(4)U一(Z)= N.众所周知，SDD矩阵是QSDD矩阵，也是非奇异矩阵，主对角元为正的 实H-矩阵是户-矩阵.引理3. 1.1他 设,4 = 0准仗以”为叫。矩阵.则存在正对角矩阵 Z)=diag(d2，0j，d, 0,使得4?是SOD

42、矩阵，即A为H-矩阵.引理3. 1.2：龙设Z = （%）eC为SDD矩阵.则L气机园引理3. 1.3U0设=（印）EC为H-矩阵且主对角元全为正，即存在正对 角矩阵d = 6Z/ 0 对任意的，使得,4。是SDD矩阵，则max拓0邛由（8）式易知，正对角矩阵5的对角元,心）为参数.然而，在实际计算 中并不实用.到目前为止，笔者没有见到如何确定&的取值范围的相关结果. 的取值问题及（8）式的最优值问题将是本章的主要研究内容，即当矩阵刀是 DSDD矩阵时，d,在定理3. 2. 1中给定条件下，讨论了（8）式的最优值问题.3.1双严格对角占优矩阵线性互补问题误差界的最优值若一3）=。，即一3）=N

43、,矩阵A SDD占优矩阵，则矩阵刀的线性互补 问题误差界可以直接利用引理3. 1.2获得.本节主要对 _（刀）。情况下的 DSDD矩阵的线性互补问题误差界最优值进行研究.定理3. 1. 1设A = （a. ） e Cn0,且早缶 rvo I人牛肢,则存在正对角矩阵J = g（wPw2,.,w）,其中, j_（），XVS G1, 心一，使得附是SOD矩阵，且 max max在0邛其中饵=%吗一幅时.证明 易证AW为SDD矩阵.进一步，对所有的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若农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）在区间上为单调递减函数，于是inf 、|。扁,皿如）, 一%,-E)min-N_ 。(/) min也若疗1,且E = R,任一（力，即mjn物=度,则 0, -，；（，） 一 （。1）幅因为/何)0, /()在区间上为单调递增函数，贝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数值例子例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),故应用式 得max2.6188(io)而由定理3.1.1得麟IS2,考虑、DSDD占优矩

47、阵2k -k-2R + 3 k /由引理3. 1.3得，正对角矩阵Ddiag2kT M-3 F,故应用(8)式得max 4.000(12)而由推论3.1.1得(13)I 2.000进一步，应用 MATLAB 代码 for i=l: 1000;D=diag（rand（4,l）;end” 随机取 1000个矩阵并计算+ L的值，参见图3. 2.图3.2例3.1.2随机取1000个矩阵Z）下的最优值图3.2中“表示，取1-1000时所对应（7-D + Z）M）_1j的值，显然（13）式比（12）式更精确.综上，本章在_（）/情况下，对正对角矩阵咋花叫,可2,羽），且叫取满足定理3. 1. 1中的条件

48、下的时的DSQD矩阵线性补问题解的误差界进行研究，得到了/（时,的最优值，这个值是存在的并且是可计算的.第四章总结第四章总结本文主要讨论了 QZ矩阵、DZ-3矩阵和DSDD矩阵线性互补问题的误差界 估计问题，从特殊矩阵的结构和性质入手，构造具有参数的正对角矩阵，应用不 等式放缩和函数单调性，得到线性互补问题误差界新的估计式.本文所得结果总结如下:（1）给出了当矩阵是OZ矩阵时，线性互补问题解的误差界估计式|（。+5孔即虬略（肱）,蜉华（叫max | II其中花厂r；（M）叫,（团1 理）77（X）= min栅急（电-/Q/Dmin叫,11（2）给出了当矩阵M是DZ-B矩阵时，线性互补问题解的误

49、差界估计式 |（/+5此（妇）顺 %（质）嘴部2顷），maxdwg,】其中S” ;. _ min如-匕(7T)1厂 min如,1,如-如 M矿）_ _+ _虬何+）二 min如,1 0广0+）而话如,1I她（硕九 给出了当矩阵电是DSQQ矩阵时，线性互补问题解的误差界的最优值maxCCcmin 丹其中:=与 叫- 圳L.j0再对（3）式进行讨论得到最优解凡：=% -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 ,参考文献彭凌.几类特殊矩阵线性互补问题的误差界D.吉首大学，2015.M. Jansen. Equilibrium points ofbimatrix games J. Journal of the Society fbr Industrial &Applied Mathematices, 1964, 12(4)： 778-780.何素艳.互补问题算法研究及其在力学中的应用D.大连理工大学，2003.苗新河.Hilbert空间中Lorentz锥线性互补问题的理论研究D.天津大学，2

51、010.吴军荣.非线性互补问题的水平值估计算法D.上海大学，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