數值分析：3-1-3-2線性方程組迭代解法

1、第三章第三章 線性方程組迭代解法線性方程組迭代解法l 3.1 3.1 概概 論論l 3.2(I) 3.2(I) Jacobi 迭代法迭代法l 3.2(II) 3.2(II) Gauss-Seidel 迭代法迭代法l 3.3 3.3 迭代法的收斂性迭代法的收斂性l 3.4 SOR法法l 本章學習要點本章學習要點l引子引子l迭代法的基本思想迭代法的基本思想l迭代法的主要步驟迭代法的主要步驟 直接法得到的解是理論上準確的，但是我們可以看得出，它們的計算計算量都是n3數量級，存儲量存儲量為n2量級，這在n比較小的時候還比較合適（n400），但是對于現在的很多實際問題，往往要我們求解很大的n的矩陣，而且

2、這些矩陣(系數矩陣)往往是含有大量的0元素。對于這類的矩陣，再用直接法時就會耗費大量的時間和存儲單元。另一方面,實際計算結果精度有時計算結果精度有時無法保證無法保證. 主要原因主要原因是在多次消去、回代過程中四則運算的誤差積累與傳播無法控制. 因此我們有必要引入一類新的方法：迭代法迭代法。 返回節(jié)返回節(jié) 迭代法是解線性方程組的一種重要的實用方法，迭代法是解線性方程組的一種重要的實用方法，特別適用于求解在實際中大量出現的，系數矩陣為特別適用于求解在實際中大量出現的，系數矩陣為稀疏陣的大型線性方程組。稀疏陣的大型線性方程組。 迭代法的基本思想是去構成一個向量序列迭代法的基本思想是去構成一個向量序列

