數值分析講義——線性方程組的解法

1、§3.7 三角分解法§3.8 追趕法§3.9 其它應用§3.10 誤差分析§3.11 總結數值分析講義第三章線性方程組的解法§3.1 引言站.1 雅可比(Jacobi)迭代法§3.2 高斯-塞德爾(Gauss-Seidel)迭代法§3.3 超松馳迭代法§3.4 迭代法的收斂性§3.5 高斯消去法§3.6 高斯主元素消去法§3.7 講評3§ 3.0 引言重要性：解線性代數方程組的有效方法在計算數學和科學計算中具有特 殊的地位和作用.如彈性力學、電路分析、熱傳導和振動、

2、以及社會科學及 定量分析商業(yè)經濟中的各種問題.分類：線性方程組的解法可分為直接法和迭代法兩種方法.(a)直接法：對于給定的方程組，在沒有舍入誤差的假設下，能在預定的 運算次數內求得精確解.最基本的直接法是Gauss消去法，重要的直接法全 都受到Gauss消去法的啟發(fā).計算代價高.(b)迭代法：基于一定的遞推格式，產生逼近方程組精確解的近似序列 . 收斂性是其為迭代法的前提，止匕外，存在收斂速度與誤差估計問題 簡單實 用，誘人.a1雅可比Jacobi迭代法(AX = b)1二基本思想：與解f(x)=0的不動點迭代相類似，將AX=b改寫為X=BX+f的形式，建立 雅可比方法的迭代格式：Xk+1=B

3、X的+f ,其中，B稱為迭代矩陣.其計算精度可 控，特別適用于求解系數為大型稀疏矩陣(sparse matrices的方程組.2問題：(a)如何建立迭代格式？(b)向量序列Xk是否收斂以及收斂條件？3例題分析：10x1 - x2 - 2x3 = 7.2考慮解方程組- x1 + 10x2 - 2x3 = 8.3(1)x1 - x2 + 5x3 = 4.2其準確解為X* =1, 1.2, 1.3.建立與式(1)相等價的形式：x1 = 0.1x20.2x3 0.72x2 = 0.1x10.2x3 0.83(2)、x3 = 0.1x1 + 0.2x2 + 0.84據此建立迭代公式：x1(k 1)= 0

4、.1x2k)0.2xk 0.72x2k 1)= 0.1x1(k)0.2x3k)0.83(3)x3k 1)= 0.1x1(k)0.2x2k)0.84取迭代初值x(0) = x20) = x30) = 0,迭代結果如下表.JocabiMethodP31.cpp迭代次數x1x2x301234567891011121314150000.720.830.840.9711.071.151.0571.15711.24821.08535 1.18534 1.282821.095098 1.195099 1.2941381.098338 1.198337 1.2980391.099442 1.199442 1.

5、2993351.099811 1.199811 1.2997771.099936 1.199936 1.2999241.099979 1.199979 1.2999751.099993 1.199993 1.2999911.099998 1.199998 1.2999971.099999 1.199999 1.2999991.11.21.31.11.21.34 Jocobi迭代公式:設方程組AX=b,通過分離變量的過程建立Jocobi迭代公式，即n, ajXj = bi,為=0(i = 1,2, ,n) i =11八x(bi - ； ajXj) (i = 1,2, ,n)aiij =1iij

