數(shù)值分析講義——線性方程組的解法

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

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

3、X的+f ,其中，B稱(chēng)為迭代矩陣.其計(jì)算精度可 控，特別適用于求解系數(shù)為大型稀疏矩陣(sparse matrices的方程組.2問(wèn)題：(a)如何建立迭代格式？(b)向量序列Xk是否收斂以及收斂條件？3例題分析：10x1 - x2 - 2x3 = 7.2考慮解方程組- x1 + 10x2 - 2x3 = 8.3(1)x1 - x2 + 5x3 = 4.2其準(zhǔn)確解為X* =1, 1.2, 1.3.建立與式(1)相等價(jià)的形式：x1 = 0.1x20.2x3 0.72x2 = 0.1x10.2x3 0.83(2)、x3 = 0.1x1 + 0.2x2 + 0.84據(jù)此建立迭代公式：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,迭代結(jié)果如下表.JocabiMethodP31.cpp迭代次數(shù)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迭代公式:設(shè)方程組AX=b,通過(guò)分離變量的過(guò)程建立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迭代公式的矩陣形式設(shè)方程組AX=b,其中，A=(aj)n為非奇異陣，X = (X1,X2, Xn)T,b=(b1,b2, bn)T將系數(shù)陣A分解為：A=

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

8、-ajxj) (i = 1,2,n)aj -1j -i 1上式稱(chēng)為Gauss-Seidel迭代法.其矩陣形式是X=-( D +L)-1UX +(D+L)-1b,Xk+1=BX(k)+f.迭代次數(shù)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嫡寫(xiě)為SOR)可以 看作帶參數(shù)3的高斯-塞德?tīng)柕ǎ荊-S方法的一種修正或加速.是求解 大型稀疏矩陣方程組的有效方法之一.2 SOR算法的構(gòu)造：設(shè)方程組AX=b,其中，A=(aj)n為非奇異陣，X二(刈,m，阿) b=(b1,b2, bn)T.假設(shè)已算出x(k),一(k 1)1i -1n lxXi(bi - ； ajxj)- ajXj) (i = 1,2,n)aj =1j -i 1相當(dāng)于用高斯-塞德?tīng)柗椒ㄓ?jì)算一個(gè)分量的公式.(k F)若對(duì)某個(gè)參數(shù)3，作Xi 與Xi(k)加權(quán)的平均，

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

11、形式:x = 0.5x2 0.25x3x2 = 0.5x1 0.5x3 - 0.5x3x1葭133 13 2據(jù)此建立迭代公式: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，迭代結(jié)果如下表.逐次超松弛迭代法次數(shù) 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次得到準(zhǔn)確值X* =1,1,2;而SOR方法只須55次即得準(zhǔn)確值.由此可見(jiàn)，適當(dāng)?shù)剡x擇松弛因子SOR法具有明顯的加速收斂效果.口§3.4迭代法的收斂性

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

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

16、 J%ax（ATA）二 J%ax（A2） .定義 矩陣A的譜半徑記為| A|2= p （A）,：（A）=定理2 .迭代法基本定理設(shè)有方程組X=BX+f,對(duì)于任意初始向量X(0)及任意f,迭代公式X(k+1)=BX(k)+f收斂的充要條件是P (B)<1, P (B)為矩陣B的譜半徑. 證：設(shè)X*為方程組X=BX+f的準(zhǔn)確解，即X* = BX*+f.對(duì)于任意初始向量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)的計(jì)算往往比較困難，盡管有各種辦法估計(jì) p (B)的上界，但往往 偏聽(tīng)偏大而不實(shí)用，由此導(dǎo)致定理的理論價(jià)值勝于實(shí)用價(jià)值，為滿(mǎn)足實(shí)際 判斂的需要，有如下定理.定理|(迭代收斂的充分條件)設(shè)有迭代公式X(k+1)=BX(k)+f,如果|B|<1則對(duì)于任意初始向量X(0)及任意 f,迭代公式均收斂.3 .從方程組的系數(shù)矩陣A判斷迭代收斂性實(shí)際中要求解的某些線性方程組，其系數(shù)矩陣往往具有一些特點(diǎn)，如系數(shù) 矩陣為對(duì)稱(chēng)正定、對(duì)角元素占優(yōu)等.由這些方程組系數(shù)矩陣的特殊性，使

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

19、本思想：用高斯消去法求解線性方程組的基本思想是設(shè)法消去方程組的系數(shù)矩陣A的主對(duì)角線下的元素，而將 Ax=b化為等價(jià)的上三角形方程組，然后再通 過(guò)回代過(guò)程便可以獲得方程組的解.這種解線性方程組的方法，常稱(chēng)為高斯消去法(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)是等價(jià)的，其系數(shù)矩陣為上三角 狀的，易于求

