第三章 線性方程組的解法

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

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

3、雅可比方法的迭代格式：Xk+1=BX(k)+f ,其中，B稱為迭代矩陣.其計算精度可控,特別適用于求解系數(shù)為大型稀疏矩陣(sparse matrices)的方程組.2 問題:(a) 如何建立迭代格式？ (b) 向量序列Xk是否收斂以及收斂條件?3 例題分析:考慮解方程組 (1)其準(zhǔn)確解為X*=1, 1.2, 1.3.建立與式(1)相等價的形式： (2)據(jù)此建立迭代公式： (3) 取迭代初值,迭代結(jié)果如下表. JocabiMethodP31.cpp 迭代次數(shù) x1 x2 x30 0 0 01 0.72 0.83 0.842 0.971 1.07 1.153 1.057 1.1571 1.2482

4、4 1.08535 1.18534 1.282825 1.095098 1.195099 1.2941386 1.098338 1.198337 1.2980397 1.099442 1.199442 1.2993358 1.099811 1.199811 1.2997779 1.099936 1.199936 1.29992410 1.099979 1.199979 1.29997511 1.099993 1.199993 1.29999112 1.099998 1.199998 1.29999713 1.099999 1.199999 1.29999914 1.1 1.2 1.315 1.

5、1 1.2 1.3 4 Jocobi迭代公式:設(shè)方程組AX=b, 通過分離變量的過程建立Jocobi迭代公式，即 由此我們可以得到Jacobi迭代公式：Jacobi迭代公式的算法1: 初始化. n, (aij), (bj), (x1) , M.2: 執(zhí)行k=1直到M為止. 執(zhí)行i=1直到n為止. ; 執(zhí)行i=1直到n為止. ; 輸出k, (xi).另外，我們也可以建立Jacobi迭代公式的矩陣形式.設(shè)方程組AX=b,其中，A=(aij)n為非奇異陣，X=(x1,x2,xn)T, b=(b1,b2,bn)T將系數(shù)陣A分解為: A=U+D+L,U為上三角矩陣，D為對角矩陣，L為下三角矩陣.于是AX

6、=b可改寫為(U+D+L)X=b X=D-1b-D-1(U+L)X由此可得矩陣形式的Jocobi迭代公式： Xk+1=BX(k)+f §3.2 高斯-塞德爾Gauss-Seidel迭代法注意到利用Jocobi迭代公式計算時，已經(jīng)計算好的值，而Jocobi迭代公式并不利用這些最新的近似值計算，仍用.這啟發(fā)我們可以對其加以改進(jìn),即在每個分量的計算中盡量利用最新的迭代值，得到上式稱為Gauss-Seidel迭代法.其矩陣形式是X=-(D+L)-1UX+(D+L)-1b, Xk+1=BX(k)+f .迭代次數(shù) x1 x2 x3 0 0 0 0 1 0.72 0.902 1.1644 2 1.

7、04308 1.167188 1.282054 3 1.09313 1.195724 1.297771 4 1.099126 1.199467 1.299719 5 1.09989 1.199933 1.299965 6 1.099986 1.199992 1.299996 7 1.099998 1.199999 1.299999 8 1.1 1.2 1.3§3.3 超松馳迭代法SOR方法1 基本思想:逐次超松弛迭代法(Successive Over Relaxation Method,簡寫為SOR)可以看作帶參數(shù)的高斯-塞德爾迭代法，是G-S方法的一種修正或加速.是求解大型稀疏矩陣

8、方程組的有效方法之一.2 SOR算法的構(gòu)造:設(shè)方程組AX=b, 其中，A=(aij)n為非奇異陣，X=(x1,x2,xn)T, b=(b1,b2,bn)T.假設(shè)已算出x(k)， (1)相當(dāng)于用高斯-塞德爾方法計算一個分量的公式.若對某個參數(shù)，作與加權(quán)的平均,即 (2)其中，稱為松弛因子.用(1)式代入(2)式，就得到解方程組AX=b的逐次超松弛迭代公式： (3)顯然，當(dāng)取=1時，式(3)就是高斯-塞德爾迭代公式.3 例題分析:利用SOR方法解方程組 (1)其準(zhǔn)確解為X*=1, 1, 2.建立與式(1)相等價的形式： (2)據(jù)此建立迭代公式： (3)利用SOR算法，取迭代初值,=1.5,迭代結(jié)果

