第6部分解线方组的迭代法

1、数 学 系university of science and technology of chinadepartment of mathematics第6章 解线性方程组的迭代法 直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3数量级，存储量为n2量级，这在n比较小的时候还比较合适（n1000 , 1g/s , 15秒秒 , 8m），但是对于现在的很多实际问题，往往要我们求解很大的n的矩阵，而且这些矩阵往往是稀疏矩阵就是这些矩阵含有大量的0元素。对于这类的矩阵，在用直接法时就会耗费大量的时间和存储单元。因此我们有必要引入一类新的方法：迭代法。 迭代法具有的特点是速度快。与

2、非线性方程的迭代方法一样，需要我们构造一个等价的方程，从而构造一个收敛序列，序列的极限值就是方程组的根数 学 系university of science and technology of chinadepartment of mathematics对方程组bax 做等价变换ggxxbmnxmxnxbmxbxnmbax11)(如：令nma，则则，我们可以构造序列gxgxkk)()1( 若*)(xxkbaxgxgx* *同时：*)(*)()()1(xxggxgxxxkkk*)()0(1xxgk0kg所以，序列收敛与初值的选取无关与初值的选取无关数 学 系university of scienc

3、e and technology of chinadepartment of mathematics定义：（收敛矩阵）0kg定理：矩阵g为收敛矩阵，当且仅当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数 学 系university of science and technology of chinadepartment of mathematicsl

4、迭代矩阵迭代矩阵)()(3)(2)(1321333333233312222223222111111131112)1()1(3)1(2)1(10000knkkknnnnnnnnnnnnknkkkxxxxaaaaaaaaaaaaaaaaaaaaaaaaxxxx数 学 系university of science and technology of chinadepartment of mathematics000011110000321332312232111312332211321333333233312222223222111111131112nnnnnnnnnnnnnnnnnnnnaaaaa

5、aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaannaad0011)(1dad数 学 系university of science and technology of chinadepartment of mathematics易知，jacobi迭代有bxadd)(bxaddx)(bdxaddx11)(bdgadiaddg111 , )( 数 学 系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数 学 系university of science and technology of chinadepartment of mathematicsl 迭代矩阵迭代矩阵ulda记nnaad0011000001121nnnaaal000001112nnnaaau数 学 系university of science and technology of chinade

7、partment of mathematicsl 迭代矩阵迭代矩阵)()()1(1)1(buxlxdxkkkbuxxldkk)()1()(blduxldxkk1)(1)1()()(bldguldg11)( , )( a=(d+l)-(-u)数 学 系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数 学 系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数 学 系university of science and technology of chinadepartment of mathematics sorsor方法收敛的快慢与松弛因子 的选择有密切关系.但是如何选取最佳松弛因子,即选取 = *,使 (g )达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.4 1.6.数 学 系university of science and technology of chinadepartment of mathematicslab06 线性方程组求根的迭代法1.编写gauss-seid

10、el迭代和sor迭代的通用程序2.用如上程序求根，并打印迭代步数和根。3113000100001335901100000931100000000107930000900030577050000074730000000030410000005002720009000229a152723020127710ax3.取松弛因子为i/50,i=1,2,99，试给出一个最佳的值数 学 系university of science and technology of chinadepartment of mathematicssample output ( represents a space)gauss-

11、seidel迭代，根和迭代步数为0.1.0.9 5sor迭代，迭代步数为1,100.99,5000数 学 系university of science and technology of chinadepartment of mathematics 定理定理 若sorsor方法收敛, 则0 2. 证证 设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数 学 系university o

12、f science and technology of chinadepartment of mathematics 定理定理 设a是对称正定矩阵, 则解方程组ax=b的sor方法,当0 0 (uy,y)=(y,ly)=(ly,y) =-i 0(ay,y)=(dy,y)-(ly,y)-(uy,y) =-2所以)()()1 (ii2222222)()(|数 学 系university of science and technology of chinadepartment of mathematics当02时,有 (-+)2-(-)2= (2-)(2-) = (2-)(2-)0所以|21, 因此(g )1,即s0r方法收敛.可得 =2/ 设是b的任一特征值, y是对应的特征向量, 则 (l