21、解.稱(chēng)以上過(guò)程為高斯消去法的消去過(guò)程.通過(guò)方程組(4)的回代 求解，可以得到準(zhǔn)確解為X*=1,-3,-2,1T這一過(guò)程為高斯消去法的回代過(guò)程2高斯消去法算法的構(gòu)造：記方程組AX丑為人(15 = b 其中，A和b的元素分別記為(1) (1)aj、h , i、j 一 1,2, , n.Step1第一次消元設(shè)。1）。0,將增廣矩陣的第i行減去mi1 = a；/a：倍，（i=2,，n）,目的是將增廣矩陣的第一列內(nèi)除每一個(gè)元素不變外，其余全部消為零，得到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)設(shè)第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計(jì)算因子 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)如此反復(fù)，經(jīng)過(guò)n-1次消元之后得到一個(gè)與原方程組等價(jià)的上三角形方程組.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消元:對(duì) k=1,2, - n-l若akk) = 0則停止計(jì)算 kk 對(duì) i=k+1,k+2, 小計(jì)算因子 mik = aikk)/ akk); ik ik kk對(duì)j=k+1,k+2, - nr計(jì)算(k i) aij二

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

25、).Gauss消去法存在的問(wèn)題是：(1)順序消元時(shí)一旦產(chǎn)生akk) = 0(這是經(jīng)?？赡艿?，消元過(guò)程則中斷；(2)此外，即使akk) # 0但絕對(duì)值很小時(shí)，由于用它作除數(shù)，引起在消去過(guò) 程中出現(xiàn)數(shù)量級(jí)及舍入誤差急劇增長(zhǎng)的系數(shù)，而使最后的計(jì)算解嚴(yán)重 地不可靠.例：?jiǎn)尉惹蠼夥匠探M10 9x1x2X1x21|x1 = r = 1.000100其準(zhǔn)確解為1 一 10_八8x2= 2-為=0.999899.當(dāng)利用Gauss消元法時(shí)，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:基本思想：主元素法是對(duì)Gauss消去法的改進(jìn).它全面或局部地選 取絕對(duì)值大的元素為主元素，僅對(duì) Gauss消去法的步驟作某些技術(shù)性地修改，使之成為一種有效的方法.從而保證和改善算法的數(shù)值穩(wěn)定性2完全主元素消去法設(shè)方程組AX=b,其中，A=(aj)n為非奇異陣,X=保必，Xn)T, b=(b1,b2,屈)經(jīng)過(guò)k-1次選主元消元后，得到下列等價(jià)方程組：選主元過(guò)程akk)在矩陣(k) 3ka(k)akn中選取絕對(duì)值最大的元素為主元素，保證a(k)ann 1ia(kkjkrkmmaxiajk)0；從而確定 ,行變換和列交換If

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

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

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

30、n計(jì)算因子mik = ar/akk)；對(duì)j=k+1,k+2, - n 廣0；從而確定ik.If ik#k then交換第k行與第ik行；然后進(jìn)行消元，如此進(jìn)行，直至 k=n-1為止.3.1 列主元素Gauss消去法算法Stepl消元:對(duì) k=1,2, - -1選主元確定i/小,，n,滿(mǎn)足iakk廣maNjr °； k -i -nf計(jì)算(k 1) _(k)aijaijmik akj(k 1) '(k)(k)bi = b - mikbkStep2回代:若a(? = 0則停止計(jì)算，detA=0.bT對(duì) 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è)講評(píng)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確軍方程，要求當(dāng) | x(k+1)-x(k)|oo<10-4 終止.5解：（1）由于方程組系數(shù)矩陣A= 1 - 12142是一個(gè)嚴(yán)格對(duì)角占優(yōu)矩- 3 10陣，故用Jacobi'Method Gauss-Seidel'Method進(jìn)行迭代求解時(shí)算法均收斂(2)用Jacobi'Method.據(jù)此建立迭代公式： 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淇計(jì)算結(jié)果如

33、表一.Jacobi'Method 計(jì)算結(jié)果（表一迭代次數(shù)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據(jù)此建立迭代：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,其計(jì)算結(jié)果如表二Gauss-Seidel&