6、=i由此我們可以得到Jacobi迭代公式：(k 1)1n kX = (bi -ajXi ) (i = 1,2, ,n) aii j Tj =iJacobi迭代公式的算法1：初始化.n, (aj), (bj), (X1) , M.2:執(zhí)行k=1直到M為止. 執(zhí)行i=1直到n為止.nUi ,(h - ' ajXj)/aii ；j =1 j=i 執(zhí)行i=1直到n為止.X 'Ui ； 輸出k, (Xi).另外，我們也可以建立Jacobi迭代公式的矩陣形式設方程組AX=b,其中，A=(aj)n為非奇異陣，X = (X1,X2, Xn)T,b=(b1,b2, bn)T將系數陣A分解為：A=

7、 U+D+L,U為上三角矩陣，D為對角矩陣，L為下三角矩陣.于是AX = b可改寫為_ -1_ -1(U+D+L )X=b = X=D-1 b- D1(U+L) X由此可得矩陣形式的Jocobi迭代公式：X k+1=BX (k)+f§3.2高斯-高德爾 Gauss-Seidel迭代法注意到利用Jocobi迭代公式計算x，“)時，已經計算好X(k),x2k),，爛；的值，而Jocobi迭代公式并不利用這些最新的近似值計 算，仍用X1(k),x2k),，Xi(k1).這啟發(fā)我們可以對其加以改進，即在每個分量的 計算中盡量利用最新的迭代值，得到1 -1 一nx(bi - ； ajx( )

8、-ajxj) (i = 1,2,n)aj -1j -i 1上式稱為Gauss-Seidel迭代法.其矩陣形式是X=-( D +L)-1UX +(D+L)-1b,Xk+1=BX(k)+f.迭代次數x1 x2 x300001 0.720.9021.164421.043081.167188 1.28205431.093131.195724 1.29777141.0991261.1994671.29971951.099891.1999331.29996561.0999861.1999921.29999671.0999981.1999991.29999981.11.21.3§3.3 超松馳迭代

9、法 SOR方法1二基本思想：逐次超松弛迭代法(Successive Over Relaxation Metho嫡寫為SOR)可以 看作帶參數3的高斯-塞德爾迭代法，是G-S方法的一種修正或加速.是求解 大型稀疏矩陣方程組的有效方法之一.2 SOR算法的構造：設方程組AX=b,其中，A=(aj)n為非奇異陣，X二(刈,m，阿) b=(b1,b2, bn)T.假設已算出x(k),一(k 1)1i -1n lxXi(bi - ； ajxj)- ajXj) (i = 1,2,n)aj =1j -i 1相當于用高斯-塞德爾方法計算一個分量的公式.(k F)若對某個參數3，作Xi 與Xi(k)加權的平均，

10、即xik 1 = (1 - )x(k) - X(k 1)=xi(k) ，(x(k 1)- xi(k)其中，3稱為松弛因子.用(1)式代入(2)式，就得到解方程組 AX=b的逐次超松弛迭代公式:(k 1) = Y(k).xixixii-1(k 1) n (k)Xi = (n ajX；)-' ajXj )(1 = 1,2,n)aiij =1j 刁顯然，當取3=1時，式(3)就是高斯-塞德爾迭代公式3例題分析：利用SOR方法解方程組4x1 - 2x2 - x3 = 0I- 2x1 4x2 - 2x3 - -2x1 - 2x2 3x3 = 3其準確解為X* =1,1,2.建立與式（1）相等價的

11、形式:x = 0.5x2 0.25x3x2 = 0.5x1 0.5x3 - 0.5x3x1葭133 13 2據此建立迭代公式:x(k 1) = 0.5x2k)0.25x3x2k 1) = 0.5x，0.5x3k) - 0.5xkx,2x2k) 133 13 2利用SOR算法，取迭代初值x1（0） = x20） = x30） = 1,3 =1.5，迭代結果如下表.逐次超松弛迭代法次數 x1 x2 x310.6250000.0625001.75000020.3906250.8828131.46875031.0175780.5166021.8085944 0.5568850.8809811.7104

12、495 1.0237120.7434231.8681036 0.7462500.9084191.8387377 0.9977150.8602641.9138948 0.8640500.9367421.9086059 0.9862590.9222251.94552310 0.9281100.9586491.94749311 0.9852420.9559441.96619812 0.9616610.9738181.96952113 0.9881030.9746991.97928914 0.9792060.9837461.98217215 0.9915210.9853181.98741616 0.9

