1、第二章 解線性方程組的迭代法2.3 Jacobi方法與Gauss-Seidel方法2一般迭代法的求解步驟依據方程組分離x得到迭代格式判斷迭代格式是否收斂迭代求解滿足終止條件,迭代結束32.3.1 Jacobi方法考慮方程組 Ax=b (2.3.1)其中 是非奇異的, 為已知向量.將矩陣A寫成如下 A=D-L-U (2.3.2)其中 為對角陣,-L,-U分別為A的嚴格下,上三角部分構成的三角陣45當D非奇異,即aii0(i=1,2,n)時,利用(2.3.2)式,可將方程組(2.3.1)寫成于是可得迭代格式稱此格式為求解方程組(2.3.1)的Jacobi迭代法.注意到L+U=D-A,故(2.3.3

2、)式也可寫成(2.3.3)(2.3.4)6Jacobi方法的迭代矩陣為Jacobi迭代法(2.3.4)式的分量形式為(2.3.6)7例2.1 用Jacobi方法解方程組82.3.2 Gauss-Seidel方法簡單迭代法(2.2.3)的分量形式是可以用這些新值來計算 ,于是可得迭代格式這種方法稱為Seidel迭代法.(2.3.7)9對Jacobi迭代(2.3.6)式運用Seidel技巧得到稱(2.3.9)式為Gauss-Seidel迭代法,其矩陣形式為并可整理成一般迭代法的形式(2.3.9)(2.3.10)10例2.1 用Jacobi和Gauss-Seidel方法解方程組11小結12小結Jac

3、obi迭代法迭代矩陣迭代格式13GS方法迭代矩陣迭代格式14例 利用迭代法求解方程組討論Jacobi和Gauss-Seidel方法的收斂性152.3.3 對角占優矩陣與不可約矩陣 定義2.4 若矩陣A=(aij)滿足條件 且至少有一個i,使不等式嚴格成立,則稱A為(按行)對角占優矩陣;若對i=1,n嚴格不等式均成立,則稱A為(按行)嚴格對角占優矩陣.類似地,可以定義(按列)對角占優矩陣和(按列)嚴格對角占優矩陣.(2.3.14)1617定義2.5 設 ,若存在置換矩陣P,使得其中B和D是階數1的方陣, O是零矩陣,則稱A為可約的,否則稱A為不可約的.定理2.6 若A為嚴格對角占優矩陣(或對角占

4、優不可約矩陣),則A是非奇異的.182.3.4 迭代法收斂的充分條件定理2.7 若系數矩陣A滿足1)按行(或列)嚴格對角占優,或者2)不可約按行(或列)對角占優,則Jacobi迭代法(2.3.6)式和Gauss-Seidel迭代法(2.3.9)式均收斂.(2.3.9)(2.3.6)19定理2.8 若A是對角元素大于零的實對稱矩陣,則Jacobi方法收斂的充分必要條件是A和2D-A皆為正定矩陣.定理2.9 設A為對稱正定矩陣,則解Ax=b的Gauss-Seidel方法收斂.202.4松弛法松弛技術的設計思想在實際計算中常常可以獲得目標值F*的兩個相伴隨的近似值F0與F1 ,于是可以取兩者的某種加

5、權平均去改善精度，即也就是說，適當選取權值系數來調整校正量，以將F0與F1加工成更高精度的結果。由于這種方法基于校正量的調整與松動，通常稱之為松弛技術。2.4.1Richardson迭代一般迭代法：Ax=b x=Hx+g2.4.1Richardson迭代一般迭代法：Ax=b x=Hx+g記令2.4.1Richardson迭代一般迭代法：Ax=b x=Hx+g記令得到：2.4.1Richardson迭代一般迭代法：Ax=b x=Hx+g記令得到：2.4.1Richardson迭代收斂性：H=I- A(H)=(I- A)1|1- A|1 A為A任意特征值當A為對稱正定矩陣時02/max A2.4.

6、2Jacobi松弛法Jacobi over relaxation (JOR)Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b記令2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b記令得到：或者2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b記令得到：或者2.4.3 SOR方法對Gauss-Seidel方法施加松弛技術Successive over relaxation (SOR)Gaus

7、s-Seidel迭代法：2.4.3 SOR方法Gauss-Seidel迭代法：記令2.4.3 SOR方法得到：矩陣形式：2.4.3 SOR方法得到：矩陣形式：第二章小結36小結向量范數矩陣范數譜半徑37常見的三種向量范數“1范數”“2范數”（歐氏范數）“范數”（最大范數）38(ATA之最大特征值)1/2行和范數列和范數譜范數（2.1.15）39譜半徑矩陣A的特征值的按模最大值稱為A的譜半徑記作，即其中是A的特征值。定理2.3對任意 ，有40一般迭代法的求解步驟依據方程組分離x得到迭代格式判斷迭代格式是否收斂迭代求解滿足終止條件,迭代結束41小結42小結Jacobi迭代法迭代矩陣迭代格式43GS方法迭代矩陣迭代格式44定理2.7 若系數矩陣A滿足1)按行(或列)嚴格對角占優,或者2)不可約按行(或列)對角占優,則Jacobi迭代法和Gauss-Seidel迭代法均收斂.定理2.8 若A是對角元素大于