（计算数学专业论文）广义线性互补问题的区间解法.pdf

摘要 摘要 本文对线性互补问题进行了研究，主要内容为： 在对国内外研究动态的综述中，首先介绍了线性系统的基本迭代法，如j a c o b i ， g a u s s s e i d e l ，超松弛迭代法，快速超松弛迭代法等；然后，介绍了线性互补问题 的两种等价形式，这两种等价形式可以应用解线性方程组的方法求解。接着，介 绍了线性互补问题的a o r ，m a o r ，g a o r ，和两阶段迭代法；最后，当系统矩 阵m 为p 矩阵时，列出了文献中给出的，线性互补问题的误差界范围。 根据国内外研究的成果，本文主要研究了一类特殊的广义线性互补问题，对 a l e f e l dg ，w a n gz y 和s h e nz h 得到的线性互补问题的区间迭代法进行了推广； 建立了这类线性互补问题解的区间界限算法，其主要的计算工作量简化为求解线 性系统。即当广义线性互补问题的系统矩阵彳，b 都为矩阵且严格对角占优时， 应用区间迭代的方法，给出一种有效的算法，能够利用计算机的高速运算和并行 运算，得到了一个嵌套序列。在有唯一解的条件下，迭代序列的区间半径逐渐缩 小，逼近其唯一解。当达到误差条件时，取区间中点为近似解，或者得到其无解的 结论。 关键词：线性互补问题，a o r 迭代法，两阶段迭代法，广义线性互补问题，区间 解法 a b s t r a c t a bs t r a c t t h i sp a p e rr e s e a r c hl i n e a rc o m p l e m e n t a r i t yp r o b l e m t h em a i nc o n t e n t si nt h i s p a p e ra l e a sf o l l o w s ： w i t ht h es u m m a r i z i n go ft h er e s e a r c ho nd o m e s t i ca n di n t e r n a t i o n a ld e v e l o p m e n t s ， t h eb a s i ci t e r a t i v em e t h o d sf o rl i n e a rs y s t e ma r ei n t r o d u c e df i r s t l y , e g j a c o b i ， g a u s s s e i d e l ，s o r ，a n da o r t h e nt h et r a n s l a t i o no fl c pt oi t se q u a lf o r mw h i c h m a k e st h em e t h o d sf o rl i n e a rs y s t e mc a nb eu s e di si n t r o d u c e d i nt h ef o l l o w i n g , i t e r a t i v em e t h o d sf o rl c p , e g a o r ，m a o r ，g a o r ，a n dt w o s t a g ei t e r a t i v em e t h o d s a r ep r e s e n t e d t h ee r r o rb o u n d sf o rl c pw h e nt h es y s t e mm a t r i xi sapm a t r i xa r e p r e s e n t e da tl a s t a c c o r d i n gt ot h er e s u l t so fr e s e a r c ha th o m ea n da b r o a d ，t h i sp a p e ri n v e s t i g a t e sa s p e c i a lk i n do fg e n e r a l i z e d o r d e rl c et h er e s u l t so fa l e f e l dg ，w a n gz ya n ds h e n z h a r ei m p r o v e d t h i sp a p e re s t a b l i s h e sa ne n c l o s u r eo ft h es o l u t i o no fg l c p , f o r w h i c ht h em a i nc o m p u t a t i o n a lc o s ti st os o l v eas y s t e mo fl i n e a rs y s t e m w h i l et h et w o s y s t e mm a t r i c e sa r el - m a t r i c e sa n ds t r i c t l yd i a g o n a l l yd o m i n a n tm a t r i c e s ，ae f f e c t i v e a l g o r i t h mi so b t a i n e da p p l y i n gt h ee n c l o s i n gi t e r a t i v em e t h o d s ，w h i c hi sa b l et ot a k e a d v a n t a g eo ft h eh i g h - s p e e dc o m p u t e rc o m p u t i n ga n dp a r a l l e lc o m p u t i n g t h e nan e s t e d s e q u e n c ei so b t a i n e d t h ei n t e r v a lr a d i u so ft h ei t e r a t i v es e q u e n c e si sn a r r o w i n g ， t e n d i n gt ot h eu n i q u es o l u t i o nw h i l et h ep r o b l e mo n l yh a so n e t h em i d p o i n to ft h e i n t e r v a li ss u p p o s e dt ob et h es o l u t i o nw h i l ee r r o rc o n d i t i o n sa r em e t e d ，o rt h e c o n c l u s i o no f t h e r ei sn os o l u t i o ni so b t a i n e d k e y w o r d s ：l i n e a rc o m p l e m e n t a r i t yp r o b l e m ( l c p ) ，t h ea o rm e t h o d ，t h et w o - s t a g e i t e r a t i v em e t h o d ，g e n e r a l i z e d - o r d e rl c p , e n c l o s i n gs o l u t i o n i i 符号说明 a 户( 彳) 。 r 删” z r 彳一1 符号说明 矩阵 矩阵a 的谱半径 矩阵a 的比较矩阵 矩阵a 的无穷范数 1 7 阶实方阵 向量x 的转置 矩阵a 的逆矩阵 i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特另t l d h 以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：王盘日期：姗g 年j 月) 盖日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：量夔 导师签名：差争丝z 兰 日期：睁乡月l l 日 第一章绪论 第一章绪论 线性互补问题( l m e a rc o m p l e m e n t a r i t yp r o b l e m ) 已经发展成为应用数学中一 个非常重要的研究领域。通常把线性互补问题归为数学规划的范畴。它与线性和 非线性规划、对策理论、不动点理论以及最优化方面都有紧密的联系。同时，在 力学、经济、工程等方面也有广泛的应用。正是由于它的广泛性，使得它得益于 运筹学、数学、计算机科学、经济学和许多其他的学科。 经过多年的发展，线性互补问题有了很多方面的扩展。虽然其最早的研究可 以追溯到1 9 4 0 年，但是集中的研究是从1 9 世纪6 0 年代开始的。线性互补问题最 早出现在线性和二次规划问题的k t t 条件中。1 9 6 3 年，h o w s o n 把双矩阵决策中 的n a s h 均衡点问题转化为一个线性互补问题，这使得互补问题引起人们的注意。 “线性互补问题”最早是于1 9 6 5 年由c o t - t i e 在他的博士论文中提出的。互补问题 很快引起当时运筹学界和应用数学界的广泛关注和浓厚兴趣，许多人参与了这类 问题的研究。由于线性互补问题最初产生于线性规划和二次规划的统一公式中， 所以二次规划现在是以后也将成为l c p 应用的一个及其重要的方面。l e m k e 和 h o w s o n 公开发表的他们著名的解决双矩阵对策问题的算法的文章( 1 9 6 4 年) 给 l c p 带来了新纪元。线性及二次规划和双矩阵对策问题在l c p 的发展中扮演了很 重要的角色。后来，随着数学规划日趋成熟，解决复杂平衡问题的进一步加强， l c p 的重要性就越来越明显了，并且它的范围发生了意义重大的扩展。当前，许 多新的研究课题都是这些扩展的结果。在解决二次规划问题时，很多高效率的算 法都是基于l c p 方程的。至2 0 世纪8 0 年代中后期，经过2 0 余年的努力，在理论 和迭代法方面都已经取得了比较丰富的成果。在1 9 9 2 年，由r i c h a r dw c o t t l e 、 j o n g - s h ip a n g 和鼬c h a r de s t o n e 共同出版了一本关于l c p 的书，文献 1 ，书中提 到了此类问题的方方面面。进入2 0 世纪9 0 年代，人们不仅丰富了互补问题的理 论研究，还提出了多种有效的迭代法，如光滑方程组法，内点法等。 电子科技大学硕士学位论文 1 1 线性互补问题的基本形式 线性互补问题是指包涵了丰富的数学理论、一系列算法以及在应用科学与技 术方面的广泛应用的一个不等式系统。具体形式为，给定向量q r “和矩阵 m r “”，在有限维实向量空间中寻找向量z ，使得 z o ，q + m z 0 ，z r ( q + m z ) = 0 成立或者说明没有这样的向量。简记为l c p ( m ，q ) 。 1 2 线性互补问题的扩展形式 正如其他任何一门科学问题，l c p 经过几十年的发展和与实际问题的结合， 产生了多方面的扩展： 1 2 1 水平线性互补问题( h l c p ( m ，n ，q ) ) 当给定向量q r 4 和矩阵m ，n r “”，求解向量x ，y r 8 ，使得 n y m x = g ，x o ，y o ，x r y = o 简记为h l c p ( m ，n ，q ) 。如果是非奇异的，水平线性互补问题可转化为线性互补 问题l c p ( n m ，n q q ) 。 1 2 2 垂直线性互补问题( v l c p ( m ，q ) ) 设m 为m x n 的矩阵且m n ，q 为咒维向量，其中 m = m m 2 ： m ， ，g 。 g i 9 2 ： 吼 m ，r ”脚，q ie r r n i , 鸭= 研。那么垂直线性互补问题就是求解向量x r 4 满足 i = 1 2 第一章绪论 r l l i q + m z o ，z o ，z i 兀( g f + m i z ) j = o ，i = 1 ，z ， j = l 简记为u z c * ( m ，g ) 。如果对每一个f 有= 1 ，那么v l c p 退化为线性互补问题。 1 2 3 广义线i ! t g l 、问题( 皿c p ( 必。，m ：，d ) 设矩阵m 。，m ：r “，pcr ”是一多面体，广义线性互补问题就是，求解向 量x e r ”，y r “满足 少一 缸p , x o ，y 0 ，j ，= 0 ， 简记为e l c p ( m l ，m 2 ，尸) 。当m 司，p = 例时，e l c f ( m 。，m 2 ，尸) 化为线性互补问 题。 1 2 4 混幂口线性互枣卜问题( m c p ) 设么，君分别为n 阶，m 阶的方阵，且给定c 彤“，d r ”，a r n , b r ”， 那么混和线性互补问题就是，求解向量u f ，1 ，r ”，使得其满足 简记为m c p 。 口+ a u + c 、，= o ，b + d u + b v = o ，v o ，1 ，r ( 6 + d “+ 曰v ) = 0 ， 1 2 5 隐线性互补问题 设a r ，口f ，h ：r ”jr ”，那么隐线性互补问题即求解向量z r ”使得 a + a z 芝o ，z o ，( 口+ 止) r ( z j i l ( z ) ) = 0 显然，当h 鄙时，隐线性互补问题转化为l c p 。 电子科技大学硕士学位论文 1 2 6 非线性互补问题 非线性互补问题就是，求解向量z r ”使得 z 0 ，f ( z ) 0 ，z r f ( z ) = 0 简记为n c p 。显然，线性互补问题是非线性互补问题的一种特殊形式。 1 3 线性互补问题的应用 如二次规划 m i n i l l l i z e 厂( 功= c r z + i 1 工r s u b j e c t t oa x b( 1 1 ) x 0 当q r “”是对称的，c r ”，a r 雕”且6 r ”。特别地，若q = 0 ，n - - - 次规 划将化为线性规划。如果x 是规划( 1 1 ) 的局部最优解，i g z , 存在一个向量y 满足以 下条件 “：- 簪ba 么x 冀0 嚣麓。0 ： m 2 ， 1 ，= + 0 ，1 ，o y 1v = 、7 则有，条件( 1 2 ) 定义了l c p ( m ，q ) ，其中 膨= ”a 0 ，g 槲b f 。 i 另外一种特殊的二次规划形式是x 有非负的限制，那么( 1 1 ) 就可以简化为 1 n i 枷z e 厂( 工) = c r z + 昙石r s u b j e c t t o 石0 ( 1 - 3 ) 当q 是半正定矩阵，那么( 1 - 3 ) 就完全等价于l c p ( q ，c ) 。也就是对任意q ，l c p ( q ，c ) 等价于( 1 - 3 ) 式这种稳定点问题。形如( 3 ) 这种类型的i 口- j 题大量地出现在工程和物理 4 第一章绪论 科学中。l c p 在解决此类问题中起到了很大的作用。 此外，双矩阵对策、市场平衡、最优停止点问题、平面中的凸包闯题都与l c p 有着密切的关系。因此，可以通过把原问题转化为较易求解的l c p 来寻求原问题 的解。相应的，可以看出，l c p 的发展对很大一部分与l c p 有密切关联的问题有 相当大的促进作用。 1 4 线性互补问题解的存在性 在线性互补问题中第一个遇到的就是有没有解的问题，自然引起了很多学者 的关注。解的存在性问题最早应该是s a m e l s o n ，t h r a l l 和w e s l e r 在1 9 5 8 年的文献 中提到的。系统矩阵膨为尸矩阵，是对于任意的向量q ，l c p ( m ，q ) 都有唯一解的 充要条件。这个结果可以说是l c p 经典的结果，随后很多对l c p 的研究都是基于 这个结果的。由此也可以看出，l c p 涉及到很多矩阵的相关知识。在实际研究过 程中，对不同条件下的系统矩阵必，问题的结果大多会很不相同，或者在研究其 它方面的问题时对m 有一些限制条件。特别地，线性互补问题与p 矩阵，即所有 主子式为正的矩阵，有着不可分割的联系。 1 5 本文的主要工作 本文从几个方面研究了有关线性互补问题，首先是迭代法，如a o r ，m a o r ， g a o r ，两阶段迭代法等，接着介绍了一些迭代法的误差界的范围。主要研究了广 义线性互补问题，得到一种可利用计算机高速运算能力的区间迭代法，推广了基 本线性互补问题的区间迭代法，得到很好的收敛效果。 电子科技大学硕士学位论文 第二章线性互补问题的迭代解法 最早的迭代法解线性互补问题出现在1 9 世纪五十年代，一直发展至今。迭代 法在解决大型线性系统方面有着很大的优势。对线性互补问题迭代解法的早期研 究主要是针对对称问题和在非负约束凸二次规划中的应用。h i l d r e t h 在1 9 5 4 年和 1 9 5 7 年用映射的松弛g a u s s s e i d e l 方法解决严格凸二次规划问题仅仅使用了不等 式约束，他的方法事实上是解决了对偶问题，这恰恰是与线性互补问题等价的。 但是当时却没有认识到。经过几十年的发展，众多学者把线性系统的迭代方法应 用在解决线性互补问题上，取得了出色的成果。在1 9 7 7 年m a n g a s a r i a n 发表了一 个解决l c p 的一般方法，并且在一定约束条件下建立了其收敛性。这一文章可以 认为是在求解l c p 的迭代法中的对称性研究的第一篇文章。从此以后，激发了很 多学者来关注这个问题。因为线性互补问题可以等价的转化成线性方程组等线性 系统的形式，所以，在这一问题的研究过程中，很多都是从解决线性系统的思路 中引用过来并加以扩展。 2 1 基本迭代法 先给出一些本文中常用到的定义： 定义2 1 1 1a = ( a ) 是 1 )z 矩阵，当a 日0 ，1 i , j n , i 歹； 2 ) 三矩阵，当么是z 矩阵并且 0 ，l i 嚣； 3 ) 严格对角占优矩阵，当i l ( 么) - i l ，l i ，j f ，l ； f j 4 ) m 矩阵，当a q 0 且0 ； 5 ) 日矩阵，当存在一个正向量d 使得l 口p p j kd ，1 i ，歹，l ； j f 6 ) p 矩阵，当其所有主子式为正； 6 第二章线性互补问题的迭代解法 7 ) q 矩阵，如果对于任意g r ”，线性互补问题l c p ( m ，q ) 有一解； 8 ) 不可约矩阵，如果a 对应的直接图是强连通的。 另有定义【2 】： ，删懒晦西峭瓦= i 圹f 勇轧脚； 2 ) a i = j ) ； 3 ) a 的谱半径记为p ( 么) 。 下面，从线性方程组出= 6 来引入迭代法，其中给定a 尺“，b r “。当a 为 非奇异矩阵时，解x = a 。1 b 是唯一的。设迭代法的一般形式： x ( ”+ 1 ) = m x ( ”) + g ，朋= 0 , 1 ，2 ， 其中m 欠雕“称为迭代矩阵，工( 0 1 称为迭代初值。 定义2 2 t 2 1 如果存在x r ”，使得任意初值x ( o r “，由上述迭代法产生的 迭代序列 x ”) 都收敛到x r “，即 l i r ax ( “) = x ， 卅 那么，就称此迭代法是收敛的，否则称之为发散的。 对于收敛的迭代法，有 记 则可以得到 工= m x + c ， s ( ”) = x ( 埘) 一x ( ”一n ， 6 ( m ) = m 掰石( m ， 由此可知，迭代法收敛的充分必要条件是 1 i m m ”= 0 m 定理2 1 2 1 迭代法收敛的充分必要条件是p ( m ) 0 有 z 0j m z + q 0 e ( z a e ( m z + g ) ) + 一z = 0 ( 2 - 3 ) z r ( 胞+ g ) = 0 j 2 3 线性互补问题的a o r 迭代算法 性： 分裂m 矩阵m = a b ，且d e t ( i + 彳) 0 ，由( 2 2 ) 式，得到迭代算法： z m + l = g ( z ”) = ( ，+ 彳) 一2 ( i ( ，一m ) z 2 - q l + b z ”- q ) ( 2 - 4 ) 定理2 2 4 1 如果q 1 ，则线性互补问题的解存在且唯一，其中， m = d 一( e + f ) ，p s = p ( 1 l + d i - 1i e + f 1 ) ， 町= 2 岛+ m 。g - i 1 1 l + - a 玎 在定理2 2 的条件下确保线性互补问题有唯一解，下面分析算法( 2 - 4 ) f f 匀& 敛 定理2 3 4 1 如果膨= a - b ，d i a g ( a ) = d 且乃 1 ，则从任何初始z o er “出 发，有迭代算法( 2 4 ) 产生的迭代序列扛”) 有意义，且都收敛到线性互补问题的唯 一解z r 4 。 从( 2 3 ) 得到与线性互补问题等价的固定点系统等式 电子科技大学硕士学位论文 z = 0 一a e ( m z + g ) ) + ( 2 - 5 ) 从文献 5 】可以知道，特殊的选取口和e 使得a ：e = d ，n z , ( 2 5 ) 就退化成 z = ( z d 叫( a 勿+ g ) ) + 在系统矩阵m 的分裂为 m = d + l + u ，( 2 - 6 ) 时，有如下a o r 迭代法： z p “= ( z p d 一1 r z e ，+ 1 + ( 刎一y l ) z ，+ 彩g 】) + 当7 = 缈时，a o r 退化为s o r 。 2 4 线性互补问题的m a o r 迭代法 在a o r 迭代法的基础上，有学者给出了其的改进形式m a o r 。当线性互补问 题的系统矩阵mn - n 循环阵时，即 。= ( 0 最) ，三= ( 呈吕 ，u = ( 三苫) m a o r 迭代法【6 1 ： 第一步：选择初始近似解z o r 4 ，令p = 0 ； 第二步：计算z ，+ 1 = ( z p d 叫 r l z ，+ 1 + ( r i m y l ) z p + q g ) + ，p = 0 ，1 ，2 ，； 第三步：如果z 川= z p ，停止。否则，令p 车p + 1 ，转到第二步。 其中，q = d i a g ( m j ，哆厶) ，c o l o ) 2 o ，q ，哆，y r ，厶，厶分别为与d l ，d 2 同阶数 的单位矩阵。 引理2 2 【5 】当线性互补问题l c p ( m ，c o 的系统矩阵m r “4 ，是对角元为正的 日矩阵时，此l c p 问题有唯一解z r “。 在文献 7 1 0 0 ，定理3 3 给出了一定条件下，线性系统的m a o r 迭代法的收敛 结果。在m a o r 应用在解决线性互补问题上后，得到了下面的收敛结果： 定理2 4 吲设m 是对角元为正的日矩阵，且具有( 2 6 ) 的分裂形式，满足 1 2 第二章线性互补问题的迭代解法 m = d - i l i - i u ， 那么对任意初始近似解z o r ”，由上述m a o r 迭代法产生的迭代序歹0p p ) 收敛于 线性互补问题的唯一解z 。r “，并且，当 。 铂 币2 而，。 吐 而2 阿，。7 毡， 时 p ( 酗r m 。a 。x ( 1 一哆i + 哆椰1 ) ) 1 ， 其中j = d 一1 ( 三+ u ) ，q = ，一y d 1 厶r = i - d ( r i m r l ) 。 以上定理，说明了m a o r 迭代法收敛的充分条件。当m 为严格对角占优矩阵 或日矩阵时，l j i l j a n ac v e t k o v i d 和s a n j ar a p a j i e 推广了上述结果。 令，他分别为对角矩阵d l ，d 2 的维数，且 l = 1 ，2 ， 1 ) ，2 = 以+ 1 ，_ + 2 ，i 1 ) 还用到以下一些符号，设x r ”，x 0 ， f ( x ) = ，g + ( x ) = l + l l - x l + 翮， i + x 厂一( z ) ：半，厂+ ( x ) = 学 定理2 5 【8 1设m r 是对角元为正的严格对角占优矩阵，令 z = m 刚a x ：l i = m z r , ( l ) , u = m 拒a i x 2 璎肾i ( u ) ，则当 岫 t l , 0 咤一锱哪篇， 时，m a o r 迭代法收敛。 1 3 电子科技大学硕士学位论文 2 5 线性互补问题的g a o r 迭代法 在对a o r ，s o r ，进行扩展后得到g a o r ，g s o r 迭代法。由引理2 1 知， 线性互补问题的等价形式 z = ( z d _ ( 勉+ g ) ) + 在系统矩阵m 分裂为m = d + l + u 时，得到g a o r 迭代法 z p = ( z p d 一1 a a l z p “+ ( 叫- a q l ) z p + q g 】) + 当口= 1 时，g a o r 退化成g s o r ： z p + 1 = ( z p d 一1 o z z 尸+ 1 + ( 叫一( 2 l ) z p + q 可d + 当口= 么，q = 国，时，g a o r 退化成a o r ： z p “= ( z p d 一1 y l ，“+ ( t o m y l ) z p + 缈g ) + 当口= ，q = ( q ，哆，) 时，g a o r 退化成二阶循环阵的m a o r ： z p 州= ( z p d 一1 y l z p + 1 + ( 伽一儿) z p + q g d + g a o r 迭代法【9 1 ： 第一步：选择初试向量z o r “，令p = o ； 第二步：计算z p “= ( z p d _ 1 棚己z p l + ( d m - a x g l ) z ，+ f 2 q ) + ； 第三步：如果z 川= z ，停止。否则，令p - p + l ，转到第二步。 其中q = 班昭( q ，嚷，嚷) ，哆墨，且口是实数。当a = 1 ，同样的方法得到 g s o r 迭代法。 定理2 6 【9 】令矩阵m = ( m 酊) r “”是对角元为正的日矩阵，那么对任意向量 z o r 一，由上述g a o r 迭代法产生的迭代序列仁p ) 收敛于线性互补问题的唯一解 z + 彤，并且，当 而 4去h 第二章线性互补问题的迭代解法 时 p ( v 。1 f ) 罂坚 1 1 一哆l + q p ( i ，j ) ) 0 。很明显，对任意向量z ，有不等式 蹬z i ( 胞) ，c ) 三 如果m 是非奇异矩阵，那么用m 。1 代替上式中的m ，且y = m q z ，于是得到 不等式 m 。一a x y ，( 坳) ，c 似。1 ) j | 吵b 由讨论过的线性互补问题的等价形式知，x + 是l c p ( m ，q ) 的解当且仅当z 是 r ( x ) - m i n ( x ，m x + q ) = 0 的解，其中较小的向量是由两向量对应元素中较小的那个 组成的向量。函数，称为l c p ( m ，q ) 的自然残差，在误差分析中经常用到。 定理2 1 0 冽令m 为，z 阶尸矩阵，z 是线性互补问题l c p ( m ，q ) 的唯一解， 设( - q ) + 0 ，那么 c ) 帜z ) k 1 + 俐( 一g ) + 忆 碍 1 + 1 m i i 。愀圳。 c ( m q ) c ( m ) f ( 一g ) + k 1 7 电子科技大学硕士学位论文 然而，式( 2 8 ) 中的c ( m ) 是不容易找到的。当m 是对角元为正的圩矩阵时， 文献 2 4 又给出了c ( m ) 的一个可以计算的下界 ( m ! n b i ) ( m ! n ( m 。1 6 ) i ) c ) l ( m a x ( 南m 两b 广2 ：孑( 6 ) ， 、 。 叫) ，) 2 一。 其中b 为任意向量，砑为m 矩阵的比较矩阵。 不难找出，每个x ，y r ”使得 m i n ( x j ，y i ) 一m i n ( x ；，y ；) = ( 1 - d f ) ( z f 一工；) + d f ( y j y ；) ，f n ， 其中 妒 y ，墨，y # y f x iy ；x ； 可以看出d ，【o ，1 ，因此，令y = 尬+ g ，y 4 = m x + g ，且 r ( x ) = ( j d + 删) ( z x ) 定理2 1 1 t 2 5 1 如果m 是p 矩阵，那么对任意x r ”，有不等式 一1 iiii+iimi ，( z ) 忆 。v 。圳。 丽1max1 i i 忆 i ，i l n 虿 2 丽矿丽1 ) i i m a xi ) m mdqo l l 一上一，+0 一 一 ，l r ” 0 x 一工l l 瓣犯一d + d m ) 一厂( x ) l l 。 d 仨【0 ，l r o i “ 田 第二章线性互补问题的迭代解法 = 面1 + t l m i o 咿k 一专学陟k 1 + i i m 万 帆 其中d 是由d 。，d ：，d 。 o ，1 】为对角元组成的对角矩阵。 上述不等式中的最左端和最右端的式子就是文献 2 4 】给出的误差上下界，也就 是说，这里得出了范围更小的误差界。 定理2 1 2 2 5 1 如果m 是对角元为正的日矩阵，那么对任意x ，b 尺n ，b 0 ，有 不等式 x 忆 _ 0 ，那么对于任意一组向量仍q r ”，问题( 3 - 1 ) 最多有一解。 从引理3 1 可以得出，当两个三矩阵彳和男是严格对角占优矩阵时，我们可 以令彩= p ( 乞= 1 ) ，那么引理3 1 的条件满足，参考文献 2 7 】，则问题( 3 1 ) 最多有一 解。 3 3 线性互补问题的区间解 用【x - 【兰，叫来表示一维实闭区间，这里实数兰x 。用【x 】= ( 【x ) ，表示以维实 闭区间，这里其每一个元素( x 】) ；都是一个一维实闭区间。我们也可以这样写一个 n 维区间 x 】： 圣z ，此时x ，工r ”f t _ x x 。我们定义区间中点为所( x 】) = + x ) 2 ， 区间半径为，( 【胡) = ( ；一s ) 2 。 第三章广义线性互补问题的区间解法 首先，从非线性互补问题 x o ，f ( x ) o ，x r 厂( 曲= 0( 3 - 2 ) 引出区间解： 引理3 2 2 8 1 令 x 】为托维区间，用f ( x 】) 表示厂在 x 上的区间扩张，如果 r ( x ， x ，d ) ：= m a x ( 0 ，z d f ( x ) + ( j d f ( x ) ) ( x 一x ) ) x 】， 当z x 是固定的且d 是正对角矩阵，那么问题( 3 2 ) 存在一解x 在区间r ( x ，i x ，d ) 内。另外，如果问题( 3 2 ) 的解x 包含在【叫中，那么有x + r ( x ， x 】，d ) 。 3 4 广义线性互补问题的区间解法 令g ( x ) = 出+ p ，厂( 功= 舭+ g ，那么( 3 1 ) 可以写成 g ( x ) o ，f ( x ) 0 ，g r ( z ) 厂( z ) = 0 ( 3 - 3 ) 当g ，f ：r ”- - + r “都是连续可微的并且在 g ( x ) 上具有区间扩张f f i x ) 。 令p ( x ) = m a x 0 ，g ( x ) 一d f ( x ) ) ，其中d 是具有正对角元的对角矩阵，称之为 正对角矩阵。 由引理3 1 知，d g o e l e v e n 在文献 2 6 1 得到广义线性互补问题有唯一解的充 分条件，也就是问题( 3 3 ) 。当a = j ( 单位矩阵) 且p = 0 时，( 3 3 ) 就成为经典的线 性互补问题。在这样的情况下，如果曰是主对角元为正的日矩阵，贝l j ( 3 3 ) 有唯一 解。文献 2 8 】中，作者得到了经典线性互补问题的区间解法。我们把这种方法扩展 到了问题( 3 3 ) 中，得到了其近似解。 定理3 1 令n 维区间 g ( x ) ，用f f i g ( x ) ) 表示厂在 g ( 石) 上的区间扩张，如 果 r ( g ( x ) ， g ( x ) 】，d ) ：= m a x 0 ，g ( x ) 一d r ( x ) + ( ，一巧。( g ( x ) ) ) ( g ( x ) 卜g ( x ) ) ) g ( 石) ， ( 3 - 4 ) 当g ( x ) g ( x ) 】是固定的且d 是正对角矩阵，那么l h - 题( 3 3 ) 存在一解x 在区间 f ( g ( x ) ， g ( x ) 】，d ) 内。另外，如果问题( 3 3 ) 的解石+ 包含在 g ( x ) 】中，那么有 g ( x ) i ( g ( 工) ， g ( x ) ，d ) 。 2 l 电子科技大学硕士学位论文 证明：对于任意的g ( y ) g ( z ) 我们有 g ( y ) 一d r ( y ) g ( x ) d r ( x ) + ( i d f ( g ( x ) ) ) ( g ( x ) 一g ( 功) ， 那么 p ( y ) = m a x o ，g ( y ) 一d f ( y ) ) m a x o ，g ( x ) - d f ( x ) + ( ，一d f ( g ( 工) 】) ) ( 函( x ) 卜g ( 工) ) ) ， 也就是说r ( g ( x ) ，眩( z ) 】，d ) 是 g ( x ) 】上的映射p ( ) 的一个区间扩张。因此，条件( 3 4 ) 说明映射p ( ) 把 g ( x ) 】映到了它自身。于是，利用映射的连续性，映射p ( ) 有一个 固定点g ( x ) g ( x ) 】。所以我们就可以通过g ( x ) = 出+ p 得到问题( 3 - 3 ) 的解工。 对于问题( 3 3 ) g ( x ) 上的任意解x 我们可以推断 g ( x ) = p ( x ) m a x o ，g ( 功- d f ( x ) + ( 1 一巧( g ( x ) ) ) ( g ( x ) 卜g ( x ) ) ) ， 上式说明g ( x 。) r ( g ( x ) ，眩( 功 ，d ) 。 推论3 1 令r ( g ( z ) ，眩( 石) 】，d ) 为( 3 4 ) 式中定义。如果 r ( g ( 功， g ( 功】，d ) n 【g ( 功】= 中， 那么问题( 3 3 ) 在 g ( x ) 】上无解。 定理3 1 说明如果我们能够找到一个区间 g ( x ) 】o ，并且满足条件( 3 4 ) ，那么就 可以计算出一个n 维区间的单调序列 g ( 力 。) ，有 g ( x ) “1 = r ( g ( x ) ， g ( 力】。，d 。) n 【g ( x ) 】，k = 0 ，1 ， g ( x ) g ( x ) 。，d 。是正对角矩阵。通常选择g ( x 。) 为g ( x 。) = 研( g ( z ) ) 。则分量 式的误差小于或者等于半径，( g ( 功 。) 。 下面我们给出问题( 3 3 ) 的区间迭代算法，当么和县是两个矩阵并且严格对 角占优。 算法3 1 ： 第一步： 令d = 旃昭( 1 ，鹾，b 2 ) ，选择【e n c l o s u r e 】为包含l h - j 题( 3 - 3 ) 的唯一 解x + 的初始区间，令k = 0 ； 第二步：令 g ( x ) 】o ：= e n c l o s u r e 】； 第三步：计算 【g ( 功r + 1 ：= 【g ( 功rn m a x o ，g ( x k ) 一d f ( x ) + ( j d b ) ( 【g ( z ) r - g ( x k ) ) ) 当达到迭代终止条件时，停止。否则，令k ：= k + l ，转到第三步。 当g ( x 七) = m ( g ( 工) r ) ，从g ( x ) = a x + p 我们可以得n x ，于是再计算 第三章广义线性互补问题的区间解法 f ( x ) = b x + q ， 因为问题( 3 3 ) 的解g ( f ) 包含在 e n c l o s u r e q 6 ，算法3 1 将计算出一个嵌套序列 g ( x ) n 。而且这一序列收敛于区间点 g ( x + ) ，g ( x + ) 】。 定理3 2 令两个三矩阵么和b 严格对角占优。如果问题( 3 3 ) 的唯一解包含在 【e n c l o s u r e q 6 ，那么算法3 1 将计算出一个嵌套序列f i g ( x ) ) ，这一序列收敛于 g ( x ) ，g ( x ) 。 证明：算法3 1 将计算出一个嵌套序列 g ( x ) n 使得对于k 0 有 g ( x ) g ( x ) r ，有 g ( z ) 】“c _ m a x 0 ，g ( x ) 一d f ( x ) + ( ，一d 忸) ( g ( x ) 】七- g ( x ) ) ) ， 又 ，( g ( x ) 】+ 1 ) r ( m a x o ，g ( x 。) 一三矿( x ) + ( ，一三旧) ( g ( x ) - g ( x 。) ) ) ) r ( g ( x ) 一旷( 工) + ( j d i 曰) ( g ( 工) r g ( x 。) ) ) = r ( ( ，一d 曰) ( 【g ( x ) 】一g ( x ) ) ) 因为g ( x ) = 肌( 眩( 工) 。) ， 又 ( i - 删( g ( 瑚_ g ( 矿) ) 邓一嬲) ( ( 五_ 】一半) = ( i - d b ) x - - z x ，彳x - - x 】 = ( j d 曰) ( 一r ( 【g ( 功r ) ，( g ( 功r ) ) = 一u 一d _ 曰) ，( g ( z ) 】七) ，( j 一d b ) ，( g ( 功 。) 一( ，一d b ) ，( g ( z ) 】。) ( ，一j ，口) ，( g ( x ) 】) ， 2 3 电子科技大学硕士学位论文 当i d b 0 ，我们有 r ( 【g ( z ) 】。“) ( j 一脚) r ( 【g ( x ) 】) 因为曰是严格对角占优的，所以召是何矩阵，于是可以得到 p ( i d b ) = p ( i d b ) = m a x o ，p d q + 卜( j - d b ) d ，( 歹一d 曰) d 】) 卜d ，矗】 ( 3 5 ) 推论3 2 令b 为有正主对角元的矩阵，并j td 0 。那么问题( 3 3 ) 解的包含关 系( 3 5 ) 成立当且仅当p d ( q + b d ) 0 。 证明：由文献 2 8 中的定理3