（计算数学专业论文）等式约束加权最小二乘问题的扰动分析.pdf

摘要 各种广义的最小二乘问题，包括最小二乘问题，总体最小二乘问题，等式约束最小二 乘问题，刚性加权最小二乘问题等，是计算数学研究的一个重要领域，也是一个非常活跃 的研究领域它在统计学，最优化问题，卫星定位，信号处理，计算物理，计算化学，地球 物理及信息科学的科学计算中均有广泛的应用 本文主要研究等式约束加权最小二乘问题关于加权约束m p 逆的上确界、加权约 束m p 逆和加权约束投影矩阵的稳定性，以及稳定且高精度的数值方法的研究，是重要 而且困难的，本文将要研究这些问题实践证明，仅仅要求系数矩阵a 的条件数较小并不 能保证等式约束加权最小二乘问题解的数值稳定性本文通过仔细分析约束加权广义逆 和约束加权投影算子的稳定性及扰动上界，研究了当加权矩阵取自实对称半正定矩阵子 集，或加权矩阵刚性但给定时，相应的等式约束加权最小二乘问题的扰动情况和数值稳 定条件并在此基础上，给出了计算等式约束加权最小二乘问题的稳定算法 关键词：约束加权广义逆，约束加权投影算子，等式约束加权最小二乘问题，稳定扰 动刚性 a bs t r a c t v a r i e t yo fg e n e r a l i z e dl e a s ts q u a r e sp r o b l e m s ，s u c h t h el e a s ts q u a r e sp r o b l e m s ， t h et o t a ll e a s ts q u a r e sp r o b l e m s ，e q u a l i t yc o n s t r a i n e dl e a s ts q u a r e sp r o b l e m sa n ds t i f f l y w e i g h t e dl e a s ts q u a r e sp r o b l e m s ，p l a yi m p o r t a n tr o l e si nc o m p u t a t i o n a lm a t h e m a t i c s m a n ye x p e r t ss h o wg r e a ti n t e r e s t si nt h i sa r e a t h e s ep r o b l e m sh a v ew i d ea p p l i c a t i o n s i ns t a t i s t i cs c i e n c e ，o p t i m i z a t i o n ，g p s ，s i g n a lp r o c e s s i n g ，c o m p u t a t i o n a lp h y s i c s ，c o m p u - t a t i o n a lc h e m i s t r y , g e o p h y s i c sa n di n f o r m a t i o ns c i e n c e ，e t c i nt h i sp a p e rw ef o c u so nt h ee q u a l i t yc o n s t r a i n e dw e i g h t e dl e a s ts q u a r e sp r o b l e m s ( w l s e ) i ti sv e r yi m p o r t a n tb u td i f f i c u l t t os t u d yt h es u p r e m u mo ft h ec o n s t r a i n e d w e i g h t e dp s e u d o - i n v e r s e s ，t h es t a b i l i t yo ft h ec o n s t r a i n e dw e i g h t e dp s e u d o - i n v e r s e sa n d t h ec o n s t r a i n e dw e i g h t e dp r o j e c t i o n sa sw e l la st dw o r ko u ts t a b l ea n dh g h - p r e c i s i o nn u - m e r i c a lm e t h o d s ，w h i c hw i l lb ed i s c u s s e di nt h i sp a p e r i ti ss h o w nt h a taw l s ep r o b l e m r m g h tb eu n s t a b l ee v e ni ft h ec o n d i t i o nn u m b e ro ft h ec o e f f i c i e n tm a t r i xi ss m a l l w h e n w e i g h t e dm a t r i c e sa r eg i v e ns t i f f l yd i a g o n a lm a t r i c e s ，o rf r o ms o m e r e a ls y m m e t r i cp o s i t i v e s e m i d e f i n i t em a t r i c e ss e t ，w eo b t a i nt h ep e r t u r b a t i o nb o u n d sa n ds t a b i l i t yc o n d i t i o n sf o r t h ew l s ep r o b l e m sb ys t u d y i n gt h ep e r t u r b a t i o n so ft h ec o n s t r a i n e dw e i g h t e dp s e u d o - i n v e r s e sa n dt h ec o n s t r a i n e dw e i g h t e dp r o j e c t i o n s f i n a l l y , w ep r o v i d es o m en u m e r i c a l s t a b l em e t h o d sf o rc o m p u t i n gw l s ep r o b l e m s k e yw o r d s ：c o n s t r a i n e dw e i g h t e dp s e u d o - i n v e r s e ，c o n s t r a i n e dw e i g h t e dp r o j e c t i o n ， c o n s t r a i n e dw e i g h t e dl e a s ts q u a r e s ，s t a b l ep e r t u r b a t i o n ，s t i f f 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果 据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过 的研究成果对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并 表示谢意 作者签名：纭躏 日期：矽p 7i i 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留学位 论文并向国家主管部门或其指定机构送交论文的电子版和纸质版有权将学位论文用 于非赢利目的的少量复制并允许论文进入学校图书馆被查阅有权将学位论文的内容 编入有关数据库进行检索有权将学位论文的标题和摘要汇编出版保密的学位论文 在解密后适用本规定 学位论文作者签名：；参鹚 日期：钞0 7 第一章等式约束加权最小二乘问题 设a c m 。n , b c 4 在求解线加权最小二乘( w l s ) 问题 i i w 5 一b ) l l ：= 瓣杪。( 却“) 0 。 时，有时会对系数矩阵a 和向量b 有一定的要求比如，把a 和向量6 如下分块 a = ( 二)，6 = ( ：) ， 其中m = m 1 + r n q ，l c ”- “，l c 4 2 “，h c “，g c “，在l ，h 中没有误差，而 在kg 中含有误差即有h 冗( l ) 这时就需要用等式约束加权最小二乘方法来处理 对于w l s 问题和等式约束最小二乘问题，【2 ，6 ，1 0 ，1 8 ，1 9 ，3 3 】研究了当加权矩阵 在某实半正定矩阵的子集中变化时，加权m p 逆或约束加权m p 逆的上确界【1 8 ，1 9 ，2 5 】 推导了这些上确界稳定的必要和充分条件，并推导了加权m p 逆及w l s 问题的扰动上 界当是给定的正定对角刚性加权矩阵时，f 2 0 ，2 l 】揭示了加权m p 逆和多重约束m p 逆的关联，并推导了加权m p 逆和对应的w l s 问题扰动稳定的条件同时，【2 7 ，3 0 】给出 了几种求解刚性w l s 问题的稳定算法加权约束m p 逆的上确界、加权约束m p 逆和加 权约束投影矩阵的稳定性，以及稳定且高精度的数值方法，是研究等式约束最小二乘问 题的主要困难，也是本文将要探索的问题 本文将要介绍等式约束加权最小二乘问题并作扰动分析归纳起来，本文主要分成 以下几个部分：第一章是预备知识主要介绍等式约束最小二乘问题的解集和等价性问 题，以及初步的扰动分析第二章研究当加权矩阵取自实对称半正定矩阵的子集z ，2 或岛 时，约束加权广义逆，约束加权投影算子和相应的等式约束加权最小二乘问题的扰动情 况第三章研究当加权矩阵非常刚性且确定时，约束加权广义逆，约束加权投影算子和相 应的等式约束加权最小二乘问题稳定的扰动情况第四章介绍关于等式约束最小二乘问 题的数值解法 1 1 等式约束加权最小二乘问题的定义和解集 1 1 等式约束加权最小二乘问题的定义和解集 给定矩阵a = ( k l ) c ，l 。一及向量b = c m “，h c ”l ，g c m 记p = i l t l ( 9 h ) c ”，其中l c ”t 。”，k 有r a n k ( w k p ) = r a n k ( k p ) 定义1 2 令伤( a ) ，所谓等式约束加权最小二乘鲟题r 以下筒记为w l s e # 孑题 ，是 i i w 5 ( k x - g ) 磐呐k y - g ) 怯 ( 1 1 ) 其中s = s ，c “：l i l y h l h2 恕0 工石一h l l 2 ) ， 借助于等式约束最小二乘问题( l s e ) 的代数性质可以研究w l s e 问题 引理删龇时m ，c n ，咧以并泓= ( 三) 定义 a 三l r p ，k ) ，。，。， 砖j m 兰( 上一( 耳p ) t w k ) l t ， 贼有 a 0 = ( ( 工 k ，( 1 p 矿 j r p ) i 矿j ) ， 嘞伽( ：嘲漏) ， 西a w = a o a = a t a = l t l + ( i 1 k p ) 。w i l 彤p 称a 0 为矩阵a 的约束加权m p 逆，p w a 为矩阵a 的约束加权投影矩阵 1 2w l s e 问题的等价性问题 定理1 2 给定矩阵l c ”- “，k 伊u “，w 伤( a ) 及_ | 句f h c ”- ，9 c m 泓= ( 三) 小( 弘w l s e i b m 阳，一为 s w l s e = $ = a 0 6 + ( i a t a ) z ) ，( 1 4 ) 7 l ：q b a t w 为矩阵a 的约束加权m p 逆。z c “为任意向量 证明w l s e 问题( 1 1 ) 的任一解应该满足约束条件l | l z 一酬22 嬲0 切一划2 ，因 z = l t h + ( i l t l ) u = l t h + p u ， 其中u c 丑为待定的向量把z 的表达式代入( 1 1 ) 式中的第一式，可得 u = ( i ，t 、，i 9 一w k a i h ) + ( j 一( w k p ) t ( w k p ) ) z ， 其中z c “再把t 的表达式代入z 中即得( 1 4 ) 式 口 本文主要研究w l s e 问题( 1 1 ) ( 1 1 ) 的极小范数最小二乘解x w l s e = a t w b ( 定 理1 2 ) ，其中a 0 = ( ( j 一( w k p ) t w k ) a t ，( w k p ) w ) 为矩阵a 的约束加权m p 逆， 再定义p w a 三a w a 0 为矩阵a 的约束加权投影矩阵( 引理1 1 ) 要研究w l s e 问题在什 么样的条件下的扰动稳定，关键就是看约束加权m p 逆和约束加权投影矩阵什么时候扰 1 2 w l s e 问题的等价性问题 下面介绍w l s e 问题( 1 1 ) 的几个等价性问题 1 k k t 方程 定理1 3 价1 ，l a , j 例给定矩阵l c 4 - “，k c “：“，w 伤( a ) ，及句量危c “，g c 砷，其中w 非奇异则w l 6 e 问题( i i ) 等价于- f 萄的l s 润题 肚睢00 吾l 卜( ；) 舻(甜 ( 5 ) 1 2w l s e 问题的等价性问题 4 这里m = m 1 + 竹1 2 ，t ，为l a g r a n g ef 句量，, r w 为加权残量，并且有 x 2 无约束l s 问题 一( k l 囊k ) 日( 吃 耳) 日 w ( x k ( w k p ) t w ) w ( w k p ) 饵 ( k p ) 一( ；p ) ( w k p ) 日 ( 1 6 ) 贝i j w l s e 润题( i 1 ) 等价于下面的无约束l s 问题 悄一圳严灿m i 。i 锄川忆御a = ( ：) z ， 3 酉分解法 定理1 5 似，j 瞑叨给定矩阵l c p m l x n ，k c m 2 x nw 仍( a ) ，及向量危c m l , g c m 2 ，其碍啊c “，定义 删，= ( 去耳) 暇“， m 8 ， 设a ( w ) 的酉分解为 a c ，= q ( ：) = q - 兄，q - ；( 詈：) 抛m l ， c 9 ， a 0 = r ( q i l ，( j q i l q l l ) q 轰w 7 ) ，( 1 1 0 ) w l s e 同题( 1 i ) 的任一解z 有如下表达式 z = m ( q 墨w g + q i l ( 危一q 1 1 q 轰 g ) ) + ( ，一r t r ) z ，z c 4 ，( 1 1 1 ) 其中极小范数w l s e 解w l s e 为 z = 硝( q 瑟w ，；g + q i l ( 一q l 。q 器1 l 矿 g ) )( 1 1 2 ) 1 3 w l s e 问题的扰动 4 q - s v d 法 定理1 6 似剐给定矩阵l c 1 “，k c ”“，w 仍( a ) ，及句量危c m l , g g “， 其中a c ”令以砂式中 t c j a ( w ) 的s v d 为 a ( w ) = z t h h = z 1 t a h i ! r ， ( 1 1 3 ) 这里z c “。“，h c “。“均为酉矩阵， t = d i a g ( t 1 ，o ) ，乃= d i a g ( h ，0 ) ， t 1 2 2 k 0 为a l w 、的非零奇异f f i , z i ，h 1 分别为z 。h 的前r 列则有 a 0 = h i t s l ( z 1 1 ，( 卜z i a z n ) z 舞呐， ( 1 1 4 ) i n a t a = i 。一h l h ， 其中z u 。z 2 1 分别为z i 的前叭行和后“2 行w l s e 闻题( 1 i ) 的任一解z 为 z = 皿可1 ( 兹w i l 9 + z 1 1 一历l 磋w 夕) ) + m 一日1 砰) z ( 1 1 5 ) 5 加权l s 法 定理1 7 似驯给定矩阵l c 詈t ”，k c “。“，a c m “，w 死( a ) ，_ | 句t h c “z ，g c “。月钌6 c 4 克! 义 阶) ：f 帆t、， w 则当t 一+ 。s o , w l s 问题 i i w ( r ) ( 血一6 ) 恢 等价于w l s e 问题( 1 1 ) 1 3 w l s e 问题的扰动 ( 1 1 6 ) ( 1 1 7 ) 本节初步推导w l s e 问题的扰动分析当w 为对角正定矩阵，g r a n k ( l ) = m 1 ，r a n k ( a ) = t i 时，g u l l i k s o n 和w j d i 【1 2 提出用加权q r 方法计算w l s e 解的方 1 _ 3w l s e 问题的扰动 法，g u l l i k s o n 1 3 则分析了该方法的向后误差分析对于一般情况，d ep i e r r o 和魏木 生 3 1 利用w l s e 问题等价予一个无约束l s 问题的事实( 定理1 4 ) ，推$ t w l s e 问题的 误差估计本节内容取自【3 】 设 = 二j - 厶露= k + a k , a = a + a a ，茆= w + a w 伤( a ) ， ( 1 1 8 ) 芫= h + a h ，爹= g + a g ，苔= b + a b ， 分别为厶k ，a ，w , h ，g ，b 的扰动形式，声= j z t z 则由定理1 2 ，扰动的w l s e 问题 i i w ；( k x 一蓟1 1 2 = m i n1 1 谚 ( r y 一 ) i l ：， 。占 一 ( 1 1 9 ) 其中多= ! ，c 4 ：l i l y 一钆= 嬲| i z 一鼬， 的解集岛l s e 为 勃工。e = 缸= 2 j + ( ，一岔勾z ：z c “) ， 其中 岛= ( 嘲蒜露) 定理1 8 若九冗( ，矩阵三和五满足等袄条件 r a n k ( l ) = r a n k ( ) 一p m 1 ，r a n k c a ) = r 痂【( 勾= r 并且 i i 岛一a w l l 2 i i a 1 1 2 1 ，i l w a w i l 2 1 ， ( 1 2 0 ) ( 1 2 1 ) jj 奎访二s f z l s e 0 2 i i a w i l 2 ( 1 l h b l l 2 + i i a i l 2 0 z w l 册0 2 ) + 6 。i i a t l l 20 a i l 2 0 z l 鲫1 1 2 + ( | i 一1 1 1 2 i i ( w k p ) t w 1 1 2 + ( i i a k i i , ( 1 2 2 ) + i i a l i l 2 i i k l t l l 2 ) l l w i l 2 i i ( w k p ) f l i d i i , 1 1 2 + o ( i ia l i i ；+ i ia k i i ；+ i f w 鸺) ， 1 3w l s e 问题的扰动 这里 k ： 0 势钏时 i1 ，当r 乱肘 如果还有r n ，贝i j ) - i ；c t - w l s e 闯题( 1 i ) 的任一w l s e 锯嚣， z = 西- ( ，一卸z 存在w l s e 问题f 1 1 9 ) 的一个解龟， l | 岔一z 0 2 反之亦然 ( 1 2 3 ) l i a i i ：( 1 l b l l 。- , i - l i a a i i z l l w l s e i l 2 ) + l i a r i l 2 l i a i l 2 i i z z w l s e i l 2 + ( i i w - a w i l 2 i f ( p ) 缈 1 1 2 ( 1 2 4 1 + ( i i , k i l 2 + 0 l i k 口) 0 i 矿i ( k p ) 旧) 0 “1 1 2 + o ( i i a l i i ；- t - l i z l k l l l + l i z x w l l ；) ， 注1 1 定理1 ，8 推导7 w l s e 溺题( 1 ，i ) 的扰动界，注意到当热叔矩阵w 的条件数菲常大 时t 则定理中推导的误差界会明显增大t 这是因为在扰动界中由加权投影矩阵得到的项 包含t 面的因子 i i w i l 2 i i ( w k p ) 幢 当w 非常病态时上面的项会明显增大 另一方面，可以用如下的公式来计算w l s e 问题( i 1 ) 的扰动界， 0 硫s e x w l s e i z 0 a 0 z ( 1 l a z , 1 1 2 + ( 1 + ) a 0 。i i = w l s e l l 。) + i i ( 谚 露向t 谚( j k ( w k p ) t w ) 1 1 2 l i t k i l 2 由上面的估圣圬e 号馏7 下面三个同题 p ，s u p 憎0 0 2 是否有界9 有哪些子集伤伤( a ) ，使得s u p w e p z ( a ) n 俐当s u p8 a 0 怯有界肘，在什么条件下s u p0 a k 也有界p 彻在仔么条件下0 鹂( f a a 0 ) i 1 2 或l l ( 茆 露声) 茆 ( j k ( w a # 1 1 2 有界 k p ) t w ) 亳界2 如果上面三个润题的答案是肯定的。刚关于w l s e 解的扰动也是有界的下两章中 将讨论i 述问题 第二章w l s e 问题的稳定性扰动 加权约束m p 逆的上确界、加权约束m p 逆和加权约束投影矩阵的稳定性，以及稳定 且高精度的数值方法，是研究w l s e 问题的主要困难，也是本文将要探索的问题本章主 要介绍当加权矩阵在某些实对称半正定矩阵的子集中变化时，加权约束m p 逆、加权 约束投影矩阵和相关w l s e 问题的稳定性内容取自【2 ，1 8 ，1 9 ，2 2 ，2 5 1 2 1约束加权m p 逆的上确界 本节介绍蜘愀p 逆的上舰设一k 一“扣( 三) 掣 定理2 1 ( f g | 。f 1 9 ，2 2 | ) 给定矩阵l ，k 1 a ，定义 现= = d j a g ( d 1 ，“。) 0 ： ( 2 1 ) s u pi i a t w l h s u pu 0 ( - 矿p ) a w e _ 0 2w z b7 一悃 = 峄) t i l 2 = ( 2 2 ) 高兰理2 2 ( 1 2 | 1 9 2 2 | ) 给定矩阵l ，k 。a ，对于某整数t2r p 给定矩阵集合流冬r m 2 x 1 v u 地，r a n k ( u t k p ) = r a n k ( k p ) = r p ， 瓢瓢忙) ( j 烈， ( 2 3 ) 2 2 约束加权m p 逆的稳定性 其中j q 产k 砷是一个指标向量的集合满足 ，( u t k p ) = j = i l ，t ，1 ： r a n k ( u ，k p ) = r a n k ( k p ) = r 一力 定义如下的m 2xm 2 实对称半正定的矩阵集合9 2 。 1 2 = = u d u t ：d = d i a g ( d 1 ，d t ) 0 u 砺 使得r a n k ( w k p ) = r a n k ( k p ) 吼| 有 s u pi i a o i l 2 w e 危 = s u p ，坠0 ( ( 7 - ) 4 ) ( 丁) 钏2 w e p 2f + + 礓一l ( 去) ( j 枞 2 2 约束加权m p 逆的稳定性 ( 2 4 ) ( 2 5 ) ( 2 6 ) l c 孑1 x n ，k c m 2 x n , a = ( 三) c ? 。n ， c z 7 ， 其中m = m 1 + m 2 ，w 伤( a ) ， 三= l + 厶詹= k + k 互= ( 妻) = a + a 分别是厶k 和a 的扰动形式则a 和五的约束加权m p 逆分别是a 0 和岛 引理2 s 伪柬加权脚逆扰动稳定的必要条例设a = ( 三) 昭“和集觎g p 2 ( a b 绘定并a 满是 s u pi i a o i l 2 0 ，定义扰动矩阵的集合s 2 ( 坊， h 五= a = ( 主) ：础c 三一诎c 功， 偿。， r a n k ( 勾= r m a k ( a ) 且l la a 1 2 订 定义2 1 设厶k ，a 由p 刀式给出，仍cp 2 ( a ) 给定，并满足 瓦1 兰w s u 。危p i i 嘲。 0 。使得 s u p s u pl i 五0 1 1 2 + o o 硅岛( 帕w 砘 引理2 4 设l c p m l 。n ，k c m 2 x n , a c “，碣，伤由定理2 磁争出，且 s u pi i a # 1 1 2 + o o n 令 刚有 见兰i n f 咿r a i 嘲n + ( 茄k ) = f ，s u p i i a b l l w e p 2 ：1 _ 1 ， p 1 兰懒i n 埘r a ( 旷i n k p ) + ( 咿昭k p ) = f ，e ii(wkp)w11wep2z 1 ， p 2 p 1 ( 2 9 ) ( 2 1 0 ) ( 2 1 2 ) 定理2 5 ( 1 1 9 1 ) 设l ，k ，a 由( 2 ， ) 式给出l 也 印2 由定理2 2 给出刚岛在2 上稳定。 当且仅当对于任意渺地和指标f 句量j = i l ，4 - p ，真中1 i l i r 呻m 2 ， r a i l l 【( 蜉) = r p 臆含r a n k ( u ，k p ) = r p ，( 2 1 3 ) 真等价于 叫嘲一p 臆含r 诎( 去) 一 亿均 2 3 约束加权投影矩阵的扰动上界 1 1 如果( 2 i 3 ) 式中的条件满足则对于常数q ( n l 。q = 盘盹和矩阵五s 2 ，有 击晨列磊赢 推论2 6 ( f i 9 | ) d 2 由定理2 i 给出， ( 2 1 5 ) 现= = d i a g ( d l ，) ：w p 2 c a ) ， ( 2 1 6 ) 贝弘0 在巩上稳定，当且仅当对于任意满足1 l - p m 2 的指标_ i 句 量j = 1 ，t ，) ，者隋 其等价于 r a n k ( k ，p ) = r p ， ，l 、 r a n ki i 2 r k ， 2 3约束加权投影矩阵的扰动上界 ( 2 1 7 ) ( 2 1 8 ) 本节讨论| l ( 谚 露声) 谚 ( ，一k ( w k p ) t w ) 1 1 2 的稳定性和扰动上界内容取自【2 5 】， 略有改动 定理2 7 仍亩定理2 j 定义，设 其中 成立当且仅当 厶三= 工+ l c m t n ，k ，霞= k + a k c m 。x n ， a = ( 三) , 4 = a + a a - - - - ( 主) 时”， r a n k ( l ) = a u k ( l ) 2a a u k ( a ) = a n k ( 勾。 ( 2 1 9 1 i i a a i l 2 见，i i a k i l 2 + i i a l i l 2 i i l l k i l 2 p 1 s u p0 ( 命露声) 茆 ( j k ( w ；k p ) t w ) 1 1 2 + o o k p 的任意静一p 行线性无关， 喀2 0 、 2 3i i i i l i i 权投影矩阵的扰动上界 1 2 当条件成立时，对于任意满足( 2 1 9 ) 式的扰动矩阵五，有 三毒rain嚣+iiakil2+iia亳l警ihlil+ihlik12，、， 仁2 1 ， e 4 = ( 1 + 6 ) ”( 1 ，。 即刊- 1 一 1 - ( 1 卅1 - - i i , x k i l 2 + i i n l ，。1 2 i - c t l l 2 1 1 k i l 2 ) 4 ) 其中r m 2 = m i n r p ，m , 2 一r + p 定理2 8 设= u d u t 伤，其中兄由定理2 绞i 义， l ，= l + a l c = 1 x n ，k ，霞= k + a k c , n 2 x n ， a = ( 三) ，互= a + a = ( 妻) c “n ， 其中 r a = k ( l ) = r 瓤1 k ( l ) = p ， r 砌( a ) = r 缸出( a ) = r ，( 2 2 2 、 i i a a i l 2 砌，l i 9 1 1 2 + l i a l i l 2 1 1 l t l l 20 k 0 2 p 1 嘲 s u pi i ( 詹声) ( ，一k ( w k p ) t w ) 1 1 2 + o o w n 当且仅当对于任一u 阮和r 维指标句勤= i l ，露) c 1 ，m ) ，其和l 4 ， r a n k ( 鳄) = r p 臆畲r a n k ( 蜉j r 尸) = r b( 2 2 3 ) 当条件或立时对于任意满足( 2 2 2 ) 式的扰动矩阵a ，有 三赢1(+莓iiakih+iialihliltlhlki+12、扛。， 亿z 4 ， e e i n ( 。 ，砷一_ l ， p 一7 - 一( 一心哕警龇) 4 ) 2 4 约束加权最小二乘问题的稳定性扰动 1 3 2 4 约束加权最小二乘问题的稳定性扰动 本节推导w l s e 问题的扰动界，内容取自【2 2 】和【2 5 】 l ，z = l + a l c m l n ，k ，霞= k + a k c = 2 n ， a = ( 三) ，互= a + a = ( 主) c 4 x n ，w ，葡= w + w 现， k 元c 4 l ，g ，官c 4 2 ，b = ( ：) ，g = ( 喜) 给定，并且 r ( l ) ， 诎( l ) = 。a n k ( 工) 2p ，a n k ( a ) = a n l 【( a ) = ， ( 2 2 5 ) k p 的任恿f p 行线性无关， i i w 一1 a w i l 2 6 1 ，i i a a i l 2 见，l i a k i l 2 + i v l i l 2 i i l + 1 1 2 i l g l l 2 p 1 对于原始的和扰动的w l s e 闯题 ( k x - g ) l l 铲，m c n i n 孵( k 一g ) 1 1 2 1 掣t u 。 ，99 r 、 彬( k z 一祧2 倒m m 。i i 一跳 蚴) 掣e u “，o0 7 、 满足慨一矶= 躲慨一砒 、。 已, a x w l s e = 雹w l s e x w l s e 则 ， 其中 一曲“枷。r 叠= p 1 ：础i i 掣i i 眨。8 ， 。1 j e t = 曲 ( 1 + 俨( 1 + 必警) 2 一- 1 ， 临七印 l _ ( 1 棚。1 - 必业掣) 4 l ， f m 2 = m i n r p ，r n 2 一r + p ) ，“= ( ，一k p ( k p ) t ) ( g k l t h ) 2 4 约束加权最小二乘问题的稳定性扰动 1 4 若r n ，剐对于w l s e 问题( 2 2 6 ) 的任意w l s e 解 z = a 0 6 + ( j a t a ) z ， 存在( 2 2 式的w l s e 解瓮，使得 0 窑一z i l 2 历= 幡1 百晤 0 6 1 1 2 + v 厄i i a a h 2 1 1 x h 2 定理2 1 0 设 + 2 ( 烂必警业+ e 4 ) i ：) l ，= l + a l c m l n ，k ，霞= k + k c m 2 n ， a = ( k l ) ，五= a + a = ( 妻) c “n ， k 左c 4 i ，g ，官c “2 ，b = ( ：) ，g = ( 喜) ， w = u d e ，t 7 ，2 给定，且 r ( l ) ， r a n l 【( ) 一r a n k ( l ) = p ，r a n l 【( 两= r a n k ( a ) = r ， r m l k ( 叮) = r p 臆含r a n k ( u a f k p ) = r p ， i i & a i l 2 p 2 ，i i 9 1 1 2 + l i l i 口吲i k i l 2 p 1 粼对于w l s e 闯题( 2 2 6 ) 和( 2 e 1 ) 的极小范数解z w l s e 寿跪w l s b 有 ( 2 2 9 ) ( 2 3 0 ) ( 2 3 1 ) i a x w l s e i l 2 瓦= 丽1 ：可i i l l a b l t 2 + ( 1 + 6 m 0 a n 2 u z l s e 0 2 ) ) 2 ( 世必掣业+ e 6 ) i i r k i l 2 ， e 6 ：曲f ( 1 + 函挫严) 2 p 刊j 1 ，。 3 2 l 一( 1 一必挫掣) 孵刊 ， 其中“= ( i k p ( k p ) t ) ( g k l * h ) 若r 0 记 k = ( ：) ，小即一 a=(三：三，c；=(：)，=，南，ca=。， ( 3 1 ) 0 兰堕w j 1 ，2 j 南，e = 燃，) l 昂= 厶，b = i q 0 ，r a n k ( 0 ) = 巧，j = 1 ，七 引理3 1 似o ) 在假a s j 的条件和记号对于j = 1 ，七，记( 如b 一1 ) 日的酉分解 为( 如易一- ) 日= 劬而，其中q 罗q j = 岛一r ，- ”弓行满秩，并记q = l ，q 2 ，饥) 则 有 ( 如弓一- ) 如b 一- 2c ! 白一q 一q 扎 ( 3 3 ) m k ( 4 ，易一1 ) = r a n k ( c ) 一r 锄k ( c j 一1 ) = q 一巧一1 j ( q ，q j ) 日( q ，劬) = 毛，q c = q z q 尹， ( 3 4 ) 1 = 1 如易一- = 如q q 尹，( 如弓一1 ) = 劬( 岛岛) ( 3 5 ) 证明当j = 1 时，( 3 3 ) 式显然成立对于2 歹七，可证四岛= c 1 1 g l + ( 如弓一- ) 如弓一- ( 【1 9 】) 又因为c i 。g 一- 和( 如弓一1 ) t 如弓一l = 弓一( 如弓一t ) 如弓一- 的 值域相互正交，所以( 3 3 ) 式成立 3 1p w a ，a 0 的等价表示 1 7 对于( 3 4 ) 一( 3 5 ) 式，可用数学归纳法当j = 1 时，( 3 4 ) 一( 3 5 ) 式显然成立假设 当1 j t 七时，( 3 4 ) 一( 3 5 ) 式也成立则对于j = t + 1 ，由( 3 3 ) 式和仇+ l 的定义可 知( q 1 ，q 件1 ) 片q t + l = 0 ，于是有 t + l ( q - ，q 件) 日( q 1 ，q 蚪t ) = 。，c i - c l + l = q l q 尹， l = l a t + l q 件1 q 嚣l = a t + l ( c j c ；+ 只) q t + l q 算l = a t + 1 只q 件1 q 并l = a 蚪1 只， 即当j = t + 1 时，( 3 4 ) 一( 3 5 ) 式也成立 口 要研究w l s e 问题在什么样的条件下的扰动稳定，关键看约束加权投影矩阵和约束 加权m p 逆什么时候扰动稳定 引理3 2 在假定，1 和亨理只j 的条件及和记号- f , 矩阵尸饥和a w 叉可表示为 聊 = 最碰，a w = 晟磁a ， ( 3 6 ) 其中 反= a 1 q 1 000 0 a 2 q 2 00 0 e a 2 a 3 q 2a 3 q 3 0 0 e 地a k q 2e k s a q a a k q k 满足r a n k ( b ) = “= r a n k ( a ) ( 3 7 ) 3 1p w a ，a 0 的等价表示 w kp 1 w 2 a 2 ( i q 1 q w k a k ( i q l q r) = ( 饥a 。q ：i ：二q 。q 譬，) 0 l l o i 形一- 娟日 ； 1 w k a q k 、豆= ( 二a ! 二2 q ：三21。三0。)；a三。 只蹦 a 1 a i 0 k ( a - q 1 q r a i o a 1 q 1 0 0 w 尸1 ) o 、l 百t 敏) ，a 1 q 1 i f 0 且r a n 】【( 展) = r a n k ( a 1 q 1 ) + r 缸k ( 反) = 又 一 a w = a a o a = a w a o a = p w a = 及碰a 1 8 日-qq ，：i 如 = 岛h lq lq r l= r l3 理弓由明证 尸 仉 仉形 。如；屯 毗 度 2 2 2 = q q q ，舰箩：们朔 耽撕 饥 ，& 醴 反 i 、 ) o 豆0 一陵 ，、，一，一 3 2p w a 与a 0 的扰动 1 9 3 2 ，所a - 与a t w 的扰动 口 本章讨论关于约束加权投影矩阵r 憎兰a a 0 和约束加权m p 逆a ：l ，扰动稳定的条 件在假定3 1 的条件和记号下，对于j = 1 ，k ，令 鑫j = a j + a 1 岛= j 一四岛， 分别为如，岛，b ，w j 的扰动项，设 q 2 q + g ， ( 3 8 ) 面i = 1 j + 叫j ， 岛三茜，2 sk , 1 1 - - - - ：一m a x 垫昱，且 2 。m 鲋a x 岍t j ) 1 ( 3 9 ) 首先给出关于励 和a 0 扰动稳定的定义 定义3 1 如果当7 0 ，一o ( 2 j i 后) ，如一0 ( 3 = 1 ：忌) 时，p 互jp w a ，就 称扰动的刚性加权投影矩阵f ， 五是稳定的类似地，当叩一0 ，一0 ( 2 j l i 冬臻| | 2 = i i ( 盈，。) i | 2 = 。， ( 3 - 1 0 ) o 砖i i 。圳砖翩i l ：= i i t 1 1 2 根据【9 ，2 9 的论述，如果当a l 一0 时，删出( 五) r a n k ( a 1 ) ，则0 盈1 1 2 一+ o o ，进 而。鹆0 2 一+ 类似地，如果当a 一0 时，r a n l 【( 勾r a n k ( a ) ，贝 j i i x 1 1 2 一+ ，迸 3 2p w a 与a 0 的扰动 2 0 而o a 0 2 一+ o o 无论是哪种情况，均有。岛- a * w i l 2 i i a 品1 2 一i i a 0 i 1 2 一+ o o ，即关 于a 0 的扰动岛不稳定 类似地，由 1 i i p 命x p w 1 1 2 l l 五盈一a z a i i l 2 ， 若r a n l 【( 五) r a a l k ( a 1 ) 或r a n l 【( 勾r a n k ( a ) ，有0 尸l i p w 1 1 2 = 1 ，即关于户协 的 扰动p 五不稳定 口 下面讨论j ) j 和岛稳定的充要条件 定理3 4 设a ，是给定的矩阵j 满足假定只j 中的条件和记号，五谚是相应的扰动矩 阵，8 ；满是 r a n k c a a 一、= r a n k ( 。) 2r j ，j = 1 ，2 ，七，或等价地 ( 3 1 1 ) r a n k