（计算数学专业论文）奇异结构化矩阵和bottduffin逆的条件数问题.pdf

复旦大学硕士毕业论文 摘要 本文主要讨论对具有某些特殊结构的奇异线性方程组和矩阵的条件数问题，如：对称 矩阵、广义对称矩阵、反对称矩阵、c i r c u l a n t 矩阵、对称t o e p l i t z 矩阵、广义对称的h a n k e l 矩阵、t o e p l i t z 矩阵、h a n k e l 矩阵等等。由此我们可以发现对某些具有特殊结构的矩阵其 条件数最差的情形就是一般意义下定义的条件数。对某些特殊的右端项，我们给出了结构 化矩阵的线性方程组条件数的估计公式，以及结构化条件数与非结构化条件数的比值。而 且我们还证明了结构化矩阵广义逆的条件数是与其所具有的结构无关。 本文的另一部分着重讨论了b o t t d u f f i n 广义逆的条件数以及约束线性方程组a x + ：b 的条件数。给出了一系列在矩阵诱导范数意义下条件数的公式。同时我们还考虑了扰动对 条件数计算的影响，定义了条件数的条件数并对其进行了详细的研究最后我们还讨论了 分量扰动对条件数以及条件数的条件数的影响，给出了条件数估计的上界 关键词；条件数；m o o r e - p e n r o s e 逆；b o t t d u f f i n 逆；约束方程组；敏感性；结构化矩阵 复旦大学硕士毕业论文 a b s t r a c t 2 i nt h i s p a p e rw es t u d yt h ec o n d i t i o nn u n l b e ro fl i n e a rs y s t e m sa n dt h ec o n d i t i o nn u m b e r o fm o o r e - p e n r o s ei n v e r s e a l lp r o b l e m sa r ec o n s i d e r e dw i t hs o m es t r u c t u r e dm a s t r i c e s ，s u c ha s s y m m e t r i c ，p e r s y m m e t r i c ，s k e w s y m m e t r i c ，c i r c u l a n t ，s y m m e t r i ct e o p l i t z ，p e r s y m m t r i ch a n k e l ， t o e p l i t za n d h a n k e lm a t r i c e s w es h o wt h a tf o rag i v e nm a t r i xt h ew o r s tc a e ss t r u c t u r e dc o n d i t i o n n u m b e ri sj u s te q u a lt ot h eu n s t r u c t u r e dc o n d i t i o nn u m b e r f o rs o m es p e c i a lr i g t l th a n ds i d e ，w e g i v et h ef o r m u l a s t oe s t i m a t et h ec o n d i t i o nn u m b e ro fl i n e a rs y s t e m sw i t hs t r u c t u r e dm a t r i c e s m o r e o v e r ，w ea l s od i s c o v e rt h a tt h e8 t u c t u r e sh a v i n gn or a l a t i o nw i t ht h em o o r e - p e n r o s ei n v e r s e c o n d i t i o nn u m b e r s i nt h ea n o t h e rp a r to ft h i s p a p e r ，w ed i s c u s s e dt h a t v a r i o u sn o r m w i s er e l a t i v ec o n d i t i o n n u m b e r st h a tm e a s u r et h es e n s i t i v i t yo fb o t t d u f f i ni n v e r s ea n dt h es o l u t i o no fc o n s t r a i n e dl i n e a r s y s t e m sa r ec h a r a c t e r i z e d t h es e s i t i v i t yo fc o n d i t i o nn u m b e ri t s e l fi s t h e ni n v e s t i g a t e d f i n a l l y , u p p e rb o u n d sa r ed e r i v e df o rt h es e n s i t i v i t yo fc 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 e y w o r d s ：c o n d i t i o nn u m b e r ；m o o r e - p e n r o s ei n v e r s e ；b o t t d u f f i ni n v e r s e ；c o n s t r a i n e dl i n - e a rs y s t e m s ；s e n s i t i v i t y ；s t r u c t u r e dm a t r i x 第一章背景知识 1 1m o o r e p e n r o s e 逆及其性质 条件数是用来衡量扰动对原数据影响的敏感性。对非奇异矩阵a r “和向量b r “ 我们求解线性方程 a x = b ， 而条件数就是衡量解x 对a ，b 的扰动敏感度。假设a 和b 的扰动分别是a ，j t z x a i i 冬e i i a i i ， 和a b ，ll a b l i5e i i dl i 并且a + a 是非奇异的如果y 是线性方程组( a + a a ) y = b + a b 的解，且e f f a _ 1 a l f ( 1 8 ，p a g e1 2 0 ，则 可l l x - y l l k 其中 一- ：= i i a - i i ii i 以i i + 且垒i 型型2 i l j 4 1 l a 由此可知，条件数，c ，是关于解x 的相对误差扰动e 的线性因子。因此我们有以下关 于非奇异线性方程组的条件数的定义 8 ，p a g e1 2 1 ： = 。l i r a s u p 丽i i x l l ：( a + a ) ( x + a x ) = b + b ， i l a a l t e i i a i i ，i i a b l ls e r l b l l 当a 结构化矩阵时，例如：对称或t o e p l i t z ，因而我们有理由要求其扰动a 也具有 同样的结构。若其结构记为5 ，则我们就可以定义结构化矩阵的条件数如下： 一；一刚l i ms u p ( 丽i i x l l ：( a + a ) ( x + z x x ) = b + b ， a ，a s ，t v a i i e i a i i ，i v d ij e i l b l i )( 1 1 ) r u m p 在 1 1 中描述了对结构化非奇异矩阵的扰动理论并且给出了对对称、广义对称、 斜对称、t o e p l i t z 、h a n k e l 和循环矩阵的条件数一个更紧的上界。 4 复旦大学硕士毕业论文 本文中我们将考虑更为一般的情形一一最小二乘问题 a x b l l = m i n ( 1 2 ) 最小二乘解是x = a + b ，其中a + 是a 的m o o r e p e n r o s e 逆【2 即唯一满足以下四个 条件的唯一矩阵 a a + a = a ，a + a 4 + = 4 十，( a a + ) h = a a + ，( a + a ) h = a + a ， 这里a 表示a 的共轭转置，而a t 表示a 的转置 令y 是最小二乘问题 l f ( a + a a ) y 一( b 十b ) i | = m i n ， 的解，则由 8 ，p a g e3 8 2 得 斜船1e aji a ( z 州“，嵩) 1 x | 二 一 i j+ | | “”叫| 。”“。7i i aj | f l x | | 5 为了简化讨论过程，我们假设残量a x b 很小。因此其条件数可以估计为2f , a t 川a + 而且对最小二乘问题进行与线性方程的条件数，c t 类似的讨论，我们可以得到它的一个下 界 一i i a + ii i 驯斜剑川 ( 1 3 ) 对右端无扰动的情形，我们定义 k o ：= | | a + 川4 i ( 1 4 ) 基旦盔堂亟坐些堡塞6 1 2 b o t t ，d u f f i n 广义逆的性质及它的条件数 电网络理论中提出了下列约束线性方程( 3 】 a z + 可= 6 ，z l ，0 l 上 其中a c n 一，b c “，子空间lcc ”容易看出( 1 5 ) 的相容性等价于下列方程组 见+ p l - ) z = b 的相容性。并且( i ) 是c ，固战解当且仅当 x = 兄z ，y = 兄1 z = b a 屁2 其中z 是( 1 6 ) 的解，r 和兄- 分别是l 和l 1 上的正交投影。若a p l + p l - 非奇异 则对任何6 c “( 1 6 ) 相容，其唯一解为 z = p l ( a p l + 吃1 ) b ，y = b a x ( 1 8 ) 定义1 2 1 珂设a c “，子空问lcc “，若a 兄+ 兄- 非奇异，则a 关于l 的 b o t t d 硼讥逆，记作4 _ 定义为 a ( ( n - - 1 = p l ( a p l + 兄- ) 一1 下列定理给出a ：的基本性质， 定理1 2 1 胆，鄙设a 兄+ 瓦- 非奇异，则 f ，约束方程组阻，纠对任何6 有唯一解 。= a ；：6 ，g = ( ，一a a 注；弘 例尸l = a ( ( l - ) 1 a 屁= 凫a a 泣； 叫 - 1 = p l a l ： = a ( ( l - ) 1 兄 只( a 才) = 三，( a i ) = l 上 ( 4 ：蹦= p l a p l a 留= a 昆- = 阮a 兄) + 复旦大学硕士毕业论文 正如前所述经典的条件数是用来描述矩阵逆对相对误差扰动的敏感性。在本文中，我 们将讨论b o t t d u f f i n 逆的在范数意义下的条件数。给定矩阵a 舻”和矩阵范数”| | ， 我们将其定义如下： c。ndb。(a)：=。1+ira。+jiasiui!p刮。ll!i!二三j：铲 ( 。) 当矩阵范数是诱导范数时，我们可以证明 c o n d 且d = k ( a ) ：= i l d l l1 l a ( - 1 因为约束方程( 1 5 ) 在电网理论中的广泛应用【3 】3 ，所以我们更关心相对于约束方程组 的条件数 a x + y = 6 ，z l ，弘l 上 c o n d b d ( a ，6 ) ；蝴l i m + s u p l l a a i l ! e i i | 4 1 i ( a + a ) ( 一i ( 6 + 6 ) 一a ；才b 1 e 悄泌b 1 7 ( 1 1 2 ) i i 6 l l 曼e 6 | | 这里我们衡量a ，6 的相对扰动对解茁的影响我们同样可以证明 一d b d 6 ) = 舭) + 甜 ( 1 1 3 ) 得 当( 11 2 ) 式中的范数 1 1 是诱导矩阵范数和任何向量范数时，由( 1 ，1 0 ) 式和( 1 - 1 3 ) 式 c o n d 8 d ( a ) c o n d 8 d ( a ，b ) ( 1 1 4 ) 条件数在实际f 司题中主要有两个用途。其一是，当在具体问题中，数据 a ，吣总会有 误差扰动，条件数的引进可以在数值计算前对扰动对界的影响有一个大约的估计另一个 用途是，当进行向后误差分析时条件数可给出一个对计算解误差的一个上界 复旦大学硕士毕业论文 以下我们引出本文中常用的一些记号。我们记h s l d e rp 一范数为，| 1 即l i x l l ：= ( 銎- ? ) 1 肛( 1 p 茎。) ，和忙f l o 。：= m n z - s ；! 。k f j 对任意向量范数”忆和怕我们 从 6 1 中可以得到相应的诱导范数”忆口 i i a l l 。，p ：2 i i 。m | | 。3 , ：x l l l a 茁| l p ，( 11 5 ) 一般来说相容性条件i i a b i i 。口 i a i i 。，口i i b i i 叩并不一定成立，但是对任意向量范数 ”我们有 a b i i 。，p i i a i l 7 ，p i i b i i 州 f 1 1 6 ) 如果= 1 卢= 。 lj a ，一= l i 。4 f m 。z ：2 。m a xi 。i j 为了简单其间，我们记 岐。为”定义f 一范数为l i a l l p ：= ( ：。啦。) m 并且对任意 矩阵a 有奇异值分解 6 a = 仉 00 。 k r ， 其中= 矗i 凹p h 一，口* ，o ，o ) ，。z a 。a t o ， 巩 和 u 】是正 交阵，= r a n k ( a ) ，则其f 范数和2 一范数分别满足i i a i i f = ( 冬1 口；) 1 2 和l i a l l 。= 第二章结构化矩阵最小二乘问题的条件数 2 1一般情形 当最j 、_ _ - - 乘问题( 1 2 ) 所对应的矩阵a 是结构化矩阵时，我们有理由假设其扰动矩阵 a 与a 具有相同的结构因而，我们可以从线性方程组的条件数( 1 1 ) 中可以导出最小 二乘问题的条件数 一= l i m e - - - ，0 黜x t l 、f | | i | ( a + a a ) ( x + a x ) 一( b + a b ) l l = r a i n ， 4 ，a a 5 ，i v a l l e i i a i i ，i v d i i e i l bj 1 ( 2 1 ) 若扰动以满足以下两个条件： r a n g e ( a a ) r a n g e ( a ) 且r a n g e ( ( a a ) t ) r a n g e ( a t ) ，( 2 2 ) 其等价于，a a + a = a 且a + a ( a a ) t = ( a a ) t ，则我们有 i ( a + a a ) + = a + 一a + ( a a ) a + + 0 ( e 2 )( 2 3 ) 这儿我们举一个例子说明存在这样的t o e p l i t z 矩阵a 和a 使得以上条件满足( 2 2 ) 并且它们都具有相同的结构： a = 14321 21432 3214 3 4 32l4 14 321 a = e 1e 4e 3 旬e l e 2e le 4e 3e 2 e 3e 2e 1e 4e 3 e 4e 3e 2e 1e 4 e 1 4e 3e 2e 1 其中e 1 = 0 1 5 3 1 0 4 ，e 2 = 7 4 6 8 1 0 4 ，e 3 = 4 4 5 1 1 0 4 ，4 = 9 3 1 8 1 0 4 ，和 6 5 = 4 6 6 0 1 0 4 若且满足条件( 2 2 ) ，则从( 2 3 ) 中我们可以推得 x - i - a x = ( a + a a ) + ( b + a b ) = x + a + a b a + ( a a ) a + b + o ( e 2 ) 复旦大学硕士毕业论文 也就相当于 尤其当 时( 2 4 ) 式可以写成 a x - a + ( a a x a b ) 曲一踹， 卅讹( + 蹁) 把上式中的a x 代如( 2 1 ) ，则有 艘糯黼( + 黜) 由此我们定义a 的扰动的线性部分为e ，即a = e l l a ie ，和 ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) 妒：= s u p 1 1 4 + e x l l ：i i a x b h = m i n ，a ，e s ，h e l l 1 ) ， ( 2 8 ) 并且我们假设e 满足条件 r a n g e ( e ) 至r a n g e ( a ) 且r a n g e ( e t ) r a n g e ( a t ) ，( 2 9 ) 相当于a a 满足条件( 2 2 ) 。因此由( 2 7 ) 和( 2 8 ) ，我们可以得出的下界 & 尚( 忖i i + 黜) 另一方面，由( 2 1 ) 和( 2 4 ) 得 由上面两式得， 瞧i i a + i i i i a i i + i i 州i 惴 1 0 旦i l x l l ( + 丽i l b l l ) 剑州川a i i 圳卅1 黜 ( 2 1 。) 复旦大学硕士毕业论文 特别当妒= lt a + i x l l 时，由( 2 1 0 ) 式可以得到 = 1 1 a + i ii i a t l + i i 州i 丽i l b l l z i i 矿i ii i a i i + i i a + i i l 删a x l l - 因为( 1 3 ) 是k 的一个下界，所以比值k 总是近似的小于或等于1 接下来我们将构造 ( 2 8 ) 中的矩阵e 使得妒= 1 i a + x 1 1 成立。 假设 a = 矿 言： y t 是a 的奇异值分解并且r a n k ( a ) = r 。我们构造e = y x t 1 1 x 1 1 ，其中x z a + b 与y = u ， u 的第r 列。显然，i i e i l 1 。则 i i a + y i l = | | y 1 ： u t u ，0 = i l a + m 因此 咿= s u p1 i a + e x | | = s u pi i a + y l ii i x l i = i i a + l | l l x | 1 以下我们验证( 2 , 9 ) 式的两个条件， a a + e = u ： u t u ，x t 川x l l = u ，x t 川x i l = e 和 a + a e t = a + a x u t l l x l i = a + a a + b u t l l x l l = x u 了l l x l l = 矿 需要强调的是至此我们尚未将矩阵限制其具有结构s 所以，我们未能对条件数一做出任 何改进。而妒有可能小于l i a + x | l ，所以在下面的章节中我们将说明具有某种结构的条 件数扩将小于一。首先，我们将介绍一个与和妒有关的参数我们知道，对任意两个 向量u 和v ，有 ( i l u i i + i i v l l ) 、互5 、i | u i i 。+ i i v l l ：sm a x ( 1 l u + v 叭l l u v 1 1 ) sl 【u l i + i t v l l 引入参数c ，1 以c 1 ，我们有 m a x ( 1 l u + v i i ，i l u v i i ) = c ( i l u l i + j i v l l ) 复旦大学硕士毕业论文 因为我们可任意选取a b 的符号，所以对( 2 4 ) 应用上式，可以推得 l i a x l izc ( i i a + a a x i i + i i a + a b i ) ， 其中1 以c 1 。因而，由( 2 1 ) 式得， 帮zc ( 嗡拶+ 错) = c ( 掣+ 等) 一方面，估计上式中e 的大小，显然有 帮茎业掣= i i 。l l x l 。l l x l 纠i 槲】一 i一“恻l 。 另一方面，如果设a b = e i i d i l y ，其中y 是一个单位向量使得l i a + y 1 1 = l i a + i i ，则对此扰动 b ，我们有 蝌=业铲=ii。llxl。l l x l 州i 黜 i1一”蚓j 由和妒的定义( 2 1 ) 式和( 2 8 ) 式，我们可以得到下面定理。 定理2 。l 。1 由以上定义，结构化矩阵的条件数为 以c ( 妒丽i i a i i + i i 酬i 黜) ， ( 2 1 1 ) 其中l 以茎c 1 对右端无扰动的情形，我们有 一 = 妒丽i i a i i ， 因此，我们将通过重点讨论q o 来分析结构化矩阵的条件数。在后面的章节中，我们将 在本节的基础上讨论具有某些特殊结构的矩阵。 2 2 对称、广义对称、反对称矩阵 在本节中我们将讨论矩阵a 对称、广义对称和反对称的情形，并且可以得到，对这类 矩阵条件数不会有任何改进。也就是说当s = 对称、广义对称、反对称) 时，c 5 = ，c 。首 先引进 1 1 中的一个引理。 引理2 2 1 ( 【1 1 】) 令s = 对称，广义对称) 且x ，y r ”使得l i x l i = l l y l l = 1 ，则存在一 个礼凡的矩阵a s 满足 y = a x 且1 i a i l = 1 ( 2 ，1 2 ) 另外，如果y t x = 0 ，则存在一个反对称矩阵a 满足俾j 圳 复旦大学硕士毕业论文 若a 是广义对称的，则l ，a 对称，其中j 是一个置换矩阵 j ：= ( 2 1 3 ) 因此，以下引理说明了对对称和广义对称矩阵的最小二乘问题有同样大小的妒，故而其条件 数相等 引理2 2 2 最小二乘问题 i f a x b | 1 = r a i n 且l i j a x j b i = r a i n 的妒相等。 证明显然，i i e l = | | j e i l 并且如果e 和a 有相同的结构，则j e 和j a 也有相同 的结构。可以证明( j a ) + = a + j 。接下来我们有l i a + e x l i = l i ( j a ) + ( j e ) x i l ， a a + e = e ( j a ) ( j a ) + ( j e ) = j e ， 与 a + a e t = e t铮 ( j a ) + ( j a ) ( j e ) t = ( j e ) t 证毕。 口 因而我们有如下结果。 定理2 2 1 对结构集合s = 对称、广义对称、反对称) ， = k 证明由( 2 1 0 ) ，我们仅需证明，当s = 对称，广义对称，反对称) 时妒= i i a + x 1 | 成立。因为有引理2 , 2 2 得，对称和广义对称矩阵有相同的条件数，因而我们仅考虑对称和 反对称的情形。 情形1 ( 对称) 令r = r a n k ( a ) 且 a = v 言： y t 1 3 复旦大学硕士毕业论文 是a 的奇异值分解。我们对v 有分划v = m 】，其中由v 的前r 列组成，则 肚叭，0o w 是a + 的奇异值分解并且其可以写成a + = h i 1 印所以 | | 时x i i = l l 时4 + b l l = l l _ 1 岬b l l = 慨i 1 时b l l = i l x l l 对向量曙x l l x l i 和e ，单位阵的第r 列，应用引理2 2 1 ，我们可以找到对称矩阵豆使得 宫印x l l x l l = e ，且悃i = 1 令f = k 豆印，则e 对称且 l i a + e x | | = i i a + e ，| | l i x l l = l l i l e ，i x l l = l i a + x _ 而且，由于a + a = a a 十= k 呼与e 对称，所以a a + e = ( k 曙) ( 营昭) = e 与 a + a e t = e t 成立。这就意味着我们在( 2 8 ) 中构造了对称矩阵e 使得妒= i t a + i ii i x i i 成 立。 情形2 ( 反对称) 一个矩阵若是反对称的，则成立a = 一a t 。可以证明( a t ) + = ( a + ) t 。 所以，由a = 一a t 易得 a + = 一( a + ) t ， ( 2 1 4 ) 换句话说，a + 也是反对称的因此， a a + = 一a ( a + ) t = ( a + 4 ) t = a + a ( 2 1 5 ) 众所周知，反对称矩阵的特征值要么是共轭的纯虚数要么是零，故而反对称矩阵的奇 异值的重数为偶数。令 a = u ；： y t 是a 的奇异值分解，则a + 的奇异值分解为 肚y 卜 1 4 复旦大学硕士毕业论文 对u 进行分化u = 【u 1u 2 u 。 ，并且我们假设1 1 11 1 2 是对应于a + 的最大奇异值的奇异 向量。因此，1 | a + u 1 1 1 = i i a + u 2 1 i = i a 十忆令 y ：= 叩1 1 1 1 + 町2 u 2 叩：+ ”；= 1 ，( 2 1 6 ) 则 i y l l = 1 且1 i a + y 1 1 = 1 i a + n 接着，我们希望能找到一个反对称矩阵e 使得e x l i x l l = y 。因而j i a + e x l i = l i a + y i jl j x i | = 1 i a + j li i x l l 记向量 a = = 一 淞 则由( 2 1 4 ) 式，我们有 x = a + b = 一( a + ) t b = 一u a 由此得 x t y = 一a t u t y = 一q 1 矸1 一o 即2 选择适当的 。和叩2 使得 0 1 叩l + q 2 q 2 = 0 ，( 2 1 7 ) 于是也就有( x l l x l l ) t y = 0 。由引理2 2 1 ，若选取q l 和q 2 使得( 2 1 7 ) 式和( 2 ，1 6 ) 式成 立，则存在一个反对称矩阵豆，使得i l 豆= 1 且雪x l l x l l = y 这里x = a + b = a + a x 所以，啻a + a x i i x i i = y 定义e ：= a + a e a + a ，易证e 反对称，i i e i i i i e i i = 1 ，并 且e x l l x l l = a + a y 因此，由( 2 1 5 ) 式，我们有 l i a + e x | | = i i a + a + a y l ii i x l l = l i a + y i x l i = i a + x m 最后我们将说明e 满足条件( 2 9 ) ： a a + e = a a + 豆a + a = e 复旦大学硕士毕业论文 因为e 反对称，所以下式也成立 a + a e t = 一a a + e = 一层= e t 2 3 进一步的讨论 口 由于一个n 札的对称、广义对称、反对称矩阵是由0 ( n 2 ) 个自由元素决定，所以我们 对这类矩阵的条件数无法改进然而，像t o e p l i t z 和h a n k e l 矩阵仅有0 ( n ) 个自由元素。 本节中我们将注重考虑这类特殊结构。首先，我们将这类矩阵按其条件数进行分类。一个 矩阵丁对称t o e p | i t z 的当且仅当l ，丁( 或丁，) 是广义h a n k e l 阵，其中，是形如( 2 1 3 ) 的 置换阵。因此，有引理2 2 2 得，对称t o e p l i t z 阵和广义对称h a n k e l 阵的最小二乘问题有 相同的条件数同样的，因为矩阵t 是t o e p l i t z 矩阵当且仅当j 7 ( 或丁d 是h a n k e l 阵， 所以h a n k e l 和( 一般) t o e p l i t z 阵的最j 、- - 乘问题也有同样的条件数本节中我们将得出 对；c i r c u l a n t 阵，对称t o e p l i t z 阵，h a n k e l 阵的条件数均成立的结论。 为了进一步讨论此类结构，我们引入向量p ，其独立决定矩阵元素，并将该矩阵分解 成决定其结构的矩阵西和其参数向量p 的乘积。特别的，若我们记v e c ( a ) 是按a 的列张 成的向量，则由a 中的独立元素组成的向量p 是v e c ( a ) 的一个子向量。而矩阵圣仅仅包 含矩阵a 的结构的信息，并使其满足 v e c ( a ) = 圣p 例如；若a 是一个礼nt o e p | i t z 矩阵且礼= 3 ： a = t 0t lt - 2 t 1t ot 一1 ( 2 1 8 ) 1 6 复旦大学硕士毕业论文 t 结构 对称反对称 c i r c u l a n t 对称t o e p l i l z h a n k e l l 七 ( 扎2 + 礼) 2( n 2 一n ) 2 n2 n 1 表2 1 ：决定结构化矩阵元素的参数个数 l 结构c i r c u l a n t 对称t o e p l i t z h a n k e l l 。 l 、元l 矿厕l 何 f卢 l1以 表2 2 ：c i r c u l a n t 矩阵，对称t o e p l i t z 矩阵和h a n k e l 矩阵，在( 2 1 9 ) 式中的常数。和口 则a 有2 n 一1 个独立元素且p 是一个( 2 n 一1 ) 向量 p = p 同时也是由v e c ( a ) 前2 n 一1 个独立元素组成的子向量。n 2 ( 2 n 一1 ) 的矩阵壬是稀疏 矩阵并且其元素为。或1 ，且满足( 2 1 8 ) 式。表2 1 列示了所讨论的结构化矩阵独立元素 的个数k ，也就是向量p 的维数 现在，我们有参数向量p 的扰动a p 来决定对结构化矩阵a 的扰动a 。尤其，如 果v e c ( a ) = 垂p ，则v e c ( a a ) = 垂( p ) 。对以上这些结构，我们用一个k 一维向量t ， t = a p ( ejj a i l ) ，来取代( 2 8 ) 式中的e 。由前面e = a ( e l i a i i ) ，我们有v e c ( e ) = ( f t 以下引理 1 1 】建立了对前面研究的结构扰动i l e i l ( 或l i a i i ) 和i ( 或i i p h ) 之间的关系。 引理2 3 1 ( 1 1 ) 令v e c ( e ) = ( f t 是前面所述的分解 a 1 1 e 1 1 1 l t l ls 卢j i e l l ， ( 2 1 9 ) 其中参数n 和口由表2 2 给出。这些上界是可以达到的c i r c u l a n t 阵的下界也是可以达 到的，但是对对称t o e p i i t z 阵和h a n k d 阵其下界仅差一个因子、2 。 由以上引理得， e 8 ：v e c ( e ) = e f t ，i i t l i o ) 1 7 加 以 以” 脚 复旦大学硕士毕业论文 c 一 e s ：1 l f 1s1 ) ( 2 2 0 ) e 5 ：v e c ( e ) = 西t ，f t l l 曼卢) 所以，我们可以用对l 的限制来代替条件i | e i | s1 。而且，在( 28 ) 中，我们有 e x = ( x t o i ) v e c ( e ) = ( x t oj ) 西t ， 其中x t 是k r o n e c k e r 积。定义一个独立于扰动4 的n 矩阵 , i j ：= ( x t 固，) 圣， 由( 2 2 0 ) 式，得妒冬s u p l l a + 田圳：i i t f ls 卢) = 3 l i a + 皿| j 。因此我们有 妒= 7 i i a + 皿 l ，对0 7s 由参数7 ，我们希望对c i r c u l a n t 阵，对称t o e p l i t z 阵，和h a n k e l 阵找到更小的妒。从 ( 21 1 ) 式，我们有以下对c i r c u l a n t 阵，对称t o e p l i t z 阵和h a n k e l 阵的条件数的结论。 定理2 3 1 对5 = c i r c u l a n t , 对称t o e p l i t z ，h a n k e l ， 艇如删槲刊州黜) ： 其中1 、2sc 1 和。曼7sp ，卢由引理2 3 给出。对右端无扰动的情形， 船删1 1 驯槲 由此我们可以一下关于结构扰动与无结构扰动条件数的比值。 推论2 ：3 1 对s = c i r c u l a n t ，对称t o e p i i t z , h a n k e l ， 等 ( 1 胴厕揣瑞微厕 2 4c i r c u l a n t 矩阵 一个n 佗c i r c u l a n t 矩阵有如下形式： c = c i r c ( c o ，c l ，c 。一1 ) = c oe l一c n 一1 c n 一1 _ ： c 1 c n l c 0 ( 2 2 1 ) 复旦大学硕士毕业论文 c i r c u l a n t 矩阵拥有一些非常好的性质 4 。尤其，若记置换阵 p = o10 0 1o 1 o 1 9 则( 2 2 1 ) 式中的c i r c u l a n t 阵c 可以写成 c = c k p 2 这多项式意味着c i r c u l a n t 阵是可交换的，而且c 可以通过f o u r i e r 变换对角化： c = f 一1 d f ，其中f 是离散的f o u r i e r 变换矩阵，d 是对角阵由此得，其广义逆c + 也是 c i r c u l a n t 阵并且c i r c u l a n t 矩阵的乘积还是c i r c u l a n t 矩阵。特别当a 是c i r c u l a n t 阵时， a a + 也是c i r c u l a n t 的。所以，如果我们在定义( 2 8 ) 式中选择e = a a + 则i i a + e x l = i i a + x | | ，这也就意味着妒i i a + x l i 另一方面，因为a + 和e 都是c i r c u l a n t 阵，故它们 可交换。因此，i i a + e x i = i l e a + x l isi i a + x | | 。由此得， 妒“= i i a + x 1 ( 2 2 2 ) 由( 2 1 1 ) 式中妒的值，我们有下面关于c i r e u l a n t 矩阵最小二乘问题的条件数。 定理2 4 1 。对c i r c u l a n t 矩阵最小二乘问题，其条件数为 “= c ( h a + x l i 槲+ 1 1 州i 黼) ， 其中1 以sc 1 对右端无扰动的情形， 哥”刮删槲 并且，由r 钊式， 竖n 0 = 尚i a + 褊赢i| | i i x | i 一| i a + i i 【i a _ 证明最后一个不等式由恻lsi d l 川a + x l | 得到。 口 在对c i r c u l a n t 阵的条件数k “”与( 1 3 ) 式中的常规条件数，c 进行比较之前，我们先 给出以下两个引理。第一个引理引自 1 1 】。而另一个给出了条件数的一个简单下界。 复旦大学硕士毕业论文 引理2 4 1 ( 1 1 ) 对任何礼n 的矩阵a ，礼维向量z ，和nx 咒c i r c u l a n t 矩阵c ，成立 i i a c l 【= l i a c “i | 和i i c z l i = i i v “z 引理2 4 2 对nxn 矩阵a 和结构集s ，若 妒ui i ( a + ) t x i l ， ( 2 2 3 ) 对某个非负的u 成立，则 k s 2 1 i a + 1 1 1 i a l l ( 2 ，2 4 ) 证明因为x 是最小二乘解，则 j | x | | 27 - - x t x = x t a + a 4 + b i i x t a + | | l i a a + | | i l b | | = l i ( a + ) t x l ll i b l l 由条件( 22 3 ) 式和上不等式，我们有 妒l i a i i + l i a 十i | | i b l i u | | ( a + ) t x l i1 a 1 1 + i i d + | | i l bj | 2 wi i ( a + f x l l i a i ji i a + t jj i b l j 2i l x | | ulj a 十l l i a m 则，( 2 , 2 4 ) 式由定理2 , 1 。1 中的( 2 1 1 ) 式推得， 口 最后，我们给出一d ”和k 的简单比值 定理2 4 2 对c i r c u l a n t 矩阵的条件数和一般最小二乘问题的条件数，我们有 竺 ；! ， ( 2 2 5 ) 托一2 i i a + 1 1 1 i a | 1 、。 证明由( 2 2 2 ) 式中的妒d ”和引理2 4 1 ，得 妒“= i i a + x l i = l i ( a + ) t x 叭 并且由引理2 4 2 得， k 。“、2 1 1 a + 圳， 由( 1 3 ) 式推得( 2 2 5 ) 口 此定理给出了比值舻“。片的下界并且证明了我们可以得到一个更小的k 6 “在【1 1 中给出了一个对非奇异矩阵a 的数值例子，说明了( 2 2 5 ) 式中比值g c l r c 一的下界是紧的。 复旦大学硕士毕业论文 2 5 对称t o e p l i t z 矩阵和h a n k e l 矩阵 2 l 形。如果a 是对称的t o e p l i t z 矩阵，我们可以进行如下分划 a = 蚓， 。e ， 其中t 和u 是m 阶矩阵且t 对称。相应的，我们对j 作分划 j = k 皿z ， 其中j l l 2 也是m 阶矩阵应用如上分划( 2 2 6 ) 与( 2 2 7 ) 及j a j = a ，我们可以证明 t = j 1 2 t j i l 2 和u t = j l l 2 u j t l 2 。其次，我们假设解x 满足x = 士j x 。这假设在稍后也 可去掉， 引理2 5 1 若矩阵b 满足b = j b j 且向量c 满足c = 士j c ，则向量d = b c 同时满足 d = j d 对广义逆b + ，我们同样可得b + c = 士，( b + c ) 证明由 士j d = 士j b c = ( j b j ) ( 土3 c ) = b c = d 及b + = ( j b j ) + = j b + j 易得 口 易得，若c = 士j c ，则c 由形式： c 乜对 其中c 。是c 得上半部分，是一个矾维向量。 现在，我们考虑( 2 8 ) 式中的a + e x 记y ：= e x 。因为e 是对称的t o e p l i t z 矩阵， 易证j e j = e 由假设x = 士j x 和引理2 5 1 ，向量y 有形式 y 屯对 记z ：= a + e x = a + y ，再由引理2 5 1 得，向量z 也由形式 z = k 斗 复旦大学硕士毕业论文 若对a + 进行如下分划： 拈眺 7 。s ， 则z = a + y 意味着 z 1 = ( 五士u l j l 2 ) y 1 ( 2 2 9 ) 由分划( 2 2 8 ) 式和a + = j a + j ，易证t 2 = j 1 2 t 1 j 1 2 与卵= j 1 2 u 1 j 1 2 成立。 下面我们说明丑士仉 2 和t 士u j l 2 之间的关系特别的，我们将说明正土仉 2 是t 4 - u j l 2 的m o o r e - p e n r o s e 逆我们首先引进两个引理。 引理2 5 2 若u r a n g e ( a ) 且由形式 u 也剖， 1 1 1 = ( t4 - u 2 ) ( a 士阢 2 ) u l = ( 五士巩以2 ) ( t 士u 2 ) u l ， ( 2 3 0 ) 证明由引理2 5 1 ，若u = j u ，则v ：= a u 和w ：= a + u 有： v = iv 1 和w = 土 胆： 由分划( 2 2 6 ) 和( 2 2