數(shù)值分析：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 本章學(xué)習(xí)要點(diǎn)本章學(xué)習(xí)要點(diǎn)l引子引子l迭代法的基本思想迭代法的基本思想l迭代法的主要步驟迭代法的主要步驟 直接法得到的解是理論上準(zhǔn)確的，但是我們可以看得出，它們的計(jì)算計(jì)算量都是n3數(shù)量級(jí)，存儲(chǔ)量存儲(chǔ)量為n2量級(jí)，這在n比較小的時(shí)候還比較合適（n400），但是對(duì)于現(xiàn)在的很多實(shí)際問題，往往要我們求解很大的n的矩陣，而且

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

3、X(k)，使其收斂至某個(gè)極限向量使其收斂至某個(gè)極限向量X* ，并且，并且X*就是要求解就是要求解的方程組：的方程組：AX = b的準(zhǔn)確解。的準(zhǔn)確解。返回節(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)進(jìn)行計(jì)算進(jìn)行計(jì)算。 nTnRxxxX 002)0(10, 如果按上述迭代公式所得到的向量序列如果按上述迭代公式所得到

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

5、的主要步驟 設(shè)有線性方程組設(shè)有線性方程組 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é)迭代矩陣 ;每迭代一次主要是計(jì)算一次矩陣乘向量 ；計(jì)算過程中,初始數(shù)據(jù)A始終不變;計(jì)算過程中涉及到的中間變量 及 ,需要兩組工作單元x(n),y(n)來存儲(chǔ).1()JBDLU( )kJB X()KX(1)kXJacobi

7、 迭代法的計(jì)算步驟迭代法的計(jì)算步驟(5(5步步) )為：為： k=1；輸入最大迭代次數(shù)；輸入最大迭代次數(shù)N，誤差，誤差以及迭代以及迭代初值初值 X=（x1，x2， ，xn） ； ), 2 , 1(/ )(niaxabyiijijijii 如果如果|Y-X|N，算法失敗。，算法失敗。 置置X=Y，即，即xi=yi (i=1,2, ,n)，轉(zhuǎn)，轉(zhuǎ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次，次，結(jié)果見結(jié)果見表表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迭代結(jié)果迭代結(jié)果表表3-13-1返回引用返回引用對(duì)于Jacobi迭代法,它的每一步設(shè)定計(jì)算順序?yàn)樵谟?jì)算迭代值 時(shí), 利用了它前面已計(jì)算的值 而此時(shí) 也已計(jì)算, 但是Jacobi迭代法并沒有充分及時(shí)地利用這些信息, 為此我們得到改進(jìn)的格式 , 稱為高

10、斯高斯塞德爾塞德爾(GaussSeidel)迭代迭代公式公式。 12nxxx1kix111121,kkkixxxJacobi迭代法的改進(jìn)迭代法的改進(jìn)( )kjx(1,2, )jn返回章返回章3.2(II) Gauss-Seidel迭代法迭代法l算法分析與描述算法分析與描述l實(shí)例求解算法分析與描述算法分析與描述), 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)的全部分量來計(jì)算的全部分量來計(jì)算X(k+1)的全部分量的。的全部分量的。 我們應(yīng)該注意到，在計(jì)算新分量我們應(yīng)該注意到，在計(jì)算新分量xi(k+1)時(shí)，分量時(shí)，分量x1(k+1), x2(k+1), , xi-1(k+1)都已經(jīng)算出。都已經(jīng)算出。返回引用返回引用 如果如果 Jacobi 法收斂，則可期望法收斂，則可期望X( (k+1) )比比X( (k) )更更好，在好，在式式( (3- -8) )中右邊第中右邊第1個(gè)求和號(hào)個(gè)求和號(hào) 中，用中，用X( (k+1) )的分量代替的分量代替X( (k) )的分量，似乎更合理些。的分量，似乎更合理些。

12、 這對(duì)許多問題來說，不僅會(huì)這對(duì)許多問題來說，不僅會(huì)加快收斂速度加快收斂速度，更重要的是，在編程序時(shí)，更重要的是，在編程序時(shí)，不必不必另設(shè)一套單元來另設(shè)一套單元來記存上一次記存上一次的的近似解近似解。這就是。這就是逐個(gè)代換算法逐個(gè)代換算法，又，又稱稱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迭代法逐次用計(jì)算出來的新值迭代法逐次用計(jì)算出來的新值代替舊值，所以在收斂的條件下，它要比代替舊值，所以在收斂的條件下，它要比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，迭代結(jié)果見，迭代結(jié)果見表表32 例例3.23.2解解| x（5）-x（4）|=8.010-4| x（5）-x|=10-4 從例從例3. .1和例和例3. .2 比較可見，比較可見，Gauss-Seidel迭代迭代5次的結(jié)次的結(jié)果果比比Jacobi 迭代迭代10次的結(jié)果還要好。次的結(jié)果還要好。 表表3. .2 例例3. .2 Gauss-Seidel迭代結(jié)果迭代結(jié)果 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