蒙偉擬Toeplitz帶狀矩陣線性方程組的并行算法(最終版)

1、擬Toeplitz帶狀矩陣線性方程組的并行算法蒙 偉（咸陽師范學院 數(shù)學與信息科學學院 陜西 咸陽 712000 ）摘 要本文主要研究了Toeplitz矩陣線性方程組的并行算法。首先介紹了Toeplitz矩陣的定義、分類及半正定性等，然后分別給出了三對角Toeplitz線性方程組、擬對稱七對角Toeplitz線性方程組的并行算法的誤差分析。最后，用Matlab語言編寫了算法程序，通過實例計算，結果表明本文算法是可行的，并且驗證了理論分析與實際計算的結果是一致的。關鍵詞：Toeplitz矩陣；Toeplitz線性方程組；誤差分析；并行算法；并行性分析；擬對稱七對角Toeplitz線性方程組Par

2、allel Algorithm for Solving Banded quasi-Toeplitz Matrix Linear EquationsMeng wei(School of Mathematics and Information Science of Xianyang NormalUniversity Xianyang 712000)AbstractThis paper studies parallel algorithm of the Toeplitz matrix linear equations. Firstly, I introduce the definition, cla

3、ssification, and semi-positive definite of Toeplitz matrix and so on, and then give the error analysis of parallel algorithm for solving the three-diagonal Toeplitz matrix linear equations and quasi-symmetry seven diagonal Toeplitz matrix linear equations. Finally, I program the algorithm procedure

4、using Matlab software. The results show that the algorithm is feasible, and the theoretical analysis is consistent with the result of practical calculation. KEY WORDS：Toeplitz matrix; Toeplitz matrix linear equations; Error analysis; Parellel algorithm; Quasi-symmetry seven diagonal Toeplitz matrix

5、linear equations目錄摘要IABSTRACTII前言11 TOEPLITZ矩陣及其性質31.1 Toeplitz的定義31.2 Toeplitz的半正定性42 三對角TOEPLITZ矩陣線性方程組的并行算法52.1 并行算法52.2 誤差分析82.3 并行性分析92.4 算例103 擬對稱七對角TOEPLITZ矩陣線性方程組的并行算法113.1并行算法113.2 誤差分析164 結論17參考文獻18附錄19謝辭24前 言Toeplitz矩陣是數(shù)學和工程中應用廣泛的特殊矩陣之一。由于工程中許多典型問題都涉及Toeplitz線性方程組的求解，所以有必要就Toeplitz線性方程組的求

6、解進行詳細介紹。利用Toeplitz矩陣具有的非正常特殊的結構，我們可以由三對角Toeplitz矩陣線性方程組的并行算法得出對稱七對角Toeplitz矩陣線性方程組的并行算法。隨著高性能并行機的出現(xiàn)，為了更好的利用并行機，研究并行算法已知變的越來越重要了。在許多的工程問題中出現(xiàn)Toeplitz矩陣的線性方程組的求解問題，研究該問題的并行算法具有重要的現(xiàn)實意義。目前，對于對稱三對角Toeplitz線性方程組的并行算法的研究，已獲得了良好的結果，并利用此推廣到了對稱五對角Toeplitz線性方程組的求解，在此我先對L.EGarey的研究過程作簡要的介紹。首先，我們先看看L.EGarey對五對角的處

7、理過程由 ，可得，計算 進行LU分解得：，且在中，是一個階的形式的矩陣，是階零矩陣。在中，是一個階的形式的矩陣，是只有其它位置為0的矩陣。只有4個非零元素：，即 （a） （b）誤差分析：這就是L.EGarey對五對角線的主要處理過程。在本文中，我們利用此思想，在文章的第一章中給出Toeplitz的定義和其性質，其次在第二章介紹三對角Toeplitz矩陣的線性方程組的算法，在第三章給出特殊對稱七對角線性方程組的算法，并給出了誤差分析。通過上機計算表明，理論與實際是一致的。1 Toeplitz矩陣及其性質1.1 Toeplitz的定義在數(shù)學和工程（例如信號處理與系統(tǒng)理論等）問題中，常常需要求解具有

8、特殊結構的線性方程組，其中 （1.1）這種形式取的矩陣稱為Toeplitz矩陣。因此，任何一條對角線取相同元素的矩陣是Toeplitz矩陣，之所以稱為Toeplitz矩陣，乃是這種特殊矩陣是Toeplitz于1900年代初在研究與Laurent級數(shù)有關的雙線性函數(shù)的一篇論文中提出來的。最常見的Toeplitz矩陣為對稱Toeplitz矩陣，即其元素還滿足對稱關系，可見，對稱Toeplitz矩陣僅由其第1行元素就可完全描述，因此，常將對稱Toeplitz矩陣簡記作。若一個復Toeplitz矩陣的元素滿足復共軛對稱關系，即 （1.2）則稱之為Hermitian Toeplitz矩陣特別地，具有特殊

