1、3.1 引言 在工程技術、自然科學和社會科學中，經常碰到許多問題最后都可歸結為解線性方程組，如電學中網絡問題、用最小二乘法求試驗數據曲線擬合問題，工程中三次樣條函數插值問題，經濟運營中投入產出問題以及大地測量、機械與建筑結構設計計算問題等等，都歸結為求解線性方程組或非線性方程組數學問題。因此線性方程組求解對于實際問題是極其主要。 第3章 解線性方程組直接法 第1頁第1頁第3章 解線性方程組直接法 常見線性方程組是方程個數和未知量個數相同n階線性方程組，普通形式為 簡記為 Ax=b，其中 ( 3.1 ) 普通b0, 當系數矩陣A非奇異(即detA0) 時，方程組（3.1）有惟一解。 第2頁第2頁

2、線性方程組數值解法普通有兩類：直接法：就是通過有限步算術運算，可求得方程組準確解辦法（若計算過程中沒有舍入誤差），如克萊姆法則就是一個直接法，直接法中含有代表性算法是高斯(Gauss)消去法。迭代法: 就是用某種極限過程去逐步迫近線性方程組準確解辦法。也就是從解某個近似值出發，通過結構一個無窮序列去迫近準確解辦法。(普通有限步內得不到準確解)第3頁第3頁 3.2 解線性方程組直接法（高斯消去法） 3.2.1 高斯消去法基本思想先用一個簡樸實例來闡明Gauss法基本思想例3.1 解線性方程組 解: 該方程組求解過程事實上是將中學學過消元法原則化,將一個方程乘或除以某個常數,然后將兩個方程相加減,

