（计算数学专业论文）线性方程组和线性最小二乘问题条件数的若干结果.pdf

摘要 近年来线性方程组的扰动分析已成为当今科学与工程计算中的热点问题之 一最近几年，一批研究工作者在非奇异线性方程组和线性最小二乘问题的条件数 方面做了大量的工作，并取得了显著的进展由于带k r o n e c k e r 积和带多右端项的 线性方程组在很多领域得到了广泛的应用，因此本文对这类方程组的条件数进行 了研究： 在第一章中我们简单回顾了线性方程组问题的研究背景和数值求解方法，并 介绍了条件数问题的来源 在第二章中我们对两类非奇异线性方程组a x = b 和( a 固b ) x = c 进行了 扰动分析，并应用矩阵导数得到范数型，混合型和分量型这三种条件数及其上界 数值例子表明条件数的上界是紧的 在第三章中我们进步在列满秩情形下，对( a 圆b ) 的m o o r e - p e n r o s e 逆和 带k r o n e c k e r 积的线性最小二乘问题做了分析，同样得出了范数型，混合型和分量 型这三种条件数及其上界数值例子表明在某种程度下是有效的 关键词：分量型，条件数，k r o n e c k e r 积，线性最小二乘，混合型，m o o r e - p e n r o s e 逆，多右端项，范数型，扰动 中图法分类号：0 1 5 1 2 1 ：0 2 4 1 1 2 a b s t r a c t p e r t u r b a t i o na n a l y s i so fl i n e a rs y s t e m sa r eo fi n c r e a s i n gi m p o r t a n c ei ns c i e n t i f i c a n de n g i n e e r i n gc o m p u t i n g c o n s i d e r a b l ew o r ka n dp r o g r e s sh a v eb e e nm a d eo v e r t h ep a s td e c a d e so nn o n s i n g u l a rl i n e a rs y s t e m sa n dl i n e a rl e a s ts q u a r e sp r o b l e m s s i n c et h el i n e a rs y s t e m si n v o l v i n gk r o n e c k e rp r o d u c ta n dm u l t i p l er i g h t h a n d sa r e w i d e l ya p p l i e di nm a n ya r e a s ，w es h a l li n v e s t i g a t et h ec o n d i t i o nn u m b e r sf o rt h e s e l i n e a rs y s t e m s ： i nc h a p t e r1w eb r i e f l yr e v i e wt h eb a c k g r o u n do fl i n e a rs y s t e m sa n dn u m e r i c a l a l g o r i t h m sf o rs o l v i n gt h e m w ea l s oi n t r o d u c et h es o u r c eo fc o n d i t i o nn u m b e r s i nc h a p t e r2w em a k ep e r t u r b a t i o na n a l y s i sf o rt h et w ok i n d so fn o n s i n g u l a r s y s t e m sa x = ba n d ( a o b ) x = c ，a n dd e r i v en o r m w i s e ，m i x e da n dc o m p o n e n - t w i s ec o n d i t i o nn u m b e r sa n dt h e i ru p p e rb o u n d sr e s p e c t i v e l y n u m e r i c a le x a m p l e s s u g g e s tt h es h a r p n e s so ft h e s eu p p e rb o u n d s i nc h a p t e r3w ef u r t h e ra n a l y z et h em o o r e p e n r o s ei n v e r s eo f ( ap b ) a n dt h e l i n e a rl e a s ts q u a r e sp r o b l e m si n v o l v i n gk r o n e c k e rp r o d u c t ，t h e no b t a i nn o r m w i s e m i x e da n dc o m p o n e n t w i s ec o n d i t i o nn u m b e r s a n dt h eu p p e rb o u n d ss i m i l a r l y n u - m e r i c a le x a m p l e ss h o wt h ee f f e c t i v e n e s st os o m ee x t e n t k e yw o r d s ：c o m p o n e n t w i s e ，c o n d i t i o nn u m b e r s ，k r o n e c k e rp r o d u c t ，l i n e a r l e a s ts q u a r e s ，m i x e d ，m o o r e - p e n r o s ei n v e r s e ，m u l t i p l er i g h t - h a n d s ，n o r m w i s e ，p e r - t u r b a t i o n c h i n e s el i b r a r yc l a s s i f i c a t i o n ：0 1 5 1 2 1 ；0 2 4 1 1 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名 斟 论文使用授权声明 f 期 d 6 、f j o 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名阿期 06 。生。知 第一章研究背景 在大量的科学与工程计算中，如计算流体力学、统计学、量子物理，化学工 程、经济模型、气象预报、图象处理、自动化控制、信号处理和控制等众多领域中， 经常要数值求解大规模线性方程组在波散射问题，如积分方程的数值计算方法， 最小二乘问题的递归计算和图像恢复 2 6 】中，我们要求解这样的方程 a ( o x ( i ) = b 0 ) ，i = l ，2 ，p ( 1 1 ) 其中a 。是n n 非奇异矩阵在高阶隐式方法求解p d e 问题 5 1 、控制论【7 】以 及结构力学 4 6 】中， a ( ) = a 一吼， 6 ( ) = b 在结构力学、控制论和电磁场多方向入射点的散射计算f 4 8 1 中， a ( 。) = a 此时方程化为多右端线性方程组 a x = b 兰【6 ( 1 ，6 ( 2 ) ，删】( 1 2 ) 对于这一类问题我们不需要逐个求( 1 1 ) 的p 个线性方程组现在已有很多好的 算法对多右端问题( 1 2 ) ，目前主要有两大类方法：块迭代方法和种子投影方法 前者始于1 9 8 0 年的o l e a f y 的块c g 方法，之后有块g m r e s 方法及其变形，块 q m r 方法，以及块e n 方法等种子投影算法是由s m i t h 等提出的，当方程组右 端在某种程度上比较接近时，此类方法有效 2 1 1 还有类似的问题，比如 f 4 0 b ) x = c 此外，还有列满秩下线性最小二乘问题 r a i n i i a z 一酬2 ， z e t “ 和 r a i n l i ( a b ) x 一6 h 2 r “ 对这些方程组的求解方法已成为国际上计算数学和科学与工程计算研究领域 中的重大课题之一对于这些问题相继提出了各种数值算法，而对其扰动分析则较 少 第一章研究背景 2 数值求解这些问题，我们得到的计算解是一个与原问题接近的问题的准 确解，向后误差可以衡量这种接近程度向后误差分析的思想在n e u m a n n 和 g o l d s t i n e1 9 4 7 年的文章中已出现f 37 1 首先明确提出向后误差分析的是g i v e n s f 1 4 ，w i l k i s o n 也作了许多开创性工作与向后误差分析相关一个概念是条件数 它可以用来反映问题对扰动的敏感程度第一个使用条件数这一概念的是t u r i n g 【5 2 】向后误差的大小反映算法的好坏，条件数则反映问题本身的性质 矩阵扰动分析一直以来是数值计算研究中一个热点问题，而关于条件数的研 究又是矩阵扰动分析的一个重要内容r i c e 在1 9 6 6 年【4 0 】给出了条件数的一般性 理论他给出了有限维欧氏空间上连续且p r 6 c h e t 可微算子的相对范数型条件数 但是这种条件数有一个缺陷就是没有考虑到数据的规模和稀疏性s k e e l 在 4 7 】 对非奇异线性方程组和高斯消去做了分量扰动分析，得出了相应的条件数之后 r o t m 在f 4 1 1 又定义了一种新的基于分量扰动的条件数g o h b e r g 和k o l t r a c h t 在 1 6 中给s k e e l 条件数和r o h n 条件数分别命名为混合型和分量型条件数，并给出 了非奇异线性方程组的这两种条件数的表达式 第二章带多右端项的一般线性方程组和k r o n e c k e r 积线 性方程组的条件数 2 1 引言 在考虑线性系统 a x = b ( 2 1 ) 时，我们需要向后误差和条件数这两个概念计算结果往往不能准确满足方程，计 算解是一个与原问题接近的方程的准确解向后误差表明了我们实际解决的问题 与原问题的接近程度条件数表示了对于数据a 和b 的小扰动解的敏感性条件数 与向后误差的乘积给出了计算解误差的一阶卜界为了使这些概念精确，我们必 须具体化扰动的种类和它们的度量数据扰动可以是范数型扰动也可以是分量型 扰动 首先范数型条件数定义为 2 3 酬舢) ：= 脚s u p 躺：( a + 酬( 外酬= 6 + 6 l i a a i l e i i e i i ，i l 圳e j 舰朋卅：= 皆刊， 这里”i l 表示任何向量范数和它相应的诱导范数，而矩阵e 和向量f 是任意的 若取e = a 和，= b ，我们有k ( a ) 尤e ，( a ，。) 2 a ( a ) ，这里托( a ) = l i a i i i i a - 1 m 分量型条件数定义为【2 3 】 c o n d e , ( 缸) ：= 觊s u p 糕：( a + l x a ) ( z + 叫6 + 6 ， i a i e e ，i , b e ，) ， 其结果是 c 。n d e ，( a ，z ) = 卫生! ：1 铲 这个条件数依赖于z 或等价地依赖于右端项b 一个对所有z 的最差敏感性度量为 c o n d e ，a a ) = m a xc o n d e ，( a ，z ) 3 第二章带多右端项的一般线性方程组和k r o n e c k e r 积线性方程组的条件数 4 对于特殊情况e = i a i 和，= l br ，我们有由s k e e l 4 7 引进的条件数 c 。n d ( a ，z ) ：；旦i ! ! - ：； i 兰业， c o n d ( a ) ：一c o n d ( a ，e ) = l ii a ii a ii i 。， 其中e = 【1 ，1 ，1 】r ，且有适当的维数注意这里采用的是h i g h a m 【2 4 1 中的记 号，在g o h b e r g 1 6 等的文章中，c o n d ( a ，z ) 被称为混合型条件数 除此以外，由r o h n 引进的分量型条件数 4 1 】为 c ( 州：一m a x l i m 。s u p 割：( a + a a + 叫_ 6 + 6 ， l a i e a i ，i 6 i e 例 ；m 觚丝幽掣土芝幽! i i z l ， ( 2 。1 ) 的特殊情况是带k r o n e c k e r 积的非奇异线性系统 3 2 】 ( a 圆b ) x = d ， 【2 2 ) 这里a r ”，b r “m 和。，d r m 由于a 和b 非奇异，所以存在一个唯 一解z = ( aob ) d 在 5 8 作者分析了范数型和分量型扰动界在那里( 2 2 ) 的 范数型条件数被定义为 镌叫a 。即) ：= 脚s u p 丽i v z i i _ ( a + 酬。( b + a b ) + 缸) = d + d ， i f ar l 刮e f l 川b i i e f l f mi i z l d l l 刮川) ( 2 2 ) 的分量型条件数被定义为 c 。n 电只，( a o b , x ) ：= 翱s u p 矬 ( a + a ) 。( b + a b 训( 卅删 一d + d ，m l 以f b t e f i a d l e ，) 这里i l 表示分量的绝对值，还有另外一种条件数被定义为 “a 圆b ，d ) ：= m i a x 。l i r a 。s u p 坦i 三产：( a + 以) 。( 日+ b ) = d + d i v a i e i a i ，i b e i b i ，i z l d l i d i ) 下面在 5 s 的结果给出了这些条件数的卜界 ，c e ，只，( a 。b ，z ) 旦垒铲+ i i a 。1 i i i f e i i + 1 1 b 1 i i i i f i i ， c 。n d e ，只，( a 。b ，z ) 韭盟丝二1 1 _ 兰i 二1 2 ! = 量 注景! 垒l 望：! ：2 i 型j 业， 第二章带多右端项的一般线性方程组和k r o n e c k e r 积线性方程组的条件数 5 。( a 。b ，d ) m 肛盥芝幽坦崆半掣业坐丑必( 2 3 ) 1 1 z i ； 这一章我们要考虑多右端的情形相应地，线性方程组( 2 。1 ) 变为形式为a x = b ，( 2 2 ) 变成( a0b ) x = c 的形式带多右端项的一般线性系统出现在很多应 用领域诸如用拟牛顿法解有多个割线方程的非线性方程组问题 9 ，2 2 ，常微分方 程反问题 2 】，波散射问题 4 8 】，结构力学问题关于线性方程组a y = b 的算法已 经有很多，例如，块c g 3 9 】，种子投影方法 4 8 ，5 】，块g m r e s ，混合块g m r e s 【4 5 】，块q m r 1 2 】，块e n 2 0 ，在这一章中我们将重点导出描述这样的带多右端 项的线性系统4 4 1 的条件数，刻画其扰动敏感性 在讨论之前我们需要一些k r o n e c k e r 积的性质 在下面的内容中，我们将要用到k r o n e c k e r 积的一些性质对a 舻“和 b r p 。口，a 圆b r 即”q 的k r o n e c k e r 积f 1 8 定义为： aob = ( 1 l i ba 1 2 b n l n b 0 2 1 ba 2 2 b 0 2 n b o 仇1 bn m 2 b o t ，l n b 以下结果可以在 1 8 ，4 3 ，2 5 ，3 2 ，3 5 ，5 3 j 找到 ( a + b ) o ( c + d ) ( a 固b ) t ( a o b ) i f a o b f l l a 引 ( 4 0 c ) ( b 固d ) r a n k ( a o b ) v e c ( a x b ) v e c ( a 固b 1 a 0b ；a o c + b o c + a o d + b o d ， = 矿圆b t ， = a t0 b t ， = l i a t 圳， = l a l o i b i ， = ( a b ) o ( c d ) ， = r a n k ( a ) r a n k ( b ) = ( b roa ) v e c ( x ) ， = ( 厶o 。 厶) ( v e c ( a ) o v e c ( s ) ) ， = v e c ( b a r ) ， ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) 这里定义、雠( a ) = 【0 1 1 ，a r a la 1 2 ，2 ，d l n ，an ni t , 而玩。 是交换矩阵，它可以具体表示为 m 协已 0 曲 m 。岸 。：l i i n 第二章带多右端项的一般线性方程组和k r o n e c k e r 积线性方程组的条件数 6 这里( m n ) = e ”( 妒) r 驴。“表示( ，j ) 初等矩阵，而0 “是m m 单位阵第i 个列向量下列交换矩阵的性质也可以在 1 8 ，4 3 】中找到对于 c 酞m 。”，z 酞m 和分 厩。v e c ( c ) 。( e 0 y ) 。b o e ) 碟。 = v e c ( c r l =yo c = c o y = 风。 ( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) ( 2 1 7 ) 本章的结构如下：在2 2 中，我们对带多右端项的一般线性系统的条件数进行分 析在2 3 中，我们考察带多右端项的k r o n e c k e r 积线性系统在2 4 ，我们给出 一些数值例子最后在2 5 将给山对将来此问题研究的评述 2 2 带多右端项的一般线性系统的条件数 条件数的一般理论可以在f 4 0 】找到，设：r “+ r “为一个映射，其中p 和p 是通常的m 和n 维赋范e u c l i d e a n 空间如果是连续的且在o o 孵“的 某个邻域中f r 6 c h e t 可微，则根据4 0 ，a o 的范数型条件数为 删(计=lim酬supl。业铲,而iialliii i l a o i i e o d 0 0 使得 b ( a ，e ) = z p | z a l i e ) ，f 在a 处的范数型条件数可以定义为 们垆弛。s u 。p 。，背揣， 如果f 在a 处f r 6 c h e t 可微，那么 们) = 掣( z l s ) ( b ) 如( a ) 所述，设b o ( o ，e ) = z ：b a i l 0 则a 的m o o r e - p e n r o s e 逆可以表示为 肚y ( 钏旷 z ， 设u = 阻1 ，】，v = 口1 ，】，则r ( a ) = s p a n v 1 ，诈) ，n ( a t ) = s p a n u r + l ，) ，其中s p a n v 1 ，坼 = “r n u = 啦地，啦r ) 在这 些记号下a2i = 1 以谚，2 至击仇醇m 。0 r e p e n r 。s e 逆的另一个重要性质是 a a t 和k a a t 分别是r “到r ( a ) 和n ( a t ) 的正交投影如果r a n k ( a ) = n ，则 a * a = 厶， a t a t 丁；( a r a ) 一1 ，a = ( a 了a ) 一1 a r 为了定义混合型和分量型的条件数，以下形式的”距离”会用到对任意点 。，b 彤，我们首先定义2 = ( e l ，c 2 ，) 了1 为 f 啦巩i f 坟0 ， 白。10 i f 吼。兢= 0 ， 【o o 其它 第三章带k r o n e c k e r 积的m o o r e p e n r o s e 逆和最小二乘问题的条件数 1 6 然后我们定义 如加j | 字器 帮) 如果d ( a ，b ) o o ，记 d ( a ，b ) = r a i n 0 i | a i 一良i i 玩i ，对i = 1 ，仃) 在本章其余的部分，我们仅考虑实数对( o ，b ) 且d ( a ，b ) o 。之后我们把这样的 距离函数d 推广到矩阵情形对任意矩阵a r , n 一，我们定义v e c ( a ) 酞_ 为 v e c ( a ) = 【订，d 羽丁，其中a = 【a ，】，对i 一1 ，仃，啦r , a 我们定 义 d ( a ，b ) = d ( v e c ( a ) ，v e c ( b ) ) 并定义0 aj | 2 m 。= i ：j l ，对任意a r ”“，我们有 l i v e c c a ) l 。= i l a i f 。 本章的结构如下：在3 2 ，我们研究aob 的m o o r e - p e n r o s e 逆的条件数在 3 3 ，我们将得出带k r o n e c k e r 积的线性最小二乘问题解的条件数在3 4 ，我们 会给出一些数值比较最后在5 3 5 ，我们对将来的研究工作做出一些评述 3 2k r o n e c k e r 积aob 的m o o r e - p e n r o s e 逆的条件数 我们重新定义映射圣：肼“。“一舻。”为垂( a ) = a t v = 舀r b = v e c ( g ) ，g r ”“) 同样我们定义：v r 一为( v e c ( g ) ) = v e c ( 圣( g ) ) 从 4 ，4 9 ，5 4 j ，我们知道矩阵a 扰动后变为b = a + a a ，其中a a r “，如 果r a n k ( b ) 增加，将会导致m o o r e - p e n r o s e 逆不连续保秩扰动可以保证m o o r e - p e n r o s e 逆的连续性在我们导出条件数的表达式以前我们将给出以下重要的引 理 引理3 2 1 【4 ，4 9 ，5 4 】设a r “， a ) 是一个m n 矩阵序列如果 a a ，则a l 一的充分必要条件是对于充分大的有r a n k ( a ) = r a n k ( a ) 引理3 2 2 【4 3 】设a r “，则a t 是它的m o o r e 。p e n r o s e 逆设s 是r m “ 的一个子集如果r a n k ( a 1 在s 上是常数，那么 ( a + a a ) t a t = 一a t ( a a ) a t + a a t 7 ( a 丁) ( k a a t ) + ( i n a t a ) ( a a r ) a t 7 a t 第三章 带k r o n e c k e r 积的m o o r e p e n r o s e 逆和最小二乘问题的条件数1 7 如果r a n k ( a ) = 仃，那么a t a = 厶，a t a t 。= ( a t a ) ，并且我们有 d a = 一a t ( d a ) a t + a a t r ( d a t ) ( i , n a a t ) ( 3 3 ) 如果我们在( 3 3 ) 的两边取v e c ，那么我们得到 d ( v e c ( a ) ) = 一( a t 7 圆a t ) + ( ( k a a t ) p ( a t a ) 一1 ) ) d v e c ( a ) ( 3 4 ) 设= v e c ( a ) ，从上面的式子我们容易得到映射西在a 处连续且f r 6 c h e t 可 微除此以外它还有矩阵表达式 ( n ) = 【一( a p 圆a t ) + ( ( k a a ) 圆( a t a ) 一1 ) 。】 【8 的主要结果是下面的定理它给出了m o o r e - p e n r o s e 逆的条件数的具体表 达式下面的推论也给出了这些条件数容易计算的上界 定理3 2 3 【8 j 设a r t “，m n k ( a ) = n ，我们有 m t ( q = 世型巡气篱箍业螂， m ) = | | 唑生趾等筹盟绁螋| | m 推论3 2 4 f 8 】在定理3 2 3 的假设下，我们有 m t ( 佻嵝业坳锱半啦， m ) j f 蛐幽业竽型卜 在这一节中，我们把【8 】中的结果推广到k r o n e c k e r 积矩阵设a 职一n ， b 础。口且两者均列满秩我们分别定义k r o n e c k e r 积的m o o r e - p e n r o s e 逆的范 数型，混合型和分量型条件数 ( a 固b ) ：= 。h 。m 。西苫挲高i 两址垦生! 兰垒l 鱼 呆舌；等芒迎， et 撕 曙；面u ； m t ( a 。b ) 。刚t i m s u p 。坠幽等群咎堕鳖， c t ( a 。b ) ：= l i m 叭s u p 一到进坐糍筹坐业k 这里鲁是分量相除且定义为鲁：= ( 鲁) ，或在m a t l a b 里的符号b a 在我们给出以上三种条件数的具体表达式之前，以下的引理将会给出 第三章带k r o n e c k e r 积的m o o r e - p e n r o s e 逆和最r j 、- - 乘问题的条件数 1 8 引理3 2 5 设映射皿：聊。4x 蟛。4 一磷；“”定义为皿( a ，b ) = ( ao b ) ，妒：r ”mxr p 叮hr m 叩g 为妒( ，b ) = v e c ( 皿( a ，日) ) = v e c ( ( a o b ) ) ，其中 a ，b 列满秩，且a = v e c ( a ) ，b = v e c ( b ) 则妒在任意( a , b ) 处连续且f r 6 c h e t 可 微它有矩阵表达式 妒协，b ) = q b m ae n s 】 其中 “= 一( a t 7 0 a + ) + ( 厶；一a a t ) 固( a t a ) 一1 k 。；，j 气= ( o j 矗o ) ( v e c ( a ) p 岛) b = 一( b t 7 0 b + ) + ( 易一b b + ) o ( b 丁b ) 一1 q ，q b = ( 厶。o 靠o ) ( 厶。o v e c ( b + ) ) 证明由引理3 2 2 ，妒的连续性显然我们取a 固b 的微分 4 3 】 d ( a b ) + = d a + o b + + a + d b t 取v e c 并用( 2 1 2 ) ，我们有 d v e c ( ( a o b ) ) = v e c ( d a t 固b t ) + v e c ( a t o d b t ) = ( kok 品 ) ( v e c ( d a ) ov e c ( b ) ) + ( 厶圆k 品圆) ( v e c ( a ) ov e c ( d b + ) ) = ( ko 品固) v e c ( v e c ( b + ) ( v e c ( d a ) ) r ) + v e c ( v e c ( d b ) ( v e c ( a ) ) t ) ) = o o ) ( 厶。圆v e c ( b ) ) v e c ( d a ) + ( v e c ( a + ) oi q p ) v e c ( d b + ) ) 由( 3 4 ) ， v e c ( d a ) = 批( ) = - ( a 7 圆a ) + ( ( k a a + ) 。( a t a ) 一1 ) ) 抵( a ) ， v e c ( d b + ) = d v e c ( b + ) = - ( b ，圆b + ) + ( ( 一b b + ) 。( b r b ) ) k 纠 d v e c ( b ) ， 由m a ，n 8 ，乃，q b 的定义，我们有 d ( v e c ( aob ) + ) = q b m ad v e c ( a ) + 只d v e c ( b ) = 【q b “r 】 d o 丁，d 6 r 】r ， 则f r 6 c h e t 导数为妒7 ( 口，6 ) = q b m a 尸a b 】 这一节的重要结果是下面的定理它给出了条件数的具体表达式 口 第三章带k r o n e c k e r 积的m o o r e p e n r o s e 逆和最小二乘问题的条件数 1 9 定理3 2 6 设a 聊”，b 嘟”，在以上的记号下我们有 川a 。b ) = 鳖型揣蝴竽盟， s ) m t ( a 圆b ) = 峻坠器辫锍掣丛 ( 3 。) 假设a t ，b t 中没有零元素，则 c t ( a b ，= f 业警端器产业 陋， 证明由引理2 2 1 ，我们得到k r o n e c k e r 积apb 的m o o r e - p e n r o s e 逆的范 数型条件数 川a 。b ) = 业警 ：峻星些鱼坐些迹亚丑哑 i i v e c ( ( aob ) t ) 1 1 2 一i q b m a p a n b i i 。 l a | | 刍+ i l bj 刍 1 i ( aob ) t l i f ：! 【叟! 生丝鱼丝删! 复l ! 垒! ! ! ! 皇! l i a ) i i f i l b 圳f 。 从引理2 2 1 ，我们有混合型条件数 m t ( a o b ) = 业! ! ：竺望! ：创塑 i 妒( 口，b ) l l 。 ：崆：竺竺竺! 兰墨到箜 ：吐兰：竺2 竺! ! 墨 出笪 竺型燮世 i i v e c l l 凶口j 。川o o ：山望星! 垒翌! ! ! 生i2 ! 鱼丝! ! 竺! ! 里1 2 l ! 竺 第三童带k r o n e c k e r 积的m o o r e - p e n r o s e 逆和最, j 、- - 乘问题的条件数 2 0 分量型条件数为 c t ( a 。b ) = jj d 州- 1 ) 坝。，b ) d 。，a 忆 = l l 。赢。d q s r ， o 乏川。 = 。淼脑酬归b 地r ， ? 三 。 旧b 地酬l v e c ( a i ) v e c ( ( aob ) t ) ；i l ! 叟星些! 兰! ( ! 丝l2 l 垦丝! 兰! ! ! 里垃i f i |v e c ( a t o b t )k 其中e 是有适当维数且元素全为1 的向量 口 定理3 2 6 给出了条件数一( a o b ) ，m ( a o b ) 和d ( a o b ) 的具体表达式 虽然这些表达式是准确的，但它们可能不易计算以下推论给出了这些条件数的可 计算上界 推论3 2 7 在定理3 2 6 的假设下，我们有 ( a b ) ( a 。b ) u p p e r ：= ! 堑写 鲁酽， m 。b ) m ( 以。bu p p e r ：2 币珂：= 7 孤+ 砸0 ， c t ( a 。b ) c ( a 。b ) u p p e r ：= fj 磊五i = j | 。， 其中 n = m a x ( 1 l v e e ( b ) “忆i i v e e ( a ) 洲l ， p = i i v e c ( a t ) l l 。l i i l 。+ | i v e c ( b t ) l l 。i i m a i i 。， ，y = i | b + i l 。i i i a + i i a i i a i + i ( a 7 a ) 一1 l i a r i i k a a + 川。， 口= f l a + i l m 馘b + i i b i i b + l + i ( b 了b ) 一1 i i b t i i 一b b 川m 麒， 矽= i 厶。ov e c ( b ) i v e c ( i a + i i a i l a f + i ( a t a ) 一1 i i a t l i 厶一a a f ) 才= i v e c ( a ) o i v e e ( i b t l l b l l b + i + i ( b t b ) 一1 l i b r l i 一b b i ) 第三章带k r o n e e k e r 积的m o o r e p e n r o s e 逆和最小二乘问题的条件数 2 l 证明首先我们有以下估计， i l 旧口 “p 圳； i q s m ar 】| 1 1 | 旧b 地r b m a x l l q b m a 。，j | r b i l 。 ( i q b m a i 。+ i f r i | 。) s m a x j q b l 。i i m a l l ，i i 尸a | | 。i i 音n ( i i q b i i 。i i m a l l 。+ i i p 4 i l 。l i v 音j i 。) 由于交换矩阵的每一行和每一列除了一个元素1 以外都是零元 素，i i k 品1 1 1 = j i j ( 品i f 。= 1 由( 2 ，7 ) ，我竹 有 i | q 口l 1 l i ko o i 厶。圆v e c ( b ) 1 1 1 = 1 v e c ( b ) 1 1 1 ， l i q b i i o 。1 1 k 品o q l l 。i i z 。圆v e c ( b ) 1 1 。= l i v e c ( b ) 1 1 。 同样地， i i r i i ，i i v e c ( a t ) 1 1 1 ，i i p ae i 。f i v e c ( a t ) l l 。 因此， i 旧b 心r 坭m a x l v e c ( b ) 1 1 - i i m a i i 。，i i v e c ( a ) 1 1 11 1 ) ( i l v e c ( a ) 1 。1 | b l | 。+ l i v e c ( b + ) 1 1 。i i m a i i 。) 用定理3 2 6 以及o t 和口的定义，我们得到 川，锌署 容易证明 l i i q s m a l v e c ( i a i ) l l 。i i q b i i 。i i i m a i v e c ( i a i ) i i 。 i l v e c ( b t ) l l o 。i i i a t 7 ioi a t 7 l + “k a a t oi ( a t a ) 一1 1 ) k 。 v e c ( i a i ) l l 。 = l l v e c ( b t ) l l 。i l v e e ( i a t l l a i i a t l ) + v e e ( 1 ( a 丁a ) 一1 i i a 丁i i k a a + f ) j | 。 = i i b | | 。a | i a i i a + i + i ( a r 以) 一1 i i a r | k a a 川。= ，y ， f i i p a n b i v e c ( i b i ) i i 。os i a + l i 。i i i b + i i b i i b + l + i ( b t b ) 一1 i b 丁i 厶一b b 川。= 0 由定理3 2 6 ，我们有 m t ( a b l 堕坠器糕瑞华 2 ! 一i i a i i 。i i b i i 。 第三章 带k r o n e c k e r 积的m o o r e p e n r o s e 逆和最小二乘问题的条件数 2 2 最后由( 2 8 ) ，我们有 同样地 q b m a i v e c ( i a i ) sl q a i i m a i v e c ( i a ) i kok ，固i i 厶。ov e e ( b t ) 1 a t 7 i 固i a t 7 i + “厶一4 a iol ( a t a ) 一1 i ) k m , , v e c ( i a i ) = l 厶o 0 | | kov e c ( b ) l v e c ( i a i i a i i a + i ( a t a ) 一1 i i a r l l 厶。一a a t i ) 1 r 日i v e c ( i b i ) l i 厶p k 矗oi q l l v e c ( a ) oo i v e c ( i b + e i b i i b l + l ( b t b ) 一1 l i b 丁1 1 # 一b b t l ) 由定理3 2 6 和( 2 1 2 ) ，以及7 和百的定义，我们得到 c c a 。b ，j i 坐立皇_ 蔓! 皇写裂丢吝甚毛；掣i l ：i i ! 生鱼丝翌望生2 ( 互望2 | | | | ( ，mok moi q ) ( v e c ( a t ) ov e c ( b t ) ) i 。 = j f 品 口 3 3 带k r o n e c k e r 积的线性最小二乘问题( k p l l s ) 的条件数 首先我们考虑线性最小二乘问题( l l s ) 【4 ，6 ，1 7 ，1 9 ，3 4 ，4 2 ，5 0 ，5 5 】 a 让一b 1 1 2 其中a r m “，b 酞”且r a n k ( a ) = n 则( 3 8 ) 存在唯一最小范数解z = a t b 设a a r ”“，a b 掰叫吏得( a + a ) = 付，考虑以下问题 ( 3 8 ) m i ni i ( a + a a ) w 一( b + x b ) 1 1 2 ( 3 9 ) e r n 类似地存在唯一最小范数解y 令a x ：= y z 并且我们有 a z = ( a + a a ) + ( 6 + a b ) 一。 第三章 带k r o n e c k e r 积的m o o r e - p e n r o s e 逆和最小二乘问题的条件数 2 3 线性最小二乘问题( l l s ) 的范数犁，混合型和分量型条件数定义如下： k b ( a ，6 ) 一川l i r a 怕s u 删pm 丽i v x 1 2 ， m 1 8 ( 以，6 ) 一圳l i m 。s u p 丽f v x 1 ， ( a ，b ) ：= f 州 , i b l 在 8 】中，l l s 的混合型条件数在下面的定理中给出在接下来的推论中这些条件 数的上界也给出了 定理3 3 1 【8 】在以上的记号下，我们有 邶，6 ) = 崆唑塑唏幽坐业， c f 5 ( a ，6 ) = i l 坚二里生二j 垒二兰l = 三 ! = 兰盟型i f 。， 其中r = b a x 推论3 3 2 8 】在定理3 3 1 的假设下，我们有 抑瑚螋世出镐半嵝， 一5(a，a)|j旦垒!且垒型j上垒；：=上蛐ll，i j 例 忆 其中r = b a x 在【5 8 】中x i a a g ，d i a o 和w e i 已经分析了非奇异线性系统( apb ) z = d 的 扰动理论带k r o n e c k e r 积的线性最小二乘问题在很多应用领域中出现过，譬 如 3 8 】， 1 】对于这些问题有很多数值算法在这一章中我t r r 着力推导条件数 现在我们考虑带k r o n e c k e r 积的线性最小二乘问题( k p l l s ) ( 见 1 ，1 0 ，1 1 ， 1 3 ，2 9 ，3 1 ，3 2 ，3 6 ，5 3 ，6 0 】) ， m i n i i ( a p b ) v c 恢 ( 3 1 0 ) 其