9、結構 （1.3）的維Toeplitz矩陣稱為Hermitian Toeplitz矩陣；而 （1.4）稱為Hermitian Toeplitz矩陣。式中，為實數(shù)，顯然，一個斜Hermitian型Toeplitz矩陣可以寫作，其中，為斜Hermitian Toeplitz矩陣，斜Hermitian Toeplitz矩陣和斜Hermitian 型Toeplitz矩陣在求解離散化的雙曲差分方程時經(jīng)常會遇到。1.2 Toeplitz的半正定性Toeplitz矩陣在數(shù)學和工程中有著廣泛的應用。例如，在信號處理中，有賴于通過求解Toeplitz矩陣方程組獲得的參數(shù)包括：遞推數(shù)字濾波器的系數(shù)，一維和二維平穩(wěn)回

10、歸（AR）模型的AR參數(shù)等，又如，信號和圖像的恢復也可歸結為Toeplitz矩陣方程組的求解，其他的應用例子有：偏微分方程和卷積型方程的求解，Pade逼近和控制理論中的最小實現(xiàn)問題等?？疾槭剑?.1）的對稱Toeplitz矩陣，令其主子式為， （1.5）則是正定的，當且僅當，然而，值得指出的是，類似的結論對于對稱Toeplitz矩陣的半正定性卻不一定成立。更具體地說，這一事實對于的半正定性并不是充分條件，請看一個反例： （1.6）在這個例子中，但是，刪去矩陣的第2行和第2列組成的主子式都不大于或等于零時，對稱Toeplitz矩陣才是半正定的，顯然，這一條件的判斷比較麻煩，下面給出了對稱Toep

11、litz矩陣半正定性的一種簡單檢驗方法，它不需要計算任何主子式。令，是一個對稱Toeplitz矩陣，若是滿足正定和條件的最小正整數(shù)，則矩陣，是半正定的，當且僅當系數(shù)服從遞歸方程， （1.7）式中，為模型的系數(shù)。Toeplitz矩陣具有以下性質：（1）Toeplitz矩陣的線性組合仍然為Toeplitz矩陣；（2）若Toeplitz矩陣的元素，則為對稱Toeplitz矩陣；（3）Toeplitz矩陣的轉置仍然為Toeplitz矩陣；（4）Toeplitz矩陣的元素相對于交叉對角線對稱。2 三對角Toeplitz矩陣線性方程組的并行算法2.1 并行算法設方程組 （2.1）其他當時，（1）轉化成 （

12、2.2）設，將進行如下分裂： （2.3）其中 ，其中，且，?？煞纸鉃椋浩渲?（2.4）由（2.4）知取的解設其中 ，即：首先求解方程組：，顯然可以化為兩個方程組：這就把一個大方程組分解成兩個小的方程組求解。如此類推我們可以把一個大方程組分解成3個，4個甚至更多，從而方便了方程組的并行求解。由，我們可以推得所以只需求解以下三個方程：，按照文獻1中的方法取其中為中的根，即。由于所以因而解的近似解 （2.5）通過如上的推理我們得到了近似解的表達式（2.5）。2.2 誤差分析在此，我們進行如下的誤差分析：因為取向量的無窮范數(shù)，那么有我們可以得到如下結論。定理：由（2.4）式得到的近似解，那么滿足由此可

13、見，得好壞直接取決于的大小，若要求，只需，由此可得到： （2.6）由于，所以若要達到精度要求，矩陣的階數(shù)應大一些。當矩陣中時就是一個對稱的。只要把用進行替代就可以處理三對角對稱情形。2.3 并行性分析為了方便起見，我們不妨設，是處理機臺數(shù)，每臺處理機求解需要的時間為： 在修正過程需要時間運算量為： 并行通訊二次需要時間為： 并行計算時間為：串行元素按時間為： 所以 并行加速比為： 并行效率 按照并行算法的意義在時，可見該并行算法具有良好的并行性。2.4 算例方程中，為一120階非對稱Toeplitz矩陣我們求得方程組的近似解要求，由（2.6）式可得取實際計算結果得：我們舉第二個例子如下：要求，

