幾類結構矩陣的快速算法及其應用.pdf

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

2、解算法、QR算法等)．然而，在許多實際應用當中，矩陣的階數(shù)n很大(n～10<'6>-10<'9>)或某個線性方程組需要多次計算直到得到一個滿意的結果(例如用迭代法時)，此時這些經典的算法由于代價太大而失去了實際意義． 因此，針對這些結構矩陣的特點而設計一些能利用它們的結構的，數(shù)值穩(wěn)定的快速算法，具有非常重要的意義．正因為結構矩陣在實際應用中所具有的重要意義，國內外眾多的學者將目光投入到這一領域．結構矩陣的快速算法中最著名的莫過于

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

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

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

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

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