（計(jì)算數(shù)學(xué)專業(yè)論文）一些結(jié)構(gòu)矩陣的快速算法.pdf

摘要 本文主要研究一些特殊結(jié)構(gòu)矩陣的快速算法首先，我們提出了關(guān)于廣義中 心對(duì)稱矩陣和廣義中心厄米特矩陣的矩陣一向量乘積的快速算法；其次，提出了 關(guān)于廣義中心對(duì)稱矩陣和廣義中心厄米特矩陣的矩陣矩陣乘積的傳統(tǒng)的快速算 法；最后提出了關(guān)于廣義中心對(duì)稱矩陣和廣義中心厄米特矩陣的矩陣矩陣乘積 的塊算法與傳統(tǒng)的算法進(jìn)行了比較，我們算法無論在計(jì)算量還是存儲(chǔ)量方面， 都能確保相當(dāng)?shù)墓?jié)省 本論文共分五章 第一章為引言主要介紹了本論文研究問題的主要背景、研究?jī)?nèi)容和創(chuàng)新 第二章主要介紹了一些在本論文中要用到的基本概念及符號(hào)表示 第三章建立了廣義中心對(duì)稱( 厄米特) 矩陣一向量乘積的快速算法并對(duì)所建 立的算法進(jìn)行了分析。說明了新建立的算法在計(jì)算量和存儲(chǔ)量方面比傳統(tǒng)的算法 有很大的改進(jìn) 第四章建立了廣義中心對(duì)稱( 厄米特) 矩陣一矩陣乘積的傳統(tǒng)的快速算法在 計(jì)算量和存儲(chǔ)量方面也有類似的改進(jìn) 第五章建立了廣義中心對(duì)稱( 厄米特) 矩陣一矩陣乘積的塊算法在此算法 中采用了分塊的矩陣乘法，并且在算法中把矩陣的乘法轉(zhuǎn)化成矩陣的加減法計(jì) 算，從而提高了計(jì)算的速度，節(jié)省了不少的內(nèi)存 關(guān)鍵詞：廣義中心對(duì)稱矩陣：廣義中心厄米特矩陣：廣義斜中心對(duì)稱矩陣；快速 算法；目m i l 算法 s o m ef a s ta l g o r j t h m sf o rc c r t a i nc l a s s e so fs t 九i c t u r e dm a t r i c e sa r ec o n s i d e r c di n t b i st h e s i s f i r s t ly ，w ep m p o v e r a if 弱ta l g o r i t h m sf o rc o m p u t j n gt h ep m d u c t so f m a t r i x v e c t o rw j t hag e n e r a l i z e dc e n t m s y m m e t r i cm a t r i x ( o rg e n e r a l j z e dc e n t r o h e 哪i t i a nm a t r i x ) s e c o n d ly w ed e v e l o ps o m ec o n v e n t i o n a lf a s ta j g o r i t h m sf o r c o m p u t i n gt l l ep r o d u c t so fm a x m a 倒b 【w i t hag c n e r a l i z e dc e n t r o s y m m e t r j cm a t r i x ( o rg e n e r a l i z c dc c n t r o h e 冊(cè)i t i 卸m a t 血) a tl a s t ，w ei n v e s t i g a t et h eb l o c ka l g o r i t h m s f o rc o m p u t i n gt l l ep 剛u d so fm a t r i x m a t r i xw i t hag e n e r a l i z e dc e n t r o s y m m e t r i c m a 砸x ( 0 rg e n e r a l i z e dc e n t m h e 徹i t i a nm a t x ) ( = o m p a n gw i t h t h ec o n v e n t j o n a l a l g o t h m s ，o u ra l g o r i t b m se n s u r es j 印m 啪ts a v j n 擎j nc o m p u t a t i o n a lc o s t s 卸d m e m o r yu n i t s n j s p a p e r c o n s i s t so ff i v ec h a p t e r s h lt h ef i r s tc h a p t e r ，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 ，i h em a i nc o n t e n t s 柚d t l i eo r i 百n a l i t i e so fc h et h e s i s i i lt h es c c o n dc h a p t e r ，w eb r i e n y 北v i e ws o m eb 硒j cd e f i n j t i o n sa n dn o t a t i o n w h j c hw i l lb eu s e di nt h et h e s i s i i lt h et h j r dc h a p t e r ，s e v e r a la 1 9 0 r i t h m sf b rc o m p u t i n gt h ep r o d u c t so fm a t r i x 。 v e d o rw i t hac c n t r o s y m m e t r i cm a t r i x ( o rac c n t r o h e 皿i t i 卸m a t r i x ) a r ep r o p o s e d w e g i v es o m ed e t a j i e da n a l y s i so ft h e s ea l g o r i t l l n l s ，c o m p a r i n gw j t h t h ec o m p u t i o n a l c o s t s 卸ds t o r a g e so f t h e n v e n t i o n a la l g o r i t l l i l l s ，o u ra l g o r i t h m sc a ns a v ea l o t i nt h ef o u n hc h a p t e r ，w eo f f c r c d s e v e r a lc o n v e n t i o n a lf a s ta l g o r i t h m sf o r c o m p u t i n gt h ep m d u c t so fm a t r i x - m a t r i ) 【w i t hag e n e r a l j z e dc c n t r o s y m m e t r i cm a t r j x ( o rag c n e r a l i z e dc e n t m h e 姍i t i a nm a 啊x ) t h o s ea l g o r i l h m sh a v et h es i m 柚a r 軸v i n g s i i lt h ei a s tc h a p t e lw ep r o p o s e daf c wb l o c ka i g o r i t h m sf o rc o m p u t i n gt h e p r o d u d s o fm a t r i x m a t r i xw i mag e n e m l i z e dc e n t r o s y m m e t r i cm a t r i x( o r a g e n e r a l i z e dc c n t r o h e 冊(cè)i t i 柚m a t r i x ) b yu s i n gb l o c k e dm 枷xp r o d u c tw h e r c m e m u l t j p i i c a t i v eo p e r a t i o n sa j 己t r a n s f o 冊(cè)e d i n t o r e l a t i v ea d d i t i v e o p e r a t i o n s ， o u r a l g o r i t h m se n s u r et h ei m p r o v e m e n to f m p u t a t j o n a ls p e e d a i l ds a v i n go fs t o r a g e n k e yw o r d s ：g e n e r a l i z e dc e n t r o s y m m e t cm a t c e s ；( k n e r a i i z e d c e n t m h e m i t i a n m a t c 囂； g e n e n l i z e d s k e wc e n t m s y m m e t r i c m a t c 髓；f a s ta i g o r i t h m s ； s t m s s e na l g o r i t h m s 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)。 作者簽名：磚噢專 日期：d 7 年上月加日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意 學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文 被查閱和借閱。本人授權(quán)長(zhǎng)沙理工大學(xué)可以將本學(xué)位論文的全部或部分內(nèi) 容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存 和匯編本學(xué)位論文。 本學(xué)位論文屬于 1 、保密口，在年解密后適用本授權(quán)書。 2 、不保密團(tuán)。 ( 請(qǐng)?jiān)谝陨舷鄳?yīng)方框內(nèi)打“”) 作者簽名： 曲乓丟 導(dǎo)師簽名： 割沖舂 日期：c 7 年s 月；日日期：p 年s 月；日 日期0 7 年歲月加日 1 1 背景 第一章引言帚一早，ii 在當(dāng)代的許多科學(xué)與工程問題中都會(huì)遇到大規(guī)模的矩陣計(jì)算問題，例如，在 計(jì)算信號(hào)復(fù)原問題時(shí)，離散的方程所表現(xiàn)的大多是一個(gè)大規(guī)模的線性方程組目 前許多的信號(hào)復(fù)原問題，大多是在對(duì)原問題的邊界加以一些特殊的限制后來進(jìn)行 研究這些限制使離散問題表現(xiàn)為具有某種特殊結(jié)構(gòu)和某些特殊性質(zhì)的線性方程 組( 例如應(yīng)用反卷積技術(shù)到信號(hào)復(fù)原問題，就會(huì)出現(xiàn)系數(shù)矩陣為循環(huán)矩陣、 而印批：矩陣、而印，比+ 月口月婦，矩陣等結(jié)構(gòu)矩陣見參考文獻(xiàn) 3 6 、 3 8 ) 雖然 以上幾類矩陣已有一些快速算法，但對(duì)于其他許多的已在信號(hào)復(fù)原問題中出現(xiàn)的 結(jié)構(gòu)矩陣( 例如應(yīng)用小波技術(shù)處理信號(hào)復(fù)原問題時(shí)，就會(huì)出現(xiàn)諸如中心對(duì)稱矩陣、 中心厄米特矩陣等結(jié)構(gòu)矩陣見參考文獻(xiàn) 1 、 3 8 ) ，至今還沒有找到有效的快 速算法因此，為了減少計(jì)算量和節(jié)省內(nèi)存，設(shè)計(jì)快速的算法( 當(dāng)討論的結(jié)構(gòu)矩 陣為非奇異矩陣時(shí)) 或有效的最小二乘解算法( 當(dāng)討論的結(jié)構(gòu)矩陣是奇異或超定 矩陣時(shí)) ，尤其顯得十分重要目前有關(guān)這方面的研究尚屬起步階段，至今只有極 少數(shù)的論文所以，對(duì)結(jié)構(gòu)矩陣的研究以及建立相關(guān)的快速算法是很有研究?jī)r(jià)值 的 對(duì)于一些超大規(guī)模的計(jì)算問題，我們就不得不研究并行算法了例如，在有 些信號(hào)復(fù)原問題中，如天氣預(yù)報(bào)、大地石油勘探等問題，所表現(xiàn)的方程組通常是 超大規(guī)模的( 上百萬階) ，串行的算法根本就不能解決這些實(shí)際問題目前，對(duì)于 有些實(shí)際問題，已有一些實(shí)用的并行算法但是對(duì)有些問題( 如圖象復(fù)原問題 等) ，由于起步階段較晚，加上計(jì)算方面的困難，目前的研究主要集中在中、小 規(guī)模的信號(hào)復(fù)原問題，而對(duì)大規(guī)模的信號(hào)復(fù)原問題和相關(guān)的超大規(guī)模計(jì)算問題 還很少有涉及然而，在實(shí)際問題中有時(shí)常會(huì)碰到這些計(jì)算問題因此，為了解 決這些超大規(guī)模問題的計(jì)算問題，很有必要進(jìn)一步研究他們的并行算法 在研究結(jié)構(gòu)矩陣線性方程組的求解的時(shí)候有時(shí)會(huì)遇到矩陣的乘積因此，矩 陣乘積也是我們要解決的問題目前，國內(nèi)外對(duì)結(jié)構(gòu)矩陣的乘積問題的研究也有 不少的研究，同時(shí)也出現(xiàn)了很多相關(guān)的算法，并且都在不同的程度上達(dá)到了我們 設(shè)計(jì)快速算法的最終目的減少計(jì)算量、節(jié)省內(nèi)存，見參考文獻(xiàn) 2 、 3 但 是至今還沒有找到最優(yōu)化的快速算法，所以其中還有許多的工作值得繼續(xù)深入 研究 線性方程組的求解問題是矩陣計(jì)算中的核心部分，許多科學(xué)與工程問題最終 會(huì)歸結(jié)到線性方程組的求解目前，對(duì)于一些結(jié)構(gòu)線性方程組，如何進(jìn)行迭代改 進(jìn)直是國內(nèi)外一個(gè)比較活躍的研究領(lǐng)域，研究的主要目的是如何利用矩陣的 特殊結(jié)構(gòu)來減少計(jì)算量和存儲(chǔ)量，從而可以節(jié)省計(jì)算的時(shí)間和計(jì)算需要的費(fèi)用， 主要結(jié)果見參考文獻(xiàn)【2 】、【3 】、【3 5 】、【4 7 】 另外，結(jié)構(gòu)矩陣有著廣泛的應(yīng)用背景，經(jīng)常出現(xiàn)在下面的一些研究領(lǐng)域中： ( 1 ) 微分方程的數(shù)值求解； ( 2 ) 馬爾可夫過程的研究； ( 3 ) 電子與機(jī)械的振動(dòng)和控制； ( 4 ) 調(diào)和恢復(fù)問題； ( 5 ) 自正交小波基的構(gòu)造： ( 6 ) 其他各種各樣的工程和物理問題 1 2 本文的研究?jī)?nèi)容和創(chuàng)新 1 2 1 本文研究的內(nèi)容 在本論文中，主要研究了廣義中心對(duì)稱矩陣( 廣義中心厄米特矩陣) 的矩陣 乘積的快速算法和此類系數(shù)矩陣線性方程組的并行計(jì)算方法此類方程組有著廣 泛的應(yīng)用背景，經(jīng)常出現(xiàn)在下面一些領(lǐng)域中：1 ) 在微分方程的數(shù)值求解中；2 ) 在某個(gè)馬爾可夫過程的研究中；3 ) 在自正交小波基的構(gòu)造中；4 ) 在多維的調(diào)和恢 復(fù)問題中：5 ) 在別的各種各樣的物理和工程問題中其中小波分析是數(shù)學(xué)中的一 個(gè)迅速發(fā)展的領(lǐng)域，正在成為一個(gè)重要和活躍的研究領(lǐng)域，更重要的是它已經(jīng)在 數(shù)學(xué)家和電子工程師之間建立了一種牢固的聯(lián)系，引起了其它學(xué)科的科學(xué)家和工 程師的注意對(duì)于小波分析是用泛函分析的方法研究的，然而在小波的研究中矩 陣方法起著一個(gè)重要的作用 論文中主要討論了三個(gè)問題第一：關(guān)于含有廣義中心對(duì)稱矩陣( 廣義中心 厄米特矩陣) 的矩陣一向量乘積的快速算法；第二：關(guān)于含有廣義中心對(duì)稱矩陣 ( 廣義中心厄米特矩陣) 的矩陣一矩陣乘積的傳統(tǒng)算法；第三：關(guān)于含有廣義中 心對(duì)稱矩陣( 廣義中心厄米特矩陣) 的矩陣一矩陣乘積的塊算法，即翮位刪n 算 法 1 2 2 本文的主要?jiǎng)?chuàng)新 1 ) 在第三章中，針對(duì)廣義中心對(duì)稱矩陣和廣義中心厄米特矩陣設(shè)計(jì)了一 種關(guān)于這兩種矩陣與向量乘積的快速算法建立的算法主要是在計(jì)算量和占用計(jì) 算內(nèi)存方面有了很大的改進(jìn)：并且對(duì)于廣義斜中心對(duì)稱矩陣也有類似的結(jié)論成 立 2 ) 在第四章中，利用第三章得出的定理和算法，把它推廣到關(guān)于廣義中 2 心對(duì)稱矩陣與矩陣乘積的問題而且算法在計(jì)算量和占用計(jì)算內(nèi)存方面也有類似 的改進(jìn) 3 ) 在第五章中，利用矩陣的分塊來計(jì)算關(guān)于廣義中心對(duì)稱矩陣與矩陣乘 積的問題，5 打n 盯繃算法相比于傳統(tǒng)算法來說，計(jì)算量和占用計(jì)算內(nèi)存都有一定 的改進(jìn) 第二章預(yù)備知識(shí) 實(shí)矩陣的集合；- ，為置換矩陣，其中次對(duì)角線( 左底到右上) 元素為1 而其它元素 定義2 1 設(shè)爿為n h 的復(fù)數(shù)矩陣，如果，一，。一爿成立，則稱彳為中心對(duì) 稱矩陣，其中，。為次對(duì)角線上元素為1 其余元素為o 的置換矩陣 定義2 2 若矩陣爿中的元素滿足下面的關(guān)系式：4 “。口，。小。，一r ”，則 月一( 罷；：暑：) ，e c r “m p ，。6 ，。a 。 4 置ln 7 a 口7 ，l ，口，c 月刪，口，6 尺4 砌，口r 1 x 1 ic 6 ，丑，j 定義2 3 設(shè)一為n n 的復(fù)數(shù)矩陣，如果，一j 。；彳成立，則稱一為中心厄 爿：f 蘭n 苧z 1 ，( 其中。：2 ，1 ) ，。彳1 。，m 爿1 ，m 定義2 4 設(shè)4 為n _ r l 的復(fù)數(shù)矩陣，如果，。- 一彳成立，則稱爿為斜中 定義2 5 一個(gè)矩陣彳c 稱為廣義中心對(duì)稱矩陣，如果翩k 一：稱為廣 義斜中心對(duì)稱矩陣，如果刖k 一一一；稱為廣義中心厄米特矩陣，如果刪k - 爿， 其中爿定義為彳的共軛 等價(jià)地，一個(gè)矩陣爿= ( 4 叫) c 為廣義中心對(duì)稱矩陣當(dāng)且僅當(dāng)口，一4 ，( ；x 。( ； 為廣義斜中心對(duì)稱矩陣當(dāng)且僅當(dāng)4 - 一4 州h ( ；為廣義中心厄米特矩陣當(dāng)且僅當(dāng) 口，一口r “n ( ) ，f ，j - 1 ，萬 顯然，當(dāng)r o ) - 萬一f + 1 ，即k 一，時(shí)，一個(gè)廣義中心對(duì)稱矩陣爿c 就變 成了一個(gè)中心對(duì)稱矩陣；一個(gè)廣義中心厄米特矩陣爿c 就變成了一個(gè)中心厄 米特矩陣 第三章廣義中心對(duì)稱矩陣的矩陣一向量乘積的計(jì)算 3 1關(guān)于矩陣一向量乘積 在這一章里，我們將討論廣義中心對(duì)稱矩陣的矩陣一向量乘積的計(jì)算 對(duì)稱的( 厄米特) 而印舷矩陣形成了中心對(duì)稱( 中心厄米特) 矩陣的一個(gè) 重要的子類，它們很自然地出現(xiàn)在數(shù)字信號(hào)處理和其它領(lǐng)域，見例 1 ，2 和其中 的文獻(xiàn)中心對(duì)稱矩陣及其相關(guān)矩陣近來在許多問題的求解中起了重要作用，這 些問題是在實(shí)的或復(fù)的物理系統(tǒng)分析中提出來的，而這些物理系統(tǒng)通常在某一水 平上是幾何對(duì)稱的，見例文獻(xiàn) 4 ，5 ，7 在傳統(tǒng)算法中，矩陣一向量乘積血的計(jì)算量為n 2 次乘法和n 2 一h 次加法，其 中爿和x 都是n 維的然而，當(dāng)4 為一結(jié)構(gòu)矩陣時(shí)，通過探索矩陣的結(jié)構(gòu)和性質(zhì)， 計(jì)算量將會(huì)大大減少近來， 把砌冊(cè) 6 考慮了矩陣一向量乘積爿石的計(jì)算，其中彳 1 為對(duì)稱中心對(duì)稱矩陣在 耙砌口_ r l 的算法中，只需要三月2 + n 次乘法和二竹2 + ，1 次加 24 法來計(jì)算“一血前不久，勵(lì)船6 e n 如r 和j ) 打伽 2 進(jìn)一步討論了更一般的情 1 形，當(dāng)爿為中心對(duì)稱矩陣時(shí)，在他們的算法中，計(jì)算“一缸用了二n 2 + d ( n ) 次乘 z 法和n 2 + d 0 ) 次加法我們注意到在f 口嬲6 翻脅和，七m d v 的算法中，主要工具 是( 斜) 中心對(duì)稱( 中心厄米特) 矩陣的約化，利用了一個(gè)簡(jiǎn)單的相似變換在 他們工作的推動(dòng)下，本章中，我們繼續(xù)討論計(jì)算觸這個(gè)問題我們首先研究所 謂的廣義中心對(duì)稱矩陣，廣義斜中心對(duì)稱矩陣和廣義中心厄米特矩陣的約化，特 別地，我們提出的關(guān)于這幾類矩陣的算法可視為而船6 朗如r 和肋小d v 的算法的 推廣我們看到我們的算法，當(dāng)計(jì)算很多的矩陣一向量乘積爿工，其中矩陣爿為同 一個(gè)廣義中心對(duì)稱矩陣，可以節(jié)省許多計(jì)算量此外，對(duì)于某廣義斜中心對(duì)稱 矩陣和廣義中心厄米特矩陣，我們也有類似的結(jié)果 3 2 幾個(gè)例子和定理 關(guān)于廣義中心對(duì)稱矩陣類，除了中心對(duì)稱矩陣外，我們還發(fā)現(xiàn)了其它的矩陣 類，它們出現(xiàn)在各種實(shí)的或復(fù)的物理和工程系統(tǒng)分析中提出的一些問題的求解 中，其中每一個(gè)k ，。是一個(gè)對(duì)稱置換矩陣我們列舉3 個(gè)例子，即三個(gè)廣義中 6 k 0 ，】 例2 塊中心對(duì)稱矩陣( 對(duì)稱塊而印f f z 矩陣可以看成一個(gè)塊中心對(duì)稱矩陣的特 k 2 一 ip l p l p ( 2 ) 例3 分塊中心對(duì)稱矩陣( 7 中的b l o c k c i r c i l l a n t - c i r c u l a i i t _ b o l c k 矩陣為一個(gè)特 殊的分塊轉(zhuǎn)中心對(duì)稱矩陣) ，其中 瑪- ( 3 ) 眾所周知，總存在一個(gè)簡(jiǎn)單的相似變換，使得每一個(gè)n n 的中心對(duì)稱矩陣相 似為一個(gè)對(duì)角塊矩陣，見 2 對(duì)于廣義中心對(duì)稱矩陣，我們有以下類似結(jié)論 定理3 1 矩陣4 c 為一個(gè)廣義中心對(duì)稱矩陣當(dāng)且僅當(dāng)存在一個(gè)如方程( 8 ) 所定義的正交矩陣q ，使得 q 7 爿q 耳( bc ) c 4 ， 其中口c 扣一i 4 一，c c 對(duì)，= ，口n 七( ，一k ) 在給出定理3 1 的證明之前，我們首先給出矩陣q 的一種構(gòu)造設(shè)k 為對(duì)應(yīng) 于不相交對(duì)換的固定積j r 的n 階置換矩陣，可以推知，k 2 一，和k 7 k 根據(jù)廣義中心對(duì)稱矩陣的定義，我們?cè)O(shè)r = t ，一，其中“。是 個(gè)對(duì)象 的f 不相交對(duì)換，定義了一個(gè)變換，它交換了第五個(gè)和第r ( 工) 個(gè)對(duì)象的位置( 我 們假設(shè) c ，：c c ) 用乞川 ) 表示對(duì)應(yīng)于變換一的置換矩陣，記為 即 巴。( ) = 1 c o l u mc 0 l u ” j ik t i 1 0 1 1 0 1 1 r o w r 。wr ( 工) ( 5 ) 因此，對(duì)應(yīng)于_ | r 的置換矩陣k 就是( 5 ) 中的矩陣只州 ) 的乘積，其中，一1 ，f k = 乞州 ) 巴r f 】 不失一般性，我們假設(shè)工一r ( 工) ，f = 1 ，f 因?yàn)楫?dāng)“一f ) 時(shí)，( 5 ) 式中 己巾l 一， 令 q ，。f ) = 1 c o l u 瑚c o l u 姍 j 。k “0 壓 2 互 2 壓壓 22 r o wr ( 上) ( 6 ) 我們可以看到，( 6 ) 中的q 肛 j 為一個(gè)j 下交矩陣，并且對(duì)于f ，s t l ，有 q 。t i j 、q p t i ，一q i 妲i j 、 定義 蠶5 珥* ， ( 7 ) 則產(chǎn)生了一個(gè)正交矩陣 我們定義一個(gè)新矩陣q ，它由( 7 ) 中的西列列交換而得到，特別地，正交 矩陣西的_ | r ( ) ，r ( ) 列為新矩陣的h 一，+ 1 ，月列，也就是說，存在一個(gè)置換 矩陣蘆使得 q 一蠶蘆一( q 1 ，q ：) ( 8 ) 其中q 1 定義為q ( 1 ：廳一f ) ，由q 的前h 一，列組成；q 2 定義為q o 一“- 1 ：n ) ，由矩 陣q 的最后，列組成 定義 k = ；( + k ) ，k ：一三( ，一k ) ( 9 ) 容易驗(yàn)證，矩陣q 1 和q 2 為( 9 ) 中矩陣k 和的最大秩分解即q l q f k ， q ：西一哎 我們現(xiàn)在回到定理1 的證明： 定理3 1 的證明：由前面的構(gòu)造，我們知道( 8 ) 中的正交矩陣已經(jīng)定義好了 ”一”假設(shè)( 8 ) 中的正交矩陣q 滿足下面關(guān)系 q 7 彳q = ( 口c ) 等價(jià)地，有 小q ( bc ) q 7 注意到，k = q 。q j q 2 講和q = ( q i ，q ) ，可推知 9 c ”q ，( bc 腿卜q ，( 曰c 刊 q 7 爿q 一( 要) 爿c q ，q ，= ( 簧三驀要三曩) 岫翹一( 曼卜刮= ( 裟麓) 因?yàn)閝 7 一q q 7 翩翹，這表示q f 爿q 2 = o 和q j 爿q 1 = o 必須同時(shí)滿足，因此，我 q 7 爿q 罩( 口c ) 其中口= q j 爿q c n 一卜肛o ，c l q ；爿q ：c m 譬二 ， 托三) 1 0 孚一 互 2 當(dāng)p 一2 黿+ 1 時(shí)，q 有如下形式： 壓 2 i ，目 一lq ，q q l q】l 壓 壓 一l l j4 一l q 口 對(duì)于j 義斜甲心對(duì)杯矩| 5 牛，我們硐如r 足埋，為j 義斜甲心對(duì)杯矩陣陰千甘似 可約性 定理3 2 設(shè)q 如方程( 8 ) 中所定義，則矩陣爿c 為廣義斜中心對(duì)稱矩 陣當(dāng)且僅當(dāng)如下關(guān)系式 q 7 彳q = ( ，) c t ， 成立，其中c n 。川，c 。“，一，口月七( ，一k ) 證：”一”設(shè)q 如( 8 ) 中所定義，等價(jià)地( 1 1 ) 式成立，所以 爿皇q ( ，e ) q 7 因?yàn)閗 = q 1 研一q ：籃，q 一( q l ，q 2 ) ，我們有 c ”q ，( fe 腿) | - ( q 川( fe 刊 ”一”設(shè)爿為廣義斜中心對(duì)稱矩陣，q 為如( 8 ) 所定義，那么由假設(shè)，我們有 q _ q = ( 要) 一c q ，幺，2 ( 要三耋簧：籠) 和 岫叫豺c 蜴，刮- ( 裟麓) 因?yàn)閝 7 爿q ；一q 7 刪磁，那么q j 一q l o 和q j 爿q 2 - o 必須要同時(shí)滿足，因此我 們有 q 7 爿q 暑( ，e ) 其中e 一研爿q j c ”m ，f t q f 爿q 1 c 7 巾。 口 對(duì)于中心厄米特矩陣，我們總可以利用一個(gè)簡(jiǎn)單的相似變換把它轉(zhuǎn)換成一個(gè) 實(shí)矩陣，同樣對(duì)于廣義中心厄米特矩陣，我們有同樣的結(jié)論這就是下面的這個(gè) 定理 定理3 3 設(shè)q 為如方程( 8 ) 中形式，并定義 u 一( q l ，j q 2 ) ( 1 2 ) 那么矩陣爿c 為廣義中心厄米特矩陣當(dāng)且僅當(dāng)下面方程 c ，”彳u = ( 雪：主：) r “” c ，。， 成立，其中j 1 1 r ( 4 ) 一( 一一n ，j 1 2 r 扣。m ，j 2 。月。一。一n ，j r 證：容易驗(yàn)證u 為酉矩陣 ”一”設(shè)u 如( 1 2 ) 所定義，等價(jià)地( 1 3 ) 式成立，所以 叫麓p 因?yàn)閗 = q l 鮮一q 2 西，u = ( q 1 ，f q 2 ) ，我們有 c 曠訓(xùn)睇閽= 一圳封j 由定義，我們得出結(jié)論月為廣義中心厄米特矩陣 ”一”設(shè)爿為廣義中心厄米特矩陣，由假設(shè)，我們有 心u 一( 要卜訓(xùn)_ ( 裴 和 f 研爿q 2 1 駢爿q 2j 班翮一鼢c q ，一咖眨篙鬻) 因?yàn)閡 ”爿u ；u ”k j k 【，所以甜爿q j q j 面，q f 爿q j 一一q f j q | ， q q 1 - 一籃鴿和辨爿q 2 一q j 鴿必須同時(shí)滿足，因此我們有 u ”一u 傺糾 i 爿2 1爿2 2 j 其中j 。講一q j r ( 一。) 巾_ f ) ，j - 2 一h n ( q f 爿q 2 ) r “一m ， j ：。一i | l l ( q j 爿q 】) 月j x ( “和j zz q j 爿q 2 r “，l m ) 記為矩陣s 的虛部 口 3 3 算法 在前面一節(jié)的討論的基礎(chǔ)上，我們將針對(duì)廣義中心矩陣( 廣義中心厄米特矩 陣) 一向量乘積4 工提出兩種算法，它們可以看作是 2 中而船6 翻d e r 和腑叼m 洲的 算法的推廣在下面算法中，我們假設(shè)算法3 1 中的矩陣爿為n x 療的廣義中心對(duì) 稱矩陣，算法3 2 中的矩陣彳為一x 月的廣義中心厄米特矩陣 算法3 1 該算法用來計(jì)算廣義中心對(duì)稱矩陣一向量乘積4 工 準(zhǔn)備步： 步i ：構(gòu)造一個(gè)如方程( 8 ) 的正交矩陣q ，把q 分劃成q 一擊( 西。，蠶z ) ， 其中m n t ( q 2 ) 一f ，f 一陽船( ，一k ) 步i i ：計(jì)算矩陣x 。矩，y 一爿a ： 步i i i ：計(jì)算矩陣否。a j x 和0 ，反y 計(jì)算步： 步l ：計(jì)算向量 y 塒工恒心) 步2 ：計(jì)算向量 z - 褂 步3 ：計(jì)算向量 “一壺彩一拉毛+ 翻 現(xiàn)在我們來給出該算法的計(jì)算量特別地，在準(zhǔn)備步中，我們需要計(jì)算z ， y ，曰和c 因此在準(zhǔn)備步中需要如f 次加減法和o 一2 ，) ( 知一f ) 次乘法在計(jì)算步 中，步1 需要型次加減法和n 一2 ，次乘法，步3 需要同樣的加減法加上n 次除法 在步2 中，由傳統(tǒng)算法，需要q f ) 2 次乘法和o 一礦一o f ) 次加法來計(jì)算匆。， f 2 次乘法和f 2 一f 次加法來計(jì)算a ，：所以，計(jì)算矩陣一向量乘積“：血的總的計(jì)算 量為抽2 + 甜2 7 月，+ 知一甜次乘法和h 2 + 爿2 + 月f + 4 f 一胛次加法在傳統(tǒng)算法中， 需要n 2 + o ( h ) 次乘法和n 2 + d o ) 次加法，比算法3 1 中的結(jié)論要好一些，而且 比而卵6 p n 如和舭小d v 的算法中的去n 2 + d ( h ) 次乘法和甩2 + d ) 次加法的結(jié) 果還要差一點(diǎn)然而，當(dāng)爿為中心對(duì)稱矩陣時(shí)，作一個(gè)小的修正，我們的算法就 注l ：如 3 中所述，我們計(jì)算了很多的乘積，就像用同樣的矩陣爿來計(jì)算五：石 一樣例如，用迭代法來計(jì)算爿工，那么只有我們算法里計(jì)算步中的步卜3 一定 會(huì)被新的向量；所替換，準(zhǔn)備步中的否和a 被儲(chǔ)存也就是說用同樣的矩陣一來 計(jì)算，每一個(gè)多余的乘積只需要0 一f ) 2 + f 2 + d 0 ) 次乘法和同樣次數(shù)的加法如果 乘積的數(shù)字充分大，那么我們的算法在計(jì)算量上就有很大的節(jié)省 注2 ：對(duì)于一個(gè)給定的廣義中心對(duì)稱矩陣，在準(zhǔn)備步中降低計(jì)算量是可能的如 果矩陣k 有一定的結(jié)構(gòu)，例如在例卜3 中的k = k ，k ，瑪在這種情況下，對(duì)應(yīng) 于k ，矩陣爿可以分劃成某種塊結(jié)構(gòu)，比如說中心對(duì)稱矩陣的情況例如，如果爿 1 4 一b 磊：象】 口一( 4 澎9 矧 扣 一- 卜輞3 鼢 2 拈刪0 輞。三 ) ) ) m 垤 m ( ( ( 啦吼 = 以，在計(jì)算矩陣一向量乘積h = 瓜時(shí)，總的計(jì)算量為( p + q ) 2 + p 2 + 2 p 口+ n 次乘法 和p + q ) 2 + 3 p 2 + 2 p + 口次加法運(yùn)算注意到g - 月一2 p ，則運(yùn)算浮點(diǎn)數(shù)可寫成 2 ，1 2 2 朋+ 印2 如果牙p ，即2 p 一廳時(shí)，此時(shí)的浮點(diǎn)數(shù)近似等于曇n 2 ，這也就 是說計(jì)算量上的一個(gè)很大的節(jié)省是可以達(dá)到的 現(xiàn)在，我們回到計(jì)算廣義中心厄米特矩陣一向量的乘積上來，即下面的算法 算法3 2 該算法用來計(jì)算廣義中心厄米特矩陣一向量的乘積a x 準(zhǔn)備步： 步l ：構(gòu)造方程( 8 ) 中的正交矩陣q ，并且把q 分劃成q = 擊( 西。，蠶：) ，其 中m 礎(chǔ)( a ：) 一f ，f = 陽礎(chǔ)( ，一k ) 令【，一擊( a ，f 蠶：) 步2 ：計(jì)算 j = 矩，和y ；爿蠶： 步3 ：計(jì)算矩陣互。：茁x ，互：1 1 1 1 ( a i 】，) ，j ：，。一i i n ( 圣：x ) 和j ：a r y 步4 ：構(gòu)造實(shí)矩陣 j 怯習(xí) 計(jì)算步： 捫州韓量y 砌( 蕘卜“h i f q ：工j 步2 ：計(jì)算向量 r e ( z ) 一j r e o ) 并定義 z = r e ( z ) + f l m ( z ) 步3 ：計(jì)算向量 “一擊沈= 扭嘶) 一蠶：h n 】+ 籀i i l l + 蠶：r e ( 圳 在準(zhǔn)備步中，我們需要計(jì)算x ，y ，j ，五：，j ：。j 。一個(gè)乏味而簡(jiǎn)單的計(jì)算表明， 1 6 計(jì)算量大約為4 n f 次復(fù)數(shù)加法和2 n 0 一型) 次復(fù)數(shù)乘法在計(jì)算步中，主要的工作 是做步2 ，它需要的計(jì)算量大約為相同維數(shù)的復(fù)矩陣一向量乘積的一半步l 和步 3 的計(jì)算量可以忽略同樣，該算法的結(jié)果看起來比傳統(tǒng)算法要差一些，但是， 如前面注中對(duì)于廣義中心對(duì)稱矩陣所說，該算法在我們用廣義中心厄米特矩陣計(jì) 算許多矩陣一向量乘積時(shí)，它保證了重要的結(jié)果而且，當(dāng)矩陣k 有一定結(jié)構(gòu)時(shí)， 那么在準(zhǔn)備步中的計(jì)算量可能會(huì)減少例如，特別地在例卜3 中，k k ，哎，巧 1 時(shí)，作一個(gè)小的修正，在準(zhǔn)備步的計(jì)算量大約為去以2 次加法和更少的乘法在其 z 它情況下，我們的算法相對(duì)來說也有一定的節(jié)省，比如說，用我們的算法來做 2 中的中心厄米特矩陣 第四章廣義中心對(duì)稱矩陣的矩陣矩陣乘積的 傳統(tǒng)算法 4 1 關(guān)于矩陣一矩陣乘積 矩陣乘法是數(shù)值代數(shù)領(lǐng)域中一個(gè)不可缺少的內(nèi)容，一直以來人們關(guān)于矩陣乘 法的研究都很多因?yàn)殛P(guān)于矩陣乘法的研究在實(shí)際問題中有著重要的應(yīng)用價(jià)值 比如越來越多的工程問題最終會(huì)歸結(jié)到關(guān)于線性方程組的求解，這樣就不能不牽 涉到矩陣乘積計(jì)算隨著科學(xué)的發(fā)展，計(jì)算機(jī)水平的不斷提高以及人們對(duì)解決問 題速度的不斷提高，我們就不得不研究新的計(jì)算方法來達(dá)到人們的不同要求從 目前來看，主要的矩陣乘法的方法可以歸納于以下幾種 ( 1 ) 關(guān)于矩陣乘法的最早的算法是我們平時(shí)最常用的傳統(tǒng)矩陣乘積算法， 也就是根據(jù)矩陣乘法的定義來計(jì)算這種計(jì)算方法不僅計(jì)算的速度慢，而且要求 計(jì)算的內(nèi)存空間要很大。并且在運(yùn)算過程中采用的是一水平級(jí)的點(diǎn)一點(diǎn)運(yùn)算，同 時(shí)當(dāng)我們涉及到超大規(guī)模的矩陣乘積時(shí)這種計(jì)算方法幾乎是沒有實(shí)際應(yīng)用價(jià)值 的用傳統(tǒng)的方法計(jì)算矩陣乘積一一p ，其中一、p 都是n 階矩陣，需要至少 加3 次浮點(diǎn)運(yùn)算見參考文獻(xiàn) 3 ( 2 ) 另外一種方法是r 鯽冊(cè)算法研，口船朗算法采用了一種遞歸的方法 把兩個(gè)h 一擁階的矩陣乘法轉(zhuǎn)換成許多階數(shù)為肌的子問題來計(jì)算，最終可以把 問題轉(zhuǎn)換成m x m 的子塊運(yùn)算，即7 個(gè)子塊矩陣乘法與1 8 個(gè)子塊矩陣的加減法運(yùn) 算在整個(gè)算法中一共需要孫崦i 一2 n2 8 1 次運(yùn)算與傳統(tǒng)的算法相比在計(jì)算量方 面有了很大的改進(jìn)：并且在，口船朗算法中采用了塊塊的三水平級(jí)的計(jì)算，減 少了計(jì)算所需要的時(shí)間，見參考文獻(xiàn) 3 ( 3 ) 目前關(guān)于矩陣乘法在需要計(jì)算量方面最少的是由脅昭陽d 和 卸p p 胚加油提出的算法，他們的算法只需要0 02 “) 次計(jì)算量，但是這種算法 在實(shí)際的運(yùn)用中沒有應(yīng)用價(jià)值見參考文獻(xiàn) 3 ( 4 ) 對(duì)于一些特殊的矩陣，根據(jù)它們相應(yīng)的性質(zhì)，提出的許多新算法在 本章的以下部分我將主要建立廣義中心對(duì)稱矩陣和廣義中心厄米特矩陣的矩陣 與矩陣乘積的算法 4 2 廣義中心對(duì)稱矩陣乘積的傳統(tǒng)算法 4 2 1 引言 在這一部分當(dāng)中，我們主要研究了關(guān)于矩陣乘積- a p 的幾種算法，用傳 統(tǒng)的算法計(jì)算矩陣乘積胛，其中彳、p 都是甩療矩陣，需要n3 次乘法運(yùn) 算以及咒3 一，1 2 次加法運(yùn)算，即大約需要2 療3 浮點(diǎn)運(yùn)算 本章中，我們運(yùn)用廣義中心對(duì)稱矩陣和廣義中心厄米特矩陣的約化性質(zhì)得到 幾個(gè)計(jì)算矩陣與矩陣乘積一爿p 的快速算法，其中彳或p 為廣義中心對(duì)稱矩陣 或廣義中心厄米特矩陣，與文【4 0 】的對(duì)應(yīng)算法相比有更一般的結(jié)果當(dāng)彳或尸為 廣義斜中心對(duì)稱矩陣，可建立類似算法，計(jì)算量方面也有類似的結(jié)果 4 2 2 知識(shí)回顧 我們先回顧一下幾個(gè)重要的關(guān)于廣義中心對(duì)稱矩陣和廣義中心厄米特矩陣 的約化結(jié)果，見第三章中的定理3 1 ，定理3 2 和定理3 3 4 2 3 算法 在以上討論的基礎(chǔ)上，我們提出兩種算法用來計(jì)算矩陣與矩陣的乘積彳p ， 在算法4 1 中，假設(shè)爿為廣義中心對(duì)稱矩陣：在算法4 2 中，假設(shè)4 為廣義中心 厄米特矩陣 算法4 1 該算法用來計(jì)算廣義中心對(duì)稱矩陣與矩陣的乘積爿尸 準(zhǔn)備步： 步1 ：構(gòu)造第三章中方程( 8 ) 所定義的正交矩陣q ，并作分劃使得 q = 擊( 西。，計(jì)其中陽州玨川州m ) 步2 ： 計(jì)算矩陣 x 一q 。，y 一爿q ： 步3 ：計(jì)算矩陣吾；拜x ，己。a ：y 計(jì)算步： 步1 ：計(jì)算矩陣 1 9 吖鋤p 甾心) 步2 ：計(jì)算矩陣 = 吖= 倒) 步3 ：計(jì)算矩陣 一去q ；抑l + 西：2 】 下面討論一下該算法4 1 的計(jì)算量在準(zhǔn)備步中我們只要計(jì)算x ，y ，和 a ，需要知f 次加減法和2 ，1 2 + ，l ，+ 型2 在計(jì)算步驟中，步1 需要2 n f 次加減法和 n 2 + 2 ，l f 次乘法；步2 中需要礦一2 ，1 2 ，+ 知f 2 一九2 次加減法和n 3 2 ，1 2 “抽f 2 次乘 法：步3 中需要_ r 1 2 + 2 ，l f 次加減法和知2 + 2 ，l f 次乘法那么共需要的計(jì)算量為 n 3 2 n 2 f + 2 ，l f 2 + 7 n f 次加法和n 3 2 ，1 2 f + 知，2 + 5 n 2 + 5 n “刀2 次乘法如果 f 一三n ，則算法4 1 中的計(jì)算量近似為三”3 個(gè)乘法運(yùn)算和三一3 個(gè)加法運(yùn)算，即n 3 個(gè) 浮點(diǎn)運(yùn)算與傳統(tǒng)的矩陣與矩陣乘積相比較，節(jié)省了大約一半的計(jì)算量如果 ，n 或f 1 ，則無需進(jìn)行約化，直接用傳統(tǒng)的乘法算法但是當(dāng)一為中心對(duì)稱矩 陣時(shí)，只要做一個(gè)小的修正，我們的算法就變成了 4 0 中對(duì)應(yīng)的算法了所以說 我們的算法是 4 0 中對(duì)應(yīng)算法的一個(gè)推廣 算法4 2 該算法用來計(jì)算廣義中心厄米特矩陣與矩陣乘積a p 準(zhǔn)備步： 步1 ：構(gòu)造第三章中方程( 8 ) 所定義的正交矩陣q ，令q 擊( 圣。，蠶：) ， 使得朋州a ：) - f ，其機(jī)刪州嘲，令u = 擊f 蠶：) 步2 ：計(jì)算x 。爿西。，y ；爿蠶：x 步3 ：計(jì)算矩陣五，；茁x ，互：；i m ( 蠶：y ) ，j ：。一i t i l ( a ：x ) 和j ：蠶：y 2 0 j = 瞄習(xí) 計(jì)算步： 步1 ：計(jì)算矩陣 肌腳兒峨階n m ， 步2 ：計(jì)算矩陣 r e ( j v ) - 一r e ( m ) l i i l ( ) 1 l n 似) 并定義 = r e ( ) + f i m ( | v ) 步3 ：計(jì)算矩陣 彤- 去叫- 搟，f 礎(chǔ)r c ( ) + f h n ( ) ) 一抑r e ( ) 一蠶：i i i l ( ) 】 + 圭 蠶。i i i l ( j v ) + a zr e ( ) 】- r e 緲) + 灑) 在該算法中，主要計(jì)算量為計(jì)算爿r e ( m ) 和爿i i i l ) ，按傳統(tǒng)的矩陣與矩陣 乘法算法，總共需要2 ，1 3 個(gè)實(shí)乘法運(yùn)算和2 n 3 個(gè)實(shí)加法運(yùn)算，總共需要4 n 3 個(gè)實(shí)浮 點(diǎn)運(yùn)算而計(jì)算爿p 則需要n 3 復(fù)乘法運(yùn)算和n 3 個(gè)復(fù)加法運(yùn)算容易觀察，一個(gè)復(fù) 乘法運(yùn)算等價(jià)于4 個(gè)實(shí)乘法加上2 個(gè)實(shí)加法運(yùn)算，一個(gè)復(fù)加法運(yùn)算等價(jià)于2 個(gè)實(shí) 加法運(yùn)算所以計(jì)算爿p ，用傳統(tǒng)算法計(jì)算則等價(jià)地需要大約8 n 3 個(gè)實(shí)浮點(diǎn)算術(shù) 運(yùn)算相比較而言，我們的算法節(jié)約了大約一半的計(jì)算量 第五章廣義中心對(duì)稱矩陣一矩陣乘積的塊算法 在上一章中，矩陣一矩陣乘積的算法需要大約加3 次浮點(diǎn)運(yùn)算，它表明還有 其它的計(jì)算矩陣一矩陣乘積的方法，使得計(jì)算量會(huì)有相當(dāng)?shù)臏p少& r 口船冊(cè)算法 是這些方法中最早被發(fā)現(xiàn)的，也是最易于解釋的一種方法該算法把兩個(gè)乘積矩 陣分劃成2 2 的塊矩陣，并且用7 個(gè)矩陣乘法和1 8 個(gè)矩陣加法來計(jì)算子塊，這 些矩陣的子塊為原矩陣階數(shù)的一半 5 1 廣義中心對(duì)稱矩陣一矩陣乘積的跏韶柳算法 算法5 1 ( 在算法4 1 中我們引進(jìn)斯口s s e n 算法( 見參考文獻(xiàn) 3 ) 就可以得到 算法5 1 ) 該算法用來計(jì)算廣義中心對(duì)稱矩陣與矩陣的乘積爿p 準(zhǔn)備步： 步1 ：構(gòu)造第三章中方程( 8 ) 所定義的正交矩陣q ，并作分劃使得 q 一擊( 蠶。，計(jì)其中觚( a ：) 乩，一枷( ，舊。 步2 ：計(jì)算矩陣 i 一爿a 。，哥= 爿蠶： 步3 ：計(jì)算矩陣 e ：薪膏，屹；a ：哥 計(jì)算步： 步1 ：計(jì)算矩陣 ，岫叫弘川餒 y 2 r 貶乏) a 在此步中我們引進(jìn)旭站e h 算法來計(jì)算z ：口y 木 z 一勛s s 明( b ，y ，1 ) 車返回z = b y ，其中曰、y 為月n 階的矩陣豐 k 匕 ， = 、ll， 芝 r r 2 q q 礦 療l ，p m ，玎 z 曩口y e b p 刪砌一b 。封y 5 限凈鰳每個(gè)子塊觶均枷研 階矩陣豐 丁，s ，r 區(qū)，卵n ( 一口。，l ，：。+ y n ，n ) 7 ：一跏韶e n ( 口。+ 口。，y 。+ y 。，n ) r ，跏n 鼯明( 礬，y 。+ y 。n ) r 。一慨一( 曰。y 。，n ) r ，一慨盯( 口，y 。一y 。，多n ) r 。一脅n 船e n ( 如，y ：，一y 。n ) r ，一& 旭船朗( b 。，y 。n ) z 1 l = r l + 丁2 一丁4 + 丁6 z 1 2 - 丁4 + r ， z 2 1 一丁6 + 丁7 z 2 2 一r 2 一r 3 + z 5 一r 7 脅川z 2 巨射 步3 ：計(jì)算矩陣 矽一擊凹- 舡a z ) 眨孫舡u + 瓴，醌厄z z ：) 算法分析：下面我們計(jì)算算法5 1 所需要的浮點(diǎn)運(yùn)算數(shù)我們知道此算法中除在 步2 較算法4 1 有所改進(jìn)以外，其他的步是一樣的在應(yīng)用r 口船明算法計(jì)算 z 制一f 名1 剮乏乏) 時(shí)需要大約2 n k l z 7 2 ，1 2 “次計(jì)算量；然而此時(shí)有： e ：；哎。= o ，故此時(shí)我們只需要1 ，1 2 8 1 次計(jì)算量 綜上所述，當(dāng)n 較大時(shí)，算法5 1 只需要1 n 2 。1 次計(jì)算量，計(jì)算過程更簡(jiǎn)單 明了，比原來的5 加船硎算法減少了總計(jì)算量的 類似地，當(dāng)彳為斜中心對(duì)稱矩陣時(shí)，利用改進(jìn)的m & 明算法計(jì)算一爿p 只需要1 n 2 ”，比原來的算法減少了大約n 2 “，故此算法有很大的實(shí)用價(jià)值 5 2 廣義中心厄米特矩陣一矩陣乘積的脅船鯽算法 在本節(jié)中總是假定爿為月n ( 月一2 冊(cè)) 階的中心厄米特矩陣，p 為h n 階 的任意的矩陣，下面我們來討論此時(shí)緲一爿尸的算法在這一部分當(dāng)中彳、p 分別 記為：月一4 + 塢：尸；號(hào)+ 幔其中4 、4 分別表示爿的實(shí)、虛部：p 。、p ：分 別表示p 的實(shí)、虛部 首先我們考慮用傳統(tǒng)算法計(jì)算一一尸，即 彤a(chǎn) 胛一( 4 + 塢) ( 號(hào)+ 以) ；4 # 一4 足+ f ( 4 罡+ 4 墨) 在這個(gè)計(jì)算過程當(dāng)中我們總共要計(jì)算4 個(gè)n x n 階矩陣的乘法以及4 個(gè)廳n 階矩 陣的加減法，需要的總計(jì)算量大約為：跏3 次計(jì)算量若用勛4 船翻算法計(jì)算大約 需要8 ，l i o | z 7 8 ，l “次計(jì)算量 算法5 2 ( 在算法4 2 中我們引進(jìn)旭韶p n 算法( 見參考文獻(xiàn) 3 ) 就可以得到 算法5 2 ) 該算法用來計(jì)算廣義厄米特矩陣與矩陣的乘積4 p 準(zhǔn)備步： 步1 ：構(gòu)造第三章中方程( 8 ) 所定義的正交矩陣q ，令q 一擊( 蠶，a ：) ， 使得旭似a ：) = f ，其中f - 陽州，訇，令u 一擊( 蠶a ：) 步2 ：計(jì)算膏。_ 蠶，：爿a ： 步3 ：計(jì)算矩陣j 。蠶。7 夏，j 。：l m ( 蠶。7 哥) ，j ：。一j m ( 蠶：孑) 和j 。；蠶：哥 步4 ：構(gòu)造實(shí)矩陣 j 也 計(jì)算