1、第七章第七章問題驅動：絎架設計問題驅動：絎架設計 絎架是能夠承受重負載的輕量結構，在橋梁設計中，一個絎架是能夠承受重負載的輕量結構，在橋梁設計中，一個個絎架和可旋轉的支點連接起來，可以把力通過該絎架從一個個絎架和可旋轉的支點連接起來，可以把力通過該絎架從一個節點傳到另一個節點。如圖節點傳到另一個節點。如圖7.1.1所示給出了一個所示給出了一個4個支點的絎個支點的絎架，架，和和都是支點。在左下角都是支點。在左下角是一個固定的點，是一個固定的點，絎架在右下角點絎架在右下角點可以水平移動量值。在支點可以水平移動量值。在支點施加施加10000N的力，絎架的受力情況如圖所示由的力，絎架的受力情況如圖所示

2、由 1234,ffff和和 5f給出。固定支點給出。固定支點同時受到水平方向的力同時受到水平方向的力 1F和垂直方向的力和垂直方向的力 2F的作用，但移動支點的作用，但移動支點只受到垂直方向的力只受到垂直方向的力 3F的作用的作用。 圖圖7.1.1 絎架的受力分析圖絎架的受力分析圖 如果整個絎架處以平衡狀態，每個支點的合力應為零向量，如果整個絎架處以平衡狀態，每個支點的合力應為零向量，因此每個支點上力的水平分量和垂直分量之和都應該為零。由因此每個支點上力的水平分量和垂直分量之和都應該為零。由此可得到一個如表此可得到一個如表 7.1.1所示的線性方程組，該方程組中的系數所示的線性方程組，該方程組

3、中的系數矩陣中含有矩陣中含有46個零元素，而僅有個零元素，而僅有18個非零元素，通常把含有大個非零元素，通常把含有大量零元素的矩陣稱為稀疏矩陣，由于使用直接法求解這類方程量零元素的矩陣稱為稀疏矩陣，由于使用直接法求解這類方程組，會破壞系數矩陣的稀疏性，這種情況下一般采用迭代法求組，會破壞系數矩陣的稀疏性，這種情況下一般采用迭代法求解方程組。解方程組。表表7.1.1支點支點水平分量水平分量垂直分量垂直分量112202Fff12202fF1423022ff13421022fff150ff3100000f 45302ff43102fF在實際應用中遇到的系數矩陣多為大型稀疏矩在實際應用中遇到的系數矩陣

4、多為大型稀疏矩陣，如用求解線性方程組的直接法求解，在計陣，如用求解線性方程組的直接法求解，在計算機上會耗費大量的時間和存儲單元。在許多算機上會耗費大量的時間和存儲單元。在許多應用問題中使用迭代法。應用問題中使用迭代法。思思路路Axb將將 改寫為改寫為 等價形式等價形式 ，建立迭代建立迭代 。從初值。從初值 出發，出發，得到序列得到序列 。xBxg1kkxBxg0 xkx研究內容：研究內容： 如何建立迭代格式？如何建立迭代格式？ 收斂速度？收斂速度？ 向量序列的收斂條件？向量序列的收斂條件？ 誤差估計？誤差估計？一般迭代法一般迭代法迭代格式的構造迭代格式的構造把矩陣把矩陣A A分裂為分裂為 ,0

5、,AQCQ11()().AxbQC xbIQ C xQ bxBxgbQgCQB11,則則將上式寫為迭代過程將上式寫為迭代過程這種迭代過程稱為這種迭代過程稱為逐次逼近法逐次逼近法，B B 稱為稱為迭代矩陣迭代矩陣。1,(2)kkxBxg*lim,nnxx收斂性定義收斂性定義：若：若 稱逐次逼近法稱逐次逼近法收斂，收斂， 否則，稱逐次逼近法否則，稱逐次逼近法不收斂或發散不收斂或發散。0,x01,nxxx給定初值給定初值 就得到向量序列就得到向量序列問題問題：*x*1limlim().kkkkxBxgxBxg定理定理1 1 任意給定初始向量任意給定初始向量x x0 0，如果由逐次，如果由逐次逼近法產

6、生的向量序列收斂于向量逼近法產生的向量序列收斂于向量x x* *，那么，那么，x x* *是方程組是方程組x=Bx+gx=Bx+g的解。的解。證明：證明：是否為方程組是否為方程組Ax=bAx=b的解？的解？迭代法的收斂條件迭代法的收斂條件定理定理 當當k 時，時，Bk 0 0 ( ( B ) 1 ) 1定理定理2 2 設線性方程組設線性方程組x=Bx+gx=Bx+g有惟一解，那么逐有惟一解，那么逐次逼近法對任意初始向量次逼近法對任意初始向量X X收斂的充分必要條收斂的充分必要條件是迭代矩陣件是迭代矩陣B B的譜半徑的譜半徑 ( (B B ) ) 11。*1*1*10()().kkkkkxBxg

