線性方程組解法綜述

線性方程組解法的研究綜述摘要：這篇論文在說明了線性方程組的應(yīng)用目的的基礎(chǔ)上，提出了線性方程組求解的研究現(xiàn)狀，并列舉了常用的求解方法，同時說明了它們的應(yīng)用條件，剖析了各種方法的不足之處。關(guān)鍵詞高斯消元迭代病態(tài)方程組一、問題提出在自然科學(xué)和工程實際應(yīng)用中，有許多問題的求解最終都轉(zhuǎn)化為線性方程組的求解問題。例如,電學(xué)中的網(wǎng)絡(luò)問題，曲線擬合中常用的最小二乘法、樣條函數(shù)插值、解非線性方程組、求解偏微分方程的差分法、有限元法和邊界元法以及目前工程實踐中普遍存在的反演問題等。特別是在圖像恢復(fù)、模型參數(shù)估計、解卷積、帶限信號外推、地震勘探等眾多領(lǐng)域，都需要求解線性方程組。由于線性方程組問題在理論上的重要性和在工程實際應(yīng)用中的大量存在，多年來人們在這方面做了廣泛深入的研究和探討，并取得了許多有價值的成果.由于模型誤差、測量誤差、計算誤差等各種誤差的存在，常常使得線性方程組中的系數(shù)矩陣和非齊次項信息具有某種程度的近似性(即擾動性)，這種近似性顯然會使得線性方程組的求解不容易得到真實的理論解。此時，不同的求解方法由于運算機理不一樣，求解過程中誤差積累程度就不一樣，因此必然會使得不同的求解方法得到的解具有不同的逼近真解的誤差程度，尤其對具有病態(tài)性的方程組而言，由于病態(tài)線性方程組的條件數(shù)很大，數(shù)據(jù)誤差以及計算過程中引入的舍入誤差往往會使線性方程組的解不穩(wěn)定，即不管原始數(shù)據(jù)的誤差多么小，都可能造成解的很大變化，使線性方程組的解嚴重失真。因此，許多現(xiàn)有的方法都是無效的，病態(tài)線性方程組的求解變得相當困難。求解線性方程組的最常用的方法主要有直接法和迭代法兩大類，其中直接法中最常用的方法是高斯消元法。但是，該方法求解病態(tài)線性方程組時不能得到合理的解，誤差很大。二、研究現(xiàn)狀目前關(guān)于線性方程組的數(shù)值解法一般有兩大類。一類是直接方法，另一類是迭代方法。直接方法最基本的是高斯消元法及其變形，這類方法是解低階稠密矩陣方程組的有效方法，近十幾年來直接法在求解具有較大型稀疏矩陣方程組方面取得了較大進展。迭代法就是用某種迭代過程去逐步逼近線性方程組的精確解，迭代法具有需要計算機的存儲單元較少，程序設(shè)計簡單，原始系數(shù)矩陣在計算過程中始終不變等優(yōu)點，但存在收斂性及收斂速度問題。迭代法是解大型稀疏矩陣方程組的重要方法。當前對迭代算法的研究已經(jīng)較為成熟，但如何使之適合新體系模型，以獲得更好的性能加速一直是應(yīng)用和體系設(shè)計者關(guān)心的問題。三、常用方法比較1.直接方法直接方法是指假設(shè)計算過程中不產(chǎn)生舍入誤差，經(jīng)過有限次運算可求得方程組的精確解的方法。事實上，由于舍入誤差的存在，用直接法一般也只能求得方程組的近似解。直接方法中主要有三種方法：克拉默法則、高斯消元法、LU分解法。（1）克拉默法則設(shè)有線性方程組（n個未知數(shù)n個方程）其矩陣形式為Ax=b其中如果線性方程組的系數(shù)行列式不為零，即det(A)≠0,則該方程組有唯一解。由克拉默法則知，其解為其中Ai為上述方程組的右端向量b代替A中第i列向量所得的矩陣。高斯消元法設(shè)（1）如果，將第一個方程中x1的系數(shù)化為1，得其中從其它n–1個方程中消x1，使它變成如下形式由方程（1）到（2）的過程中，元素a11起著重要的作用，特別地，把a11稱為主元素。如果（2）中a220，則以a22（1）為主元素，可以把方程組（3）化為：（3）針對（3）繼續(xù)消元，重復(fù)同樣的手段，第k步所要加工的方程組是：設(shè)a≠0，第k步先使上述方程組中第k個方程中x的系數(shù)化為1，然后再從其它（n-k）個方程中消，消元公式為:按照上述步驟進行n次后,將原方程組加工成下列形式:回代公式為:綜上所述,高斯消去法分為消元過程與回代過程，消元過程將所給方程組加工成上三角形方程組，再經(jīng)回代過程求解。由于計算時不涉及xi,i=1,2,…,n，所以在存貯時可將方程組AX=b，寫成增廣矩陣（A,b）存貯。下面，我們統(tǒng)計一下高斯消去法的工作量；在（4）第一個式子中，每執(zhí)行一次需要n?(n?k)次除法，在（4）第二個式子中，每執(zhí)行一次需要[n?(k?1)]×(n?k)次除法。因此在消元過程中，共需要次乘作法。此外，回代過程共有次乘法。匯總在一起，高斯消元法的計算量為：。(3）選主元的高斯消元法主元素法一般包括兩種：列主元素法和全主元素法。這兩種主元素法的精度差不多，且全主元素法程序設(shè)計復(fù)雜且占用機器時間較多。在實際應(yīng)用中一般采用列主元素法，它既簡單又能保證計算精度。方法如下：給定線性方程組Ax=b，設(shè)（1）列主元的高斯消元法的具體過程如下：第一步：首先在增廣矩陣（1）中的第一列選取絕對值最大的元，如，則有，將（1）中的第一列嶼第列互換。為方便起見，記行互換后的增廣矩陣為[，]，然后進行第一次消元，得矩陣：第二步：在矩陣[A（2），b（2）]的第二列中選主元，比如，將矩陣[A（2），b（2）]的第二行與第i2進行互換，再進行第二次消元，得矩陣[A（3），b（3）].第k步：在矩陣[A(k)，b（k）]的第k列中選主元，進行第k次消元。如此，經(jīng)過n?1步，增廣矩陣（1）被化成上三角形，最后由回代過程求解。并且可證明，只要det（A）0，列主元素法就可以順利完成，即不會出現(xiàn)akk（k）=0的情景。（4）矩陣的三角分解法把一個n階方陣A分解成結(jié)構(gòu)簡單的三角形矩陣稱為矩陣的三角分解。事實上，只要A非奇異，經(jīng)過一定的行交換后，它一定可以分解成兩個三角形矩陣的乘積。設(shè)A=LU,其中L為單位下三角矩陣，U為上三角矩陣。對矩陣A進行LU分解是有條件的，它要求在對A進行高斯消元的時候，所有的主元素均不為零。那么，A滿足什么條件才能保證這一要求呢？見下面的定理。定理：若A為n階矩陣，且所有順序主子式都不等于零，則存在唯一的單位下三角矩陣L和上三角矩陣U使A=LU。如果線性方程組Ax=b的系數(shù)矩陣已經(jīng)進行三角分解，A=LU，則解方程組Ax=b等價于求解兩個三角形方程組Ly=b,Ux=y，即由可求出再由解得用三角分解法求解線性方程組的乘法運算量是數(shù)量級。由于在求出，，yi后，aij和bi就無須保留了，故上機計算時，可把L,U和y存在A,b所占的單元，回代時x取代y，整個計算過程中不需要增加新的存儲單元。而且系數(shù)矩陣的三角分解與右端常數(shù)項無關(guān)，故在計算系數(shù)矩陣相同而右端項不同的一系列方程組時，用三角分解法更為簡便。2.迭代方法迭代法是從某一取定的初始向量x（0）出發(fā)，構(gòu)造一個適當?shù)牡?，逐次計算出向量x（1），x（2），....，使得向量{x（k）}收斂于方程組的精確解。這樣，取適當大的k，可取x（k）方程組的近似解。與直接法不同的是，即使在計算過程中無L舍入誤差，迭代法也難以獲得精確解。而迭代法具有計算簡單，易于編制程序等優(yōu)點，特別適合于求解大型稀疏線性方程組。L（1）雅可比（Jacobi）迭代法的系數(shù)矩陣A非奇異，不妨設(shè)aii0，將方程組（2）變形為建立迭代公式取初始量x（0）后，由式三反復(fù)迭代得到向量序列{x（k）}，滿足x（k+1）=Bx（k）+g，（k=0,1,2.....n）其中B為迭代矩陣，迭代公式為為了方便的表示出迭代矩陣B，常把系數(shù)矩陣分解為A=D-L-U,其中D=diag（a11，a22.....ann），于是有x（k+1）=D-1（L+U）x（k）+D-1b，即B=D-1(L+U)=D-1(D-A)=I-D-1A,g=D-1b.高斯——賽德爾（Gauss-Seidel）迭代法的基礎(chǔ)上，改寫：如下；取初始量想x（0）后，得迭代公式結(jié)論通過上述分析，發(fā)現(xiàn)各解線性方程組的方法都存在不足之處：1.直接法實際計算中，由于舍入誤差的存在和影響，這種方法只能求得線性方程組的近似解。對于高階方程組，直接法求解的計算量往往過大。（1）克拉默法則求解線性方程組：必須計算n+1個n階行列式并做n次除法，而每個n階行列式的計算又需要作(n?1)×n!次乘法，計算量十分驚人。例如當n=20時，需要作5.109×109次乘法，因而此法是不實用的。(k)(k+1)(k+1)(k+1)(k+1)(k+1)（2）高斯消元法：在消元的過程中，可能出現(xiàn)主元為零的情況，這時消元法無法進行，即使主元不為零但很小，若用其作除數(shù)(k)(k+1)(k+1)(k+1)(k+1)(k+1)矩陣的三角分解法：矩陣A可以進行三角分解是有條件的，它要求A為方陣且A的所有順序主子式均不等于零。2.迭代法迭代法存在收斂性及收斂速度問題，在判斷收斂性時，一般尋找迭代矩陣，這時會涉及到矩陣的求逆和乘法運算，而矩陣的譜半徑一般也不易求出。另外，迭代法的計算訪存比較低，尤其是系數(shù)矩陣為稀