（計算數學專業(yè)論文）幾類結構矩陣的譜問題.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 ) 或某個線性方 程組需要多次計算直到得到個滿意的結果( 例如迭代法時) ，此時這些經典的算法 由于代價太大而失去了實際意義 因此，針對這些結構矩陣的特點而設計些能利用它們的結構的，數值穩(wěn)定的快 速算法，具有非常重要的意義正因為結構矩陣在實際應用中所具有的重要意義，國 內外眾多的學者將目光投入到這領域結構矩陣的快速算法中最著名的莫過于快 速傅里葉變換( 即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 廈門大學學位論文原創(chuàng)性聲明 茲呈交的學位論文，是本人在導師指導下獨立完成的研 究成果。本人在論文寫作中參考的其它個人或集體的研究成 果，均在文中以明確方式標明本人依法享有和承擔由此論 文而產生的權利和責任 責任人c 簽孫慨司 刪月；o 日 廈門大學學位論文著作權使用聲明 本人完全了解廈門大學有關保留、使用學位論文的規(guī)定。 廈門大學有權保留并向國家主管部門或其指定機構送交論文 的紙質版和電子版，有權將學位論文用于非贏利目的的少量 復制并允許論文進入學校圖書館被查閱，有權將學位論文的 內容編入有關數據庫進行檢索，有權將學位論文的標題和摘 要匯編出版。保密的學位論文在解密后適用本規(guī)定。 本學位論文屬于 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 瓦】等等我們知道，處理與這些結構矩 陣有關的矩降汁算問題( 例如計算特征值、求解線性方程組等) ，若矩陣的 階數較小時，通常的經典算法是可行的然而，在許多實際應用當中，矩 陣的階數很大，此時這些經典的算法由于未充分利用這些矩陣的結構，計 算花費代價太大而失去了實際意義因此，針對這些結構矩陣的特點而設 計些數值穩(wěn)定的快速，超央速的數值算法，具有非常重要的意義 提到快速算法，最著名的莫過于陜速傅里葉變換( 即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 矩陣求逆的快速算法與復雜性分析方面；西北工業(yè)大學的徐仲、 第一章緒論 張凱院、陸全等在v a n d e r m o n d e 、t o e p l i t z 矩陣類的快速算法方面；中國 科學院數學機械研究中心的支麗紅在符號與數值的混合計算方面 本節(jié)將給出本文所涉及到的幾類結構矩陣的定義及相關的性質，其中 的性質均只列出參考文獻而不給出證明 定義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 小節(jié)有關矩陣的復正交對角化的計算過程中 墨三主壁整望! 鯉! 竺垡堅堂望塑絲! 塹墮壁堡焦箜：堡鎏墨盤 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 的循環(huán)矩陣中，即 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 容易看出，循環(huán)矩陣的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 玩 由于循環(huán)矩陣與向量的積可以利用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 矩陣夠扒到個循環(huán)矩陣中而設計陜速算法的 思想廣泛應用于預條件方法中( 見文【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 三對角化 在本節(jié)中，利用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 ，然后把得到結果賦給- ，不斷循環(huán)計算，即，= 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 = 我們發(fā)現計算誤差為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壘! 壘衛(wèi)士壘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 ) 若要證明礎風= ，則可等價轉化為