線性方程組解法綜述

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