9、如下表. 逐次超松弛迭代法次數(shù) x1 x2 x3 1 0.625000 0.062500 1.750000 2 0.390625 0.882813 1.468750 3 1.017578 0.516602 1.808594 4 0.556885 0.880981 1.710449 5 1.023712 0.743423 1.868103 6 0.746250 0.908419 1.838737 7 0.997715 0.860264 1.913894 8 0.864050 0.936742 1.908605 9 0.986259 0.922225 1.945523 10 0.928110 0.

10、958649 1.947493 11 0.985242 0.955944 1.966198 12 0.961661 0.973818 1.969521 13 0.988103 0.974699 1.979289 14 0.979206 0.983746 1.982172 15 0.991521 0.985318 1.987416 16 0.988509 0.990038 1.989513 17 0.994341 0.991414 1.992397 18 0.993538 0.993946 1.993806 19 0.996367 0.994950 1.995424 20 0.996313 0.

11、996342 1.996331 21 0.997724 0.997018 1.997254 22 0.997871 0.997798 1.997822 23 0.998596 0.998234 1.998355GS迭代法須迭代85次得到準(zhǔn)確值X*=1, 1, 2;而SOR方法只須55次即得準(zhǔn)確值.由此可見，適當(dāng)?shù)剡x擇松弛因子，SOR法具有明顯的加速收斂效果. §3.4 迭代法的收斂性1. 向量和矩陣范數(shù) (a) 向量范數(shù) Rn空間的向量范數(shù) | · | ,對任意, 滿足下列條件： (正定性) (齊次性) （三角不等式） 常見的向量范數(shù)有：(1) 列范數(shù)：(2) 譜范數(shù)：(歐

12、幾里德范數(shù)或向量的長度,模)(3) 行范數(shù)：(4) p范數(shù): 上述范數(shù)的幾何意義是:=max(|x2-x1|,|y2-y1|) ;=|x2-x1|+|y2-y1| ;. 向量序列依坐標(biāo)收斂于向量x* 的充要條件是向量序列依范數(shù)收斂于向量x*,即.(b) 矩陣范數(shù) 空間的向量范數(shù) | · | ,對任意, 滿足下列條件：常見的矩陣范數(shù)有： (行和范數(shù)) (列和范數(shù)) (譜范數(shù)) 若A對稱，則有. 矩陣A的譜半徑記為,r(A) =,其中l(wèi)i 為A 的特征根。2. 迭代法基本定理 設(shè)有方程組X=BX+f,對于任意初始向量X(0)及任意f,迭代公式X(k+1)=BX(k)+f收斂的充要條件是&

13、lt;1,為矩陣B的譜半徑.證：設(shè)X*為方程組X=BX+f的準(zhǔn)確解，即 X*=BX*+f.對于任意初始向量X(0)及任意f,迭代公式X(k+1)=BX(k)+f,于是， 由此可得,迭代法收斂的充要條件是.即,<1. 上述定理是線性方程組迭代解法收斂性分析的基本定理，然而由于的計算往往比較困難，盡管有各種辦法估計的上界，但往往偏聽偏大而不實(shí)用，由此導(dǎo)致定理的理論價值勝于實(shí)用價值，為滿足實(shí)際判斂的需要，有如下定理. (迭代收斂的充分條件) 設(shè)有迭代公式X(k+1)=BX(k)+f，如果|B|<1,則對于任意初始向量X(0)及任意f, 迭代公式均收斂.3. 從方程組的系數(shù)矩陣A判斷迭代收

14、斂性實(shí)際中要求解的某些線性方程組，其系數(shù)矩陣往往具有一些特點(diǎn)，如系數(shù)矩陣為對稱正定、對角元素占優(yōu)等.由這些方程組系數(shù)矩陣的特殊性，使得我們可以直接從方程組的系數(shù)矩陣A出發(fā)來討論迭代法的收斂性. 設(shè)，滿足 且至少有一個i值，使得 成立，則稱A為對角占優(yōu)矩陣；若 ,則稱A為嚴(yán)格對角占優(yōu)矩陣. 如果為嚴(yán)格對角占優(yōu)矩陣，則對任意的初值x(0),解方程組AX=B的Jacobi法、Guess-Seidel迭代法均收斂. HW: 3.1 3.2 3.3（上機(jī)實(shí)習(xí)） §3.5 高斯消去法 1 基本思想:用高斯消去法求解線性方程組的基本思想是設(shè)法消去方程組的系數(shù)矩陣A的主對角線下的元素，而將Ax=b化