35、#39;Metho卅算結(jié)果（表二|迭代次數(shù)x1x2x300001-2.44.42.12-4.582.8052.05753-3.93352.9878751.983063，、一，dxia2X2= bi,3.2設(shè)有方程組12 2(a11,a12豐 0)a2iXi222X2 = b2迭代公式為:X(k)二。(b1 - a12X2k-1) an(k)1(k-1)X2電 - a2iX1)a22(k= 1,2,3.)求證由上述迭代公式產(chǎn)生的向量序列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法的一種改進(jìn)(修正).-

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,其計(jì)算結(jié)果如表三SOR'Method計(jì)算結(jié)果俵三)次數(shù)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,若能求得一個(gè)下三角方陣L和一個(gè)上三角方陣U，使得A=LU,則我們稱(chēng)方陣A有LU三角分解.X u由高斯消去法，我們知道它是通過(guò)逐步消元過(guò)程，將方程組的系數(shù)矩陣A轉(zhuǎn)變?yōu)橐粋€(gè)上三角矩陣，這實(shí)際上相當(dāng)于用一系列初等矩陣左乘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)即相當(dāng)于：記：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由上述討論可知，高斯消去法實(shí)質(zhì)上產(chǎn)生了一個(gè)將系數(shù)矩陣 A分解為上三 角陣與下三角陣相乘的因式分解.若A的所有順序主子式均不為0,則A的LU分解唯一（其中L為單位下三角陣）.設(shè)有方程組AX=b,并設(shè)A=LU,于是AX=LUX=b其中,nun( £J)> aiJ=匯*Jt=l令 UX=Y,則 LY=b.于是求解AX=b的問(wèn)題等價(jià)于求解兩個(gè)方程組 UX=Y和LY=b.具體的

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

43、1r 1lir =( 一 " likUkr)/Urr (i ， k =1Step2順推過(guò)程:求解LY=bi -1yh-' J%(i = 1,2, ,n)j=iStep3回代過(guò)程:回代過(guò)程解UX=YnXi = (yi - ' UjXj)/Uii(i = n,n-1, ,1).ji4算例用Doolittle分解法解方程組123x114L o II I I252x2=18_315x3_20解：用Doolittle算法計(jì)算得：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三對(duì)角方程組具有如下形式的方程組:Cidia?b2C2X2d2bn 1nCn-1anbn 一人一 dn利用高斯消元法，經(jīng)過(guò)n-1次消元后,Xn-1qn-1Un-1稱(chēng)為三對(duì)角方程組.特點(diǎn)：其系數(shù)矩陣為一種帶狀的稀疏矩陣，非零元素集中分布在主對(duì)角線及相鄰兩條次對(duì)角線上，且系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)陣，即in| |C11|b/出 | |Ci | a = 0,Ci = 0,i = 2,3, ,n - 1.bn 1aI可得等價(jià)的方程組:- qn其中,u1 = G/b1,q1=d/n,U = c /(b - u _1a) (i =

45、 2,3，n - 1)=追的過(guò)程qi = (di - x-ai)/(bi - u-aj(i = 2,3, ,n)利用回代依次求出ui ,qi,i = 1,2j,n,于是，% = qntU趕的過(guò)程lx = q - UiK+1 (i = n - 1, n 2,，1)HW: 3.6 3.7 3.8 (希望上機(jī)實(shí)習(xí))§3.9其它應(yīng)用1計(jì)算|Aj定理設(shè) A= (aj)n：a) det(A)=det(AT);b) 數(shù) 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由以上定理可知，通過(guò)高斯消元法的計(jì)算可得到行列式的值.例1用列主元素法求det(A)的值，其中11-3 - 2A 23111_ 1- 22解：由矩陣A的LU分解過(guò)程，可知lAFa；%*' an_(,Nannn,因止匕, 若用列主元素法求行列式的值，只須將每一步的主元素相乘即可，當(dāng)然要 注意行列式的值的符號(hào)改變.其計(jì)算過(guò)程如下所示.11.0000 -23.0000 _ 1.0000-23.000011.0000 _ 1.0000 -23.00000.0000_ 0.0000-23.00000.00

47、00 _ 0.00001計(jì)算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在某些應(yīng)用中，如在統(tǒng)計(jì)學(xué)中，可能還需要計(jì)算矩陣 A的逆，并且將它明顯地表示為A-1.1.1利用A的LU分解計(jì)算A-1設(shè)A=(aj)n為滿(mǎn)秩矩陣，則AX=I ,(1)這里I為單位矩陣，顯

48、然X為A的可逆矩陣A-1. 將方程(1)改寫(xiě)為AX,X,X(n)=I(1),1,I(n)(2)其中，X(j), I(j)分別表示X和I的第j列.于是，方程(2)又可改寫(xiě)為n個(gè)線性方程組的形式：AX(j)=I(j) ,1 三 j 三 n(3)由于這n個(gè)方程組的系數(shù)矩陣相同，故可應(yīng)用LU分解法來(lái)進(jìn)行計(jì)算，這樣A-1 =X,X，X.并且能夠極大地節(jié)省計(jì)算工作量1.2利用高斯消元法計(jì)算-1例如：對(duì)矩陣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問(wèn)題的提出設(shè) 方程組 AX=b,其 中，A=（aj）n為非奇 異陣，X=（