13、885090.9900381.98951317 0.9943410.9914141.99239718 0.9935380.9939461.99380619 0.9963670.9949501.99542420 0.9963130.9963421.99633121 0.9977240.9970181.99725422 0.9978710.9977981.99782223 0.9985960.9982341.998355GS迭代法須迭代85次得到準確值X* =1,1,2;而SOR方法只須55次即得準確值.由此可見，適當地選擇松弛因子SOR法具有明顯的加速收斂效果.口§3.4迭代法的收斂性

14、1.向量和矩陣范數(a)向量范數定義 Rn空間的向量范數|對任意x, y w Rn,滿足下列條件：(1) |x|之 0； |x卜 0 u x = 0 (正定性)(2)儼 xH=| |x|(齊次性)(3) |x+y|v|x|+|y|(三角不等式)常見的向量范數有：(1)列范數:I無卜=X X*i = l(2)譜范數：(歐幾里德范數或向量的長度，模)(3)行范數:II五h三嘲XIp范數:r i/pII無卜=S I下產上述范數的幾何意義是| X|：=max(|x2-xi|,y2-yi|);| X|1二|x2-xi|+|y2-yi| ;22|x|b= G - )也 - yj .定理向量序列x(k)依坐

15、標收斂于向量x*的充要條件是向量序列x(k)依范數收斂于向量x*,即lim |x(k) - x*卜0. k一,二(b)矩陣范數定義 Rm*n空間的向量范數| | 對任意A, Bw RmXn,滿足下列條件：(1) 11A卜 0; |A|= 0 匕 A= 0(2) |: A|M: | |A|(3) |A B|£|A| |B|(4) |AB|M|A|B|常見的矩陣范數有:n11AL= max£ |aj |（行和范數）1 " j =i Jn| A| 1 = max £ | aj |（列和范數）1 i =1|A|2= Jmax（ATA）（譜范數）若 A 對稱，則有

16、 J%ax（ATA）二 J%ax（A2） .定義 矩陣A的譜半徑記為| A|2= p （A）,：（A）=定理2 .迭代法基本定理設有方程組X=BX+f,對于任意初始向量X(0)及任意f,迭代公式X(k+1)=BX(k)+f收斂的充要條件是P (B)<1, P (B)為矩陣B的譜半徑. 證：設X*為方程組X=BX+f的準確解，即X* = BX*+f.對于任意初始向量X(0)及任意f,迭代公式X(k+1)=BX(k)+f,于是,X(k) - X* = BX(2f - (BX* f)=B(X(k-1) - X*)=B2(X(k-2) - X*) 9=Bk(X(0) - X*)由此可得，迭代法收

17、斂的充要條件是BkT 0(kT -).即，p(B)<i.上述定理是線性方程組迭代解法收斂性分析的基本定理，然而由于p (B)的計算往往比較困難，盡管有各種辦法估計 p (B)的上界，但往往 偏聽偏大而不實用，由此導致定理的理論價值勝于實用價值，為滿足實際 判斂的需要，有如下定理.定理|(迭代收斂的充分條件)設有迭代公式X(k+1)=BX(k)+f,如果|B|<1則對于任意初始向量X(0)及任意 f,迭代公式均收斂.3 .從方程組的系數矩陣A判斷迭代收斂性實際中要求解的某些線性方程組，其系數矩陣往往具有一些特點，如系數 矩陣為對稱正定、對角元素占優(yōu)等.由這些方程組系數矩陣的特殊性，使

18、得 我們可以直接從方程組的系數矩陣 A出發(fā)來討論迭代法的收斂性.定義設A= (aj)n“w Rn)滿足nB |- ' |aj |, i = 1,2, ,n j =1 j :i且至少有一個i值，使得n| aii11 aij|j =1j ；i成立，則稱A為對角占優(yōu)矩陣；若nB | ' |aj |, i = 1,2, ,n, j =1 j=i則稱A為嚴格對角占優(yōu)矩陣定理如果A=（a,Rn"為嚴格對角占優(yōu)矩陣，則對任意的初值x，解方程組AX=B的Jacobi法、Guess-Seidel迭代法均收斂.HW: 3.1 3.2 3.3 （上機實習）§3.5高斯消去法1二基