3、X(k)，使其收斂至某個極限向量使其收斂至某個極限向量X* ，并且，并且X*就是要求解就是要求解的方程組：的方程組：AX = b的準確解。的準確解。返回節(jié)返回節(jié)解線性方程組迭代法的主要步驟是解線性方程組迭代法的主要步驟是: :1.1.把所給的線性方程組把所給的線性方程組AX=b 化成如下形式的同解化成如下形式的同解方程組方程組 X=BX+f （3-1) 2. 2. 給出初始向量給出初始向量 , ,按迭按迭代公式代公式 X(k+1)=BX(k)+f (k=0,1,2,) （3-2)進行計算進行計算。 nTnRxxxX 002)0(10, 如果按上述迭代公式所得到的向量序列如果按上述迭代公式所得到

4、的向量序列 X (k) 收斂于某個向量收斂于某個向量X * , ,則則X* 就是方程組就是方程組 AX =b 的的解，并稱此迭代法解，并稱此迭代法收斂收斂。否則，就叫不收斂或發(fā)。否則，就叫不收斂或發(fā)散。散。 式式(3-1)(3-1)、(3-2)(3-2)中的矩陣中的矩陣B ，稱為稱為迭代矩陣迭代矩陣。 本章重點介紹三個迭代法，即：本章重點介紹三個迭代法，即： 1）Jacobi迭代法迭代法, 2）Gauss-Seidel 迭代法迭代法, 3）超松弛迭代法（超松弛迭代法（SOR法）法） 及其收斂性。及其收斂性。 返回章返回章3.2(I) Jacobi迭代法迭代法l數學問題的描述lJacobi迭代法

5、的主要步驟 設有線性方程組設有線性方程組 AX =b 即即 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111（3- -3） 其中其中 A=(aij)nn 非奇異（非奇異（A 0），且），且a ii0 (i=1,2,n), 由式由式（3-3）得）得 （3- -4） ), 2 , 1(nixabxajijijiiii 返回引用返回引用若記若記 000000211221212211nnnnnnaaaUaaaLaaaD則有則有 A=D-L-U成立成立，而，而式（式（3- -4）的矩陣形式為的矩陣形式為 DX =（L+U）X+b （3- -5） 等式

6、兩邊乘以等式兩邊乘以D-1，得，得 X= D-1（L+U）X+ D-1b （3- -6） 由此得到迭代公式由此得到迭代公式 X（k+1）= D-1（L+U）X（k）+ D-1b （3-7）即即 （3-8）), 2 , 1 , 0(), 2 , 1(/ )()()1( kniaxabxiikjijijiki這種迭代法，稱為這種迭代法，稱為Jacobi迭代法。迭代法。 返回節(jié)返回節(jié)迭代矩陣 ;每迭代一次主要是計算一次矩陣乘向量 ；計算過程中,初始數據A始終不變;計算過程中涉及到的中間變量 及 ,需要兩組工作單元x(n),y(n)來存儲.1()JBDLU( )kJB X()KX(1)kXJacobi

7、 迭代法的計算步驟迭代法的計算步驟(5(5步步) )為：為： k=1；輸入最大迭代次數；輸入最大迭代次數N，誤差，誤差以及迭代以及迭代初值初值 X=（x1，x2， ，xn） ； ), 2 , 1(/ )(niaxabyiijijijii 如果如果|Y-X|N，算法失敗。，算法失敗。 置置X=Y，即，即xi=yi (i=1,2, ,n)，轉，轉； 例例3.13.1 158311102253116 21043243214321321xxxxxxxxxxxxxx求解求解Jacobi迭代公式為：迭代公式為： 8/ )315(10/ )211(11/ )325(10/ )26()(3)(2)1(4)(4

8、)(2)(1)1(3)(4)(3)(1)1(2)(3)(2)1(1kkkkkkkkkkkkkkxxxxxxxxxxxxxx解解:選取選取X（0）=(0,0,0,0)T,迭代迭代10次，次，結果見結果見表表3-1 返回引用返回引用kx1（k） x2（k） x3（k） x4（k） 00.0000 0.0000 0.0000 0.0000 10.6000 2.2727 -1.1000 1.8750 21.0473 1.7157 -0.8052 0.8852 30.9326 2.0533 -1.0493 1.1309 41.0152 1.9537 -0.9681 0.9739 50.9890 2.01

9、14 -1.0103 1.0214 61.0032 1.9922 -0.9945 0.9944 70.9981 2.0023 -1.0020 1.0036 81.0006 1.9987 -0.9990 0.9989 90.9997 2.0004 -1.0004 1.0006 101.0001 1.9998 -0.9998 0.9998例例3.13.1迭代結果迭代結果表表3-13-1返回引用返回引用對于Jacobi迭代法,它的每一步設定計算順序為在計算迭代值 時, 利用了它前面已計算的值 而此時 也已計算, 但是Jacobi迭代法并沒有充分及時地利用這些信息, 為此我們得到改進的格式 , 稱為高

10、斯高斯塞德爾塞德爾(GaussSeidel)迭代迭代公式公式。 12nxxx1kix111121,kkkixxxJacobi迭代法的改進迭代法的改進( )kjx(1,2, )jn返回章返回章3.2(II) Gauss-Seidel迭代法迭代法l算法分析與描述算法分析與描述l實例求解算法分析與描述算法分析與描述), 2 , 1(/ )(1)(11)() 1(niaxaxabxiinijkjijijkjijiki (3-8)(3-8)可寫成形如可寫成形如 原原Jacobi迭代公式迭代公式(3- -8), 2 , 1 , 0)(, 2 , 1(/ )()()1( kniaxabxiikjijijik

11、i 在在Jacobi 迭代中，是用迭代中，是用X(k)的全部分量來計算的全部分量來計算X(k+1)的全部分量的。的全部分量的。 我們應該注意到，在計算新分量我們應該注意到，在計算新分量xi(k+1)時，分量時，分量x1(k+1), x2(k+1), , xi-1(k+1)都已經算出。都已經算出。返回引用返回引用 如果如果 Jacobi 法收斂，則可期望法收斂，則可期望X( (k+1) )比比X( (k) )更更好，在好，在式式( (3- -8) )中右邊第中右邊第1個求和號個求和號 中，用中，用X( (k+1) )的分量代替的分量代替X( (k) )的分量，似乎更合理些。的分量，似乎更合理些。

12、 這對許多問題來說，不僅會這對許多問題來說，不僅會加快收斂速度加快收斂速度，更重要的是，在編程序時，更重要的是，在編程序時，不必不必另設一套單元來另設一套單元來記存上一次記存上一次的的近似解近似解。這就是。這就是逐個代換算法逐個代換算法，又，又稱稱Gauss-Seidel迭代法迭代法。 因此，我們就得到新的迭代公式：因此，我們就得到新的迭代公式：), 2 , 1(/ )(1)(11) 1() 1(niaxaxabxiinijkjijijkjijiki （3-9)-9) 這就是這就是Gauss-Seidel迭代迭代公式公式 X( (k+1) )=BG X( (k) ) + fG （3- -10）

13、 其中其中 BG=(D-L)-1U，fG=(D-L)-1b，稱稱BG為為G-S迭代矩陣。迭代矩陣。 由于由于Gauss-Seidel迭代法逐次用計算出來的新值迭代法逐次用計算出來的新值代替舊值，所以在收斂的條件下，它要比代替舊值，所以在收斂的條件下，它要比Jacobi迭迭代法收斂速度快。代法收斂速度快。 返回節(jié)返回節(jié)Gauss-Seidel迭代公式的其矩陣形式為：迭代公式的其矩陣形式為：用用Gauss-Seidel迭代法求解迭代法求解例例3. .1 Gauss-Seidel迭代公式為迭代公式為 8/ )315(10/ )211(11/ )325(10/ )26()1(3)1(2)1(4)(4)

14、1(2)1(1)1(3)(4)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkkkkkkxxxxxxxxxxxxxx仍取仍取x（0）=（0，0，0，0）T，迭代結果見，迭代結果見表表32 例例3.23.2解解| x（5）-x（4）|=8.010-4| x（5）-x|=10-4 從例從例3. .1和例和例3. .2 比較可見，比較可見，Gauss-Seidel迭代迭代5次的結次的結果果比比Jacobi 迭代迭代10次的結果還要好。次的結果還要好。 表表3. .2 例例3. .2 Gauss-Seidel迭代結果迭代結果 k x 1（k） x 2（k） x 3（k） x 4（k） 0 0.0000 0.0000 0.0000 0.0000 1 0.6000 2