數(shù)值分析：6.1-6.2線性方程組迭代解法

1、第六章第六章 線性方程組迭代解法線性方程組迭代解法 l 6.1 6.1 概概 論論 l 6.2(I) 6.2(I) Jacobi 迭代法迭代法 l 6.2(II) 6.2(II) Gauss-Seidel 迭代迭代 法法 l 6.3 6.3 迭代法的收斂性迭代法的收斂性 l 6.4 SOR法法 l 本章學(xué)習(xí)要點(diǎn)本章學(xué)習(xí)要點(diǎn) l引子引子 l迭代法的基本思想迭代法的基本思想 l迭代法的主要步驟迭代法的主要步驟 直接法得到的解是理論上準(zhǔn)確的，但是我們可以直接法得到的解是理論上準(zhǔn)確的，但是我們可以 看得出，它們的計(jì)算量都是看得出，它們的計(jì)算量都是n3數(shù)量級(jí)，存儲(chǔ)量為數(shù)量級(jí)，存儲(chǔ)量為n2 量級(jí)，這在量級(jí)

2、，這在n比較小的時(shí)候還比較合適（比較小的時(shí)候還比較合適（n400），）， 但是對于現(xiàn)在的很多實(shí)際問題，往往要我們求解很但是對于現(xiàn)在的很多實(shí)際問題，往往要我們求解很 大的大的n的矩陣，而且這些矩陣的矩陣，而且這些矩陣(系數(shù)矩陣系數(shù)矩陣)往往往往是含有是含有 大量的大量的0元素。對于這類的矩陣，再用直接法時(shí)就會(huì)元素。對于這類的矩陣，再用直接法時(shí)就會(huì) 耗費(fèi)大量的時(shí)間和存儲(chǔ)單元。另一方面耗費(fèi)大量的時(shí)間和存儲(chǔ)單元。另一方面,實(shí)際實(shí)際計(jì)算結(jié)計(jì)算結(jié) 果精度有時(shí)無法保果精度有時(shí)無法保. 主要原因是在多次消去、回代過主要原因是在多次消去、回代過 程中四則運(yùn)算的誤差積累與傳播無法控制程中四則運(yùn)算的誤差積累與傳播無

3、法控制. 因此我們因此我們 有必要引入一類新的方法：迭代法。有必要引入一類新的方法：迭代法。 返回節(jié)返回節(jié) 迭代法是解線性方程組的一個(gè)重要的實(shí)用方法，迭代法是解線性方程組的一個(gè)重要的實(shí)用方法， 特別適用于求解在實(shí)際中大量出現(xiàn)的，系數(shù)矩陣為特別適用于求解在實(shí)際中大量出現(xiàn)的，系數(shù)矩陣為 稀疏陣的大型線性方程組。稀疏陣的大型線性方程組。 迭代法的基本思想是去構(gòu)成一個(gè)向量序列迭代法的基本思想是去構(gòu)成一個(gè)向量序列X(k)， 使其收斂至某個(gè)極限向量使其收斂至某個(gè)極限向量X* ，并且，并且X*就是要求解就是要求解 的方程組：的方程組： AX=b 的準(zhǔn)確解。的準(zhǔn)確解。 返回節(jié)返回節(jié) 解線性方程組迭代法的主要步