15、為等價的上三角形方程組，然后再通過回代過程便可以獲得方程組的解.這種解線性方程組的方法，常稱為高斯消去法(Gaussian Elimination).2 例題分析:利用高斯消去法求解方程組: (1)利用ri-,i=2,3,4.得 (2)利用ri-,i=3,4.得 (3)利用ri-,i=4.得 (4)顯然，方程組(4)與(1)是等價的，其系數(shù)矩陣為上三角狀的，易于求解.稱以上過程為高斯消去法的消去過程.通過方程組(4)的回代求解，可以得到準(zhǔn)確解為X*=1, -3, -2,1T. 這一過程為高斯消去法的回代過程. 2 高斯消去法算法的構(gòu)造:記方程組AX=b為A(1)X=b(1), 其中，A(1)和

16、b(1)的元素分別記為Step1:第一次消元 設(shè)，將增廣矩陣的第i行減去倍，(i=2,n),目的是將增廣矩陣的第一列內(nèi)除每一個元素不變外，其余全部消為零，得到A(2)X=b(2),即其中 Step2:第k次消元() 設(shè)第k-1次消元已完成，且，得到A(k)X=b(k),即計算因子， 如此反復(fù)，經(jīng)過n-1次消元之后得到一個與原方程組等價的上三角形方程組.Step3:回代 只要就可以回代求解3 高斯消去法算法Step1消元:對k=1,2,n-1 若則停止計算 對i=k+1,k+2,n 計算因子;對j=k+1,k+2,n 計算;Step2回代: 對i=n,n-1,1 （高斯消去法的條件）(1) 若A

17、的所有順序主子式均不為0，則高斯消元無需換行即可進(jìn)行到底，且得到唯一解.(2) 若消元過程中允許對增廣矩陣進(jìn)行行交換，則方程組Ax=b可用消去法求解的充要條件是A可逆.§3.6 高斯主元素消去法1 主元素及其選取問題Gauss消去法第k次消去是用第k個方程來消去第k+1,n個方程中的xk,條件是.是實(shí)現(xiàn)第k次消元的關(guān)鍵元素，稱為第k次消去的主元(素).Gauss消去法存在的問題是：(1) 順序消元時一旦產(chǎn)生(這是經(jīng)常可能的)，消元過程則中斷；(2) 此外，即使但絕對值很小時，由于用它作除數(shù)，引起在消去過程中出現(xiàn)數(shù)量級及舍入誤差急劇增長的系數(shù)，而使最后的計算解嚴(yán)重地不可靠.例：單精度求

18、解方程組其準(zhǔn)確解為 當(dāng)利用Gauss消元法時，舍入誤差 惡性傳播× · 基本思想: 主元素法是對Gauss消去法的改進(jìn). 它全面或局部地選取絕對值大的元素為主元素，僅對Gauss消去法的步驟作某些技術(shù)性地修改，使之成為一種有效的方法.從而保證和改善算法的數(shù)值穩(wěn)定性.2 完全主元素消去法設(shè)方程組AX=b, 其中，A=(aij)n為非奇異陣，X=(x1,x2,xn)T, b=(b1,b2,bn)T.經(jīng)過k-1次選主元消元后，得到下列等價方程組： 選主元過程 在矩陣中選取絕對值最大的元素為主元素，保證 從而確定 ik , jk. 行變換和列交換If ik ¹ k the

19、n 交換第 k 行與第ik行;If jk ¹ k then 交換第 k 列與第jk列;值得注意的是，在全主元消去過程中，列交換已改變了x各分量的順序，因此，必須在每次列交換的同時，記錄調(diào)換后未知數(shù)的排列次序. 消元 回代求解 還原未知數(shù)的排列次序2.1 全主元素Gauss消去法算法Step1消元:對k=1,2,n-1 選主元 確定 ik , jk,滿足 若則停止計算，detA=0. If ik ¹ k then 交換第 k 行與第ik行;If jk ¹ k then 交換第 k 列與第jk列; 消元對i=k+1,k+2,n計算因子 ;對j=k+1,k+2,n 計算