14、由（2.6）式可得取實際計算解果得：近似解和精確解的誤差在分裂后生成的誤差都小于這就意味著解的各個分量誤差均小于，解的符合性較好。其中為把矩陣進行LU分解時的下三角矩陣中的元素，為非對稱矩陣修正時的，是修正方程的近似解。由程序的運行結果和理論計算非常的接近，滿足誤差分析的精度要求。由于實際的計算結果和理論結果結合的比較合適，沒有出現(xiàn)較大的誤差。由于矩陣的元素取值非常的苛刻，對于隨機輸入元素的計算結果離理論結果非常的遠，如主對角元素為，其出現(xiàn)的誤差達到了，離我們的理論結果相去甚遠。3 擬對稱七對角Toeplitz矩陣線性方程組的并行算法3.1并行算法在許多的工程問題中都會出現(xiàn)特征值的求解問題。在

15、對特征值求解的研究中，向后差分法和有限分法都存在比較狹窄的使用前提。對于滿足有邊界條件和輔助條件的系統(tǒng)是完全的且系數(shù)矩陣是對稱的，而以自然輔助條件取代邊界條件和輔助條件的系統(tǒng)，帶狀系數(shù)矩陣變成了非對稱的。對于帶狀擬對稱系統(tǒng)引出了新的研究工作。為了尋找一個有效的并行解法求解工程中更為一般的問題，在文獻1中引入了一個五角對角線擬Toeplitz帶狀對稱矩陣的有效并行算法。為推廣該方法的應用，我認為可以對其作進一步的推廣，以適應更為復雜的問題的求解。本文以七對角線為例，對于更高階的推廣可以依次進行類型的拓展。首先，我們引入一個階的系統(tǒng) （3.1）其中 （3.2）矩陣就是一個對稱七對角擬Toeplit

16、z矩陣。令 有令，則可寫成如下形式參照文獻1中五對角線矩陣的處理方法，將分解為其中為三對角線對稱矩陣，為無對角線對稱矩陣，分別為：由知道，我們可以得到如下等式有方程組 我們求得的值。由的值我們可以求得的值。在該處理過程中，需要滿足為主對角占優(yōu)矩陣，則必須成立。為一無對角線帶狀對稱矩陣，則對可進行如同的分解，則，和均為一個三對角線帶狀對稱矩陣。此時令此時或者其中必須有一個成立。不失一般性，不妨令，綜合對的處理條件，我們要進行操作的充分條件是或者或者由于為對角占優(yōu)（也是一樣處理）可以寫成如下形式其中其中，按照在文獻2中的方法對進行分解得，我們注意對和都是對角占優(yōu)的。由和的兩個關系，令且 由這些值，

17、分解到和只需要少量的計算量。我們也可以把寫出如下形式 （3.3），若，則，若，則在中，是一個階的形式的矩陣，是階零矩陣。在中，是一個階的形式的矩陣，是只有其它位置為0的矩陣。只有4個非零元素：，即 右邊的數(shù)字表示對應的行數(shù)由，得即：用文獻2中的并行方法進行求解的近似解 （3.4）再求解，得（7）式的近似值，以此類推，這種方法可以廣泛的推廣到把系統(tǒng)分成4個或更多的子系統(tǒng)而用并行算法求解。除了一些明顯的限制外，修正部分要求每個方程組的階數(shù)足夠的大，以適應最終近似的準確度要求。利用1中的方法，得到方程組的近似解，即就是（3.2）的近似解。要求（3.1）的解，必須對解進行修正。因為所以其中這時我們需要

18、求兩個向量，使得，設，其中是方程個不同的根。顯然，的確定只需的前三與后三個方程解得。而，這樣我們得到了方程組（3.1）的近似解3.2 誤差分析設， 分別是，的近似解，因為 =所以可見其誤差直接取決于三個三對角線性方程組的解的誤差，其近似度等于 所以解七對角線性方程組結果的好壞，關鍵的問題就是其近似分解出的每個三對角線性方程組的結果的好壞，只要三對角線性方程組的結果好，則七對角線性方程組的結果也不會差。我們只給出算法分析，由于方程最終的近似需要修正很多的誤差，在程序上進行實現(xiàn)比較困難，我們用并行算法求解七對角甚至更高的時候，修正的部分比較多，為了實現(xiàn)更加近似的近似解，我們要對誤差的修正做更加精確

19、的修正。4 結論本文采用并行數(shù)值解法解決了具有Toeplitz系數(shù)矩陣的七對角線性方程組，我們在論文的開頭引入了我們要解決的系統(tǒng)并對其進行了第一步的修正處理，在論文的第二部分，我們具體的分析了對稱系統(tǒng)的性質及其可以修正的修正過程，我們分別對第一部分中引入的系統(tǒng)作了LU分解和并行算法的處理，并比較了他們處理的條件和最后結算量在不同條件下的比較。在本文的第三部分，我們對擾動系統(tǒng)作了修正，并且找到第一部分引入系統(tǒng)的近似解，通過引入的定理對系統(tǒng)的最終解做出了近似并分析了各自在給定精度下的允許誤差限。并最終求解出系統(tǒng)的最終近似解。在論文的最后一部分，我們再一次對處理系統(tǒng)的LU方法和本文提供的近似并行解法