7、xBxgxxB xxBxx證明：證明：*11lim()0lim0( )1.kkkkxxBB因此，因此，注：要檢驗一個矩陣的譜半徑小于注：要檢驗一個矩陣的譜半徑小于1 1比較困比較困難，所以我們希望用別的辦法判斷收斂性。難，所以我們希望用別的辦法判斷收斂性。 定理定理3 3 若逐次逼近法的迭代矩陣滿若逐次逼近法的迭代矩陣滿 足足B1B1， 那么逐次逼近法收斂。那么逐次逼近法收斂。RemarkRemark:因為矩陣范數因為矩陣范數 都可以都可以直接用矩陣的元素計算，因此直接用矩陣的元素計算，因此, ,用定理用定理3 3，很，很容易判別逐次逼近法的收斂性。容易判別逐次逼近法的收斂性。1,BFB,B定

8、理定理 4 （充分條件）（充分條件）若存在一個矩陣范數使得若存在一個矩陣范數使得 | B | 1, 則則迭代收斂，且有下列誤差估計：迭代收斂，且有下列誤差估計：11|*|1 |kkkBxxxxB1110|*|1|kkBxxxxB證明：證明：111*( *)( *)kkkkkxxB xxB xxxx111| *| | |(| *| |)kkkkxxBxxxx迭代法的誤差估計迭代法的誤差估計11| *|1 |kkkBxxxxB誤差表達誤差表達式及收斂式及收斂速度速度。停機準則。停機準則。1110().()kkkkkxxB xxBxx11110|*|1 |1 |kkkkBBxxxxxxBB110|

9、| |kkkxxBxxnnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111（4 4.1） 1 1雅克比（雅克比（JacobiJacobi）迭代法）迭代法設有設有n n階方程組階方程組幾種常用的迭代格式幾種常用的迭代格式若系數矩陣非奇異，且若系數矩陣非奇異，且 (i = 1, 2, n)，將方程組將方程組0iia()()()11,22112323121222213132121111111nnnnnnnnnnnnnxaxaxabaxxaxaxabaxxaxaxabax（4.1）改寫成改寫成然后寫成迭代格式然后寫成迭代格式()()()(11,)(22

10、)(11)1()(2)(323)(121122)1(2)(1)(313)(212111)1(1111knnnknknnnnknknnkkkknnkkkxaxaxabaxxaxaxabaxxaxaxabax（4.2）（4.2）式也可以簡單地寫為式也可以簡單地寫為), 2, 1(1)(1)1(nixabaxkjnijjijiiiki（4.3）寫成寫成矩陣形式矩陣形式：A =LUDBfJacobi 迭代陣迭代陣(1 )1()1()()kkkJxDLUxDbBxf(4.4)()()AxbDLU xbDxLU xb11()xDL U xD b112233nnaaDaa2131321230000nnnaL

11、aaaaa 1213123230000nnnaaaaaUa 33111112131122212321313231123()00000000JnnnnnnnnBD L Uaaaaaaaaaaaaaaaa 1311211111123221222222313233333331230000nnJnnnnnnnnnnaaaaaaaaaaaaBaaaaaaaaaaaa Algorithm: Jacobi Iterative Method Solve .Given an initial approximation .Input: the number of equations and unknowns n;

12、 the matrix entries a ; the entries b ; the initial approximation X0 ; tolerance TOL; maximum number of iterations Mmax.Output: approximate solution X or a message of failure.Step 1 Set k = 1;Step 2 While ( k Mmax) do steps 3-6Step 3 For i = 1, , n Set ; /* compute xk */Step 4 If then Output (X ); S

13、TOP; /* successful */Step 5 For i = 1, , n Set X 0 = X ; /* update X0 */ Step 6 Set k +;Step 7 Output (Maximum number of iterations exceeded); STOP. /* unsuccessful */Axb0XiinjijjijiiaXabX 1)0(TOLXXXXiini |0|max|0|1What if aii = 0?迭代過程中，迭代過程中，A 的元素的元素不改變，故可以不改變，故可以事先調整事先調整好好 A 使得使得aii 0，否則否則 A不可逆不可逆

14、。必須等必須等X(k)完全計算完全計算好了才能計算好了才能計算X(k+1)，因此，因此需要需要兩組向量兩組向量存儲。存儲。A bit wasteful, isnt it?)(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk )(13)(3)(434) 1(232) 1(13133) 1(3bxaxaxaxaaxknnkkkk)(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax 只存一組向量即可。只存一組向量即

15、可。寫成寫成矩陣形式矩陣形式：(1)1(1)()1()kkkxDLxUxDb(1)()()kkDL xUxb(1)1( )1()()kkxDLUxDLbBfGauss-Seidel 迭代陣迭代陣2 2高斯高斯賽得爾賽得爾(Gauss-Seidel)(Gauss-Seidel)迭代法迭代法(4.5)(4.6)111()()kkxDLUxDLbBG-SgGauss-Seidel 迭代陣迭代陣其迭代格式的矩陣形式為其迭代格式的矩陣形式為()ADLU()()AxbDLU xbDL xUxb11()()xDLUxDLb1kG SkG SxBxg事實上，這相當于對系數矩陣事實上，這相當于對系數矩陣A A作

16、的另一個分裂：作的另一個分裂：定理定理5 5 n n階矩陣階矩陣A A是按行是按行嚴格嚴格對角占優矩陣對角占優矩陣的充分必要條件是的充分必要條件是JacobiJacobi迭代法的迭代矩迭代法的迭代矩陣滿足陣滿足 BBJ J1.1.定理定理6 6 n n階矩陣階矩陣A A是按列是按列嚴格嚴格對角占優矩陣對角占優矩陣的的充分必要條件是充分必要條件是JacobiJacobi迭代法的迭代矩陣迭代法的迭代矩陣滿足滿足 BBJ J1 11.1.相關性質相關性質 JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法的收斂性迭代法的收斂性 定理定理 7 7 如果如果A

17、 A是按行是按行( (列列) )嚴格對角占優的嚴格對角占優的矩陣，那么矩陣，那么JacobiJacobi和和G GS S迭代法都收斂迭代法都收斂. . 定理定理 8 8 設設A A是不可約對角占優矩陣，是不可約對角占優矩陣， 那么那么Jacobi迭代法與迭代法與GS迭代法都收斂迭代法都收斂. .定理定理 9 9 若若A A是是n n階正定矩陣，那么，階正定矩陣，那么，G-SG-S迭迭代法收斂代法收斂. .定理定理 1010 設設A A是有正對角元的是有正對角元的n n階對稱矩陣，階對稱矩陣，那么那么JacobiJacobi迭代法收斂的充分必要條件是迭代法收斂的充分必要條件是A A和和2D-A2

18、D-A同為正定矩陣同為正定矩陣. .注意的問題注意的問題（2）Jacobi迭代法和迭代法和Gauss-Seidel迭代法的收斂迭代法的收斂 性沒有必然的聯系性沒有必然的聯系：即當即當Gauss-Seidel法收斂時，法收斂時，Jacobi法可能不收斂；法可能不收斂；而而Jacobi法收斂時，法收斂時， Gauss-Seidel法也可能不收斂。法也可能不收斂。（1）Jacobi迭代法和迭代法和Gauss-Seidel迭代法的迭代迭代法的迭代 矩陣不同：矩陣不同：BJ =D-1(L+U), B G-S = (D-L)-1U（3 3）JacobiJacobi迭代和迭代和Gauss-SeidelGau

19、ss-Seidel迭代的特征方程：迭代的特征方程：()()ijn nAaDLU0JIBJacobiJacobi迭代迭代1112121222120nnnnnnaaaaaaaaa1(L+U)0ID(L+U)0DGauss-SeidelGauss-Seidel迭代迭代0G SIB1() U0IDL1112121222120nnnnnnaaaaaaaaa(L)U)0D舉例舉例12312312321121xxxxxxxxx例如用用Jacobi迭代法求解不收斂，但用迭代法求解不收斂，但用 Gauss-Seidel法收法收斂。斂。1231231232212223xxxxxxxxx用用Jacobi迭代法求解收

