（计算数学专业论文）几类结构矩阵的谱问题.pdf

几类结构矩阵的谱问题 u l 摘要 众所周知，在工程计算和实际应用中有许多问题最终都归结为矩阵计算问题，而 且不同的应用会导出些具有特殊结构的矩降i 博最常见的些结构矩阵有t o e p - - l i t z 矩阵l a 一j 】，h a n k e l 矩阵【毗+ j 】，t o e p l i t z - p l u s - h a n k e l 矩阵，c a u c h y 矩阵【：盈1i 】 等等处理与这些结构矩阵有关的矩阵计算问题( 例如计算特征值、求解线性方程组 等) ，若矩阵的阶数较小时，通常的经典算法是可行的( 例如l u 分解算法、q r 算法 等) 然而，在许多实际应用当中，矩阵的阶数仃很大( n 1 0 6 1 0 9 ) 或某个线性方 程组需要多次计算直到得到个满意的结果( 例如迭代法时) ，此时这些经典的算法 由于代价太大而失去了实际意义 因此，针对这些结构矩阵的特点而设计些能利用它们的结构的，数值稳定的快 速算法，具有非常重要的意义正因为结构矩阵在实际应用中所具有的重要意义，国 内外众多的学者将目光投入到这领域结构矩阵的快速算法中最著名的莫过于快 速傅里叶变换( 即f f t ) ，有许多胬彭享法均是由快速傅里叶变换导出的因此，著 名数学家c h a r l e sv a nl o a n 曾这样评价快速傅里叶变换算法： “从计算的角度看， 快速傅里叶变换是本世纪最杰出的成就之一，毫不夸张地说，快速傅里叶变换改变 了科学与工程计算的面貌，如果没有它，生活将会是另种景象” 本论文主要研究了实h a n k e l c i r c u l a n t 和h a n k e l s k e w c i r c u l a n t 矩阵的奇异值分 解，给出了对称t o e p l i t z - p l u s - h a n k e l 矩阵特征值的快速算法和这个计算矩阵特征值 算法的数值实验理论和数值实验显示，这个侥速算法是行之有效的 第章，我们简单介绍了研究结构矩阵决速算法的现实意义，研究概况以及常 用的研究方法，同时也给出了与本论文有关的几类结构矩阵的定义及其基本性质 第二章，我们给出了n 阶对称t o e p l i t z - p l u s - h a n k e l 矩阵与个佗维向量乘积的 快速算法；并利用他阶矩阵的对称陛，对其实施l a n c z o s 三对角化和q r 对角化， 计算出矩阵的所有特征值该算法的计算复杂度为d ( n 2l o gn ) 第三章，我们研究了实h a n k e l - c i r c u l a n t 、h a n k e l - s k e w c i r c u l a n t 矩阵与h a n - k e l 矩阵的关系，并给出了它们的奇异值分解，为我们研究实h a n k e l - c i r c u l a n t 矩阵、 h a n k e l - s k e w - c i r c u l a n t 矩阵的奇异值分解提供了理论基础 关键词：结构矩阵；快速算法；t o e p l i t z 矩阵；h a n k c l 矩阵；对称t o e p l i t z p l u s - h a n k e l 矩阵；h a n k e l c i r c u l a n t 矩阵；h a n k e l - s k e w - c i r c u l a n t 矩阵。 a b s t r a c t m a n yi m p o r t a n tp r o b l e m si ne n g i n e e r i n ga n da p p l i e ds c i e n c e sc a nb ef i - n a l l yr e d u c e dt om a t r i xc o m p u t a t i o np r o b l e m s m o r e o v e r ，v a r i o u sa p p l i c a t i o n s o f t e ni n t r o d u c es o m es p e c i a ls t r u c t u r e si n t ot h ec o r r e s p o n d i n gm a t r i c e s a m o n g c l a s s i c a le x a m p l e sa r et o e p l i t zm a t r i c e s 【a i - i ，h a n k e lm a t r i c e s 【a i 州】，t o e p l i t z - p l u s - h a n k e lm a t r i c e s ，c a u e h ym a t r i c e s 【去】a n do t h e r s w h e nw ed e a lw i t h t h er e l a t e dm a t r i xp r o b l e m ( s u c ha sc o m p u t i n g e i g e n v a l u e ，s o l v i n gl i n e a rs y s t e m s a n d8 0o n ) w i t hs p e c i a ls t r u c t u r e ，a sw ek n o w ，t h es t a n d a r dl i n e a ra l g e b r a ( s u c ha s g a u s s i a ne l i m i n a t i o na l g o r i t h m ，q r ta l g o r i t h m ，e t c ) a r e ，o fc o u r s e ，r e a d i l ya v a i l a b l ef o rs m a l l - s i z ep r o b l e m s h o w e v e r ，i nm a n yp r a c t i c a la p p l i c a t i o n s ，t h eo r d e r o fm a t r i c e sa r ev e r yl a r g e 一1 0 6 1 0 9 ) o rt h el i n e a re q u a t i o n sm a yh a v et ob e s o l v e do v e ra n do v e ra g a i n ( s u c ha si t e r a t i v em e t h o d s ) ，w i t hd i f f e r e n tp r o b l e mo r m o d e lp a r a m e t e r s ，u n t i las a t i s f a c t o r ys o l u t i o nt ot h eo r i g i n a lp h y s i c a lp r o b l e m i so b t a i n e d i ns u c hc a s e s ，t h en u m b e ro ff l o p sr e q u i r e dt os o l v et h er e l a t e dm a t r i x p r o b l e m sc a nb e c o m ep r o h i b i t i v e l yl a r g es ot h a tt h e s ec l a s s i c a lm e t h o d sh a v en o s e n s e s t h e r e f o r e t oa c h i v i n gaf a s ta n ds t a b l ea l g o r i t h mf o rt h e s em a t r i c e sw i t h s p e c i a lo fc h a r a c t e r i s t i cs t r u c t u r ei sa l li m p o r t a n ti s s u ei nm a n ya p p l i e da r e a s t h u s ，i ti sn o ts u r p r i s i n gt h a ti nr e c e n ty e a r st h ed e s i g no ff a s ta l g o r i t h m sf o r s t r u c t u r e dm a t r i c e sh a sb e c o m ea ni n c r e a s i n g l yi m p o r t a n ta c t i v i t yi nad i v e r s e v a r i e t yo fb r a n c h e so ft h ee x a c ts c i e n c e s a st of a s ta l g o r i t h m s ，p e r h a p st h e m o s tw i d e l ya n di m p o r t a n t l yk n o w ne x a m p l eo ff a s ta l g o r i t h m si st h ef a s tf o u r i e r t r a n s f o r m ( f f t ) t h e r ea r em a n yc l a s s i c a lf a s ta l g o r i t h m sw h i c ha r eb e e nd e d u c e d b yf f t i t si m p o r t a n c ei sw i d e l ya c k n o w l e d g e da n dn i c e l yd e s c r i b e di nn u m e r o u s p a p e r sa n dm o n o g r a p h s ，e g ，a sf o l l o w s ：“t h ef a s tf o u r i e rt r a n s f o r m ( f f t ) i so n e o ft h et r u l yg r e a tc o m p u t a t i o n a ld e v e l o p m e n t so ft h i sc e n t u r y i th a sc h a n g e d t h ef a c eo fs c i e n c ea n de n g i n e e r i n gs ot h a ti ti sn o ta ne x a g g e r a t i o nt os a yt h a t l i f ea sw ek n o wi tw o u l db ev e r yd i f f e r e n tw i t h o u tf f t ”( c h a r l e sv a nl o a n ，a f a m o u sm a t h e m a t i c i a n ) i nt h i sp a p e r ，w em a i n l yd i s c u s ss v do fh a n k e l - c i r c u l a n ta n dh a n k e l s k e w - c i r c u l a n tm a 七r i c e sa n dd e s i g na f a s ta l g o r i t h mf o rs y m m e t r i ct o e p l i t z - p l u s - h a n k e l m a t r i c e s a st h e o r e t i c a la n dn u m e r i c a le x p e r i m e n t sr e s u l t ss h o w ，t h ef a s ta l g o - r i t h mi sv e r yu s e f u l i nc h a p t e rl w eg i v eab r i e fi n t r o d u c t i o nt ot h ei m p o r t a n c e 、t h e c u r r e n tr e - s e a r c hs i t u a t i o na n dc l a s s i c a lr e s e a r c hm e t h o d s o ns t r u c t u r e dm a t r i c e s m o r e o v e r ， 8 n ed e f i n i t i o na n dp r o p e r t i e so ft h es t r u c t u r e dm a t r i c e sw h i c ha r ed i s c u s s e di n o u rp a p e rh a v eb e e ng i v e n i nc h a p t e r2 ，w ep r e s e n taf a s ts y m m e t r i ct o e p l i t z - p l u s - h a n k e lm a t r i x - v e c t o r p r o d u c ta l g o r i t h ma n da p p l yt h el a n c z o s - t y p et r i d i a g o n a l i z a t i o na n dq r - t y p e d i a g o n a l i z a t i o nm e t h o d t of i n da l lt h ee i g e n v a l u e so fa nn ns y m m e t r i ct o e p l i t z - p l u s - h a n k e lm a t r i xi nd ( n 2l o g 九) o p e r a t i o n i nc h a p t e r3 ，w es t u d yt h er e l a t i o nb e t w e e nr e a lh a n k e l c i r c u l a n t 、h a n k e l - s 1 【e w c i r c u l a n tm a t r i xa n dh a n k e lm a t r i x m o r e o v e r ，w ep r e s e n ts e v e r a ls i n g u l a r v a l u ed e c o m p o s i t i o n so fr e a lh a n k e l c i r c u l a n ta n dh a n k e l s k e w c i r c u l a n tm a t r i - c e s t h es i n g u l a rv a l u ed e c o m p o s i t i o n so ft h i sc h a p t e ra r eg i v e ni ne x p l i c i tf o r m w h i c hc a nb ee a s i l ye v a l u a t e di nc o m p u t e rp r o g r a m sa n dp r o v i d eau 刍e f u lb a s i s f o rt h e o r e t i c a li n v e s t i g a t i o n s k e yw o r d s ：s t r u c t u r e dm a t r i x ；f a s ta l g o r i t h m ；t o e p h t zm a t r i x ；h a n k e lm a - t r i x ；s y m m e t r i ct o e p l i t z p l u s h a n k e lm a t r i x ；h a n k e l - c i r c u l a n t m a t r i x ；h a n k e l s k e w - c i r c u l a n tm a t r i x 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研 究成果。本人在论文写作中参考的其它个人或集体的研究成 果，均在文中以明确方式标明本人依法享有和承担由此论 文而产生的权利和责任 责任人c 签孙慨司 删月；o 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。 厦门大学有权保留并向国家主管部门或其指定机构送交论文 的纸质版和电子版，有权将学位论文用于非赢利目的的少量 复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘 要汇编出版。保密的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书 2 、不保密( 一 ( 请在以上相应括号内打” ”) 日期：蜥j 月弘日 嗍。勿承广f 月妒 第一章绪论 第一章绪论 1 1 引言 众所周知，在工程和实际应用中有许多问题最终都归结为矩阵计算问 题，而且有许多应用需要计算的矩阵是一些具有特殊结构的矩阵 最常见的些结构矩阵有t o e p l i t z 矩阵k j 1 ，h a n k e l 矩阵【口】，t o e p l i t z - p l u s - h a n k e l 矩阵，c a u c h y 矩阵【= = 1 瓦】等等我们知道，处理与这些结构矩 阵有关的矩降汁算问题( 例如计算特征值、求解线性方程组等) ，若矩阵的 阶数较小时，通常的经典算法是可行的然而，在许多实际应用当中，矩 阵的阶数很大，此时这些经典的算法由于未充分利用这些矩阵的结构，计 算花费代价太大而失去了实际意义因此，针对这些结构矩阵的特点而设 计些数值稳定的快速，超央速的数值算法，具有非常重要的意义 提到快速算法，最著名的莫过于陕速傅里叶变换( 即f f t ) ，有许多快 速算法均是由快速傅里叶变换导出的因此，著名数学家c h a r l e sv a nl o a n 曾这样评价快速傅里叶变换算法：“从计算的角度看，快速傅里叶变换是 本世纪最杰出的成就之一，毫不夸张地说，快速傅里叶变换改变了科学与 工程计算的面貌，如果没有它，生活将会是另一种景象”有许多经典的 快速算法都因此诞生在本论文中，第二章所给的快速算法也都号决速傅 里叶变换有关 正因为结构矩阵在实际应用中e 獬的重要意义，国内外众多的学者 将目光投入到这领域目前，在国外已经出现了多个研究群体，主要有 以t h o m a sk a i l a t h 为代表的研究群体( 位移秩方法) ；以g e o r gh e i n i g 为 代表的研究群体( 四种基本类型位移结构矩阵的计算，矩阵广义逆的位移 结构) ；以v i c t o ry p a n 为代表的研究群体( 多项式与结构矩阵的计算，牛 顿结构迭代算法) ；以v a d i mo l s h e v s k y 为代表的研究群体( 有理插值与结 构矩阵的快速算法的研究) 等在国内，许多学者也在相关课题上做了大 量的研究工作，西安交通大学的游兆勇、李磊、路浩等在t o e p l i t z 矩阵、 c i r c u l a n t 矩阵求逆的快速算法与复杂性分析方面；西北工业大学的徐仲、 第一章绪论 张凯院、陆全等在v a n d e r m o n d e 、t o e p l i t z 矩阵类的快速算法方面；中国 科学院数学机械研究中心的支丽红在符号与数值的混合计算方面 本节将给出本文所涉及到的几类结构矩阵的定义及相关的性质，其中 的性质均只列出参考文献而不给出证明 定义1 2 1n 阶f o u r i e r 矩阵定义如下： f ，要1 耍1 蒌1 ：喜、 f 丽万 丽 丽 1 l lu护 u n 以i i 丽丽 而万 i r = i 击岳长弋w 2 ( n 矿- 1 ) i ， ( 1 ) l 妻毒杀! 每j 其中u = e 掣，i 为虚数单位 另介绍与n 阶f o u r i e r 矩阵有紧密联系的矩阵 ( g ) 职= 弓去扩门+ j ) ，p = 0 ，1 ，n 一1 ，g = 0 ，l ，n 一1 i j 因而我们有 g = d i a y ( i ，。1 ，。孚) f 众所周知，f o u r i e r 矩阵是酉矩阵，是对称矩阵个f o u r i e r 矩阵乘 以个向量相当于对这一向量作离散f o u r i e r 变换( 即d f t ) 。1 9 6 5 年， j w c o o l e y 给出了著名的快速傅里叶变换( 即f f t ) 定理1 2 2 1 1 对长度为n 的向量作离散f o u r i c r 变换及逆离散f o u r i e r 变 换所需的运算量及存储空间均为o ( nl o gn ) ， 定义1 2 3n 阶t o e p l i t z 矩阵定义如下： t 卜t 0 墨 t n 一1 t n - 2 2 2 3 忙 ”： 幻“ 第一章绪论 3 日薯 lk h n 一- ，2 之：1 _ 乏：乏：j a = t + h = ( o 撺一j l + h i + j 一2 ) ；1 ( 4 ) 1 3 设计结构矩阵快速算法的常用方法及本文的结构 研究结构矩阵的快速算法有着悠久的历史，相关的文献非常之多然 而常用的研究方法不外乎以下几种： 1 、利用快速傅里叶变换( f f t ) 2 、利用结构矩阵的特殊结构，构造出相应的递归关系例如文献【2 j 和【3 1 3 、位移结构理论，详见文献【4 】和【5 】- 4 、利用结构矩阵与多项式插值之间的关系，见文献【6 】 本文给的快速算法所用的研究方法主要是前两种，在第二章中，我们 给出了n 阶对称t o e p l i t z - p l u s - h a n k e l 矩阵与个n 维向量乘积的快速算 法；并利用其对称性，对其实施l a n c z o s 三对角化和q r 对角化，计算出 矩阵的所有特征值，该算法的计算复杂度为o ( n 2l o g 礼) 第三章，我们研究了实h a n k c l - c i r c u l a n t 、h a n k e l - s k c w c i r c u l a n t 矩阵与 h a n k e l 矩阵的关系，并给出了它们的奇异值分解，为我们研究实h a n k e l c i r c u l a n t 矩阵、h a n k e l s k e w - c i r c u l a n t 矩阵奇异值分解提供了理论基础 墨三主壁整堡望丝生趔坚兰：i 塑型堑生壁垒焦笪：睦鲨墨叁 4 第二章对称t o e p l i t z p l u s - h a n k e l 矩阵特征值的快速算法 结构矩阵的特征值问题在科学与工程计算、图像和信号处理领域中有 着重要的应用，已引起不少学者的关注( 见文献【7 1 【8 1 【9 1 【1 0 】【1 1 】【1 2 1 1 3 】) 然 而对于t o e p l i t z - p l u s - h a n k e l 矩阵的特征值，相应的数值算法涉及很少，有 文献【1 4 】本章主要介绍求对称t o e p l i t z - p l u s - h a n k e l 矩阵特征值问题的一 种算法 2 1 复对称 首先我们的想法是利用对称t o e p l i t z - p l u s h a n k e l 矩阵的对称性这里 不妨记几阶对称t o e p l i t z - p l u s - h a n k e l 矩阵为a ，假设a 为非亏损矩阵，则 矩阵a 的特征值分解为 a = x d x ， ( 5 ) 其中d 为对角矩阵，x 为非奇异矩阵这里取x 为复正交矩阵，即 x x 丁= ， ( 6 ) 因此a = x d x t 首先对矩阵a 实施l a n c z o s 三对角化，则有 a = q j q t ，( 7 ) 其中q 为复正交矩阵，j 为复对称三角矩阵再对矩阵，实施对角化， 得 j = w d w r ，( 8 ) 其中彤为复正交矩阵，d 为对角矩阵因而我们可得( 5 ) 式，并且有 x = q w ( 9 ) 我们知道l a n c z o s 算法主要运算量是计算矩阵与向量的乘积般来说，n 阶矩阵与向量的计算复杂度为d ( n 2 ) 这里我们基于l a n c z o s 算法原理，提 出一种陕速计算几阶对称t o e p l i t z p l u s h a n k e l 矩阵与向量的乘积的算法， 它的计算量只需o ( nl o gn ) 因而我们对礼阶对称t o e p l i t z - p l u s - h a n k e l 矩阵 第二章对称t o e p l i t z - p l u s - h a n k e l 矩阵特征值的快速算法 5 实施l a n c z o s 三对角化，所需的计算复杂度为o ( n 2l o g n ) 上述得到的三 对角矩阵具有复对称性，为了保持它的对称| 生和三对角结构，我们在q r 迭代过程中采用复正交变换 2 2 复正交变换 在计算矩阵特征值问题过程中，我们利用2 阶复正交阵将2 维向量化 为( 1 2 ) 式根据( 6 ) 式，我们提供两种2 阶复正交矩阵的般形式 其中c 24 - s 2 = 若( 1 0 ) 式矩阵 2 维复向量 其中z ；4 - z ； g = ( _ 二s ：) ，( ：二c ) ， g = ) ， 元素为实数，则它就成为g i v e n s 旋转变换对于给定的一 x = ( 三：) ， c 1 1 ， ( 紫) ， 算法1 ( 复正交变换) 给定一2 维复向量x ( 见( 1 1 ) 式) ，现利用该算法 计算复正交变换矩阵( 见( 1 0 ) 式) 的元素c 和s 使得( 1 2 ) 式成立 i f ( i x lj i z 2 i ) 扣x 2 x 1 ；c = 1 用；s = t c ； e l s e 丁= x l x 2 ；s = 1 订而芽；c = 7 ，s ； e n di f 这个算法将应用到本章第5 小节有关矩阵的复正交对角化的计算过程中 墨三主壁整望! 鲤! 竺垡坚堂望塑丝! 堑堕壁堡焦箜：堡鎏墨盘 6 2 3 计算对称t o e p l i t z - p l u s - h a n k e l 矩阵与向量的乘积 现描述一礼阶t o e p l i t z - p l u s - h a n k e l 矩阵与任一他维向量的乘积的一种 快速算法，即计算a z ，其中a = t + h 因而礼阶t o e p l i t z - p l u s - h a n k e l 矩 阵与n 维向量的乘积 a v = ( t + h ) v = t v + h v ( 1 3 ) 就转化成个n 阶t o e p l i t z 矩阵和个n 阶h a n k e l 矩阵分别与一佗维向 量的乘积计算 这里记i i 为n 扎阶的置换矩阵，即 i i = 由t o e p l i t z 矩阵与h a n k e l 矩阵的结构特点，可得 h i i = n ， ( 1 4 ) 其中瓦为t o e p l i t z 矩阵因而( 1 3 ) 式可转化为 a v = t v + h v 兰t v + ( h r l ) ( r l v ) = t v + 死( ) ，( 1 5 ) 故我们只需考虑几n 阶的t o e p l i t z 矩阵与向量和乘积计算下面我们以 ( 1 4 ) 式的t o e p l i t z 矩阵瓦为例我们将它嵌入个( 2 n 一1 ) ( 2 n 一1 ) 阶 0 1 0 o 0 o ； l 0 的循环矩阵中，即 g ( e h ) 这里 九2 n 一1h 2 n 一2 2 n 一3 h t i h 2 n 一1h 2 n 一2 n + 1 h 2 n 一1h 2 n 一2 h n + 1 n 一1 h n + 2 lh n + 3 1h n 一2 h 1 h 2 n 一1 n + 2h n + 1 危n 一1h n 一2h n 一3 2 n lh 2 n 一2h 2 n 一3 h n 魏= ( kk + 。 。+ 。 ：。一。尼。k k 一。) r 容易看出，循环矩阵的n 强酣顷序主子阵即为t o e p l i t z 矩阵a 。 给定个n 维的向量 计算矩阵向量的积 y = ( 魄沈幼) r ， 利用( 1 5 ) 式和( 1 8 ) 式，则有 p h = h v p h = h v = ( n ) ( ) = t h ( n ) 令玩为一( 2 n 1 ) 维的向量： 玩= ( 蜥o o ) 丁， 容易看出，p h 为向量溉的前孔个分量，其中 y h 三瓯( e h l l 玩 由于循环矩阵与向量的积可以利用f f t 来计算( 见文【1 7 】) ，即 既( e ) 玩= i f f t ( f f t ( d ) 术，t ( 莎) ) ， ( 1 7 ) ( 1 8 ) ( 1 9 ) 加加； 。腑k ； l 2 凡 危k m 抛蛔 一 一 n 胁舻k ； 一 n + 胁h 腑； n + + k m 腑； h k ； 第二章对称t o e p l i t z - p l u s - h a n k e l 矩阵特征值的快速算法8 其中d 为矩阵t 的第列，f f t ( v ) 表示向量u 的快速傅里懒，i f f t ( v ) 表示向量t ，的递惠傅里叶变换， “翱表示两个向量对应元素的积由 于，t ( 口) 的计算复杂度为o ( nl o gn ) 注1 ：通过将t o e p l i t z 矩阵够扒到个循环矩阵中而设计陕速算法的 思想广泛应用于预条件方法中( 见文【1 8 】和文【1 9 1 ) 由引理2 ，可以得到如下算法： 算法2 ( 计算对称t o e p l i t z - p l u s - h a n k e l 矩阵与向量的乘积) 该算法利用 f f t 计算一n 维向量l ，与n n 阶对称t o e p l i t z - p l u s - h a n k e l 矩阵的乘积： ( 1 ) 定义两个( 2 n 一1 ) 一维的向量如和f i t ： e = lh 。 n + l ，h + 2 7 屹t l l 九1 h n 1 ) ， 耻( t ot l t 2 t n - 1t n - 1 l n - 2 t 1 ) 丁 ( 2 ) 定义两个( 2 n 一1 ) 维的向量如和仇，其中 玩= ( 一l n0 0 ) ，仇= ( 1 1 屹0 0 ) ( 3 ) 由下列公式计算y 和y 。： y h = i f f t ( f f t ( e h ) 术f f t ( 玩) ) ，y t = i f f t ( f f t ( t ) 木f f t ( f , t ) ) ( 4 ) 令y = y h + 乳= ( y ly 2 y 2 n 一2 抛。一1 , l l ，则 p = ( y 。耽蚍。) t 2 4l a n c z o s 三对角化 在本节中，利用l a n c z o s 迭代过程推导出将对称t o e p l i t z - p l u s - h a n k e l 矩阵转化成个对称三对角矩阵的方法我们的目标是寻找一个复正交矩 阵q 使得( 7 ) 式成立，即 a q = q j ( 2 0 ) 令 q = ( q l ，q 2 ，q 3 ) ， g ：- 章对称t o c p l i t z - p l u s - h a n k e l 矩阵特征值的快速算法 9 和 j = a 1p l o 岛& 2 侥 仍。 艮一l 0 风一1q n ( 2 1 ) 比较( 2 0 ) 式左右两边矩阵的第尼列，有 a 毗= 风一l 毗一l + q k 毗+ 反毗+ 1 ， ( 2 2 ) 其中& q o = 0 ，风q n + 1 = 0 因为q 是复正交矩阵，即q = 如，可得 o t k = a q k 由( 2 2 ) 式可得 凤q 七+ 1 = a q k q k q 瞻一仇一l q * 一1 令 r k = a q k d k q k 一口k 一1 q k l ， 我们可得 侥= r 阢，q k 十l = ( 1 p k ) r k 其中k 礼因而我们可以推得般l a n c z o s 三对角化的算法这里只用 到t o e p l i t z - p l u s - h a n k e l 矩阵的复对称性 算法3 ( l a n c z o s 三对角化) 给定个n 阶复对称矩阵a ，现要计算个 复正交矩阵q 使得a = q j q r ，其中j 是个复对称三对角矩阵，见( 2 1 ) 式 初始化q 1 使得酊q l = 1 ； 令r o = q l ；风= l ；q o = o ；k = o ； w h i l e ( 仇0 ) q k + i = ( 1 p k ) r k ； k = 尼- i - 1 ： a k = q t a q k ； 第二章对称t o c p l i t z p l u s h a n k e l 矩阵特征值的快速算法 1 0 r k = a q 七一o r k q k 一凤一l q k 一1 ； 凤= o ：瓦； 若熊0 ，则算法3 将运行到k = 仃该算法的主要计算量是t o e p l i t z - p l u s - h a n k e l 矩阵与向量的乘积a q 七利用算法2 可知矩阵l a n c z o s 三对角 化算法的计算复杂度为o ( n 2l o gn ) 2 5 复正交对角化 我们的下任务是利用q r 迭代算法把个复对称三对角矩阵约化成 对角矩降般地，我们采用带w i l k i n s o n 位移的隐式q r 算法( 见文献 【2 0 】) ，并且在迭代的过程中用复正交变换来取代酉变换这里记 l c n 一1 ：n ，n 一：n ，= ( 五：1j 厶- m l , n ) 算法4 ( 复对称q r 算法) 给定个n 阶复对称三对角矩阵正首先计 算q t j q ，然后把得到结果赋给- ，不断循环计算，即，= q t j q 其中q 为若干个复正交矩阵的乘积 初始化q = ，； 计算矩阵l 且逼近厶n 的个特征值p 令z 1 = j 1 1 一p ；x 22j 2 1 ； 计算复正交矩阵昭( 应用算法1 ) 利用z 。取代z 。 j = g ：k j g k ； q = q g k ； x l = + l 。k ；x 2 = + 2 k ； 一 茎三主塾整垒望生! 兰型坚! ：! 墅生! 堑堕壁垒焦箜：塞造墨鎏 1 1 2 6 算法与数值实验 根据前面所述，我们就可以得到个计算n 阶t o e p l i t z - p l u s - h s n k e l 矩 阵特征值的算法，它的计算复杂度为o ( n 2l o gn ) 算法5 ( 快速t o e p l i t z - p l u s - h a n k e l 矩阵特征值算法) ( 1 ) 利用算法3 三对角化矩阵a 在算法3 中计算对称t o e p l i t z - p l u s - h a n k e l 矩阵与向量的乘积时运用算法2 ( 2 ) 利用带w i l k i n s o n 位移的隐式q r 算法把个复对称三对角矩阵约 化成对角矩阵，计算过程应用算法4 例1 令n = 4 ，对称t o e p l i t z - p l u s - h a n k e l 矩阵为 厂5 5 o 54 5 0 5 、厂n 5 4 50 5 7 与、 a = 卜i 三：奠；篡i + l 兰尝羔尝1 一o 5 4 5o 5 5 5 ，7 5 一o 54 5o 5 针对这一问题，分别采用本文的算法、m a t l a b 的工具函数e i g ( ) 计算矩阵a 的特征值，计算结果如下表所示计算中取计算精度为= 1 1 0 1 4 这里假设m a t l a b 的工具函数e i g ( ) 计算的特征值是充分地精确，经由 计算误差公式 腑r = 我们发现计算误差为1 0 。t ，可以看出我们的算法可以正确地计算出对称 t o e p l i t z - p l u s - h a n k e l 矩阵的特征值 第三章实h a n k e l - c i r c u l a a t 和h a n k e l - s k e w - c i r c u l a n t 矩阵的奇异值分解 1 2 第三章实h a n k e l - c i r c u l a n t 和h a n k e l s k e w c i r c u l a n t 矩阵的奇异值分解 3 1 引言 h a n k e l 矩阵是类非常重要的结构矩阵，它的奇异值分解在众多的领 域有着广泛的应用，例如物理学，图像处理，系统论等等，详见文【21 11 2 2 2 3 】 等由于h a n k e l 矩阵是对称矩阵，从而实h a n k e l 矩阵的特征值总是实数 本文给出了与h a n k e l 矩阵相关的两子类矩阵( 即为实h a n k e l c i r c u l a n t 和 h a n k e l s k e w c i r c u l a n t 矩阵) 的奇异值分解的显式表达式，为我们的理论研 究提供重要基础 定义3 1 1n 阶h a n k e l - c i r c u l a n t 矩阵定义如下： 风= 日c ( ， l ，h 一1 ) = h n 一2h n h n 一1 h o h 一4h 九一 h n 一3h n 一 定义3 1 2n 阶h a n k e l s k e w - c i r c u l a n t 矩阵定义如下： 矾：风。危，：r耋：芝；豢：兰：、， ( 2 3 ) ( 2 4 ) 显然，h a n k e l - c i r c u l a n t 矩阵和h a n k e l - s k e w - c i r c u l a n t 矩阵完全由它的第一 列元素确定它们是两类特殊的h a n k e l 矩阵根据上述定义，我们容易 得到下面的分解定理 m 胁； 舻加 肺胁； 胁舻 第三章实h a n k e l - c i r c u l a n t 和h a n k e l - s k e w - c i r c u l a n t 矩阵的奇异值分解 1 3 定理3 1 3 每个h a n k e l 矩阵都可以分裂成个h a n k e l - c i r c u l a n t 矩 阵与个h a n k e l - s k e w - c i r c u l a n t 矩阵之和，即日= 阢+ 风： h c = 盎q 垒n垒! 垒卫士垒2 = 2 垒2 墨：21 垒! = 呈 2222 垒! 垒2 !垒2 垒盐2 皇! ! ：三皇丑j 堕皿 2 22 2 耻慷2 _ f i n 一1 2 u o + h 2 f h 一2 一 2 h 一2 2 h n 一1 2 这里也是h a n k e l - c i r c u l a n t 矩阵，凰是h a n k e l s k e w - c i r c u l a n t 矩阵 记j 为单位矩阵，而记 j ：f ； l 。 | 1 0 o1 0 10 1 o0 0 00 容易验证有产= ， = ( ：0 。) 是正交矩阵容易验证有n = f = f 2 在这里我们给出几个重要的引理： 引理3 1 4 任给k 个复数o t l ：o t 2 ，o t 七，且a j 0 ，0 2 7 r ，歹= 1 ，2 ，k 若后阶复矩阵 e ：娑舭夕( e 警，e 孚) ， = 乃e 竹，其中勺2 兰：耋：苫。 一：一。一： 辜 薹。字学 第三章实h a r t k e l - c i r c u l a n t 和h a n k e l - s k c w - c i r c u l a n t 矩阵的奇异值分解 1 4 和2 七阶复矩阵 则有硝风= 1 2 七， 风= 旧- ! 箍) c 2 k 2 k ，l k e t i k e i kl 1 2 k d i a g ( a l ，o l k ，a k ，a 1 ) 凰= r o d i a g ( r l ，r k ，一r 七， 证明：( i ) 若要证明础风= ，则可等价转化为