第6章解線性方程組的迭代法

1、數(shù) 學(xué) 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS第6章 解線性方程組的迭代法 直接法得到的解是理論上準(zhǔn)確的，但是我們可以看得出，它們的計(jì)算量都是n3數(shù)量級，存儲(chǔ)量為n2量級，這在n比較小的時(shí)候還比較合適（n1000 , 1G/s , 15秒秒 , 8M），但是對于現(xiàn)在的很多實(shí)際問題，往往要我們求解很大的n的矩陣，而且這些矩陣往往是稀疏矩陣就是這些矩陣含有大量的0元素。對于這類的矩陣，在用直接法時(shí)就會(huì)耗費(fèi)大量的時(shí)間和存儲(chǔ)單元。因此我們有必要引入一類新的方法：迭代法。 迭代法具有的特點(diǎn)是速度快。與

2、非線性方程的迭代方法一樣，需要我們構(gòu)造一個(gè)等價(jià)的方程，從而構(gòu)造一個(gè)收斂序列，序列的極限值就是方程組的根數(shù) 學(xué) 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS對方程組bAx 做等價(jià)變換gGxxbMNxMxNxbMxbxNMbAx11)(如：令NMA，則則，我們可以構(gòu)造序列g(shù)xGxkk)()1( 若*)(xxkbAxgxGx* *同時(shí)：*)(*)()()1(xxGGxGxxxkkk*)()0(1xxGk0kG所以，序列收斂與初值的選取無關(guān)與初值的選取無關(guān)數(shù) 學(xué) 系University of Scienc

3、e and Technology of ChinaDEPARTMENT OF MATHEMATICS定義：（收斂矩陣）0kG定理：矩陣G為收斂矩陣，當(dāng)且僅當(dāng)G的譜半徑eps) x1=x2; for(i=0;in;i+) x2i=0; for(j=0;ji;j+) x2i += Aij*x1j for(j=i+1;jn;j+) x2i += Aij*x1j x2i=-(x2i-bi)/Aii 4、輸出解x2數(shù) 學(xué) 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSl 迭代矩陣迭代矩陣ULDA記nnaaD0

4、011000001121nnnaaaL000001112nnnaaaU數(shù) 學(xué) 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS易知，Jacobi迭代有bxULD)(bxULDx)(bDxULDx11)(bDgADIULDG111 , )( 數(shù) 學(xué) 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSl 收斂條件收斂條件 迭代格式收斂的充要條件是G的譜半徑eps) for(i=0;in;i+) for(j=0;ji

5、;j+) x2i += Aij*x2j for(j=i+1;jn;j+) x2i += Aij*x2j x2i=-(x2i-bi)/Aii 4、輸出解x2數(shù) 學(xué) 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSl 迭代矩陣迭代矩陣)()()1(1)1(bUxLxDxkkkbDUxDxLDIkk1)(1)1(1)(bDLDIUxDLDIxkk111)(111)1()()(bLDUxLDxkk1)(1)1()()(bLDgULDG11)( , )( 是否是原來的方程的解？A=(D-L)-U數(shù) 學(xué) 系Uni

6、versity of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSl 收斂條件收斂條件迭代格式收斂的充要條件是G的譜半徑eps) for(i=0;in;i+) temp-0 for(j=0;ji;j+) temp += Aij*x2j for(j=i+1;jn;j+) temp += Aij*x2j temp = -(x2i-bi)/Aii x2i = (1-omega)*x2i+omega*temp 4、輸出解x2數(shù) 學(xué) 系University of Science and Technology of ChinaDEPART

7、MENT OF MATHEMATICS)()1 (1)(1)1(1)()1(bDUxDLxDxxkkkkl 迭代矩陣迭代矩陣bDxUDIxLDIkk1)(1)1(1)1()(bDLDIxUDILDIxkk111)(111)1()()1()(bDLDIgUDILDIG111111)( )1()( 定理： 松弛迭代收斂20定理： A對稱正定，則松弛迭代收斂20是否是原來的方程的解？數(shù) 學(xué) 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS SORSOR方法收斂的快慢與松弛因子 的選擇有密切關(guān)系.但是如何選取

8、最佳松弛因子,即選取 = *,使 (G )達(dá)到最小,是一個(gè)尚未很好解決的問題.實(shí)際上可采用試算的方法來確定較好的松弛因子.經(jīng)驗(yàn)上可取1.4 1.6.數(shù) 學(xué) 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSLab06 線性方程組求根的迭代法1.編寫Gauss-Seidel迭代和SOR迭代的通用程序2.用如上程序求根，并打印迭代步數(shù)和根。3113000100001335901100000931100000000107930000900030577050000074730000000030410000005

9、002720009000229A152723020127710Ax3.取松弛因子為i/50,i=1,2,99，試給出一個(gè)最佳的值數(shù) 學(xué) 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS 定理定理 若SORSOR方法收斂, 則0 2. 證證 設(shè)SORSOR方法收斂, 則 (G )1,所以 |det(G )| =| 1 2 n|1而 det(G ) =det(D- L)-1 (1- )D+ U) =det(E- D-1L)-1 det(1- )E+ D-1U)=(1- )n于是 |1-|1, 或 02數(shù)

10、學(xué) 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS 定理定理 設(shè)A是對稱正定矩陣, 則解方程組Ax=b的SORSOR方法,當(dāng)00 (Uy,y)=(y,Ly)=(Ly,y) =-i 0(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y) =-2所以)()()1 (ii2222222)()(|數(shù) 學(xué) 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS當(dāng)02時(shí),有 (-+)2-(-)2= (2-)(2-) = (2-)(2-)0所以|21, 因此(G )1,即S0R方法收斂.可得 =2/ 設(shè)是B的任一特征值, y是對應(yīng)的特征向量, 則 (L+U)y=Dy于是 (Ly,y)+(Uy,y)=(Dy,y)