線性方程組解法綜述

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