19、本思想：用高斯消去法求解線性方程組的基本思想是設法消去方程組的系數矩陣A的主對角線下的元素，而將 Ax=b化為等價的上三角形方程組，然后再通 過回代過程便可以獲得方程組的解.這種解線性方程組的方法，常稱為高斯消去法(Gaussian Elimination)2例題分析:利用高斯消去法求解方程組6x1 - 2x212x1 - 8x2 3x1 - 13x2 -6x1 4x22x3 4x4= 126x3 10x4 = 349x3 3x4 = 27x318x4= 386x1 - 2x22x3 4x4 = 126x3 10x4 = 349x3 3x4 = 27x3 - 18x4 = 38利用 ri-aG

20、4zad.得an6xi - 2x2 2x3 4x4 = 12-4x2 + 2x3 + 2x4 = 1012x2 8x3 x4 = 212x23x3 - 14x4 = 26aif .利用ri-再2)=3,4.得a226x1 - 2x2 2x3 4x4 = 12-4x2 + 2x3 + 2x4 = 102x3 - 5x4 = - 94x3- 3 = -21利用 r"3M3，i=4得a336x1 - 2x2 2x3 4x4 = 12(4)-4x2 + 2x3 + 2x4 = 102x3 - 5x4 = - 9-3x4= 3顯然，方程組(4)與(1)是等價的，其系數矩陣為上三角 狀的，易于求

21、解.稱以上過程為高斯消去法的消去過程.通過方程組(4)的回代 求解，可以得到準確解為X*=1,-3,-2,1T這一過程為高斯消去法的回代過程2高斯消去法算法的構造：記方程組AX丑為人(15 = b 其中，A和b的元素分別記為(1) (1)aj、h , i、j 一 1,2, , n.Step1第一次消元設。1）。0,將增廣矩陣的第i行減去mi1 = a；/a：倍，（i=2,，n）,目的是將增廣矩陣的第一列內除每一個元素不變外，其余全部消為零，得到AX=b，即A b(1) =a：)a21)ai(2)a22)a1(n)a21n)b(1)局) a(1)A(2)b(2)a(1)an2aa12ann) a

22、;? a2n)bn1)b(1).(2)b2bn2)其中(1)mi1aj二 bi工；(i,j = 2,n)mmStep2第 k 次消元(2 w k w n - 1)設第k-1次消元已完成，且a? kk0 ,得到 A(k)X=b(k),即A(k) b(k)=(1)(1)a11 a12(2) a22a a1k(2)a2kaa1 n(2)a2nb；1) b22)akk)akk)bkk)akk)(k) ann(k)bn計算因子 Fk = ai(kk) / akk) (i = k + 1,n), lkik kk(i, j = k 1,., n)"(E'F-Ekak：,bi(k 1) 二

23、bi(k)- mikbkk)如此反復，經過n-1次消元之后得到一個與原方程組等價的上三角形方程組.a；?a1(2).a：)x1b(1)A(n) b(n)=ann) -Xn-bnn)Step3:回代只要ann)豐o就可以回代求解x 二 b(n) /a(n)xn n annn、(i)a.，xj=i 1 15 (i = n- 1,1)aiib(i)-X 二一3高斯消去法算法Stepl消元:對 k=1,2, - n-l若akk) = 0則停止計算 kk 對 i=k+1,k+2, 小計算因子 mik = aikk)/ akk); ik ik kk對j=k+1,k+2, - nr計算(k i) aij二