4、驟是解線性方程組迭代法的主要步驟是: : 1.1.把所給的線性方程組把所給的線性方程組AX=b 化成如下形式的同解化成如下形式的同解 方程組方程組 X=BX+f （1) 2. 2. 給出初始向量給出初始向量 , ,按迭按迭 代公式代公式 X(k+1)=BX(k)+f (k=0,1,2,) （2) 進(jìn)行計(jì)算進(jìn)行計(jì)算。 n T n RxxxX 00 2 )0( 1 0 , 如果按上述迭代公式所得到的向量序列如果按上述迭代公式所得到的向量序列 X (k) 收斂于某個(gè)向量收斂于某個(gè)向量X * , ,則則X* 就是方程組就是方程組 AX =b 的的 解，并稱此迭代法收斂。否則，就叫不收斂或發(fā)解，并稱此迭

5、代法收斂。否則，就叫不收斂或發(fā) 散。散。 式式(1)(1)、(2)(2)中的矩陣中的矩陣B ，稱為迭代矩陣。稱為迭代矩陣。 研究研究 內(nèi)容：內(nèi)容： 如何建立迭代格式？如何建立迭代格式？ 向量序列的收斂條件？向量序列的收斂條件？ 收斂速度？收斂速度？ 誤差估計(jì)？誤差估計(jì)？ 本章重要介紹三個(gè)迭代法，即：本章重要介紹三個(gè)迭代法，即： 1）Jacobi迭代法迭代法, 2）Gauss-Seidel 迭代法迭代法, 3）超松弛迭代法（超松弛迭代法（SOR法）法） 及其收斂性。及其收斂性。 返回章返回章 3.2(I) Jacobi迭代法迭代法 l數(shù)學(xué)問題的描述數(shù)學(xué)問題的描述 lJacobi迭代法的主要步驟迭

6、代法的主要步驟 設(shè)有線性方程組設(shè)有線性方程組 AX =b 即即 nnnnnn nn nn bxaxaxa bxaxaxa bxaxaxa 2211 22222121 11212111 （3） 其中其中 A=(aij)nn 非奇異（非奇異（A 0），且），且a ii0 (i=1,2,n), 由式由式 （3）得）得 （4） ), 2 , 1(nixabxa j ij ijiiii 返回引用返回引用 若記若記 0 0 0 0 0 0 2 112 21 2122 11 n n nnnn a aa U aa a L a a a D 則有則有 A=D-L-U成立成立，而式（，而式（3- -4）的矩陣形式為

7、）的矩陣形式為 DX =（L+U）X+b （5） 等式兩邊乘以等式兩邊乘以D-1，得，得 X= D-1（L+U）X+ D-1b （6） 由此得到迭代公式由此得到迭代公式 X（ （k+1）= D-1（ （L+U）X（ （k）+ D-1b （ （7） 即即 （8） ), 2 , 1 , 0( ), 2 , 1( / )( )()1( k ni axabx ii k j ij iji k i 這種迭代法，稱為這種迭代法，稱為Jacobi迭代法。迭代法。 返回節(jié)返回節(jié) nnnnnn nn nn bxaxaxa bxaxaxa bxaxaxa . . . . 2211 22222121 11212111

8、 0 ii a 寫成矩陣形式寫成矩陣形式： A = -L -U D () () AxbDLUxb DxLU xb 11 ()xDLU xD b Bf Jacobi 迭代陣迭代陣 1 11 () k k xDL U xD b 11 22 33 nn a a Da a 21 3132 123 0 0 0 0 nnn a Laa aaa 12131 232 3 0 0 0 0 n n n aaa aa Ua 33 1 1 1112131 1 2221232 1 31323 1 123 () 00 00 00 00 J n n n nnn nn BD L U aaaa aaaa aaaa aaa a

9、13112 111111 23221 222222 31323 333333 123 0 0 0 0 n n Jn nnn nnnnnn aaa aaa aaa aaa Baaa aaa aaa aaa 迭代矩陣迭代矩陣 ; 每迭代一次主要近似計(jì)算一次矩陣乘向量每迭代一次主要近似計(jì)算一次矩陣乘向量 ； 計(jì)算過程中計(jì)算過程中,初始數(shù)據(jù)初始數(shù)據(jù)A始終不變始終不變; 計(jì)算過程中涉及到的中間變量計(jì)算過程中涉及到的中間變量 及及 ,需要兩需要兩 組工作單元組工作單元x(n),y(n)來存儲(chǔ)來存儲(chǔ). 1 () J BDLU ( )k J B X ()K X (1)k X Jacobi 迭代法的計(jì)算步驟迭代

10、法的計(jì)算步驟(5(5步步) )為：為： k=1；輸入最大迭代次數(shù)；輸入最大迭代次數(shù)N，誤差，誤差以及迭代以及迭代 初值初值 X=（x1，x2， ，xn） ； ), 2 , 1(/ )(niaxaby iij ij ijii 如果如果|Y-X|N，算法失敗。，算法失敗。 置置X=Y，即，即xi=yi (i=1,2, ,n)，轉(zhuǎn)；，轉(zhuǎn)； 例例1 1 1583 11102 25311 6 210 432 4321 4321 321 xxx xxxx xxxx xxx 求解求解 Jacobi迭代公式為：迭代公式為： 8/ )315( 10/ )211( 11/ )325( 10/ )26( )( 3

11、)( 2 )1( 4 )( 4 )( 2 )( 1 )1( 3 )( 4 )( 3 )( 1 )1( 2 )( 3 )( 2 )1( 1 kkk kkkk kkkk kkk xxx xxxx xxxx xxx 解解: 選取選取X（ （0）=(0,0,0,0)T,迭代 迭代10次，次，結(jié)果見結(jié)果見表表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

12、.0493 1.1309 41.0152 1.9537 -0.9681 0.9739 50.9890 2.0114 -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 -1.9998 0.9998 例例3.13.1迭代結(jié)果迭代結(jié)果 表表1 1 返回引用返回引用 對于Jacobi迭代法,它的每一步設(shè)定計(jì)算順序?yàn)?在計(jì)算迭代值 , 利用它前面已計(jì)算的值

