幾類結(jié)構(gòu)矩陣的快速算法及其應(yīng)用.pdf

1、眾所周知，在工程計(jì)算和實(shí)際應(yīng)用中有許多問題最終都?xì)w結(jié)為矩陣計(jì)算問題，而且不同的應(yīng)用會(huì)導(dǎo)出一些具有特殊結(jié)構(gòu)的矩陣計(jì)算．最常見的一些結(jié)構(gòu)矩陣有Toeplitz矩陣[αi-j]，Hankel矩陣[αi+j]，Vandermonde矩陣[a<,i><'j-1>]，Cauchy矩陣[1/a<,i>-b<,j>]等等．處理與這些結(jié)構(gòu)矩陣有關(guān)的矩陣計(jì)算問題(例如，求解線性方程組、計(jì)算特征值等)，若矩陣的階數(shù)較小時(shí)，通常的經(jīng)典算法是可行的(例如．LU分

2、解算法、QR算法等)．然而，在許多實(shí)際應(yīng)用當(dāng)中，矩陣的階數(shù)n很大(n～10<'6>-10<'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)矩陣的快速算法中最著名的莫過于

3、快速傅里葉變換(即FFT)，有許多快速算法均是由快速傅里葉變換導(dǎo)出的．因此，著名數(shù)學(xué)家Charles Van Loan曾這樣評(píng)價(jià)快速傅里葉變換算法：“從計(jì)算的角度看，快速傅里葉變換是本世紀(jì)最杰出的成就之一，毫不夸張地說，快速傅里葉變換改變了科學(xué)與工程計(jì)算的面貌，如果沒有它，生活將會(huì)是另一種景象”． 本論文主要研究了Toeplitz矩陣、日ankel矩陣、Pascal矩陣以及合流Cauchy-Vandermonde矩陣的一些性質(zhì)及

4、相關(guān)的快速算法，同時(shí)還給出這些快速算法的數(shù)值實(shí)驗(yàn)和在一些問題中的應(yīng)用．理論和數(shù)值實(shí)驗(yàn)顯示，這些快速算法是行之有效的． 第一章，我們簡(jiǎn)單介紹了研究結(jié)構(gòu)矩陣快速算法的現(xiàn)實(shí)意義、研究概況以及常用的研究方法，同時(shí)也給出了與本論文有關(guān)的幾類結(jié)構(gòu)矩陣的定義及其基本性質(zhì)． 在第二章和第三章，我們主要是利用Toeplitz矩陣和Hankel矩陣的特殊結(jié)構(gòu)，導(dǎo)出相應(yīng)的遞推關(guān)系式，然后再利用快速傅里葉變換(FFT)，給出了計(jì)算Toeplit

5、z矩陣的正弦變換和Hankel矩陣的余弦變換的快速算法(算法計(jì)算復(fù)雜度為O(nlogn))．該算法不僅快而且存貯有效，因?yàn)樵趫?zhí)行該快速算法的過程中，不需要存貯任何矩陣．同時(shí)在第二章中，我們還給出了該快速算法在利用Jacobi旋轉(zhuǎn)變換計(jì)算Toeplitz矩陣的特征值中的應(yīng)用。數(shù)值實(shí)驗(yàn)顯示，對(duì)變換后的矩陣?yán)肑acobi旋轉(zhuǎn)變換方法求其特征值所需要的掃描次數(shù)大約為對(duì)原矩陣?yán)肑acobi旋轉(zhuǎn)變換方法求其特征值所需要的掃描次數(shù)的三分之一．

6、 第四章，我們研究了Pascal矩陣的一些性質(zhì)，并且給出了計(jì)算系數(shù)矩陣為Pascal矩陣的線性方程組的解的一個(gè)快速算法，該算法的計(jì)算復(fù)雜度為O(nlogn)，比文[22]所給的快速算法運(yùn)算量要少([22]中所給的快速算法的計(jì)算復(fù)雜度為O(n<'2>).))．此外，我們還將我們所設(shè)計(jì)的快速算法用到了常系數(shù)非同態(tài)常微分方程的求解中． 第五章，我們討論了一類在有理插值問題中有著廣泛應(yīng)用的矩陣，即合流Cauchy-Vandermon

7、de矩陣．利用塊．Neville消去，給出了合流Cauchy-Vandermonde矩陣及其逆矩陣的塊雙對(duì)角分解，推廣了文[52]的結(jié)果． 第六章，我們討論了K．R．：Driessel在文[19]中所提出的一個(gè)問題，即Problem A：任給n個(gè)實(shí)數(shù)，若它們是一個(gè)n階實(shí)Hankel矩陣的特征值，則這n個(gè)實(shí)數(shù)必須滿足何條件?對(duì)Problem A，我們給出了幾個(gè)必要條件，并且得到了Problem A的必要條件的一個(gè)通用表達(dá)式，推廣了