24、ajk) - mikakjk)(k 1)(k)(k)bi= h - mikbkStep2回代:對 i=n,n-1, /(i)ai(i)xjXia(i)ii定理(高斯消去法的條件)(1) 若A的所有順序主子式均不為0,則高斯消元無需換行即可進行到底，且得到唯一解.(2) 若消元過程中允許對增廣矩陣進行行交換，則方程組Ax=b可用消去法求解的充要條件是 A可逆.§3.6高斯主元素消去法1主元素及其選取問題Gauss消去法第k次消去是用第k個方程akkX 一 akkk = bkk)來消去第k+i-n個方程中的不條件是ak7豐O.akk)是實現第k次消元的 關鍵元素，稱為第k次消去的主元(素

25、).Gauss消去法存在的問題是：(1)順序消元時一旦產生akk) = 0(這是經?？赡艿?，消元過程則中斷；(2)此外，即使akk) # 0但絕對值很小時，由于用它作除數，引起在消去過 程中出現數量級及舍入誤差急劇增長的系數，而使最后的計算解嚴重 地不可靠.例：單精度求解方程組10 9x1x2X1x21|x1 = r = 1.000100其準確解為1 一 10_八8x2= 2-為=0.999899.當利用Gauss消元法時，8999a22 = 1 - m21 1 = 0.0.01 109 - 109 = 1099舍入誤差b2 = 2 - m21 1 = - 1010-9 1 1 _10-91

26、1 11 2I 0-109-10” 惡性傳播=x2=1,x1 = 0 X:基本思想：主元素法是對Gauss消去法的改進.它全面或局部地選 取絕對值大的元素為主元素，僅對 Gauss消去法的步驟作某些技術性地修改，使之成為一種有效的方法.從而保證和改善算法的數值穩(wěn)定性2完全主元素消去法設方程組AX=b,其中，A=(aj)n為非奇異陣,X=保必，Xn)T, b=(b1,b2,屈)經過k-1次選主元消元后，得到下列等價方程組：選主元過程akk)在矩陣(k) 3ka(k)akn中選取絕對值最大的元素為主元素，保證a(k)ann 1ia(kkjkrkmmaxiajk)0；從而確定 ,行變換和列交換If

27、ik,k then交換第k行與第ik行;If jk then交換第k列與第jk列；值得注意的是，在全主元消去過程中，列交換已改變了 x各分量的順序，因此，必須在每次列交換的同時，記錄調換后未知 數的排列次序. 消元 回代求解 還原未知數的排列次序2.1 全主元素Gauss消去法算法Stepl消元:對 k=1,2, - n-l選主元確定ik,上必小n,滿足|需max1染0；“一 .- -, , j n(k) 若a-jk = 0;則停止計算，detA=0. If ibk then交換第k行與第ik行；If jbk then交換第k列與第jk列； 消元對 i=k+1,k+2, - n計算因子mik

28、= ar/akk) ;對j=k+1,k+2, - n(k 1) = f(k)(k)aijaijmikakj丁" 1 人出+1) - u(k) 曰 K(k);b bi - b - mikdStep2回代:若ann) = 0則停止計算，detA=0.對 i=n,n-1,1bT - 'n ajn)Xjj小1yi 二-()aiiStep3還原排列次序:對 i=1,2, f-Ix* := yi(3)列主元素消去法在計算機上實現主元素消去法意味著進行數的比較操作，全選主元素法需要相當多的計算時間，因此常采用局部選主元素的方法.列主元素消去法依次按列選主元素，只須進行方程行交換，不產生未知

29、數次序的調換.按列選主元過程設方程組AX=b的增廣矩陣為首先在A(1)中第一列選取絕對值最大的元素為主元素，保證|a(1)i|= max| S|(1)| 0;從而確定 ik.1 三i&n 行變換If ik# 1 then交換第1行與第ik行;重復上述過程，設已完成第k-1次按列選主元消元后，得到下列等價方程組:(1)(1)(1)：b(1)a11 a12a1ka1n1在方框內的諸元素中選取絕對值最大的元素為主元素，保證| all 產 max a 若ak,k = °；則停止計算，detA=0.If i"k then交換第k行與第ik行;消元對 i=k+1,k+2, -

