第6章解线性方程组的迭代法.ppt

数 学 系,University of Science and Technology of China,DEPARTMENT OF MATHEMATICS,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,6,章 解线性方程组的迭代法,直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是,n,3,数量级，存储量为,n,2,量级，这在,n,比较小的时候还比较合适（,n400,），但是对于现,在的很多实际问题，往往要我们求解很大的,n,的矩阵，而且这些矩阵往往是系数矩阵,就是这些矩阵含有大量的,0,元素。对于这类的矩阵，在用直接法时就会耗费大量的时,间和存储单元。因此我们有必要引入一类新的方法：迭代法。,迭代法具有的特点是速度快。与非线性方程的迭代方法一样，需要我们构造一,个等价的方程，从而构造一个收敛序列，序列的极限值就是方程组的根,对方程组,做等价变换,如：令,，则,则，我们可以构造序列,若,同时：,所以，序列收敛,与初值的选取无关,定义,6.1,：（收敛矩阵）,定理：,矩阵,G,为收敛矩阵，当且仅当,G,的谱半径,eps,),x1=x2;,for(i,=0;i,n;i,+),x2i=0;,for(j,=0;j,i;j,+),x2i+=,Aij,*x1j,for(j,=i+1;j,n;j,+),x2i+=,Aij,*x1j,x2i=-(x2i-bi)/Aii,4,、输出解,x2,迭代矩阵,记,易知，,Jacobi,迭代有,收敛条件,迭代格式收敛的充要条件是,G,的谱半径,eps,),for(i,=0;i,n;i,+),for(j,=0;j,i;j,+),x2i+=,Aij,*x2j,for(j,=i+1;j,n;j,+),x2i+=,Aij,*x2j,x2i=-(x2i-bi)/Aii,4,、输出解,x2,迭代矩阵,是否是原来的方程的解？,A=(D-L)-U,收敛条件,迭代格式收敛的充要条件是,G,的谱半径,eps,),for(i,=0;i,n;i,+),temp-0,for(j,=0;j,i;j,+),temp+Aij,*x2j,for(j,=i+1;j,n;j,+),temp+=,Aij,*x2j,temp=-(x2i-bi)/Aii,x2i=(1-omega)*x2i+omega*temp,4,、输出解,x2,迭代矩阵,定理：,松弛迭代收敛,定理：,A,对称正定，则松弛迭代收敛,是否是原来的方程的解？,SOR,方法收敛的快慢与松弛因子,的选择有密切关系,.,但是如何选取最佳松弛因子,即选取,=,*,使,(,),达到最小,是一个尚未很好解决的问题,.,实际上可采用试算的方法来确定较好的松弛因子,.,经验上可取,1.41.6.,定理,若,SOR,方法收敛,则,0,2.,证,设,SOR,方法收敛,则)1,所以,|,det,(,)|=|,1,2,n,|1,而,det,(,)=det,(,D,-,L,),-1,(1-,),D,+,U,),=det,(,E,-,D,-1,L,),-1,det(1-,),E,+,D,-1,U,),=,(1-,),n,于是,|,1-,|1,或,0,2,定理,设,A,是对称正定,矩阵,则解方程组,Ax=b,的,SOR,方法,当,00,(,Uy,y,)=(,y,Ly,)=(,Ly,y,),=,-i,0(,Ay,y,)=(,Dy,y,)-(,Ly,y,)-(,Uy,y,)=,-2,所以,当,0,2,时,有,(,-+),2,-(-),2,=(2-)(2-),=(2-)(2-)0,所以,|,|,2,1,因此,(,)1,即,S0R,方法收敛,.,可得,=2/,设,是,B,的任一特征值,y,是对应的特征向量,则,(,L,+,U,),y,=,Dy,于是,(,Ly,y,)+,(,Uy,y,)=,(,Dy,y,),当,A,对称正定时,即,2-0,时,|0,而,(,2D-A,),y,y,)=(,Dy,y,)+(,Ly,y,)+(,Uy,y,)=,+2,即,当,A,对称正定时,Jacobi,迭代法收敛,2,D,-,A,正定,.,