20、;Step2回代: 若則停止計算，detA=0. 對i=n,n-1,1Step3還原排列次序: 對i=1,2,n-1x* := yi(3) 列主元素消去法在計算機(jī)上實(shí)現(xiàn)主元素消去法意味著進(jìn)行數(shù)的比較操作，全選主元素法需要相當(dāng)多的計算時間，因此常采用局部選主元素的方法.列主元素消去法依次按列選主元素，只須進(jìn)行方程行 交換，不產(chǎn)生未知數(shù)次序的調(diào)換. 按列選主元過程 設(shè)方程組AX=b的增廣矩陣為 首先在A(1)中第一列選取絕對值最大的元素為主元素，保證 從而確定 ik. 行變換If ik ¹ 1 then 交換第 1 行與第ik行;重復(fù)上述過程，設(shè)已完成第k-1次按列選主元消元后，得到下列

21、等價方程組： 在方框內(nèi)的諸元素中選取絕對值最大的元素為主元素，保證: 從而確定 ik. If ik ¹ k then 交換第 k 行與第ik行;然后進(jìn)行消元，如此進(jìn)行，直至k=n-1為止.3.1 列主元素Gauss消去法算法Step1消元:對k=1,2,n-1 選主元 確定 ik,滿足; 若則停止計算，detA=0. If ik ¹ k then 交換第 k 行與第ik行; 消元對i=k+1,k+2,n計算因子;對j=k+1,k+2,n 計算;Step2回代: 若則停止計算，detA=0. 對i=n,n-1,1(4) 例題分析:求解方程組:解之得：X*=(-0.479107

22、 -0.033089 0.355552)THW: 3.5 作業(yè)講評33.1 設(shè)有方程組 (1) 考察用Jacobi'Method、Gauss-Seidel'Method解方程組的收斂性.(2) 用Jacobi'Method、Gauss-Seidel'Method解方程，要求當(dāng)| x(k+1)-x(k)|<10-4終止. 解：(1) 由于方程組系數(shù)矩陣A=是一個嚴(yán)格對角占優(yōu)矩陣，故用Jacobi'Method、Gauss-Seidel'Method進(jìn)行迭代求解時算法均收斂.(2) 用Jacobi'Method. 據(jù)此建立迭代公式：取迭

23、代初值,其計算結(jié)果如表一.Jacobi'Method計算結(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.

24、00098713-4.00022.99922.00024714-3.999732.9998261.999815-3.999893.0001671.99989416-4.000053.0000812.00002817-4.000042.9999742.00003318-42.9999742利用Gauss-Seidel'Method，據(jù)此建立迭代:取迭代初值,其計算結(jié)果如表二.Gauss-Seidel'Method計算結(jié)果(表二)迭代次數(shù)x1x2x300001-2.44.42.12-4.582.8052.05753-3.93352.9878751.9830634-3.991763.

25、0105282.0015115-4.004512.9981162.0003386-3.999313.0000031.9998647-3.999973.0000752.0000178-4.000032.9999832.000002 3.2 設(shè)有方程組迭代公式為：求證由上述迭代公式產(chǎn)生的向量序列X(k)收斂的充要條件是證明: 顯然，上述迭代格式屬于Jacobi迭代格式，其迭代矩陣為X(k)=BX(k-1)+f,其中，B=，由迭代法基本定理得：. 即 3.3 用SOR方法解下列方程組(取松弛因子),要求 | x(k+1)-x(k)|<10-4,.解: SOR方法是Gauss-Seidel法的一

26、種改進(jìn)(修正).Gauss-Seidel'Method 迭代格式為：，因此，SOR法的迭代式為：取迭代初值,其計算結(jié)果如表三.SOR'Method計算結(jié)果(表三)次數(shù) x1 x2 00010.6-1.321.3221.272-0.85440.67230.85824-1.0716480.4137641.0713408-0.9642680.213100850.9642927-1.0178590.107048161.0178566-0.9910710.053563870.9910715-1.0044640.026785181.0044643-0.9977680.013392890.9