13、 而此時(shí) 也已計(jì)算, 但是Jacobi迭代 法并沒有充分及時(shí)地利用這些信息, 為此我們得到改 進(jìn)的格式 , 稱為高斯高斯塞德爾塞德爾(GaussSeidel)迭代迭代 公式公式。 12n xxx 1k i x , 111 121 kkk i xxx 1,2,in Jacobi迭代法的改進(jìn)迭代法的改進(jìn) l j x(1,2, ;1, )jn lk 返回章返回章 3.2(II) Gauss-Seidel迭代法迭代法 l算法分析與描述算法分析與描述 l實(shí)例求解 算法分析與描述算法分析與描述 ), 2 , 1(/ )( 1 )( 1 1 )() 1( niaxaxabx ii n ij k jij i

14、j k jiji k i (8)(8) 可寫成形如可寫成形如 原原Jacobi迭代公式迭代公式(8) ), 2 , 1 , 0)(, 2 , 1(/ )( )()1( kniaxabx ii k j ij iji k 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( (

15、k+1) )比比X( (k) )更更 好，在式好，在式( (8) )中右邊第中右邊第1個(gè)求和號(hào)個(gè)求和號(hào) 中，用中，用X( (k+1) )的的 分量代替分量代替X( (k) )的分量，似乎更合理些。的分量，似乎更合理些。 這對許多問題來說，不僅會(huì)這對許多問題來說，不僅會(huì)加快收斂速度加快收斂速度， 更重要的是，在排程序時(shí)，更重要的是，在排程序時(shí)，不必不必另設(shè)一套單元來另設(shè)一套單元來 記存上一次記存上一次的的近似解近似解。這就是。這就是逐個(gè)代換算法逐個(gè)代換算法，又，又 稱稱Gauss-Seidel迭代法迭代法。 因此，我們就得到新的迭代公式：因此，我們就得到新的迭代公式： ), 2 , 1(/ )(

16、 1 )( 1 1 ) 1() 1( niaxaxabx ii n ij k jij i j k jiji k i （9)9) 這就是這就是Gauss-Seidel迭代公式迭代公式 X( (k+1) )=BG X( (k) ) + fG （10） 其中其中 BG=(D-L)-1U，fG=(D-L)-1b，稱稱BG為為G-S迭代矩陣。迭代矩陣。 由于由于Gauss-Seidel迭代法逐次用計(jì)算出來的新值迭代法逐次用計(jì)算出來的新值 代替舊值，所以在收斂的條件下，它要比代替舊值，所以在收斂的條件下，它要比Jacobi迭迭 代法收斂速度快。代法收斂速度快。 返回節(jié)返回節(jié) Gauss-Seidel迭代公

17、式的其矩陣形式為：迭代公式的其矩陣形式為： 用用Gauss-Seidel迭代法求解迭代法求解例例1 Gauss-Seidel迭代公式為迭代公式為 8/ )315( 10/ )211( 11/ )325( 10/ )26( )1( 3 )1( 2 )1( 4 )( 4 )1( 2 )1( 1 )1( 3 )( 4 )( 3 )1( 1 )1( 2 )( 3 )( 2 )1( 1 kkk kkkk kkkk kkk xxx xxxx xxxx xxx 仍取仍取x（ （0）=（ （0，0，0，0）T，迭代結(jié)果見，迭代結(jié)果見表表2 例例2 2 解解 | x（ （5）-x（4）|=8.0 10-4 | x（ （5）-x| =10-4 從例從例1和例和例2 比較可見，比較可見，Gauss-Seidel迭代迭代5次的結(jié)果次的結(jié)果比比 Jacobi 迭代迭代10次的結(jié)果次的結(jié)果還要好