3、逐步減少方程中未知數,最后使每個方程只含有一個未知數,從而得出所求解。整個過程分為消元和回代兩個部分。 第4頁第4頁（1）消元過程第1步:將方程乘上(-2)加到方程 上去,將方程 乘上 加到方程 上去,這樣就消去了第2、3個方程 項,于是就得到等價方程組 第5頁第5頁第2步：將方程 乘上 加到方程 上去，這樣就消去了第3個方程 項，于是就得到等價方程組 這樣，消元過程就是把原方程組化為上三角形方程組，其系數矩陣是上三角矩陣。 （2）回代過程回代過程是將上述三角形方程組自下而上求解，從而求得原方程組解： 第6頁第6頁闡明：前述消元過程相稱于對原方程組 增廣矩陣進行下列變換( 表示增廣矩陣第 行）

4、 同樣可得到與原方程組等價方程組 第7頁第7頁 由此看出,高斯消去法解方程組基本思想是設法消去方程組系數矩陣A主對角線下元素,而將Ax=b化為等價上三角形方程組,然后再通過回代過程便可取得方程組解。換一個說法就是用矩陣行初等變換將原方程組系數矩陣化為上三角形矩陣,而以上三角形矩陣為系數方程組求解比較簡樸,能夠從最后一個方程開始,依次向前代入求出未知變量 這種求解上三角方程組辦法稱為回代, 通過一個方程乘或除以某個常數,以及將兩個方程相加減,逐步減少方程中變元數,最后將方程組化成上三角方程組,普通將這一過程稱為消元,然后再回代求解。通常把按照先消元,后回代兩個環節求解線性方程組辦法稱為高斯（Ga

5、uss）消去法。第8頁第8頁3.2.2 高斯消去法算法結構 我們知道,線性方程組(3.1)用矩陣形式表示為 ( 3.3 ) 解線性方程組（3.1）高斯（Gauss）消去法消元過程就是對( 3.3 )增廣矩陣進行行初等變換。將例3.1中解三階線性方程組消去法推廣到普通 階線性方程組并記則高斯消去法算法結構歸納為： 第9頁第9頁 消元過程,高斯消去法消元過程由n-1步構成： 第1步 設 ,把(3.3)中第一列中元素 消為零,令 用 乘以第1個方程后加到第 個方程上去,消去第2n個方程未知數 ,得到 即 其中 第10頁第10頁第k步 （k=2,3,n-1）繼續上述消元過程，設第k-1次消元已經完畢，

6、得到與原方程組等價方程組 記為 其中第11頁第11頁只要 ,消元過程就能夠進行下去,直到通過n-1次消元之后，消元過程結束，得到與原方程組等價上三角形方程組,記為 或者寫成 第12頁第12頁即 (3.7) （2）回代過程就是對上三角方程組（3.7）自下而上逐步回代解方程組計算，即 第13頁第13頁（3）高斯消去法計算環節： 消元過程;設 計算 回代過程 第14頁第14頁 普通線性方程組使用高斯消去法求解時，在消元過程中也許會出現 情況，這時消去法將無法進行；即使 ，但它絕對值很小時，用其作除數，會造成其它元素數量級嚴重增長和舍入誤差擴散，將嚴重影響計算結果精度。實際計算時必須避免這類情況發生。

7、主元素消去法就可填補這一缺點。 第15頁第15頁互換標準：通過方程或變量次序互換，使在對角線位置上取得絕對值盡也許大系數作為akk(k)，稱這么akk(k) 為主元素，并稱使用主元素消元法為主元素法依據主元素選取范圍分為：列主元素法、行主元素法、總體選（全）主元素法記筆記3.2.4 高斯主元素消去法第16頁第16頁主元素法意義例3.2 用高斯消去法求下列方程組解 解： 擬定乘數 ，再計算系數 假設計算在4位浮點十進值計算機上求解,則有 這時方程組實際形式是 由此回代解出 ,但這個解不滿足原方程組,解是錯誤。這是由于所用除數太小使得上式在消元過程中“吃掉”了下式，處理這個問題辦法之一就是采用列選

8、主元高斯消元法。即按列選絕對值大系數作為主元素，則將方程組中兩個方程相互換，原方程組變為 得到消元后方程組 第17頁第17頁這時 因而方程組實際形式是 由此回代解出 ,這個結果是正確 可見用高斯消去法解方程組時,小主元也許造成計算失敗,由于用絕對值很小數作除數,乘數很大,引起約化中間結果數量級嚴重增長,再舍入就使得計算結果不可靠了,故避免采用絕對值很小主元素。以便減少計算過程中舍入誤差對計算解影響。第18頁第18頁總體選（全）主元素消去法 是通過方程或變量次序互換，使在對角線位置上取得絕對值盡也許大系數作 ，稱這么 為主元素。盡管它算法更穩定，但計算量較大，實際應用中大多數使用列主元素消去法即

9、可滿足需要。 第19頁第19頁全主元素法不是按列選主元素，而是在全體待選系數中選取，則得全主元素法。例3.3 用全主元素法解下列線組 10 x1 - 19x2 - 2x3=3 (1)-20 x1 +40 x2 + x3 =4 (2) x1 + 4x2 + 5x3=5 (3)解：選擇所有系數中絕對值最大40作為主元素，互換第一、二行和互換第一、二列使該主元素位于對角線第一個位置上，得40 x2 - 20 x1 + x3 =4 (4)-19x2+10 x1 - 2x3=3 (5) 4x2+ x1 +5x3=5 (6)記筆記第20頁第20頁計算m21=-19/40=0.475，m31=4/40=0.

10、1(5)- m21(4), (6)- m31(4) 消去x2 得 0.5x1 1.525 x3 =4.9 (7) 3x1 + 4.9 x3 =4.6 (8)選4.9為主元素 4.9 x3 + 3x1=4.6 (9)1.525 x3 +0.5x1=4.9 (10)計算m32=-1.525/4.9=-0.31122， (10)- m32(9)消去x2得1.43366x1=6. 33161 (11)記筆記第21頁第21頁保留有主元素方程40 x2 - 20 x1 + x3 =4 (4) 4.9x3 + 3x1=4.6 (9) 1.43366x1=6. 33161 (11)進行回代x1=4.41634

11、 x3 =-1.76511x2=2.35230第22頁第22頁3.2.4.1 列主元素法列主元素法就是在待消元所在列中選取主元，經方程行互換，置主元素于對角線位置后進行消元辦法。 例3.4 用列主元素法解下列線性方程組 10 x1 - 19x2 - 2x3=3 (1)-20 x1 +40 x2 + x3 =4 (2) x1 + 4x2 + 5x3=5 (3)解：選擇-20作為該列主元素，-20 x1 +40 x2 + x3 =3 (4) 10 x1 - 19x2 - 2x3=4 (5) x1 + 4x2 + 5x3=5 (6)計算m21 =10/-20=-0.5 m31=1/-20=-0.05

12、第23頁第23頁(5)- m21(4), (6)- m31(4)得 x2 1.5x3=5 (7)6x2 + 5.05x3=5.2 (8)選6為主元素6x2 + 5.05x3=5.2 (9) x2 1.5x3=5 (10)計算m32=1/6=0.16667， (10)- m32(9) 得-2.34168x3=4.13332 (11)記筆記第24頁第24頁保留有主元素方程 -20 x1 +40 x2 + x3 =4 (4) 6x2 + 5.05x3 =5.2 (9) -2.34168x3=4.13332 (11)進行回代x3 =-1.76511x2=2.35230 x1=4.41634記筆記 列選

13、主元素計算方法與高斯消去法完全一樣,不同是在每步消元之前要按列選出主元。第25頁第25頁例3.5 用矩陣初等行變換求解方程組 解: 用矩陣初等行變換求解,對增廣矩陣 (下面帶下劃線元素為主元素) 第26頁第26頁第27頁第27頁3.2.5 高斯-約當（Jordan）消去法 高斯消去法有消元和回代兩個過程，消去是對角線下方元素。當對消元過程稍加改變便可使方程組 化為對角陣 （3.8） 這時求解就不需要回代了,這種將主元素化為1,并用主元將其所在列冗余元素全都消為0,即消去對角線上方與下方元素,這種辦法稱為高斯-約當消去法,這時等號右端即為方程組解第28頁第28頁例3.6 用高斯-約當(Jorda

14、n)消去法求方程組解 解 方程組相應增廣矩陣 列選主元故得 第29頁第29頁定理3.4 設A為非奇異矩陣，方程組AX = I增廣矩陣為 C =A I ，假如對C應用高斯-約當消去法化為 I B，則 =B。例3.7 用高斯-約當（Jordan）消去法求 逆矩陣 第30頁第30頁解 C = A I = 第31頁第31頁3.3 矩陣三角分解法 矩陣三角分解法是高斯消去法解線性方程組一個變形解法 。3.3.1 矩陣三角分解原理 應用高斯消去法解n階線性方程組Ax=b, 通過n步消元之后, 得出一個等價上三角型方程組A(n) x=b(n), 對上三角形方程組用逐步回代就能夠求出解來。上述過程可通過矩陣分

15、解來實現。 將非奇異陣A分解成一個下三角陣L和一個上三角陣U乘積 A=LU 稱為對矩陣A三角分解，又稱LU分解。第32頁第32頁其中第33頁第33頁方程組Ax=b系數矩陣A通過順序消元逐步化為上三角型A(n),相稱于用一系列初等變換左乘A結果。事實上，第1列消元將A(1)=A化為A(2)，若令：則依據距陣左乘有L1A(1)=A(2)第34頁第34頁第2列消元將A(2)化為A(3)，若令：經計算可知 L2A(2)=A(3),依這類推,普通有LkA(k)=A(k+1)第35頁第35頁mi1= a(1) i1/ a(1) 11 i=2,3,n于是矩陣 通過消元化為上三角陣 過程可表示為上述矩陣 是一

16、類初等矩陣,它們都是單位下三角陣，且其逆矩陣也是單位下三角陣,只需將 改為 ,就得到 。即 第36頁第36頁于是有 其中 第37頁第37頁L為由乘數構成單位下三角陣，U為上三角陣，由此可見，在 條件下，高斯消去法實質上是將方程組系數矩陣A分解為兩個三角矩陣乘積A=LU。這種把非奇異矩陣A分解成一個下三角矩陣L和一個上三角矩陣U乘積稱為矩陣三角分解，又稱LU分解。 顯然，假如 ,由行列式性質知，方程組系數矩陣A前n-1個順序主子矩陣 非奇異，即順序主子式不等于零，即第38頁第38頁其中 （A主子陣） 反之,可用歸納法證實,假如A順序主子式 則 于是得到下述定理： 第39頁第39頁 把A分解成一個

17、單位上三角陣L和一個下三角陣U乘積稱為杜利特爾（Doolittle）分解。其中 第40頁第40頁若把A分解成一個下三角陣L和一個單位上三角陣U乘積稱為克洛特分解Crout） 其中 第41頁第41頁3.3.2 用三角分解法解方程組 求解線性方程組Ax=b時,先對非奇異矩陣A進行LU分解使A=LU，那么方程組就化為 LU x=b從而使問題轉化為求解兩個簡樸三角方程組 L y=b 求解 y U x=y 求解 x這就是求解線性方程組三角分解法基本思想。下面只簡介杜利特爾（Doolittle）分解法。設A=LU為第42頁第42頁 由矩陣乘法規則 由此可得U第1行元素和L第1列元素第43頁第43頁 再擬定

18、U第k行元素與L第k列元素,對于k=2,3, ,n計算： 計算U第k行元素 （j=k,k+1,n） 計算L第k列元素 （i=k,k+1,n） 第44頁第44頁利用上述計算公式便可逐步求出U與L各元素求解 Ly=b , 即計算: 求解 Ux=y , 即計算： 第45頁第45頁 顯然, 當 時, 解Ax=b直接三角分解法計算才干完畢。設A為非奇異矩陣, 當 時計算將中斷或者當 絕對值很小時，按分解公式計算也許引起舍入誤差積累，因此可采用與列主元消去法類似辦法，對矩陣進行行互換，則再實現矩陣三角分解。 用直接三角分解法解Ax=b大約需要 次乘除法。 第46頁第46頁例3.8 用三角分解法解方程組 求解 Ly=b 得 y= 2，2，1T 求解 Ux=y 得 x= -1，0，1 T因此方程組解為 第47頁第47頁本章小結 本章簡介理解線性方程組直接法。直接法是一個計算量小而精度高辦法。直接法中含有代表性算法是高斯（Gauss）消去法（在第一章提到克萊姆算法也