30、n計算因子mik = ar/akk)；對j=k+1,k+2, - n 廣0；從而確定ik.If ik#k then交換第k行與第ik行；然后進行消元，如此進行，直至 k=n-1為止.3.1 列主元素Gauss消去法算法Stepl消元:對 k=1,2, - -1選主元確定i/小,，n,滿足iakk廣maNjr °； k -i -nf計算(k 1) _(k)aijaijmik akj(k 1) '(k)(k)bi = b - mikbkStep2回代:若a(? = 0則停止計算，detA=0.bT對 i=n,n-1,1J (n)aij xjj T 1(n)(4)例題分析:0.00

31、1x12.000x23.000x3=1.000求解方程組：- 1.000x13.712x24.623x3=2.0002.000x1 - 1.070x2 + 5.643x3 = 3.0001123解之得：X* =(-0.479107 -0.033089 0.355552)THW: 3.5作業(yè)講評35x1 2x2 x3 -123.1 方程組 - x1 + 4x2 + 2x3 = 202x1 - 3x2 10x3 = 3(1)考察用 Jacobi'Method、Gauss-Seidel'Method解方程組的收斂性 用 Jacobi'Method Gauss-Seidel&#

32、39;Metho確軍方程，要求當 | x(k+1)-x(k)|oo<10-4 終止.5解：（1）由于方程組系數矩陣A= 1 - 12142是一個嚴格對角占優(yōu)矩- 3 10陣，故用Jacobi'Method Gauss-Seidel'Method進行迭代求解時算法均收斂(2)用Jacobi'Method.據此建立迭代公式： x1(k d) = - 0.4x2k) - 0.2x3k) - 2.4x2k '1)= 0.25x1(k) - 0.5x3k)5x3k0.2x1(k) - 0.3x2k)0.3取迭代初值x1(0) = x20)=制0) = 0淇計算結果如

33、表一.Jacobi'Method 計算結果（表一迭代次數x1x2x300001-2.450.32-4.464.252.283-4.5562.7452.4674-3.99142.62752.03475-3.857942.98481.886536-3.971233.092251.9670287-4.030313.023682.021928-4.013862.9814642.0131659-3.995222.9899541.9972110-3.995423.002591.9960311-4.000243.0031291.99986212-4.001223.0000092.00098713-4

34、.00022.99922.00024714-3.999732.9998261.999815-3.999893.0001671.99989416-4.000053.0000812.00002817-4.000042.9999742.00003318-42.9999742利用Gauss-Seidel'Methocj據此建立迭代：x1(k 0.4x2k) _ 0.2x3k) - 2.4x2k 1) = 0.25x(k 1) - 0.5x3k)5.=-0.2x(k 1)-0.3x2k1) 0.3取迭代初值x1(0) = x20) = x30) = 0,其計算結果如表二Gauss-Seidel&

35、#39;Metho卅算結果（表二|迭代次數x1x2x300001-2.44.42.12-4.582.8052.05753-3.93352.9878751.983063，、一，dxia2X2= bi,3.2設有方程組12 2(a11,a12豐 0)a2iXi222X2 = b2迭代公式為:X(k)二。(b1 - a12X2k-1) an(k)1(k-1)X2電 - a2iX1)a22(k= 1,2,3.)求證由上述迭代公式產生的向量序列X(k)收斂的充要條件是證明：顯然，上述迭代格式屬于Jacobi迭代格式，其迭代矩陣為X( k)= bx (k-1)+f,其中，B= I_ a21-a22a12a

36、11 I,由迭代法基本定理得:0X(k) ' X* 匕P(B)<1u葉虹 a21 < 1.如 a224-3.991763.0105282.0015115-4.004512.9981162.0003386-3.999313.0000031.9998647-3.999973.0000752.0000178-4.000032.9999832.0000023.3用SOR方法解下列方程組(取松弛因子8=1.2)，要求| x(k+1)-x-小 4 2x1x2 = 1(k)ll：-<io-4，.x1 - 4x2 = 5解：SOR方法是Gauss-Seide法的一種改進(修正).-