20、斂，迭代法求解收斂，但用但用 Gauss-Seidel法不收斂。法不收斂。022022101 ,023220002JG SBB BJ的特征值為的特征值為0，0，0， 而而BGS的特征值為的特征值為 0，2，2系數矩陣系數矩陣A A是正定矩陣，因此用是正定矩陣，因此用 Gauss-SeidelGauss-Seidel法收斂法收斂. .12123231221251xxxxxxx11 02122025D A 是正定矩陣，因此用是正定矩陣，因此用 JacobiJacobi迭代法收斂迭代法收斂. .利用定理利用定理7A A是有正對角元是有正對角元的的n n階對稱矩陣階對稱矩陣13412312341234

21、10 5783 113282322717xxxxxxxxxxxxxx 線性方程組的系數矩陣為線性方程組的系數矩陣為10015183032811227A是嚴格對角占優的，所以是嚴格對角占優的，所以Jacobi和和Gauss-Seidel迭代格式迭代格式均收斂。均收斂。3 3超松馳法（超松馳法（Sequential Over-Relaxation)Sequential Over-Relaxation)(1)1(11)1(1kjnijijkjijijiiikixaxabax), 2, 1()1 (1)()1(nixxxkikiki)(1)1(11)()1()1 (kjnijijkjijijiiikikixaxabaxx（1）迭代）迭代（2）加速）加速（4.7）矩陣形式：矩陣形式：()(1)( )1(1)( )(1)kkkkxxDbLxUx(1)()()(1)kkDL xDUxb(1)1( )1()(1)()kkxDLDU xDLb即即超松弛法的收斂性超松弛法的收斂性定理定理1111 SOR SOR方法收斂的必