（計(jì)算數(shù)學(xué)專業(yè)論文）幾類結(jié)構(gòu)矩陣的譜問題.pdf

幾類結(jié)構(gòu)矩陣的譜問題 u l 摘要 眾所周知，在工程計(jì)算和實(shí)際應(yīng)用中有許多問題最終都?xì)w結(jié)為矩陣計(jì)算問題，而 且不同的應(yīng)用會(huì)導(dǎo)出些具有特殊結(jié)構(gòu)的矩降i 博最常見的些結(jié)構(gòu)矩陣有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 】 等等處理與這些結(jié)構(gòu)矩陣有關(guān)的矩陣計(jì)算問題( 例如計(jì)算特征值、求解線性方程組 等) ，若矩陣的階數(shù)較小時(shí)，通常的經(jīng)典算法是可行的( 例如l u 分解算法、q r 算法 等) 然而，在許多實(shí)際應(yīng)用當(dāng)中，矩陣的階數(shù)仃很大( n 1 0 6 1 0 9 ) 或某個(gè)線性方 程組需要多次計(jì)算直到得到個(gè)滿意的結(jié)果( 例如迭代法時(shí)) ，此時(shí)這些經(jīng)典的算法 由于代價(jià)太大而失去了實(shí)際意義 因此，針對(duì)這些結(jié)構(gòu)矩陣的特點(diǎn)而設(shè)計(jì)些能利用它們的結(jié)構(gòu)的，數(shù)值穩(wěn)定的快 速算法，具有非常重要的意義正因?yàn)榻Y(jié)構(gòu)矩陣在實(shí)際應(yīng)用中所具有的重要意義，國 內(nèi)外眾多的學(xué)者將目光投入到這領(lǐng)域結(jié)構(gòu)矩陣的快速算法中最著名的莫過于快 速傅里葉變換( 即f f t ) ，有許多胬彭享法均是由快速傅里葉變換導(dǎo)出的因此，著 名數(shù)學(xué)家c h a r l e sv a nl o a n 曾這樣評(píng)價(jià)快速傅里葉變換算法： “從計(jì)算的角度看， 快速傅里葉變換是本世紀(jì)最杰出的成就之一，毫不夸張地說，快速傅里葉變換改變 了科學(xué)與工程計(jì)算的面貌，如果沒有它，生活將會(huì)是另種景象” 本論文主要研究了實(shí)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 矩陣的奇異值分 解，給出了對(duì)稱t o e p l i t z - p l u s - h a n k e l 矩陣特征值的快速算法和這個(gè)計(jì)算矩陣特征值 算法的數(shù)值實(shí)驗(yàn)理論和數(shù)值實(shí)驗(yàn)顯示，這個(gè)僥速算法是行之有效的 第章，我們簡(jiǎn)單介紹了研究結(jié)構(gòu)矩陣決速算法的現(xiàn)實(shí)意義，研究概況以及常 用的研究方法，同時(shí)也給出了與本論文有關(guān)的幾類結(jié)構(gòu)矩陣的定義及其基本性質(zhì) 第二章，我們給出了n 階對(duì)稱t o e p l i t z - p l u s - h a n k e l 矩陣與個(gè)佗維向量乘積的 快速算法；并利用他階矩陣的對(duì)稱陛，對(duì)其實(shí)施l a n c z o s 三對(duì)角化和q r 對(duì)角化， 計(jì)算出矩陣的所有特征值該算法的計(jì)算復(fù)雜度為d ( n 2l o gn ) 第三章，我們研究了實(shí)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 矩陣的關(guān)系，并給出了它們的奇異值分解，為我們研究實(shí)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 矩陣的奇異值分解提供了理論基礎(chǔ) 關(guān)鍵詞：結(jié)構(gòu)矩陣；快速算法；t o e p l i t z 矩陣；h a n k c l 矩陣；對(duì)稱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 廈門大學(xué)學(xué)位論文原創(chuàng)性聲明 茲呈交的學(xué)位論文，是本人在導(dǎo)師指導(dǎo)下獨(dú)立完成的研 究成果。本人在論文寫作中參考的其它個(gè)人或集體的研究成 果，均在文中以明確方式標(biāo)明本人依法享有和承擔(dān)由此論 文而產(chǎn)生的權(quán)利和責(zé)任 責(zé)任人c 簽孫慨司 刪月；o 日 廈門大學(xué)學(xué)位論文著作權(quán)使用聲明 本人完全了解廈門大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定。 廈門大學(xué)有權(quán)保留并向國家主管部門或其指定機(jī)構(gòu)送交論文 的紙質(zhì)版和電子版，有權(quán)將學(xué)位論文用于非贏利目的的少量 復(fù)制并允許論文進(jìn)入學(xué)校圖書館被查閱，有權(quán)將學(xué)位論文的 內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，有權(quán)將學(xué)位論文的標(biāo)題和摘 要匯編出版。保密的學(xué)位論文在解密后適用本規(guī)定。 本學(xué)位論文屬于 1 、保密() ，在年解密后適用本授權(quán)書 2 、不保密( 一 ( 請(qǐng)?jiān)谝陨舷鄳?yīng)括號(hào)內(nèi)打” ”) 日期：蜥j 月弘日 嗍。勿承廣f 月妒 第一章緒論 第一章緒論 1 1 引言 眾所周知，在工程和實(shí)際應(yīng)用中有許多問題最終都?xì)w結(jié)為矩陣計(jì)算問 題，而且有許多應(yīng)用需要計(jì)算的矩陣是一些具有特殊結(jié)構(gòu)的矩陣 最常見的些結(jié)構(gòu)矩陣有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 瓦】等等我們知道，處理與這些結(jié)構(gòu)矩 陣有關(guān)的矩降汁算問題( 例如計(jì)算特征值、求解線性方程組等) ，若矩陣的 階數(shù)較小時(shí)，通常的經(jīng)典算法是可行的然而，在許多實(shí)際應(yīng)用當(dāng)中，矩 陣的階數(shù)很大，此時(shí)這些經(jīng)典的算法由于未充分利用這些矩陣的結(jié)構(gòu)，計(jì) 算花費(fèi)代價(jià)太大而失去了實(shí)際意義因此，針對(duì)這些結(jié)構(gòu)矩陣的特點(diǎn)而設(shè) 計(jì)些數(shù)值穩(wěn)定的快速，超央速的數(shù)值算法，具有非常重要的意義 提到快速算法，最著名的莫過于陜速傅里葉變換( 即f f t ) ，有許多快 速算法均是由快速傅里葉變換導(dǎo)出的因此，著名數(shù)學(xué)家c h a r l e sv a nl o a n 曾這樣評(píng)價(jià)快速傅里葉變換算法：“從計(jì)算的角度看，快速傅里葉變換是 本世紀(jì)最杰出的成就之一，毫不夸張地說，快速傅里葉變換改變了科學(xué)與 工程計(jì)算的面貌，如果沒有它，生活將會(huì)是另一種景象”有許多經(jīng)典的 快速算法都因此誕生在本論文中，第二章所給的快速算法也都號(hào)決速傅 里葉變換有關(guān) 正因?yàn)榻Y(jié)構(gòu)矩陣在實(shí)際應(yīng)用中e 獬的重要意義，國內(nèi)外眾多的學(xué)者 將目光投入到這領(lǐng)域目前，在國外已經(jīng)出現(xiàn)了多個(gè)研究群體，主要有 以t h o m a sk a i l a t h 為代表的研究群體( 位移秩方法) ；以g e o r gh e i n i g 為 代表的研究群體( 四種基本類型位移結(jié)構(gòu)矩陣的計(jì)算，矩陣廣義逆的位移 結(jié)構(gòu)) ；以v i c t o ry p a n 為代表的研究群體( 多項(xiàng)式與結(jié)構(gòu)矩陣的計(jì)算，牛 頓結(jié)構(gòu)迭代算法) ；以v a d i mo l s h e v s k y 為代表的研究群體( 有理插值與結(jié) 構(gòu)矩陣的快速算法的研究) 等在國內(nèi)，許多學(xué)者也在相關(guān)課題上做了大 量的研究工作，西安交通大學(xué)的游兆勇、李磊、路浩等在t o e p l i t z 矩陣、 c i r c u l a n t 矩陣求逆的快速算法與復(fù)雜性分析方面；西北工業(yè)大學(xué)的徐仲、 第一章緒論 張凱院、陸全等在v a n d e r m o n d e 、t o e p l i t z 矩陣類的快速算法方面；中國 科學(xué)院數(shù)學(xué)機(jī)械研究中心的支麗紅在符號(hào)與數(shù)值的混合計(jì)算方面 本節(jié)將給出本文所涉及到的幾類結(jié)構(gòu)矩陣的定義及相關(guān)的性質(zhì)，其中 的性質(zhì)均只列出參考文獻(xiàn)而不給出證明 定義1 2 1n 階f o u r i e r 矩陣定義如下： f ，要1 耍1 蔞1 ：喜、 f 麗萬 麗 麗 1 l lu護(hù) u n 以i i 麗麗 而萬 i r = i 擊岳長(zhǎng)弋w 2 ( n 礦- 1 ) i ， ( 1 ) l 妻毒殺! 每j 其中u = e 掣，i 為虛數(shù)單位 另介紹與n 階f o u r i e r 矩陣有緊密聯(lián)系的矩陣 ( g ) 職= 弓去擴(kuò)門+ 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 矩陣是酉矩陣，是對(duì)稱矩陣個(gè)f o u r i e r 矩陣乘 以個(gè)向量相當(dāng)于對(duì)這一向量作離散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 對(duì)長(zhǎng)度為n 的向量作離散f o u r i c r 變換及逆離散f o u r i e r 變 換所需的運(yùn)算量及存儲(chǔ)空間均為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 設(shè)計(jì)結(jié)構(gòu)矩陣快速算法的常用方法及本文的結(jié)構(gòu) 研究結(jié)構(gòu)矩陣的快速算法有著悠久的歷史，相關(guān)的文獻(xiàn)非常之多然 而常用的研究方法不外乎以下幾種： 1 、利用快速傅里葉變換( f f t ) 2 、利用結(jié)構(gòu)矩陣的特殊結(jié)構(gòu)，構(gòu)造出相應(yīng)的遞歸關(guān)系例如文獻(xiàn)【2 j 和【3 1 3 、位移結(jié)構(gòu)理論，詳見文獻(xiàn)【4 】和【5 】- 4 、利用結(jié)構(gòu)矩陣與多項(xiàng)式插值之間的關(guān)系，見文獻(xiàn)【6 】 本文給的快速算法所用的研究方法主要是前兩種，在第二章中，我們 給出了n 階對(duì)稱t o e p l i t z - p l u s - h a n k e l 矩陣與個(gè)n 維向量乘積的快速算 法；并利用其對(duì)稱性，對(duì)其實(shí)施l a n c z o s 三對(duì)角化和q r 對(duì)角化，計(jì)算出 矩陣的所有特征值，該算法的計(jì)算復(fù)雜度為o ( n 2l o g 禮) 第三章，我們研究了實(shí)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 矩陣的關(guān)系，并給出了它們的奇異值分解，為我們研究實(shí)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 矩陣奇異值分解提供了理論基礎(chǔ) 墨三主壁整堡望絲生趔堅(jiān)蘭：i 塑型塹生壁壘焦笪：睦鯊墨叁 4 第二章對(duì)稱t o e p l i t z p l u s - h a n k e l 矩陣特征值的快速算法 結(jié)構(gòu)矩陣的特征值問題在科學(xué)與工程計(jì)算、圖像和信號(hào)處理領(lǐng)域中有 著重要的應(yīng)用，已引起不少學(xué)者的關(guān)注( 見文獻(xiàn)【7 1 【8 1 【9 1 【1 0 】【1 1 】【1 2 1 1 3 】) 然 而對(duì)于t o e p l i t z - p l u s - h a n k e l 矩陣的特征值，相應(yīng)的數(shù)值算法涉及很少，有 文獻(xiàn)【1 4 】本章主要介紹求對(duì)稱t o e p l i t z - p l u s - h a n k e l 矩陣特征值問題的一 種算法 2 1 復(fù)對(duì)稱 首先我們的想法是利用對(duì)稱t o e p l i t z - p l u s h a n k e l 矩陣的對(duì)稱性這里 不妨記幾階對(duì)稱t o e p l i t z - p l u s - h a n k e l 矩陣為a ，假設(shè)a 為非虧損矩陣，則 矩陣a 的特征值分解為 a = x d x ， ( 5 ) 其中d 為對(duì)角矩陣，x 為非奇異矩陣這里取x 為復(fù)正交矩陣，即 x x 丁= ， ( 6 ) 因此a = x d x t 首先對(duì)矩陣a 實(shí)施l a n c z o s 三對(duì)角化，則有 a = q j q t ，( 7 ) 其中q 為復(fù)正交矩陣，j 為復(fù)對(duì)稱三角矩陣再對(duì)矩陣，實(shí)施對(duì)角化， 得 j = w d w r ，( 8 ) 其中彤為復(fù)正交矩陣，d 為對(duì)角矩陣因而我們可得( 5 ) 式，并且有 x = q w ( 9 ) 我們知道l a n c z o s 算法主要運(yùn)算量是計(jì)算矩陣與向量的乘積般來說，n 階矩陣與向量的計(jì)算復(fù)雜度為d ( n 2 ) 這里我們基于l a n c z o s 算法原理，提 出一種陜速計(jì)算幾階對(duì)稱t o e p l i t z p l u s h a n k e l 矩陣與向量的乘積的算法， 它的計(jì)算量只需o ( nl o gn ) 因而我們對(duì)禮階對(duì)稱t o e p l i t z - p l u s - h a n k e l 矩陣 第二章對(duì)稱t o e p l i t z - p l u s - h a n k e l 矩陣特征值的快速算法 5 實(shí)施l a n c z o s 三對(duì)角化，所需的計(jì)算復(fù)雜度為o ( n 2l o g n ) 上述得到的三 對(duì)角矩陣具有復(fù)對(duì)稱性，為了保持它的對(duì)稱| 生和三對(duì)角結(jié)構(gòu)，我們?cè)趒 r 迭代過程中采用復(fù)正交變換 2 2 復(fù)正交變換 在計(jì)算矩陣特征值問題過程中，我們利用2 階復(fù)正交陣將2 維向量化 為( 1 2 ) 式根據(jù)( 6 ) 式，我們提供兩種2 階復(fù)正交矩陣的般形式 其中c 24 - s 2 = 若( 1 0 ) 式矩陣 2 維復(fù)向量 其中z ；4 - z ； g = ( _ 二s ：) ，( ：二c ) ， g = ) ， 元素為實(shí)數(shù)，則它就成為g i v e n s 旋轉(zhuǎn)變換對(duì)于給定的一 x = ( 三：) ， c 1 1 ， ( 紫) ， 算法1 ( 復(fù)正交變換) 給定一2 維復(fù)向量x ( 見( 1 1 ) 式) ，現(xiàn)利用該算法 計(jì)算復(fù)正交變換矩陣( 見( 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 這個(gè)算法將應(yīng)用到本章第5 小節(jié)有關(guān)矩陣的復(fù)正交對(duì)角化的計(jì)算過程中 墨三主壁整望! 鯉! 竺垡堅(jiān)堂望塑絲! 塹墮壁堡焦箜：堡鎏墨盤 6 2 3 計(jì)算對(duì)稱t o e p l i t z - p l u s - h a n k e l 矩陣與向量的乘積 現(xiàn)描述一禮階t o e p l i t z - p l u s - h a n k e l 矩陣與任一他維向量的乘積的一種 快速算法，即計(jì)算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 ) 就轉(zhuǎn)化成個(gè)n 階t o e p l i t z 矩陣和個(gè)n 階h a n k e l 矩陣分別與一佗維向 量的乘積計(jì)算 這里記i i 為n 扎階的置換矩陣，即 i i = 由t o e p l i t z 矩陣與h a n k e l 矩陣的結(jié)構(gòu)特點(diǎn)，可得 h i i = n ， ( 1 4 ) 其中瓦為t o e p l i t z 矩陣因而( 1 3 ) 式可轉(zhuǎn)化為 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 矩陣與向量和乘積計(jì)算下面我們以 ( 1 4 ) 式的t o e p l i t z 矩陣瓦為例我們將它嵌入個(gè)( 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 強(qiáng)酣頃序主子陣即為t o e p l i t z 矩陣a 。 給定個(gè)n 維的向量 計(jì)算矩陣向量的積 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 為向量溉的前孔個(gè)分量，其中 y h 三甌( e h l l 玩 由于循環(huán)矩陣與向量的積可以利用f f t 來計(jì)算( 見文【1 7 】) ，即 既( e ) 玩= i f f t ( f f t ( d ) 術(shù)，t ( 莎) ) ， ( 1 7 ) ( 1 8 ) ( 1 9 ) 加加； 。腑k ； l 2 凡 危k m 拋蛔 一 一 n 脅艫k ； 一 n + 脅h 腑； n + + k m 腑； h k ； 第二章對(duì)稱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 ，的遞惠傅里葉變換， “翱表示兩個(gè)向量對(duì)應(yīng)元素的積由 于，t ( 口) 的計(jì)算復(fù)雜度為o ( nl o gn ) 注1 ：通過將t o e p l i t z 矩陣夠扒到個(gè)循環(huán)矩陣中而設(shè)計(jì)陜速算法的 思想廣泛應(yīng)用于預(yù)條件方法中( 見文【1 8 】和文【1 9 1 ) 由引理2 ，可以得到如下算法： 算法2 ( 計(jì)算對(duì)稱t o e p l i t z - p l u s - h a n k e l 矩陣與向量的乘積) 該算法利用 f f t 計(jì)算一n 維向量l ，與n n 階對(duì)稱t o e p l i t z - p l u s - h a n k e l 矩陣的乘積： ( 1 ) 定義兩個(gè)( 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 ) 定義兩個(gè)( 2 n 一1 ) 維的向量如和仇，其中 玩= ( 一l n0 0 ) ，仇= ( 1 1 屹0 0 ) ( 3 ) 由下列公式計(jì)算y 和y 。： y h = i f f t ( f f t ( e h ) 術(shù)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 三對(duì)角化 在本節(jié)中，利用l a n c z o s 迭代過程推導(dǎo)出將對(duì)稱t o e p l i t z - p l u s - h a n k e l 矩陣轉(zhuǎn)化成個(gè)對(duì)稱三對(duì)角矩陣的方法我們的目標(biāo)是尋找一個(gè)復(fù)正交矩 陣q 使得( 7 ) 式成立，即 a q = q j ( 2 0 ) 令 q = ( q l ，q 2 ，q 3 ) ， g ：- 章對(duì)稱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 風(fēng)一1q n ( 2 1 ) 比較( 2 0 ) 式左右兩邊矩陣的第尼列，有 a 毗= 風(fēng)一l 毗一l + q k 毗+ 反毗+ 1 ， ( 2 2 ) 其中& q o = 0 ，風(fēng)q n + 1 = 0 因?yàn)閝 是復(fù)正交矩陣，即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 三對(duì)角化的算法這里只用 到t o e p l i t z - p l u s - h a n k e l 矩陣的復(fù)對(duì)稱性 算法3 ( l a n c z o s 三對(duì)角化) 給定個(gè)n 階復(fù)對(duì)稱矩陣a ，現(xiàn)要計(jì)算個(gè) 復(fù)正交矩陣q 使得a = q j q r ，其中j 是個(gè)復(fù)對(duì)稱三對(duì)角矩陣，見( 2 1 ) 式 初始化q 1 使得酊q l = 1 ； 令r o = q l ；風(fēng)= 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 ； 第二章對(duì)稱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 將運(yùn)行到k = 仃該算法的主要計(jì)算量是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 三對(duì)角 化算法的計(jì)算復(fù)雜度為o ( n 2l o gn ) 2 5 復(fù)正交對(duì)角化 我們的下任務(wù)是利用q r 迭代算法把個(gè)復(fù)對(duì)稱三對(duì)角矩陣約化成 對(duì)角矩降般地，我們采用帶w i l k i n s o n 位移的隱式q r 算法( 見文獻(xiàn) 【2 0 】) ，并且在迭代的過程中用復(fù)正交變換來取代酉變換這里記 l c n 一1 ：n ，n 一：n ，= ( 五：1j 厶- m l , n ) 算法4 ( 復(fù)對(duì)稱q r 算法) 給定個(gè)n 階復(fù)對(duì)稱三對(duì)角矩陣正首先計(jì) 算q t j q ，然后把得到結(jié)果賦給- ，不斷循環(huán)計(jì)算，即，= q t j q 其中q 為若干個(gè)復(fù)正交矩陣的乘積 初始化q = ，； 計(jì)算矩陣l 且逼近厶n 的個(gè)特征值p 令z 1 = j 1 1 一p ；x 22j 2 1 ； 計(jì)算復(fù)正交矩陣昭( 應(yīng)用算法1 ) 利用z 。取代z 。 j = g ：k j g k ； q = q g k ； x l = + l 。k ；x 2 = + 2 k ； 一 莖三主塾整壘望生! 蘭型堅(jiān)! ：! 墅生! 塹墮壁壘焦箜：塞造墨鎏 1 1 2 6 算法與數(shù)值實(shí)驗(yàn) 根據(jù)前面所述，我們就可以得到個(gè)計(jì)算n 階t o e p l i t z - p l u s - h s n k e l 矩 陣特征值的算法，它的計(jì)算復(fù)雜度為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 三對(duì)角化矩陣a 在算法3 中計(jì)算對(duì)稱t o e p l i t z - p l u s - h a n k e l 矩陣與向量的乘積時(shí)運(yùn)用算法2 ( 2 ) 利用帶w i l k i n s o n 位移的隱式q r 算法把個(gè)復(fù)對(duì)稱三對(duì)角矩陣約 化成對(duì)角矩陣，計(jì)算過程應(yīng)用算法4 例1 令n = 4 ，對(duì)稱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 針對(duì)這一問題，分別采用本文的算法、m a t l a b 的工具函數(shù)e i g ( ) 計(jì)算矩陣a 的特征值，計(jì)算結(jié)果如下表所示計(jì)算中取計(jì)算精度為= 1 1 0 1 4 這里假設(shè)m a t l a b 的工具函數(shù)e i g ( ) 計(jì)算的特征值是充分地精確，經(jīng)由 計(jì)算誤差公式 腑r = 我們發(fā)現(xiàn)計(jì)算誤差為1 0 。t ，可以看出我們的算法可以正確地計(jì)算出對(duì)稱 t o e p l i t z - p l u s - h a n k e l 矩陣的特征值 第三章實(shí)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 第三章實(shí)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 矩陣是類非常重要的結(jié)構(gòu)矩陣，它的奇異值分解在眾多的領(lǐng) 域有著廣泛的應(yīng)用，例如物理學(xué)，圖像處理，系統(tǒng)論等等，詳見文【21 11 2 2 2 3 】 等由于h a n k e l 矩陣是對(duì)稱矩陣，從而實(shí)h a n k e l 矩陣的特征值總是實(shí)數(shù) 本文給出了與h a n k e l 矩陣相關(guān)的兩子類矩陣( 即為實(shí)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 矩陣) 的奇異值分解的顯式表達(dá)式，為我們的理論研 究提供重要基礎(chǔ) 定義3 1 1n 階h a n k e l - c i r c u l a n t 矩陣定義如下： 風(fēng)= 日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 矩陣定義如下： 礬：風(fēng)。危，：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 矩陣根據(jù)上述定義，我們?nèi)菀?得到下面的分解定理 m 脅； 艫加 肺脅； 脅艫 第三章實(shí)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 每個(gè)h a n k e l 矩陣都可以分裂成個(gè)h a n k e l - c i r c u l a n t 矩 陣與個(gè)h a n k e l - s k e w - c i r c u l a n t 矩陣之和，即日= 阢+ 風(fēng)： 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 容易驗(yàn)證有產(chǎn)= ， = ( ：0 。) 是正交矩陣容易驗(yàn)證有n = f = f 2 在這里我們給出幾個(gè)重要的引理： 引理3 1 4 任給k 個(gè)復(fù)數(shù)o t l ：o t 2 ，o t 七，且a j 0 ，0 2 7 r ，歹= 1 ，2 ，k 若后階復(fù)矩陣 e ：娑舭夕( e 警，e 孚) ， = 乃e 竹，其中勺2 蘭：耋：苫。 一：一。一： 辜 薹。字學(xué) 第三章實(shí)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 七階復(fù)矩陣 則有硝風(fēng)= 1 2 七， 風(fēng)= 舊- ! 箍) 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 ) 若要證明礎(chǔ)風(fēng)= ，則可等價(jià)轉(zhuǎn)化為