37、0.5x2k) - 0.50.25x1(k 1)1.25一(k 1)XiGauss-Seidel'Method 迭代格式為： x2k 1)因此，SOR法的迭代式為:(k 1)(k)xi- (1 -)xi_(k 1)Xi(k)Xi '一(k 1)(XiJ”一天)i = 1,2.取迭代初值x1(0) = x20) = 0,其計算結果如表三SOR'Method計算結果俵三)次數x1x2|X(k) - X(k-1)|00010.6-1.321.3221.272-0.85440.67230.85824-1.0716480.4137641.0713408-0.9642680.213

38、100850.9642927-1.0178590.107048161.0178566-0.9910710.0535638789101112131415160.99107151.00446430.99776791.00111610.9994421.0002790.99986051.00006980.99996511.0000174-1.004464-0.997768-1.001116-0.999442-1.000279-0.99986-1.00007-0.999965-1.000017-0.9999910.02678510.01339280.00669640.00334820.00167410.

39、00083710.00041850.00020930.00010465.232E-05§ 3.7 三角分解法定義1 矩陣A的LU分解:已給n階方陣A,若能求得一個下三角方陣L和一個上三角方陣U，使得A=LU,則我們稱方陣A有LU三角分解.X u由高斯消去法，我們知道它是通過逐步消元過程，將方程組的系數矩陣A轉變?yōu)橐粋€上三角矩陣，這實際上相當于用一系列初等矩陣左乘A.2高斯消去法的矩陣形式：Stepl:第一次消元(a1(1)A(1) b(1) =0)：(1)(1)aila12,(1)(1)a21 a22. ai(1). a21n)ai(i)ai(2)a22)a . nna. alna

40、.a2nH1)b(1).(2)b2=A(2)b(2)an2).a . nnbn2)即相當于：記：Li10- m2i1I =IIL- mM000=II1=a(1)/ai(i1)2,3,n.L1A(1) b(1)二-0mi1其中，.a(1)0b(1)(2)b27 A(2) bbn2)000000_001mk 1,kmn,kLn -1 Ln -2L2LJAb(1)=a；1)0. 0A(n) b(n)Stepk:第 k 次消元(akk) # 0):LkA(k)bk) = A(E：b(k'),其中,1 0 00 10000 01000100 000 1Step n-1:第 n-1 次消元（a；、

41、 豐 0）：二A(1)ib(1) =L；1L-2 LnLn：1A(n) 'b(n)于是可以推出A = LU .=lL二 A(n)Ln.21Ln：1其中m21L=L；L； Ln_21Lm31mb-mn1mn2由上述討論可知，高斯消去法實質上產生了一個將系數矩陣 A分解為上三 角陣與下三角陣相乘的因式分解.若A的所有順序主子式均不為0,則A的LU分解唯一（其中L為單位下三角陣）.設有方程組AX=b,并設A=LU,于是AX=LUX=b其中,nun( £J)> aiJ=匯*Jt=l令 UX=Y,則 LY=b.于是求解AX=b的問題等價于求解兩個方程組 UX=Y和LY=b.具體的

