（计算数学专业论文）lcp问题的理论分析及研究.pdf

摘要 摘要 本文涉及线性腻补问题( l c p ) 的解和一些特殊的矩阵，如p 一矩阵，尉一矩阵， 必一矩阵。因为这蹙特殊矩阵本身具有豹特性，所以它们对线性互补问题解的确 定是辈常耋要蕊。通过在蠢准线蕊互釜蠢霞受嚣逯毽矩薄蠹划线性互褡勰题簿麓 局部唯一性来研究广义线性互补问题( e l c p ) 的局部唯一解。本文主要寻找广义线 性互补问题包含的两类特殊情况，垂直线性腻补问题( v l c p ) 和水平线性牲补问题 ( h l c p ) 察熬藜翅。 邋过裁焉谗父獬关予多藤体集石x 鬻 l w + q w _ 斌彬芝r 5 ，l 薅美蒯， qe r 脚) 的列( 行) 非邋化性( n d 憔) 刻划垂直线性互补问题和水平线性互补问题的局 部唯一解来研究广义线性互於润题的解，得到了两个关于广义线性互李 阏题解的 薪蕊结巢，一是悉簸阵霪瑟菲避他性来裁剃泓，册蘸h 捌p 往，二是黑矩阵坌薛 非退化性来刻划 肘，的矿列p 性。 关键谶：线性互补阏题，广义翁靛互补闻题，矩阵，非退仡，局部唯一解 a b s t r a c t a b s t r c t t h i sp a p e ri sc o n c e r n e dw i t ht h es o l u t i o n st ol i n e a rc o m p l e m e n t a r i t yp r o b l e ma n d s o m ec l a s s e so fi m p o r t a n tm a t r i c e s ：p - m a t r i x ，h - m a r i x ，m - m a t r i x b e c a u s eo ft h e c h a r a c t e r so fi t s e l f , i ti sv e r yi m p o r t a n tt os t u d yt h es o l u t i o n st ol i n e a rc o m p l e m e n t a r i t y p r o b l e m i nt h i sp a p e r , w es t u d yt h el o c a lu n i q u e n e s so ft h es o l u t i o n st ot h ee x t e n d e dl i n e a r c o m p l e m e n t a r i t yp r o b l e m ( e l c p ) b ym e a n so fac o n c e p tw h i c hi sa ne x t e n s i o no ft h e n o n d e g e n e r a t em a t r i xi nt h es t a n d e r dl c et h ee l c pc o n t a i n sa ss p e c i a lc a s e st h e v e r t i c a l 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 ( v l c p ) ，h o r i z o n t a ll i n e a rc o m p l e m e n t a r i t y p r o b l e m ( h l c p ) ，t h ep a p e ri sd e v o t e dt of i n dt h ec h a r a c t e r i z a t i o no ft h es o l u t i o n st o v e r t i c a ll i n e a rc o m p l e m e n t a r i t yp r o b l e ma n dh o r i z o n t a ll i n e a rc o m p l e m e n t a r i t y p r o b l e m u s i n gt h ec o l u m n ( r o w ) n o n d e g e n e r a c y ( n op r o p e r t y ) o f m ，) w i t hr e s p e c tt ox ( x ：= 三w + q w o ，w r 。) ，l r ”州，q r ”) c h a r a c t e r i z i n gt h el o c a lu n i q u e n e s so f t h e s o l u t i o n st ov e r t i c a ll i n e a r c o m p l e m e n t a r i t yp r o b l e m ( v l c p ) ，h o r i z o n t a l l i n e a r c o m p l e m e n t a r i t yp r o b l e m ( h l c p ) ，w eo b t a i nt w on e wr e s u l t sf o rt h es o l u t i o n st ot h e e x t e n d e dl 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 ，w ea l s oo b t a i nt h en o n d e g e n e r a c yo ft h em a t r i x qc h a r a c t e r i z i n gt h eh - c o l u m np - p r o p e r t ya n dv c o l u m np - p r o p e r t yt ot h ep a i r m ， 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 ，e x t e n d e dl 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 ， m a t r i x ，n o n d e g e n e r a c y , l o c a lu n i q u e n e s so ft h es o l u t i o n s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同意对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期：付谚年夕月杉日 第一章引言 1 1 研究背景 第一章引言 在文献【l ，2 ，3 】中l c p 闼题涉及到有着丰富的数学理论和各种算法的不等式体 系，并被广泛的应用到科学和技术中来。随着数学规划的成熟和对解复杂的均衡 问题的需要的加强，l c p 问题的重要性越来越明显，范围也更广了。今天随着它 的扩展，许多新的研究课题已经溺现。除了它本身广泛的癍用之外，线性互补问 题还包括两个基本的特点，在文献f 2 ，3 ，4 ，5 e 懿n 它们对数学规划和均衡问题都是很 关键的。一个是补的概念，这是非线性规划的普遍性质。另一个是线性的性质。 线性和补为分析和理解在数学规划稠均衡规划中的复杂性质提供了基础的分析需 要。蠢此对l c p 问题的理论分搴厅及研究具有着重要的实熏价值。 1 2l o p 问题的基本概念及预备定理 给定n 阶实矩阵m 和n 维实向量q ，l c p 问题是找到一个n 维实向量z 使得 它满足： z 0 ，( 1 1 ) q + m z 0 ， z | ( 晕+ 勉) 一0 ， 其中z t 为向量z 的转置。 定义董2 。1 瑟1 ：对予矩阵么= 嘞 r ， ( i )如果它的所有主子矩阵是正定的，它就称为p 矩阵； ( i i ) 如果l 嘞| i ( 么) t - k l ，i = 1 ，。，露，它就称为严格对焦占优矩阵； i 毒 ( 1 2 ) ( 1 3 ) 电子科技大学硕士学位论文 ( i i i ) 如果 o 和o ，i c j ，i ，= l ，孵，它就称为三矩阵； ( i v )如果它是个非奇异的三矩阵且满足彳一0 ，它就称为膨矩阵； ( v )如果它的比较矩阵( 么) 是鲋矩阵，它就称为劈矩阵。 定理1 2 1 【6 】：m 是p 矩阵当且仅当l c p ( q ，m ) 对于所有向量ge r “有唯一解。 定理薹。2 2 峨掰是嚣矩阵氨它的对角线上的元素是正的，那么l c p ( q ，掰) 有 唯一解。 1 3 本文主要工作 对于l c p 问题中的理论研究仍有许多工作值得去做，尤其是对于广义l c p 问 题解麴理论研究及分析。本文研究广义线性互李 闷题及它的解的情况，并对广义 线性互补问题和线性互补问题之间的联系进行了全面了解。 通过利用矩阵膨的唯一性刻划l c p ( q ，m ) 的解的局部唯一性和 膨，) 关于 x 的歹g ( 行) j 暑退化性刻划广义线性互补问题的解的局部唯一性来研究广义线性 互补问题的解，得到两个关于广义线性互补问题解的新的结果，用矩阵q 的菲退 化性来刻划了 m ，) 的h 列p 性和y 列p 性。这些新的结果对于研究广义线性互 补阈题的解以及一些迭代法的全局收敛的分析是很有用。 2 第二章l c p 问题及广义l c p 问题的理论分析 第二章l o p 问题及广义l o p 问题的理论分析 l c p 问题在数学规划中是一个基本问题，随着它在工程，经济，如二次规划 问题和市场均衡问题等领域的应用的扩大，它的重要性和广泛性越来越明显。在 文献 2 9 中介绍了关于l c p 的推广，被称为广义l c p 。问题起源于对离散事件系 统的研究，另外它也被用于对混合系统的分析中。广义l c p 与l c p 问题也有着密 切的联系，事实上l c p 是广义l c p 问题的一个特殊情况。在文献 1 0 ，1 1 】中知如果 广义l c p 问题的解的可行集是有界的，那么任何一个广义l c p 问题都可简化成 l c p 问题。在文献 1 l ，1 2 ，1 3 中知v l c p 和h l c p 在可行集有界的条件下都可转化 成c p 。 2 1 一些特殊矩阵的性质和相关定理 矩阵m r “”被称为半正定矩阵，如果对任意x r ”，有x i m x 0 成立。m 被 称为正定矩阵，如果对任意x r ”，x 0 ，有x m x o 。这里定义的正定矩阵不限制 是对称矩阵。m 被称为最矩阵，如果不等式组m x o ，x 0 ，x 0 有解。m 被称为 s 矩阵，如果不等式组m x o ，x 0 有解。由以上的定义可得到： 正定矩阵) c p 矩阵) c s 矩阵) 。 定理2 1 1 【2 】：矩阵m r 是s 矩阵，当且仅当对于任意的q r “，l c p ( q ，m ) 有可行解。 定理2 1 2 2 】：矩阵m r 是一半正定矩阵，对于任意的ger “，若c 尸( g ，m ) 是可行的，则l c p ( q ，m ) 必有解。其解集为凸集。 定理2 1 3 2 】：矩阵m r 是一正定矩阵，则对于任意的q r “，l c p ( q ，m ) 电子科技大学硕士学位论文 有唯一解。 定理2 1 4 2 】：矩阵m 是个半正定矩阵，如果c p ( g ，m ) 是可行的，那么它就 一定有解。三吲g ，m ，g = c t ，一，h m = ( ：) ，有解 z l = ( 1 ，。) ，z 2 = ( o ，1 ) ，z 3 = ( 三1 ，j 1 ) 。 定理2 1 5 2 】：矩阵m r 是半正定矩阵，任意一个向量g r “那么有： ( a ) 如果z 1 ，z 2 是l c p ( q ，m ) 的两个解，则 ( z i ) ( g + 勉2 ) = ( z 2 ) ( g + 尬1 ) = 0 。 ( 2 1 ) ( b ) 如果z 。l c p ( q ，m ) 的一个解，nz 是非退化解和m 船是非奇异的，这里的 口= i ：乏 0 ) ，那么z 。是l c p ( q ，m ) 的唯一解。 ( c ) 如果矩阵m 是对称矩阵且又是半正定矩阵，那么对于任意的两个解z 1 ，z 2 有 m z l ：m z 2 。 此定理表明了对于矩阵m 是半正定矩阵的l c e ( q ，m ) 问题的解集是个凸立 方体集。 定理2 1 6 2 】：给定矩阵m r 和向量g r ”，下面的条件等价： ( a ) l c p ( q ，m ) 的解集是凸集。 ( b ) 对于任意z 1 ，z 2 是l c p ( q ，m ) 的两个解，( 2 1 ) 式成立，且三c p ( g ，m ) 的解集是凸 集，那么它等价于x 。，这里的口= i ：z i o ，v z s o l ( q ，m ) ) 。 矩阵m r “”被称为只矩阵，如果它的所有主子式是非负的。所有正定矩阵 是属于p 矩阵的，由只矩阵的定义有所有半正定矩阵是属于只矩阵的，下面给出 一些与尸矩阵刻划结果相似的定理。 定理2 1 7 2 , 1 4 1 ：矩阵m r “”，下面的条件是等价的 4 第二章l c p 阏题及广义l c p 阀题的理论分析 ( a ) 肼是只矩阵。 ( b ) 对于任意o z ，存在一个下标七，使得磊够o 和z k ( m z ) 。o 成立。 ( c ) 膨的所有实特征根和它的主予矩阵都是菲负。 上面定理( b ) 中的条件乙。是必要条件。例如：m = ( 三二 ，很明显它不 是矩阵。任意一个z = f z l ，z 2 ) o ，我们能得至五( 勉) 。= 彳o ，因此如果我们去 掉条件o ，m 将满足定理中( b ) 中的条件。取z = ( o ，1 ) 能看出m 将不满足定理 2 1 7 中嘞中的所有条件。 在定理2 1 5 ( c ) 中，如果m 是对称半正定矩阵，那么对于任意的两个解z 1 ，z 2 ， 能得到疆个相同向量w = q + 勉。( i = 1 ，2 ) 。这个w 的唯一性与z 的唯一性是相似的。 下面就来介绍关于w 的唯一性的判断标准。 定理2 1 8 2 , 1 s ：矩阵m r ，下面的条件是等价的： ( 鸯对于所有向量鼙k ( m ) ，如果z 4 ，z 2 是l c p ( q ，m ) 的两个解，那么m z = m z 2 。 ( b ) 对于每个向量有z i ( m z ) ，0 ，i = l ，2 ，z ，那么有m z = 0 。 ( c ) 对于每个指标集掰，有掰。= 0 ，这个丝搿的列向量是线性相关的。 显然如果m 尺“”是非奇异矩阵的那么它满足定理2 2 8 中的条件( c ) ，那么m 是p 矩阵。 在文献 1 l 】中矩阵m r “8 是p 矩阵被称为是第一类，如果它至少有个元素 正，否则称为第二类。m 被称为几乎p 矩阵，如果它的所有适当主子式是正定的 且它的行列式值是非负。掰被称为是z 矩阵，如果它的所有非主对角线上的元素 是非芷。 弓l 理2 1 9 【1 6 】：矩阵m r 舢是几乎p 矩阵当且仅当彳一1 是p 矩阵。 现在我们根据对任意向量g r ”，l c p ( q ，掰) 解的个数来考虑一些特殊矩阵的 电子科技大学硕士学位论文 性质。在文献 8 中m r “4 是p 矩阵当且仅当l c p ( q ，m ) 对于所有向量q r 8 有唯 一解，k o j i m a 和s a i g a l 对p 矩阵进行了研究，并证明了下面的定理。 定理2 1 。1 0 2 】：矩阵m r 是p 矩阵。如果嚣 0 或任意的 存在分量是不大于等于零的向量q ，l c p ( q ，m ) 恰有两个解。如果对存在元素不小 于零的矩阵掰和对存在分量不大于等于零的向量垡，l c p ( q ，m ) 有唯一解，对任 意q 0 且m 是非退化的矩阵，n l c p ( q ，m ) 恰有三个解。 定理2 1 1 1 1 2 1 ：如果掰 p ( g ) ，b 是个非负矩阵。我们知道彳是m 矩 阵当璺仅当它是z 矩阵且它又是夕矩阵。在文献【9 】中有更多关于掰矩阵的等徐条 件的定义。，矩阵还有下面的一个等价定义，么是f 矩阵当且仅当它的所有( 靠一1 ) 主子矩阵是m 矩阵并且它的行列式值是负的。 对于所有的向量垡，如果l c p ( q ，m ) 有解，那么在这个闻题里的矩燕掰被称 为q 矩阵。对于l c p ( q ，m ) ，无论它是否有可行集，如果它都有解，那么在这个问 题里的矩阵膨被称为q 矩阵。 定理2 1 1 3 2 0 1 ：矩阵m 是非奇异的z 矩阵，j j g 么m q 当且仅当m 1 岜q 。 定理2 1 1 4 2 1 ：m 是f 矩阵，那么对于任意g o ，g o ，l c p ( q ，髟) 恰有两个 解，当q o ，q 0 时无解。其余隐况时最多有两个解。 定理2 1 1 5 【2 】：m 是z 矩阵，如果对于任意垡o ，q o ，l c p ( q ，m ) 有两 个解且对于其它情况时它有有限个解，那么膨是f 矩阵。 6 第二章l c p 阀题及广。义l c p 阏题的理论分据 豳上囱两个定理还得到了f 翻一个定理。 定理2 1 1 6 1 2 1 ：m 是z 矩阵，当且仅当对于任意g 0 ，q 够0 ，l c p ( q ，m ) 有两 个解或最多有两个篇。 对于一个矩阵的定义，可能会有许多等价的定义，如：m 是p 矩阵当且仅当 对于任意一个非零向量x r ”，有m a x 。 x e ( m x ) ，) 0 。在文献 1 8 中利用此定义 m a t h i a s 和p a n g 弓| 入了一个与p 矩阵有关的定义，即a ( m ) 的值 口( 肘卜m 一i n m a x , , 釉蕾( 尬) r ) 。( 2 - 2 ) 并且在文献 3 0 1 中n a i h u a x i u 也孳| 入个与夕矩阵有关的定义，邸f l ( m ) 的僮 ( m 卜m 恍a ：x 。 m a x l 甜翻蕾) ，) 。 ( 2 3 ) 定理2 1 1 7 e 1 8 】：如果矩阵m 是个p 矩阵，那么g ( 掰) 满足： 口( 膨) o 无解。 2 3 广义l o p 的基本概念和定理 l c p 问题是数学规划中的基本问题之一，它在工程和经济等中也越来越重要， 随后出现了关于l c p 问题的推广，即广义l c p 闻题。且广义l c p 闻题的重要性 也是不容忽视的，它丽样在工程和经济的等领域的应雳孛是非常重要的，荠且l c p 问题的线性推广是广义l c p 问题的一种特殊情况。另外在某些情况下广义l c p 问 题可以简化成l c p 问题。所以对于广义l c p 问题分析研究也是非常有意义的工作。 在文献 1 9 ，2 0 中，给定矩阵a r “8 ，b r q ”，和向量c r p ，d r q ，和关于 m 的指标集办，屯墨 1 ，p ) ，e l c p 问题是找到一个向量x r ”满足： a x o ， b x = d ， n ( a x - c ) ，= o 。 j = lf 癣 ( 2 6 ) ( 2 7 ) ( 2 。8 ) e l c p 问题的可行集被定义为f = 扛r ”l a x c ，b x = d ) ，对于不等式a x c 的第i 个的不等式差变量s 掰翠( i ，x ) 被定记为s u r p ( i ，砖= ( 血一力；。条件( 2 8 ) 表示 1 0 第二章l c pt 鼯- j 题及广义l c pl - j 题的理论分恚蓐 的是e l c p 的补条件。 对于e l c p 和l c p 都包含了积的和。然而对于e l c p 这个积可能包含个，两 个或更多乘积因子，丽对于l c p 一般这个积只包含两个乘积因子。著且在文献 1 3 】 中有一个算法可寻找到e l c p 的所有解。 对于给定矩阵a ，b e r ”和向量a ，b e r 胛，v l c p 问题是找到一个向量x e r ” 使得 ( 彳x + 口) ( b x + 6 ) 一0 ， ( 2 9 ) a x + a 0 b x + b 怠0 ，( 2 。1 0 ) 成立。 对于给定矩阵c ，d e r ”和向量q e r 册，h l c p 问题是找到一个向量 缸，y ) e r 2 ”使得 一d y = q ， ( 2 1 1 ) x y = 0 ，x ；0 ，y 0 ， ( 2 1 2 ) 成立。 定理2 3 。2 5 【1 0 1 1 】：l c p 是e l c p 的一个特殊情况。 定理2 3 。2 6 1 1 0 , l l 】：如果盈p 的不等式的差变量在它的可行集上是有界的，那么 这个e l c p 可转化成l c p 问题。 目前对于广义线性互补问题和线性互补问题之间联系的一些结论都是在基于 某些矩阵非奇异的条件下得到的。在一些条件下广义线性互补问题能转化成线性 互补问题使入们想到了能否也能在某些条件下把扩展的线性互补问题转化成线性 互补问题。在文献 1 0 ，1 8 ，2 1 q 咄n 水平线性互补问题可转化成线性互补问题，并且 在文献 2 1 ，2 4 】中还给出了一个算法把水平线性互补问题转化成线性互补问题。在文 献 1 0 1 中知垂直线性互牢 问题可转化成线性互补闯题。并且对于i l c p 的不等式的差 变量在它的可行集上是有界的条件下在文献 1 0 l q b 给出了详细的步骤将这个g l p 问题转化成线性互补问题。在这里我们就不详细介绍了。 因为广义线性互 b l ；l 题与线性互枣 阀题之闻有着密切的关系，所以线性互补 问题的理论对广义线性互补问题的理论分析将非常有用。通过对广义线性互补问 电子科技大学硕士学位论文 题与线性互补问题之间的这些关系的了解，以及对它们解的理论分析，得到两个 关于广义线性互补问题解的新的结果，用矩阵q 的非退化性来刻划了_ m ，) 的日 列尸性和v 列p 性。为此在第三章对广义线性互补问题的解进行了研究。结果表 明这些新的结果对确定广义线性互补问题的解非常有用。 1 2 第三章e l c p 的局部唯一解 第三章e l c p 的局部唯一解 在文献 1 0 ，2 2 】中知道l c p 是e l c p 的一个特殊情形。在文献 2 0 ，2 7 ，2 8 ，1 9 中 l c p 问题在矩阵对策，经济均衡，障碍，供应链等问题中有着非常重要的作用。 对于一个给定的l c p 问题解的存在性，在文献 2 3 ，2 4 ，2 5 ，2 6 中它的解的唯一性已经 成为一个热点问题。由于l c p 和e l c p 之间有着紧密的联系，所以对e l c p 的研究 也变得越来越重要。在文献 1 0 中v l c p ，h l c p 是e l c p 的一个特殊例子。在文 献【2 2 】中g o w d a 介绍和刻画了矩阵的列充分性和行充分性以及p 性质。在文献【9 中张和x i u 对e l c p 的解的局部唯一进行了研究，并且对它解的局部唯一性给出 了一些新的定理。本文将针对这个解的局部唯一性来进行研究。在这篇文章中， 借助在标准l c p 中非退化矩阵的推广和在文献 1 8 中h l c p 的性质这一概念来研 究e l c p 的局部唯一解。然后我们提出一些新的关于v l c p ，h l c p 的局部唯一解 的结果，这些结果对我们研究它们的解以及一些迭代法的全局收敛的分析是很有 用。 3 1 局部唯一解 首先，我们介绍关于e l c p 的另一种表达形式称为x l c p ( m ，n ，x ) 。这个 x l c p 问题就是：给定矩阵m ，n r “和在r ”上的一个多面体集x ， x ：= l w + q w o ，w r7 ，l r ”“，q r ”，( 3 1 ) 找到向量x 0 ，y 0 ，x ，y r “使得它们满足m x n y x ，x y = 0 。然后再引入 m ，) 关于多面体集x 的列( 行) 非退化( n d 性) 的概念和列非退化性与x l c p 的局 部唯一解的刻划。 对于一个列向量x ，记 矿= m a x 0 ，z ) ， 电子科技大学硕士学位论文 x 一= m a x 0 ，- x 。 那么，工= x + 一z 一。对于列向量x ，y ，记 根据x 的定义， x oy = ( x l y l ，吒儿) ，( x ，y ) = ( z ，y ) 。 彳一x = 三( 一w 2 ) o ，m 0 ) ， d + x = l w w 0 ) ，o + x = l w w 0 ) ， ( o + x ) = 孝l 孝= o ，孝o ) 。 对于矩阵m ，n r ”，我们称 m ，) 是 m ，) 的列重排，如果对于每个指标f ， m f - 鸠和n i = m 或m 产m 和n i = m j 。 这里下标与相对应的列有关。我们也称 m ，) 是 m ，) 的扭列重排，如果对于 指标i ， m 。t = m 酗峨= n i 或m j i = 一n i 酗k = 一m i 这里o + x 代表的是x 的退化集，( d + x ) + 这个退化集的对偶集。在这一节我们 介绍在x l c p 中的局部解问题，在介绍之前，首先给出列( 行) 非退化和局部唯一解 的定义。 定义3 1 1 1 9 , 3 0 ：给定矩阵m ，n r ”x ”和在r ”上的一个多面体集 x ：= l w + q w o ，wer 7 ) ，l r ”7 ，q r ”，称 肘，) 关于x 有列非退化性或 n d 性，如果它满足下面的条件： m u 一旷f t x x 和u 。1 ，= 0j ( “，1 ，) = ( 0 ，0 ) ， ( 3 - 2 ) 称 m ，) 关于x 有行非退化性或行n d 性，如果它满足下面的条件： m u 一肌x z 和w e ( 0 + x ) w = 0 。( 3 - 3 ) 定义3 1 2 2 ，9 】：z + ；是l c p ( q ，m ) 的一个解，它被称为是局部唯一解，如果存在 1 4 第三章e l c p 的局部唯一解 一个z 的一个邻域，在此邻域里z 是这个问题的唯一解。 定义3 1 3 【9 】：x e c p ( m ，n ，z ) 的一个解z + = ( 石x y ) 是局部唯一解，如果存在 一个z + 的一个邻域，在此邻域里z 是这个问题的唯一解。 定理3 1 4 【9 】： m ，) 关于x 有列非退化性或列d 性当且仅当对于任意的向 量p r ”，x l c p ( m ，n ，x + p ) 的每一个解如果它存在，那么它就是局部唯一解。 以上的定理表明了对于任意的向量p r ”，列n d 性与x z c p ( m ，n ，x ) 的局部 唯一解之间的关系。 我们可以发现上面的原理对于任意的 m ，) 的列重排和扭列重排都是正确的， 因为列n d 性对于这两类重排是不变的。在文献 3 0 中x l c p 的解集被描述一个仿 射空间的零集，这个解集是多面体集的有限组合。如果这个x l c p 的每一个解都是 局部唯一的，上面的定理说明了列n d 性成立当且仅当对于任意的向量p ， x l c p ( m ，n ，x + p ) 的解集是有限集。 定理3 1 5 9 1 3 0 1 ：给定矩阵m ，n r 和一仿射子空间x = l w + q wer 7 ) 其中 z = r a n k ( l ) ，不失一般性，假设z = ( x ，y + ) 是x l c p ( m ，n ，x ) 的解。定义这个指标 集 口= j x ； o ，巧= o ) ， = j x ；= o ，西= o ) ， y = j x ；= o ，y j o ) ， 那么，它是局部唯一解当且仅当下面的系统仅有零解： m u n v x - x ， ( 3 4 a ) t = 0 ，坳o ，坳o ， ( 3 - 4 b ) 以上的定理给出了在一个给定x l c p ( m ，n ，x ) 的解和x 是一个仿射子空间的 条件下它是局部唯一解的充要条件。 1s 也予科技大学硕士学缱论文 3 2 非退亿矩降和局部唯一性 定义3 2 。舻：矩阵嚣霆“8 被称为是菲退化的，絮栗它翡舞有主子式都是菲 零。 对于认识非退化矩阵与方程的基本解的非退化概念是很重要。 像p 矩阵一样，非退纯矩阵捌娜了l c p ( q ，m ) 戆解戆瞧一性。下面来看看一些 关于它的刻划定理。 定理3 2 。7 【2 】：给定矩阵m r 俐，下面的条件是等价的： ( 醇掰是非退纯的。 ( b ) 对于任意的向量q 岜r ”，l c p ( q ，m ) 有有限个解，或者只有零解。 赫对于所有麓囊量q r 8 ，l c p ( q ，嚣) 戆解都存在，劐它是属部唯一解。 定理3 2 8 【2 l ：z + 舞kl c p ( q ，肘) 的解。定义指标集如下： g = 9 ：乏=suptols u p p z g 3 童l ：乏 = 声= i ：墨= o a n d ( q + m z f = 0 。 那么z 4 是l c p ( q ，m ) 的局部唯一解当且仅当 ( 气，z p = ( 礴蹲 是下面方程 膨徽毛+ 和= o ( 3 - 6 ) w 8 2 m 融z 。+ m z 8 芝q ( 3 0 、) 知o ( 3 8 ) 惦z b = o ( 3 9 的唯一解。 特别地，懿栗茗+ 是菲运纯解，掰激是雩善奇弊酶，嚣么z + 是局部唯一解。 1 6 第三肇e l c p 的局部唯一解 二二二纛o = 二一。 方程( 3 - 6 ) 至( 3 9 ) 是混合五c p 的一个例子。如果是非奇异的，我们 能解= 埘二和a 把= 肘艘一m 加m - i m 础加入到方程( 3 。6 ) 至( 3 9 ) 中， 我稍得到三吸0 ，) 。因此，如果蚝是菲奇界酶，z 是局部唯解当且仅当这个 l c p ( o , ) 只有零解。 3 3 关于v l o p 、h l o p 的刻划 定义3 3 9 1 8 1 ；绘定矩薄掰，g 冀，称澎，册有y 列夕性，如果有 m a x ( m x ) f 【舭) f 0 ，v 0 x r ” 在这个条件下，在文献【2 l 】中知玩绺最多有一个解。我们再看个与 砑，奶有关 的货似，) 的值， 掰似，) 2 r a i n ：， m a x ( m x ) f ( 舨) f ，。(3一10)isigm | = i 一 “ 一 这个值的定义是非常好的，它是有限的，且为正的。它可以被看成是您c p 的货( 膨) 值的推广。由( 3 9 ) 明显可以看出 m a x 一( m x ) r 嘲，g 渺，研删三， ( 3 。1 1 ) 利用( 3 1 0 ) 在文献【7 】中m a t h i a s 和p a n g 还得到了一个关于况c 尸解的全局误 差边界。 定理3 3 。1 0 1 8 】：若+ 是您印的一个解。如果 材， 有矿列p 性，那么有 i i x - x u 。s 丽 i m + n l ) v x e r , ( 3 1 2 ) 这里8 ( x ) = m i n m x + a ，n x + b 。 当m 和是方阵时，y 列p 性成为m 和是非奇异矩阵和埘一t ( m n 一1 ) 是p 矩阵的条件e 并且这个窿 掰，n 幂f lc r ( n m 一1 ) ( a ( m n - t ) 的量之间还有如下的关系。 1 7 电子科技大学硕+ 学位论文 定理3 3 1 1 1 8 】：假设m 和n 是方阵。这个口 m ，) 有v 列p 性，那么有 烈必册南烈脚m 引眠m 赢烈脚k 下面介绍关于h l c p 的a ( m ) 量的推广。在文献 1 8 】中称 m ，) 有日列p 性， 如果对于任意非零向量( “，v ) r 2 ”和m u n v = 0 有 m a ，x u y i 0 。 l g s ” 这个性质保证了h l c p 有唯一解。h l c p 是当x = q ) 时，x l c p ( m ，n ，x ) 的 一个特殊情况。 设p = m ，- n 和列向量= 厶，厶 r 2 ，那么对于任意向量( “，v ) r 2 ”满足 m u - n v = 0 ，则存在一个向量孝r 使得 u = 厶f ，v = 厶f ， 那么 m ，) 有h 列尸性，即有 僻( 厶洲厶亭) r o ，v o 善硝。 在此条件下，在文献 1 8 ，2 1 中定义的关于 m ，n ) 的a m ，n ) 的值： 口似，) - p m 牡i n m 。a x 。( l l g ：) t ( 厶鳓。 定理3 3 1 1 1 8 ：( 工+ ，y + ) h l c p 的一个解如果 m ，) ：f i n 列p 性，那么我们 有 il(五y)一(z，y)|。错tlminx，y)o。， 对于任意( 石，y ) r 2 ”和尬一n y = q 。 定理3 3 1 2 ：设m 和是方阵，如果 m ，) 有日列p 性，那么( 厶互1 ) ( 三。与1 ) 第三耄e l c p 的局部唯一解 州川赢州销饥 嘞 赢似辆1 ) o 定理3 3 1 3 9 】：i 整h l c p ( m ，n ，g ) 中给定矩阵m ，r 一，定义关予 膨， 的 矩阵q ： ( m n 、 岔2 d蠢j 。” q 是一个( m + n ) x 2 n 的矩阵，并j i t d = 西a g ( d j ) 和d = 疣a g ( d j ) 是任意的两个对角 矩阵。那么有 ( a ) 这个 m ，n 有列n d 性当且仅当在( 3 。1 3 ) 中定义的矩阵q 中对于任意的满足 以d = o ，d j + d j o ，= 1 ，2 ，刀的对角矩阵d 和d ，q 都是列满秩的。 镥) 这个 m ，n ) 有行n d 性当且仪当在( 3 1 3 ) 中定义的矩薄q 中对于任意的满足 嘭d j = o ，d j + d j 0 ，j = l ，2 ，麒的对角矩阵d 和d ，q 都是行满秩的。 这个定理显示了( 3 - - 1 3 ) 的矩阵q 的秩与 m ，n 的列n d 性之间的关系从而 有了h l c p ( m ，n ，q ) 的局部唯一解。特别的当m = n 时，它阐述了这个 h l c p ( m ，n ，g ) 有歹ln d 性当且仅当m 或是非奇异的和如果m n 或n q m 是 非退化矩阵。 上面的定理也显示了，对于这个h l c p ( m ，n ，q ) ，当m n 时，这个行n d 性是不 成立的；对于这个h z c p ( m ，n ，q ) ，当m 慈时，这个列n d 性是不成立昀。因此 在m 有列n d 性。 又良列n d 性知上面这个定理是有助于在文献【2 2 ，2 3 ，2 5 ，2 8 1 q bh l c p ( m ，n ，q ) 的一些迭代法的全局收敛的分析。对于v l c p 问题有一些结果是与上面的两个定 理相似。 3 ，4 新的结果 定理3 3 。1 4 ：在h l c p ( m ，n ，q ) 中给定矩阵m ，n e r “”，定义关于 拟，n 】- 的 矩阵q ： q ：一瞄斟 洛蜘 ：一| 一 l ， ( 3 1 5 ) i 参d ； q 是一个( 朋+ n ) x2 n 的矩阵，并且d = d i a g ( d j ) * id = d i a g ( d j ) 是任意的两个对角 矩阵。那么这个 拟，有日列p 性当且仅当在( 3 - - 1 5 ) 中定义的矩阵q 中对于 任意的满足嘭d j