27、977679-1.0011160.0066964101.0011161-0.9994420.0033482110.999442-1.0002790.0016741121.000279-0.999860.0008371130.9998605-1.000070.0004185141.0000698-0.9999650.0002093150.9999651-1.0000170.0001046161.0000174-0.9999915.232E-05§3.7 三角分解法1 矩陣A的LU分解: 已給n階方陣A,若能求得一個下三角方陣L和一個上三角方陣U,使得A=LU,則我們稱方陣A有LU三角分

28、解.由高斯消去法，我們知道它是通過逐步消元過程，將方程組的系數(shù)矩陣A轉(zhuǎn)變?yōu)橐粋€上三角矩陣，這實(shí)際上相當(dāng)于用一系列初等矩陣左乘A.2 高斯消去法的矩陣形式:Step1:第一次消元():即相當(dāng)于:記： 其中,.Step k:第k次消元(): ,其中， Step n-1:第n-1次消元():記于是可以推出.其中.由上述討論可知，高斯消去法實(shí)質(zhì)上產(chǎn)生了一個將系數(shù)矩陣A分解為上三角陣與下三角陣相乘的因式分解.若A的所有順序主子式均不為0，則 A 的 LU 分解唯一（其中 L 為單位下三角陣）.設(shè)有方程組AX=b,并設(shè)A=LU,于是 AX=LUX=b其中，令UX=Y,則 LY=b.于是求解AX=b的問題等

29、價于求解兩個方程組UX=Y和LY=b. 具體的解法如下：(1) 利用順推過程解LY=b,其計算公式為: .(2) 利用回代過程解UX=Y,其計算公式為: .上述方法稱為求解線性方程組的三角直接分解法.這種分解又稱為Doolittle分解法.3 Doolittle分解法算法Step1分解: 對i=1,2,n; 計算U的第r行,L的第r列元素 對r=2,3,n Step2順推過程: 求解LY=bStep3回代過程: 回代過程解UX=Y .4 算例用Doolittle分解法解方程組 解: 用Doolittle算法計算得: 解得LY=(14,18,20)T,得Y=(14,-10,-72)T UX=(1

30、4,-10,-72)T,得X=(1,2,3)T§3.8 追趕法1 三對角方程組 具有如下形式的方程組：稱為三對角方程組.特點(diǎn)：其系數(shù)矩陣為一種帶狀的稀疏矩陣，非零元素集中分布在主對角線及相鄰兩條次對角線上，且系數(shù)矩陣為嚴(yán)格對角占優(yōu)陣，即利用高斯消元法，經(jīng)過n-1次消元后，可得等價的方程組：其中， 追的過程利用回代依次求出，于是, 趕的過程HW: 3.6 3.7 3.8（希望上機(jī)實(shí)習(xí)）§3.9 其它應(yīng)用1 計算|A| 設(shè)A=(aij)n:a) det(A)=det(AT);b) 數(shù)a乘A的一行得：det=adet(A);c) A的兩行互換得：det=-det(A);d) A的

31、一行乘以a加到另一行得：det=det(A);e) A的兩行成比例：det(A)=0;f) det(AB)=det(A)·det(B); 其中B=(bij)n由以上定理可知，通過高斯消元法的計算可得到行列式的值.例1 用列主元素法求det(A)的值，其中 解：由矩陣A的LU分解過程，可知，因此，若用列主元素法求行列式的值，只須將每一步的主元素相乘即可，當(dāng)然要注意行列式的值的符號改變.其計算過程如下所示.1 計算A-1在某些應(yīng)用中，如在統(tǒng)計學(xué)中，可能還需要計算矩陣A的逆，并且將它明顯地表示為A-1.1.1 利用A的LU分解計算A-1設(shè)A=(aij)n為滿秩矩陣，則AX=I， (1)這里I為單位矩陣，顯然X為A的可逆矩陣A-1.將方程(1)改寫為AX(1),X(2),X(n)=I(1),I(2),I(n) (2)其中，X(j), I(j)分別表示X和I的第j列.于是，方程(2)又可改寫為n個線性方程組的形式: AX(j)=I(j) , (3)由于這n個方程組的系數(shù)矩陣相同，故可應(yīng)用LU分解法來進(jìn)行計算，這樣A-1=X(1),X(2),X(n).并且能夠極大地節(jié)省計算工作量.1.2 利用高斯消元法計算A-1例如：對矩陣，求A-1.解: 故 §3