42、解法如下：(1)利用順推過程解LY=b,其計算公式為：i -1y =卜-1必(i =1,2, ,n).j =1(2)利用回代過程解UX=Y,其計算公式為：nX = (yi - ' UijXj)/Uii(i = n,n -1,1).j T 1上述方法稱為求解線性方程組的三角直接分解法.這種分解又稱為Doolittle分解法.3 Doolittle分解法算法Step1分解:對i=1,2,nuii = aiili1 = 21/u11計算U的第r行,L的第r列元素對 r=2,3,n,n)+ 11 ,n,且r , n)r -1Uri = % 一 " lrkUki(i =r， 1,k =

43、1r 1lir =( 一 " likUkr)/Urr (i ， k =1Step2順推過程:求解LY=bi -1yh-' J%(i = 1,2, ,n)j=iStep3回代過程:回代過程解UX=YnXi = (yi - ' UjXj)/Uii(i = n,n-1, ,1).ji4算例用Doolittle分解法解方程組123x114L o II I I252x2=18_315x3_20解：用Doolittle算法計算得：100 123A = 21001- 4= LU_3- 5 1_00- 24解得 LY=(14,18,20)T,得 Y=(14,-10,-72)TUX=

44、(14,-10,-72)T,得 X=(1,2,3)T§ 3.8追趕法1三對角方程組具有如下形式的方程組:Cidia?b2C2X2d2bn 1nCn-1anbn 一人一 dn利用高斯消元法，經過n-1次消元后,Xn-1qn-1Un-1稱為三對角方程組.特點：其系數矩陣為一種帶狀的稀疏矩陣，非零元素集中分布在主對角線及相鄰兩條次對角線上，且系數矩陣為嚴格對角占優(yōu)陣，即in| |C11|b/出 | |Ci | a = 0,Ci = 0,i = 2,3, ,n - 1.bn 1aI可得等價的方程組:- qn其中,u1 = G/b1,q1=d/n,U = c /(b - u _1a) (i =

45、 2,3，n - 1)=追的過程qi = (di - x-ai)/(bi - u-aj(i = 2,3, ,n)利用回代依次求出ui ,qi,i = 1,2j,n,于是，% = qntU趕的過程lx = q - UiK+1 (i = n - 1, n 2,，1)HW: 3.6 3.7 3.8 (希望上機實習)§3.9其它應用1計算|Aj定理設 A= (aj)n：a) det(A)=det(AT);b) 數 a 乘 A 的一行得：det-4 =adet(A);TVc) A的兩行互換得：det4二-det(A);d) A的一行乘以a加到另一行得：det4=det(A);e) A的兩行成比

46、例：det(A)=0;f) det(AB)=det(A) det(B);其中 B=(bj)n由以上定理可知，通過高斯消元法的計算可得到行列式的值.例1用列主元素法求det(A)的值，其中11-3 - 2A 23111_ 1- 22解：由矩陣A的LU分解過程，可知lAFa；%*' an_(,Nannn,因止匕, 若用列主元素法求行列式的值，只須將每一步的主元素相乘即可，當然要 注意行列式的值的符號改變.其計算過程如下所示.11.0000 -23.0000 _ 1.0000-23.000011.0000 _ 1.0000 -23.00000.0000_ 0.0000-23.00000.00

47、00 _ 0.00001計算A-1-3.000011.0000-2.000011.0000-3.0000-2.000011.00002.2609-1.521711.00002.26090.0000-2.00001.0000 =2.00001.0000-2.0000 =2.00001.0000-1.5217 =2.04351.0000(行交換)(消元)(消元)-1.5217 = |A 卜 53.00001.0192在某些應用中，如在統(tǒng)計學中，可能還需要計算矩陣 A的逆，并且將它明顯地表示為A-1.1.1利用A的LU分解計算A-1設A=(aj)n為滿秩矩陣，則AX=I ,(1)這里I為單位矩陣，顯

48、然X為A的可逆矩陣A-1. 將方程(1)改寫為AX,X,X(n)=I(1),1,I(n)(2)其中，X(j), I(j)分別表示X和I的第j列.于是，方程(2)又可改寫為n個線性方程組的形式：AX(j)=I(j) ,1 三 j 三 n(3)由于這n個方程組的系數矩陣相同，故可應用LU分解法來進行計算，這樣A-1 =X,X，X.并且能夠極大地節(jié)省計算工作量1.2利用高斯消元法計算-1例如：對矩陣A=1611- 4解：-1 A I 1 = - 6-41二0一 095故 A-1 = | 10_-8A-18- 249 - 10 ，求 A-1.34 - 58-21004910 0 1 034- 500 10095-28181010-3201-82-1-2818-322-1§ 3.10 差分析1問題的提出設 方程組 AX=b,其 中，A=（aj）n為非奇 異陣，X=（