20、的運算量作了最后的比較，并指出了近似并行解法的優(yōu)越性和前景分析。參 考 文 獻1 LEGarey A parallel numerical algorithm for near symmetric and banded systems 2 WMYanKLChung，A fast algorithm for soving special tridiagonal systems，Computing 52(1994)203-2113 JMMcNally，LEGarey，REShaw，A split-correct parallel algorithm for solving tridiagonal

21、symmetric Toeplitz systems，IntJComputMaths 4M.M.chawla，C.P.Katti，A new fourth-orded method for computing eigenvalue，of two-point boundary value problems，BIT20(1980)511-5145M.Chen，On the solution of circulant liner systems，SIAMJ.Numer.Anal.24(1987)668-6836L.E.Garey，R.E.Shaw，A parallel algorith for so

22、lving Toeplitz liner systems，Appl.Math.Comp.100(1999)241-2477J.H.Bramble，B.E.Hubbard，On afinite difference analogue of an elliptic boundary value problem which is nerthei diagonally dominant nor of non-negative type，J.Math.Phys.43(1964)117-1328A.Ralston，A First Course in Numerical Analysis，McGraw-Hi

23、ll，New York，19659O.Rojo，A new method for solving symmetrical circulant tridagonal systems of liner equations，Comput.Math.Appl.20(1990)61-6710 R.E.Shaw，L.E.Garey，A fast method for solving second order boundary value Volterra integro-differential equations，Int.J.Comput.Math 65(1997)121-12911 成田誠之助著.張賢

24、達譯.數(shù)學系統(tǒng)控制理論及應用.北京：機械工業(yè)出版社，198412 陳景良，陳向輝.特殊矩陣.北京：清華大學出版社，200113 黃琳.系統(tǒng)與控制理論中的線性代數(shù).北京：科學出版社，198414 數(shù)學手冊編寫組，數(shù)學手冊.北京：高等教育出版社，197915 張賢達.現(xiàn)代信號處理.北京：清華大學出版社，199516 張賢達.現(xiàn)代信號處理（第二版）.北京：清華大學出版社，200217 張賢達.信號處理中的線性代數(shù).北京：科學出版社，199718 張賢達.矩陣分析與應用.北京：清華大學出版社，2004附 錄求解程序：使用Matlab按照并行算法的思想求解Toeplitz矩陣線性方程組的近似解并分析了它

25、們的誤差，充分證明該方法的現(xiàn)實意義和廣闊的發(fā)展前景。我們只附求三對角非對稱的程序如下：n=input（請輸入矩陣的維數(shù)）；a1=input（請輸入主對角線元素）；b1=input（請輸入第一行第二列的元素）；c1=input（請輸入第二行第一列的元素）；b=zeros(n，1)；b9=1；for i=1:n v=i b(i，1)=b9；endb；A=zeros(n)；for i=1:nfor j=1:n if i=j A(i，j)=a1； elseif j=i+1 A(i，j)=b1； else A(i，j)=0； end end endA；A1=zeros(n)；A1=A；if c1>

26、=b1A1=A/b1；b=b/b1；else A1=A/c1； b=b/c1；endA1；b；a2=A1(2，2)；c2=A1(2，1)；S=solve(f-d=a2，-f*d=c2，f，d)f=S.f；f=double(S.f)；d=S.d；d=double(S.d)；/求，其實由關系我們可以用求解/if abs(d)<1 /使用取絕對值大于1的/ f /由關系，求出/ delse d1=input(您輸入元素不符合條件，請重新輸入)；endA2=zeros(n)；A2=A1；A2(1，1)=f；A2；m=ceil(n/2) pl=zeros(m)；for i=1:mfor j=1:m

27、 if i=j p1(i，j)=a2；elseif i=j+1 p1(i，j)=c2；elseif j=i+1 p1(i，j)=1；else p1(i，j)=1；p1(1，1)=A2(1，1)； p1(m，m)=A2(n，n)； endend p1k=n-m for i=1:kfor j=1:k if i=jp2(i，j)=a2；elseif i=j+1p2(i，j)=c2；elseif j=i+1 p2(i，j)=1；else p2(i，j)=0；p2(1，1)=A2(1，1)； p2(k，k)=A2(n，n)； end p2s=zeros(n)；for i=1:m forj=1:ms(j，i)=p1(j，i)； endendfor i=1:k； for j=1:k s(m+j，m+i)=p2(j，i)； endendb1=zeros(m，1)；b2=zeros(k，1)；for i=1:m b1(i，1)=b(i，1)；endfor i=1:k b2(i，1)=b(m+i，1)；endb1；b