（計(jì)算數(shù)學(xué)專業(yè)論文）hermitian+toeplitz方程組快速算法的研究.pdf

摘要 結(jié)構(gòu)矩陣的理論和算法研究是近年來(lái)的個(gè)研究熱點(diǎn)，本文主要研究 怎樣用直接法快速求解h e r m i t i a nt o e p l i t z 方程組問題。已有資料顯示， 利用h e r m i t i a nt o e p l i t z 矩陣結(jié)構(gòu)和d f t ，可把h e r m i t i a nt o e p l i t z 矩陣變 換為h e r m i t i a nc a u c h y 矩陣，或利用位移結(jié)構(gòu)和置換矩陣，可把h e r m i t i a n t o e p l i t z 矩陣變換為實(shí)c a u c h y 矩陣。本文首先利用中心h e r m i t i a n 矩陣的 約化性質(zhì)，通過一個(gè)簡(jiǎn)單的酉變換把一個(gè)h e r m i t i a nt o e p l i t z 矩陣相似為 一個(gè)實(shí)對(duì)稱的t o e p l i t z 矩陣加上一個(gè)實(shí)h a n k e l 矩陣，然后利用d f t 把一 個(gè)實(shí)對(duì)稱的t o e p l i t z + h a n k e l 矩陣變?yōu)橐粋€(gè)實(shí)對(duì)稱的c a u c h y 矩陣。 雖然已有作者給出了求解t o e p l i t z + h a n k e l 方程組的快速算法，但是這 些算法欠缺穩(wěn)定性，所以這里我們主要研究基于實(shí)對(duì)稱c a u c h y 矩陣快速 分解的h e r m i t i a nt o e p l i t z 方程組快速算法，研究表明，我們的算法更加 穩(wěn)定。 本文共分為五章，主要內(nèi)容如下： 第一章為緒論，主要介紹了本論文的研究背景和選題依據(jù)，以及研究 內(nèi)容和創(chuàng)新。 第二章主要介紹了一些在本文中要用到的基本概念和符號(hào)表示。 第三章首先綜述了利用不同的變換把h e r m i t i a nt o e p l i t z 矩陣變換為 h e r m i t i a nc a u c h y 矩陣和實(shí)c a u c h y 矩陣。然后研究了利用酉變換把 h e r m i t i a nt o e p l i t z 矩陣變換成t o e p l i t z + h a n k e l 矩陣，再利用d f t 把 t o e p l i t z + h a n k e l 矩陣變換成實(shí)對(duì)稱c a u c h y 矩陣。 第四章給出了基于實(shí)對(duì)稱c a u c h y 矩陣快速分解的h e r m i t i a nt o e p l i t z 方程組快速算法。 第五章綜述了t o e p l i t z 方程組預(yù)處理方法的最新進(jìn)展，主要?dú)w納了兩 類方法：循環(huán)預(yù)處理方法和非循環(huán)預(yù)處理方法。 關(guān)鍵詞：h e r m i t i a nt o e p l i t z 矩陣；t o e p l i t z + h a n k e l 矩陣；c a u c h y 矩陣； 實(shí)對(duì)稱c a u c h y 矩陣；快速算法 a bs t r a c t t h et h e o r ya n da lg o r i t h m s f o rs t r u c t u r e dm a t r i c e sh a v ei n t r i g u e d r e s e a r c h e r sf o ry e a r s t h i st h e s i sf o c u so nh o wt od e v e l o pf a s t d i r e c t m e t h o d sf o rs o l v i n gh e r m i t i a nt o e p l i t zs y s t e m al a r g el i t e r a t u r e s h o w s t h a ta nh e r m i t i a nt o e p l i t zm a t r i xc a nb em a p p e di n t oa nh e r m i t i a nc a u c h y m a t r i xb ye x p l o i t i n gt h eh e r m i t i a nt o e p l i t z s t r u c t u r ea n dd f t ，o rr e a l c a u c h ym a t r i c e sb ye x p l o i t i n g s h i f ts t r u c t u r ea n dp e r m u t a t i o n i nt h i s t h e s i sw ef i r s te x p l o i tt h er e d u c i b l ep r o p e r t i e so fc e n t r o h e r m i t i a nm a t r i xt o r e d u c ea nh e r m i t i a nt o e p l i t zm a t r i xi n t o ar e a ls y m m e t r i ct o e p l i t z + h a n k e lm a t r i xv i aas i m p l eu n i t a r ys i m il a r i t yt r a n s f o r m a t i o n ，a n dt h e nu s e t h ed f tt ot r a n s f o r mt h i sr e a ls y m m e t r i ct o e p l i t z + h a n k e lm a t r i xi n t oa r e a ls y m m e t r i cc a u c h ym a t r i x t h e r ee x i s ts o m ef a s ta l g o r i t h m sf o rs o l v i n gt h et o e p l i t z + h a n k e ls y s t e m h o w e v e r t h o s ea l g o r i t h m sa r el a c k o fn u m e r i c a ls t a b i l i t y 。t h e r e f o r e w e f h r t h e rs t u d yt h ef a s ta l g o r i t h mf o rt h es o l u t i o no ft h eh e r m i t i a nt o e p l i t z s v s t e mw h i c ha r em a i n l yb a s e do nt h ef a s tf a c t o r i z a t i o no fr e a ls y m m e t r i c c a u c h vm a t r i c e s i ti ss h o w nt h a to u ra l g o r i t h mi s m o r es t a b l et h a nt h e e x i s t e da l g o r i t h m s t h i st h e s i sc o n s i s t so ff i v ec h a p t e r sw h i c ha r eo r g a n i z e da sf o l l o w s ： t h ef i r s tc h a p t e ri sa ni n t r o d u c t i o n w em a i n l yi n t r o d u c et h eb a c k g r o u 。 n d t h em a i nc o n t e n t sa n dt h em o t i v a t i o no ft h e s i s i nt h es e c o n dc h a p t e r ，w eb r i e f l yr e v i e ws o m eb a s i cd e f i n i t i o n sa n d n o t a t i o n sw h i c hw i l lb eu s e di nt h et h e s i s i nt h et h i r dc h a p t e r ，w ef i r s ts u r v e ys o m ev a r i o u st r a n s f o r m a t i o n s w h i c ha r em a p p i n gt h eh e r m i t i a nt o e p l i t zm a t r i c e si n t oh e r m i t i a nc a u c h y m a t r i c e so rr e a lc a u c h ym a t r i c e s t h e nw ec o n s i d e ra n o t h e rw a y ，t h a tl s f i r s tt or e d u c ea nh e r m i t i a nt o e p l i t zm a t r i xi n t oar e a ls y m m e t r i ct o e p l i t z + h a n k e lm a t r i xv i aas i m p l eu n i t a r ys i m i l a r i t yt r a n s f o r m a t i o n ，a n dt h e nt o t r a n s f o r mt h i sr e a ls y m m e t r i ct o e p l i t z + h a n k e lm a t r i xi n t oar e a ls y m m e t 。 r i cc a u c h ym a t r i xv i ad f t i nt h ef o u r t hc h a p t e r ，w ed e v e l o ps t a b l ed i r e c ta l g o r i t h m sf o rs o l v i n g t h eh e r m i t i a nt o e p l i t zs y s t e m ，w h i c h a r eb a s e do nf a s ta n ds t a b l e f a c t o r i z a t i o no fr e a ls y m m e t r i cc a u c h ym a t r i c e s i nt h ef i f t hc h a p t e r ，w er e v i e ws o m en e wp r o g r e s so fp r e c o n d l t l o n l n g n t e c h n i q u e sf o rt o e p l i t zs y s t e m s ，w h i c h c a nb er o u g h l yd i v i d e di n t ot w o c l a s s e s ：c i r c u l a n tp r e c o n d i t i o n e ra n dn o n c i r c u l a n tp r e c o n d i t i o n e r k e yw o r d s ：h e r m i t i a nt o e p l i t zm a t r i x ：t o e p l i t z + h a n k e lm a t r i x ；c a u c h y m a t r i x ；r e a ls y m m e t r i cc a u c h ym a t r i x ：f a s ta l g o r i t h m i i i 長(zhǎng)沙理工大學(xué) 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所 取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任 何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。對(duì)本文的研究做出重要貢 獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本人完全意識(shí)到本聲明的 法律后果由本人承擔(dān)。 作者簽名：權(quán)麥才 日期：別。年歲月訪日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意 學(xué)校保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文 被查閱和借閱。本人授權(quán)長(zhǎng)沙理工大學(xué)可以將本學(xué)位論文的全部或部分內(nèi) 容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存 和匯編本學(xué)位論文。 本學(xué)位論文屬于 l 、保密口，在年解密后適用本授權(quán)書。 2 、不保密團(tuán)。 ( 請(qǐng)?jiān)谝陨舷鄳?yīng)方框內(nèi)打“ ) 作者簽名：狠燾才 導(dǎo)師簽名：勁j ( 、辛厶 日期：堋。年歹月夠日 日期：加f d 年r 月礦日 1 1 研究背景 第一章緒論 矩陣是數(shù)學(xué)上的一個(gè)重要概念，用矩陣的理論和方法來(lái)處理錯(cuò)綜復(fù)雜 的問題，已經(jīng)成為科技領(lǐng)域內(nèi)不可缺少的數(shù)學(xué)工具。 眾所周知，在工程和實(shí)際應(yīng)用中有許多問題最終歸結(jié)為矩陣計(jì)算，結(jié) 構(gòu)矩陣的理論和算法研究是近年來(lái)的一個(gè)研究熱點(diǎn)，有許多實(shí)際應(yīng)用產(chǎn) 生結(jié)構(gòu)矩陣，而利用這些結(jié)構(gòu)矩陣，人們也許能設(shè)計(jì)更快或更精確的算 法。常見的一些結(jié)構(gòu)矩陣有t o e p l i t z 矩陣、h a n k e l 矩陣、v a n d e r m o d e 矩 陣、c a u c h y 矩陣等等。處理這些結(jié)構(gòu)有關(guān)的矩陣計(jì)算問題( 例如，求線性 方程組、特征值問題等) ，若矩陣的階數(shù)較小的時(shí)候，通常的經(jīng)典算法是 可行的( 例如l u 分解算法，q g 算法等) 。然而，許多實(shí)際應(yīng)用中，矩陣的 階數(shù)療很大或某個(gè)線性方程組需要多次計(jì)算直到得到一個(gè)滿意的結(jié)果( 例 如用迭代法時(shí)) ，此時(shí)這些經(jīng)典的算法由于計(jì)算代價(jià)太大而失去實(shí)際意義。 因此，針對(duì)其矩陣結(jié)構(gòu)而設(shè)計(jì)數(shù)字穩(wěn)定、快速、超快速的數(shù)值算法，具 有非常重要的意義。目前，在國(guó)內(nèi)外主要有以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 m o l s h e r v s k y 為代表的研究群體( 有理插值與結(jié)構(gòu)矩陣快速算法的研究) 等。 在國(guó)內(nèi)，許多學(xué)者也在相關(guān)課題上做了大量的研究工作，西安交通大學(xué) 的游兆永、李磊等在t o e p l i t z 矩陣、循環(huán)矩陣求逆的快速算法與復(fù)雜性 分析方面，西北工業(yè)大學(xué)的徐仲、張凱院等在v a n d e r m o d e 、t o e p l i t z 矩 陣類的快速算法方面。結(jié)構(gòu)矩陣中的t o e p l i t z 矩陣在數(shù)值分析、自動(dòng)控 制、數(shù)字信號(hào)處理、譜分析、線性預(yù)測(cè)最小二乘估計(jì)等眾多科學(xué)領(lǐng)域中 廣泛的應(yīng)用，它是應(yīng)用最廣泛的特殊矩陣之一，也是近年來(lái)計(jì)算數(shù)學(xué)研 究較為熱門的一類特殊矩陣。 早期的t o e p l i t z 求解法的研究大多集中在直接方法上，直接應(yīng)用求解 線性代數(shù)系統(tǒng)的經(jīng)典方法g a u s s i a n 消去法求解t o e p l i t z 系統(tǒng)的復(fù)雜度為 o ( n 3 ) 。但是由于t o e p l i t z 矩陣僅由2 n 一1 個(gè)元素決定，所以期望能夠找到 一種復(fù)雜度低于o ( n 3 ) 的t o e p l i t z 求解法，研究人員經(jīng)過努力將t o e p l i t z 求解的復(fù)雜度降到了o ( n 2 ) ，例如l e v i n s o n ( 19 4 6 ) ，t r e n c h ( 19 6 4 ) 和 z o h a r ( 19 7 4 ) 做了不少工作，但要求丁矩陣的刀一l 階主子式可逆。2 0 世紀(jì) 8 0 年代，b r e n t ( 19 8 0 ) 、b i t m e a d ( 19 8 0 ) 、m o r “l(fā)9 8 0 ) 以及a m m a r ( 19 8 8 ) 等， 提出了復(fù)雜度為o ( n l 0 9 2n ) 的快速直接求解t o e p l i t z 方法。然而對(duì)于對(duì)稱 正定t o e p l i t z 矩陣，b u n c h 研究了上述直接求解的穩(wěn)定性，指出當(dāng)矩陣有 奇異或病態(tài)的主子矩陣時(shí)算法會(huì)崩潰，最終導(dǎo)致不精確的計(jì)算結(jié)果，大 量的研究人員研究了如何避開奇異子矩陣或病態(tài)子矩陣從而避免算法崩 潰，特別的c h a n 和h a n s e n ( 19 9 2 ) 首次引進(jìn)l o o k a h e a d 技術(shù)改進(jìn)的 l e v i n s o n 算法。但l o o k a h e a d 技術(shù)改進(jìn)的l e v i n s o n 算法的時(shí)間復(fù)雜度取 決于病態(tài)主子矩陣的數(shù)目而且在最壞的情況下時(shí)間復(fù)雜度為o ( n 3 ) 。 目前，對(duì)t o e p l i t z 矩陣的研究主要集中在兩個(gè)方面：一是研究t o e p l i t z 矩陣本身的數(shù)學(xué)性質(zhì)；二是研究以t o e p l i t z 矩陣為系數(shù)矩陣的線性方程組 的求解問題，以及怎樣用計(jì)算機(jī)來(lái)實(shí)現(xiàn)算法。 關(guān)于t o e p l i t z 矩陣方程組主要有三個(gè)算法：( 1 ) 求解y u l e w a l k e r 問題 的t y = 一阢，】rd u r b i n 算法；( 2 ) 求解一般t o e p l i t z 矩陣線性方程組 t x 。= b 的l e v i n s o n 算法；( 3 ) 計(jì)算逆b = 巧1 的t r e n d 算法。t o e p l i t z 矩陣 有特殊的結(jié)構(gòu)和性質(zhì)也有很好的應(yīng)用，而特殊的t o e p l i t z 矩陣有著自己 特殊的結(jié)構(gòu)和良好的算法。 h e r m i t i a nt o e p l i t z 矩陣是一種特殊的t o e p l i t z 矩陣，它具有t o e p l i t z 矩陣一般的結(jié)構(gòu)性質(zhì)，同時(shí)也有著一些自己特有的結(jié)構(gòu)和性質(zhì)。h e r m i t i a n t o e p l i t z 矩陣的幾種特殊類型在圖像處理中的圖像存儲(chǔ)問題等領(lǐng)域有非 常廣泛的應(yīng)用，但目前有關(guān)h e r m i t i a nt o e p l i t z 方程組的直接法快速算法 研究相對(duì)較少，如果能利用矩陣的這些結(jié)構(gòu)和性質(zhì)，設(shè)計(jì)相關(guān)的算法， 將大大減少它的計(jì)算量。因此，對(duì)h e r m i t i a nt o e p l i t z 矩陣結(jié)構(gòu)和性質(zhì)的 研究以及設(shè)計(jì)相關(guān)此類矩陣的速算法是很有研究?jī)r(jià)值的。 1 2 研究?jī)?nèi)容和創(chuàng)新 1 2 1 研究?jī)?nèi)容 本論文主要研究?jī)?nèi)容如下： 利用簡(jiǎn)單的酉變換把一個(gè)h e r m i t i a nt o e p l i t z 矩陣變換成實(shí)t o e p l i t z 和h a n k e l 矩陣之和，再利用d f t 把實(shí)t o e p l i t z + h a n k e l 矩陣變換成實(shí)對(duì) 稱c a u c h y 矩陣，最后討論了分解實(shí)對(duì)稱c a u c h y 的穩(wěn)定的快速算法。 1 2 2 主要?jiǎng)?chuàng)新 本文利用h e r m i t i a nt o e p l i t z 矩陣的結(jié)構(gòu)和性質(zhì)，通過簡(jiǎn)單的酉變換把 2 h e r m i t i a nt o e p l i t z 矩陣變換成實(shí)t o e p l i t z + h a n k e l 矩陣，再通過d f t 把 t o e p l i t z + h a n k e l 矩陣變換為實(shí)對(duì)稱 c a u c h y 矩陣的快速算法，通過比較， c a u c h y 矩陣，給出了分解實(shí)對(duì)稱 這種算法更穩(wěn)定，且減少了計(jì)算量。 第二章預(yù)備知識(shí)及常見記號(hào) 眾所周知，在工程和實(shí)際應(yīng)用中有許多問題最終都?xì)w結(jié)為矩陣計(jì)算 問題。而且有許多的應(yīng)用需要計(jì)算的矩陣是一些具有特殊結(jié)構(gòu)的矩陣。 在這一節(jié)中，將本文所涉及的有關(guān)概念及性質(zhì)簡(jiǎn)述一下： 定義2 1n 階f o u r i e r 矩陣定義如下： e = 緲2 ( ”- 1 ) 石 其中，i 為虛數(shù)單位即i = 一l 。易知f o u r i e r 矩陣是酉矩陣，即f = f 7 ， 是對(duì)稱矩陣，即f = f r ，且有f 。1 燈= d i a g ( 1 ，國(guó)，緲2 ，c o ”1 ) ，可見 緲，j = 1 , 2 9 * o9 n l 是矩陣k 的刀個(gè)特征值，而，的各列是對(duì)應(yīng)的單位特征正 交特征向量。一個(gè)f o u r i e r 矩陣乘以一個(gè)向量相當(dāng)于對(duì)這一向量作離散的 f o u r i e r 變換( 即d f t ) 。 定義2 2 形如 r = hk = f 2 ，l t o f 一斛3 的力階方陣稱為t o e p l i t z 矩陣，若其元素滿足對(duì)稱關(guān)系， 即 t 一= 0 ( = 1 ，2 ，刀一1 ) ，則稱為對(duì)稱t o e p l i t z 矩陣；如果其元素滿足 t j = t j ( j = 1 ，2 ，刀一1 ) ，則稱為h e r m i t i a nt o e p l i t z 矩陣。t o e p l i t z 矩陣的特 點(diǎn)是主對(duì)角線上的各元素彼此相等，平行于主對(duì)角線的各對(duì)角線上的元 素仍彼此相等。顯然，兩個(gè)刀階t o e p l i t z 矩陣相加和數(shù)乘t o e p l i t z 矩陣， 其結(jié)果還是t o e p l i t z 矩陣。由t o e p l i t z 矩陣的定義可以看出，t o e p l i t z 矩 陣t 是特殊的次對(duì)稱矩陣。若t 是可逆的，r 1 仍是次對(duì)稱的，但它一般不 再是t o e p l i t z 矩陣。 4 去譬等坐石 上石塵再生石； 土石旦石生打；生打上打上石一|石；上打 一 之 o； o“；氣 1 例如：t ：i2 l - 4 2 4 q i 12i ，而r 一= 2li - i 咣 0 一 o 一比 可見t 是對(duì)稱t o e p l i t z 矩陣，但丁一不是t o e p l i t z 矩陣。 定義2 3 給定兩組數(shù)口，島( = l ，2 ，刀) ，且口f 乃，( ，- ，= 1 , 2 ，力) ，稱 矩陣 c - ( 去l 為c a u c h y 矩陣。 定義2 4 給定兩組復(fù)數(shù)c = ( q ) ? 和d = ( 吐) ：i ，有 v ( c ，d ) ( 彳) = ( c ，一d j ) a l ， 為廣義c a u c h y 矩陣。 定義2 5 h = ( 啊鏟- ) = 7 l ih 2h 。 紅嗚 吃+ 。 吃吃+ 。 吃 的對(duì)稱矩陣稱為h a n k e l 矩陣，h a n k e l 矩陣和t o e p l i t z 矩陣有著密切的聯(lián) 系，可以直接驗(yàn)證，若用次單位矩陣j 左乘或右乘h a n k e l 矩陣日，其結(jié) 果或h j 都是t o e p l i t z 矩陣t 。有關(guān)t o e p l i t z 矩陣的一些結(jié)果可以轉(zhuǎn)化 h a n k e l 矩陣的相應(yīng)結(jié)果，求解h a n k e l 矩陣為系數(shù)矩陣的線性方程組 h x = f 也是研究的熱點(diǎn)之一。 定義2 6j 為次單位矩陣 ，= ( e n , e 川，e 1 ) = 可以容易驗(yàn)證j = ，j 2 = j 定義2 7n 階位移矩陣z 砌其中 z l = z 8 。= 00 10 ol ： 0 sl l0 o ：。 o o o 01 00 ： ： 10 j 0 。： 0 01 1 驢 ，z l = 定義2 8 離散的s i n e ( d s t ) 變換為 特別有s = 矽= 0 我們有 s o o 0oo一1 1o00 01； o010 ( s i n - - 玎- 萬(wàn)t t ) ”t ，：1 ，刀 幾_ r 1 z 鼎= 2 d i a g ( c o s 羔：1 ，刀 當(dāng)s = 緲= 1 時(shí)離散的e o s i n e ( d c t - i i ) 變換為 = 伽n 警h = 0 ，朋_ 1 ，z 1 1 s i i = 2 紕( c o s 爭(zhēng)小0 ，朋一1 其中k j2 夕石，_ ，= o 和t 2 l 6 第三章he r m i t ia nt o e p l i t z 矩陣變換 本章首先綜述了利用不同的變換把h e r m i t i a nt o e p l i t z 矩陣變換為 h e r m i t i a nc a u c h y 矩陣和實(shí)c a u c h y 矩陣。然后討論了利用酉變換把 h e r m i t i a nt o e p l i t z 矩陣變換成t o e p l i t z + h a n k e l 矩陣，再利用d f t 把 t o e p l i t z + h a n k e l 矩陣變換成實(shí)對(duì)稱c a u c h y 矩陣。 3 1h e r m i t i a nt o e p l i t z 矩陣變換為h e r m i t i a nc a u c h y 矩陣 我們把h e r m i t i a nt o e p l i t z 矩陣變換為h e r m i t i a nc a u c h y 矩陣，這樣保 持h e r m i t i a n 對(duì)稱性，由位移方程 z z l t z ? = g j g ( 3 1 1 ) 由( 3 1 1 ) 利用d f t 變換f ( ) f 得 f t f 一f z 汪z jf = f g j g f 我們有 f t f 一f z l f f t f f z jf = f g j g f 其中c = 刀f 為h e r m i t i a nc a u c h y 矩陣，我們得到 c k k = g j d 2 廚： 其中人= 忍f ， 人( f ，) = p ”， j = 0 ，擰一l ， 3 2h e r m i t i a nt o e p l i t z 矩陣變換為實(shí)c a u c h y 矩陣 通過位移矩陣z 防和置換矩陣p 把h e r m i t i a nt o e p l i t z 矩陣變換為實(shí) c a u c h y 矩陣；分解c a u c h y 矩陣將是實(shí)運(yùn)算，這樣在存儲(chǔ)量上有很大的改 進(jìn)?？紤]n 階h e r m i t i a nt o e p l i t z 矩陣，t 和z 囂對(duì)應(yīng)的位移方程可以寫為 z j t z 啦= g z g ， 此時(shí)為反對(duì)稱矩陣，g 矩陣秩為4 ，對(duì)于實(shí)對(duì)稱t o e p l i t z 矩陣我們有 邢二r e a l ( t ) s 囂p7 如下形式： p s 二r e a l ( t ) s 囂p r = m 1z ： m ，和m ：是實(shí)對(duì)稱c a u c h y 型矩陣i 量i 。另外，我們易知構(gòu)成t 虛部滿足方 7 程： p s 二h n 昭c 丁，s 掰f r = 羔一詈 心是實(shí)c a u c h y 矩陣且階數(shù)為 蘭 蘭 。 定義3 2 1 矩陣 。= 乞墨 其中厶和1 2 單位矩陣階數(shù)分別為 阱睜，= 仃刪 d p s t t s ，肚瞄 其中 托m 1 篆 是實(shí)c a u c h y 矩陣。 這樣，我們給出了如何把h e r m i t i a nt o e p l i t z 矩陣變換成實(shí)c a u c h y 矩 陣的方法。 3 3h e r m i t i a nt o e p l i t z 矩陣變換為實(shí)對(duì)稱c a u c h y 矩陣 在這一節(jié)里，我們討論如何利用酉變換把h e r m i t i a nt o e p l i t z 矩陣變換 成t o e p l i t z + h a n k e l 矩陣，再利用d f t 變換把t o e p l i t z + h a n k e l 矩陣變換 成實(shí)對(duì)稱c a u c h y 矩陣。 3 3 1h e r m i t i a nt o e p l i t z 矩陣變換為實(shí)t o e p l i t z + h a n k e l 矩陣 對(duì)于一個(gè)n xn 復(fù)矩陣彳，如果有a = 以a j m 成立，稱為中心對(duì)稱矩陣，有 a = 以a j m 成立，稱為中心h e r m i t i a n 矩陣，么是4 的共軛矩陣。對(duì)稱 ( h e r m i t i a n ) t o e p l i t z 矩陣是中心對(duì)稱( h e r m i t i a n ) 矩陣的重要一種類型。我 們只討論n 階方陣的的情況，假設(shè)矩陣彳是n xn 中心h e r m i t i a n 矩陣，其 中n = 2 k ，把彳分解四個(gè)k x k 塊 彳：i 蘭霉- ： l l 以彳1 2 以以a u d 七j 定義3 3 1 1 令 8 q = 铘一以t ( 3 3 小) 容易驗(yàn)證q 是酉矩陣 引理3 3 1 2 令q 如( 3 3 1 1 ) 所示，如果a c h 默”則 咖q = l r i 州e ( a l l l + l + a 1 2 j t ；- r e i r n ( ( a i1 _ - a ：r 2 以j ) , 猷腳 ：i 酬h 4 - i + l 酬一以1 m 4 z 以i l i r a a l lr e a l ljl i i l l 彳1 2 以一r e a i 2 j t j = t + h ( 3 3 1 2 ) 這里 r=1沁主：一h1，日=rean以一im&2j,ima r e a _ i m a i 2 j tr e 4 2 j , j il 1 ll jj 一 由于a 是h e r m i t i a nt o e p l i t z 矩陣，故 一( i m a l l ) r = i m a l l 易知t 是實(shí)對(duì)稱t o e p l i t z 矩陣，即為中心對(duì)稱t o e p l i t z 矩陣。h 是h a n k e l 斜中心對(duì)稱矩陣。這樣h e r m i t i a nt o e p l i t z 矩陣a 通過酉變換成了t o e p l i t z 矩陣和h a n k e l 矩陣的和。即 q ：a q n = t + h r e ( t ) 和i m ( z ) 分別矩陣t 的實(shí)部和純虛部。 引理3 3 1 2 的逆也成立，也就是如果矩陣 占= 匱b 外”，l 島。：z j g 如( 3 2 1 1 ) 所示，則 卵醇= ，盎。崔孓甚：盎。：，船一- b 2 2 ) + h i ( b a ，+ 刪b 1 2 ) j 以k c h 引理3 3 1 3 任意矩陣b c ”，存在唯一一對(duì)矩陣蜀，墾c h “”，使得 b = 蜀+ i b 2 證明：對(duì)任意矩陣b c 臟”，令 蜀：墜簪，島= 冬些 容易知道馬，島c h “”，且b = 蜀+ 嘎 唯一性：若存在另一對(duì)矩陣曩，砬c h 肼“使得q + i b i = b 我們有如下關(guān)系式 且q = i b ；一蠅， 9 等式兩邊左乘和右乘以得 蜀一耳= f 砬一嘎 表明蜀一鳥= 啦+ 遙，有晝= 茸且墾= 璉，因此完全證明了引理3 3 1 3 。 我們證明了通過酉變換把h e r m i t i a nt o e p l i t z 變換成t o e p l i t z + h a n k e l 陣，這其中只用到了少量的復(fù)運(yùn)算，大幅度減少了運(yùn)算量。 3 3 2t o e p l i t z + h a n k e l 矩陣變換為實(shí)對(duì)稱c a u c h y 矩陣 這節(jié)我們主要研究利用d f t 把t o e p l i t z + h a n k e l 矩陣變換成實(shí)對(duì)稱 c a u c h y 矩陣，對(duì)于t o e p l i t z 矩陣t 定義為： 2 c 。d ，( c 。s 諺- c o s 驢, j ) ，( q ) 刀( 乃) = ( q 一以) ；( c ，) 一g ( d ，) ) 而 g o ) = 毒：r a o ) 一口+ ( ，) ，g ( f ) = 口一o ) 一掌彬+ ( ，) n - i q ( f ) = 吼九 七= 0 我們考慮h a n k e l 矩陣 n - i 口一( r ) = 吼t k = o h ： 6 州t ：n - i 吃斗。j s t + 玩小。s t ， ( c j d j ) l ( c ，) 7h l ( d j ) = h ( c ，) 一h ( d ，) 辦( ，) = ( 6 川一i f 肛一咖川+ i f ) ，辦( f ) = eb 川一f ”一蛾- l + k ， 2 叫小嘶- c o s q j ) f ( 啪7 n l ( d j ) = ( c , d j - 1 ) ( h ( 啪叫t ) ) 對(duì)于t o e p l i t z + h a n k e l 矩陣a = t + h 我們有 2 c f d j ( c o s , 一c o s g r j ) 訛f ) ra l ( d j ) - - 2 c 怠j 譽(yù)盎瓤琵；：沾( 布1 ) + 嘭辦( 嘭) j + 乜g ( 町1 ) + 辦( 嘭) j 定理3 3 2 1 令孝，叩是兩個(gè)復(fù)數(shù)且閣= i r i = 1 ，q ，嘭分別是是孝和r 的n 階根，我們有c o s , = r e c f ，c o sf = r e a , ，對(duì)于t o e p l i t z + h a n k e l 矩陣a - - t + h ， 矩陣c = 矽( 孝) 彳緲( 孝) r 分別對(duì)于c o s ( c , ) ? 和c o s ( 拼的秩4 ，如果善r 且勿1 ，則 1 0 其中 p ( c ，) 一q ( c ，) d ，一c ，g ( d s ) + p ( d ，) c i i = = 二。_ = 二 9 2 n c j ( c o s 矽l c o s ，) d ， p o ) = t g ( t ) 一辦( f ) ，q ( f ) = g o ) 一t h ( t ) p ( t ) = t g ( t 叫) + 辦( ，) ，q ( t ) = g ( t 一) + t h ( t ) ( 3 3 2 1 ) 定理3 3 2 2 令a = t + h ，則1 以i = kp 相對(duì)于( t ) ? 的秩4 ，其元素 表示如下： 其中 。f 盟型絲，f ， 托2 1 紅：高1 戶， 口：= ，+ + ( 一1 ) “7 + ( 一1 ) “1 9 ，+ ( 一1 ) 。+ 1 9 ? ， = ( 一1 ) “+ 療+ ( 一1 ) p l g j + ( 一1 ) “1 9 j f 面給出使t o e p l i t z + h a n k e l 變換為c a u c h y 型矩陣常用的變換。 引理3 3 2 3 若a 是t o e p l i t z + h a n k e l 矩陣則i - i r 織ia 程f i 是2 x2 的塊結(jié)構(gòu) 【c 腑野而g 是秩2 的c a u c h y 矩陣。 引理3 3 2 4 若a 是t o e p l i t z + h a n k e l 矩陣，則矩陣n7 群4 ( 群) r i 和 f 1 7 硝彳( 醭) n 是2 x2 塊結(jié)構(gòu)【c 口r 是秩2 c a u c h y 矩陣。 引理3 3 2 5 若a 是t o e p l i t z + h a n k e l 矩陣1 - i 卜圳na 1 7 是2 x 2 的塊結(jié)構(gòu) 【c ，p 而q 是秩訓(xùn)c a u c h y 矩陣，其中產(chǎn)攝r js i n 學(xué)l 引理3 3 2 6 若a 是t o e p l i t z + h a n k e l 矩陣，f i7 等么( 群) r f ir i7 群彳( 硝) r f i 是2 x2 的塊結(jié)構(gòu)( g ) ；且使得c a u c h y 矩陣c f ，的秩2 c o s 肛姚厶艮s 羋 咖糾礦變換科崩咖羋) ：1 第四章h e r m i t i a nt o e p li t z 方程組 本章主要研究討論了基于實(shí)對(duì)稱c a u c h y 矩陣快速分解的h e r m i t i a n t o e p l i t z 方程組快速算法。給出了求解h e r m i t i a nt o e p l i t z 方程組快速算 法，并通過算法研究，發(fā)現(xiàn)此算法更具有穩(wěn)定性，且計(jì)算量有所減少。 4 1 實(shí)對(duì)稱c a u c h y 方程組 我們用選主元的方法求解實(shí)對(duì)稱c a u c h y 方程組，實(shí)對(duì)稱c a u c h y 矩陣 生成向量z 和y 取決于關(guān)系式 y = z k 和y = z + k ( 4 1 1 ) 其中k 是，陣。 命題4 。1 1 ( 1 ) 如果c ，= d ，( f = 1 ，) ，c 是對(duì)稱矩陣且r 是偶數(shù)，則( 4 1 1 ) 的第一個(gè)關(guān)系式對(duì)于于z 有 k = l 0 二上 2 生o 2 ( 2 ) 如果q = - d 艇= 9 o9 ，) 且c 是h e r m i t i a n 矩陣( 4 1 1 ) 的第二個(gè)關(guān)系式 對(duì)于z 有 k = 名一：p 命題4 1 2 令矽為線性分式變換矽( 兄) = 掰， q = ( x 。) ， 乃= ( y ，) ， 則s t e i n 位移方程c d ( c ) c d ( d ) = r 等價(jià)于s y l v e s t e r 位移方程 d ( x ) c + c d ( y ) 2 畝d ( 鍛+ 1 ) r d ( a y + 1 ) 一般選主元會(huì)破壞矩陣的對(duì)稱性，我們用對(duì)角選主元代替部分選主元 來(lái)保持矩陣結(jié)構(gòu)的對(duì)稱性，但是，簡(jiǎn)單的對(duì)角選主元并不會(huì)提高計(jì)算的 速度，我們使用塊對(duì)角選主元代替對(duì)角選主元，這樣能夠提高計(jì)算的速 度。我們主要是用b u n c h k a u f m a n - p a r l e t t 選主元算法，此算法運(yùn)用的塊 選主元且塊是1 階或2 階的。 1 2 給出一個(gè)對(duì)稱矩陣a ，b u n c h k a u f m a n p a r l e t t 算法計(jì)算置換陣p ，一 個(gè)單位下三角陣m 和塊對(duì)角陣d ( 1 階或2 階) 使得 p7 a p = m d m r ( 4 1 2 ) 尸取決于控制著選主元的速度參數(shù)口，。 口 a ；t ，則元素c l 。是好的選主元，令p = i 跳到( c ) ( a 3 ) 計(jì)算o r = m a x 棚a ( a 4 ) 若| 口l 。o r 獻(xiàn)2 ，元素口。任然是好選主元素，令p = i 跳到( c ) ( a 5 ) 若l a t o m o r a 2 ，a 。是好選主元素，令p = 1 1 。跳到( c ) ( b ) 不存在任何滿足l l 對(duì)角元，令s = 2 ，p = i s 用 ( c ) 計(jì)算 c c ，令剮p r = ：苫 ，且。是s s 陣， ( c 2 ) 計(jì)算d 的s c h u r 補(bǔ)彳( “n ， ( c 3 ) 計(jì)算m 的生產(chǎn)的列元素令為e d ， 重復(fù)運(yùn)用b u n c h k a u f m a n p a r l e t t 算法會(huì)產(chǎn)生我們想要的分解 p r a p = m d m r ，這個(gè)分解來(lái)解方程組a x = b ，對(duì)于實(shí)矩陣彳，給定對(duì)稱分 解尸c p7 = m d m7 需要坶( 力) = 刀2 次乘法和彳s ，( 刀) = 甩2 次加法，一個(gè)復(fù)矩陣大 部分運(yùn)算要執(zhí)行復(fù)運(yùn)算，一個(gè)復(fù)數(shù)乘法相當(dāng)于四個(gè)實(shí)數(shù)乘法和兩個(gè)實(shí)加 法，一個(gè)復(fù)加法相當(dāng)于兩個(gè)實(shí)加法，如果在復(fù)的條件下，分解h e r m i t i a n 矩陣彳解線性方程組a _ x ；b 的計(jì)算量為m s c ( n ) = 4 n 2 次乘法和a s a n ) = 4 n 2 次 加法。 聯(lián)合l u c a u c h y 算法和b u n c h k a u f m a n p a r l e t t 算法我們?nèi)菀椎玫?b u n c h k a u f m a n p a r l e t t c a u c h y 算法。 算法4 1 4 ( b u n c h k a u f m a n p a r l e t t c a u c h y 算法) ： 令c 是由生成向量y 和z = 構(gòu)成的n xnc a u c h y 矩陣，對(duì)于元素( c ，d ) ， 當(dāng)i 歹時(shí)有q c ，若c = d ，則c 為對(duì)角陣d i a g ( c ) 。計(jì)算置換矩陣p ， s 的階數(shù)( j = l o r 2 ) 是選主元塊d 的階數(shù)，s 是列向量是分解矩陣m 的下三 角的列向量，由生成向量】，和z ，使得z = y k 1 初始值：令口= ( 1 1 + 1 廣j i f f 一) ，j = 1 ， 2 ( a ) 找一個(gè)lx l 對(duì)角元， ( a 1 ) 我們首先計(jì)算矩陣 c 第一列元素的非對(duì)角元， c i = ( 口訂) ? = ( d i a g ( c ：塒) 一d 。，) 。1 藝：。k y 。，令兄= i 口m l l = m a x 2 矗勤l 吼l i ， ( a 2 ) 若i a l i i 以令p = i ，d = 口l l ，e = c l ，跳至0 ( c ) ， ( a 3 ) 計(jì)算c 的第m 列非對(duì)角元，g = ( a i = ) ? = ( d i a g ( c d ) - 以，) 。1 巧k y ， 而，= 1 ，