第6部分解線方組的迭代法

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

2、非線性方程的迭代方法一樣，需要我們構(gòu)造一個等價的方程，從而構(gòu)造一個收斂序列，序列的極限值就是方程組的根數(shù) 學(xué) 系university of science and technology of chinadepartment of mathematics對方程組bax 做等價變換ggxxbmnxmxnxbmxbxnmbax11)(如：令nma，則則，我們可以構(gòu)造序列g(shù)xgxkk)()1( 若*)(xxkbaxgxgx* *同時：*)(*)()()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; / x1 是第k步，x2是第k+1步 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

4、迭代矩陣迭代矩陣)()(3)(2)(1321333333233312222223222111111131112)1()1(3)1(2)1(10000knkkknnnnnnnnnnnnknkkkxxxxaaaaaaaaaaaaaaaaaaaaaaaaxxxx數(shù) 學(xué) 系university of science and technology of chinadepartment of mathematics000011110000321332312232111312332211321333333233312222223222111111131112nnnnnnnnnnnnnnnnnnnnaaaaa

5、aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaannaad0011)(1dad數(shù) 學(xué) 系university of science and technology of chinadepartment of mathematics易知，jacobi迭代有bxadd)(bxaddx)(bdxaddx11)(bdgadiaddg111 , )( 數(shù) 學(xué) 系university of science and technology of chinadepartment of mathematicsl 收斂條件收斂條件 迭代格式收斂的充要條件是g的譜半徑eps) x1=x2; /x1

6、 是第k步，x2是第k+1步 for(i=0;in;i+) t=0.0 for(j=0;ji;j+) t += aij*x2j for(j=i+1;jn;j+) t += aij*x2j x2i=-(t-bi)/aii 4、輸出解x2數(shù) 學(xué) 系university of science and technology of chinadepartment of mathematicsl 迭代矩陣迭代矩陣ulda記nnaad0011000001121nnnaaal000001112nnnaaau數(shù) 學(xué) 系university of science and technology of chinade

7、partment of mathematicsl 迭代矩陣迭代矩陣)()()1(1)1(buxlxdxkkkbuxxldkk)()1()(blduxldxkk1)(1)1()()(bldguldg11)( , )( a=(d+l)-(-u)數(shù) 學(xué) 系university of science and technology of chinadepartment of mathematicsl 收斂條件收斂條件迭代格式收斂的充要條件是g的譜半徑eps) x1=x2; /x1 是第k步，x2是第k+1步 for(i=0;in;i+) temp=0 for(j=0;ji;j+) temp += aij

8、*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 chinadepartment of mathematics)()1 (1)(1)1(1)()1(bduxdlxdxxkkkkl 迭代矩陣迭代矩陣bxudxldkk)()1()1()(bldxudldxkk1)(1)1()()1()(bldgudldg11)( )1()( 定理： 松弛迭代收斂20定理： a對稱正定

9、，則松弛迭代收斂20數(shù) 學(xué) 系university of science and technology of chinadepartment of mathematics sorsor方法收斂的快慢與松弛因子 的選擇有密切關(guān)系.但是如何選取最佳松弛因子,即選取 = *,使 (g )達(dá)到最小,是一個尚未很好解決的問題.實(shí)際上可采用試算的方法來確定較好的松弛因子.經(jīng)驗(yàn)上可取1.4 1.6.數(shù) 學(xué) 系university of science and technology of chinadepartment of mathematicslab06 線性方程組求根的迭代法1.編寫gauss-seid

10、el迭代和sor迭代的通用程序2.用如上程序求根，并打印迭代步數(shù)和根。3113000100001335901100000931100000000107930000900030577050000074730000000030410000005002720009000229a152723020127710ax3.取松弛因子為i/50,i=1,2,99，試給出一個最佳的值數(shù) 學(xué) 系university of science and technology of chinadepartment of mathematicssample output ( represents a space)gauss-

11、seidel迭代，根和迭代步數(shù)為0.1.0.9 5sor迭代，迭代步數(shù)為1,100.99,5000數(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(i+ d-1l)-1 det(1- )i- d-1u)=(1- )n于是 |1-|1, 或 02數(shù) 學(xué) 系university o

12、f science and technology of chinadepartment of mathematics 定理定理 設(shè)a是對稱正定矩陣, 則解方程組ax=b的sor方法,當(dāng)0 0 (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時,有 (-+)2-(-)2= (2-)(2-) = (2-)(2-)0所以|21, 因此(g )1,即s0r方法收斂.可得 =2/ 設(shè)是b的任一特征值, y是對應(yīng)的特征向量, 則 (l