第二章解线性方程组的迭代法

第二章解线性方程组的迭代法第一页，共三十九页，编辑于2023年，星期四对方程组做等价变换从某一初值x(0)出发，我们可以构造序列若同时：所以，序列收敛与初值的选取无关如令A=D-L-U，于是x=D-1(L+U)x+D-1b,第二页，共三十九页，编辑于2023年，星期四定义5.1：设G为n阶方阵，若Gk0，则称G为收敛矩阵定理：即矩阵G为收敛矩阵，当且仅当G的谱半径<1由知，若有某种范数则，迭代收敛第三页，共三十九页，编辑于2023年，星期四迭代法的收敛性定理：迭代法X(m+1)=GX(m)+g收敛的充分必要条件是迭代矩阵G为收敛矩阵，即G的谱半径(G)<1。定理：

迭代法X(m+1)=GX(m)+g的迭代矩阵G的某种范数||G||＝q<1,那么：1）对任意初值X(0)及g右端向量，迭代格式收敛于X*;2)||X(m)-X*||qm

||X(1)–X(0)||/(1-q);3)||X(m)-X*||q

||X(m)–

X(m-1)||/(

1-q).第四页，共三十九页，编辑于2023年，星期四Jacobi迭代第五页，共三十九页，编辑于2023年，星期四格式很简单：第六页，共三十九页，编辑于2023年，星期四1、输入系数矩阵A和向量b，和误差控制eps2、x1={0,0,…..,0},x2={1,1,…..,1}//赋初值3、while(||A*x2-b||>eps){x1=x2;for(i=0;i<=n;i++){x2[i]=0;for(j=0;j<i;j++){x2[i]+=A[i][j]*x1[j]}for(j=i+1;j<n;j++){x2[i]+=A[i][j]*x1[j]}x2[i]=-(x2[i]-b[i])/A[i][i]}}4、输出解x2Jacobi迭代算法第七页，共三十九页，编辑于2023年，星期四

迭代矩阵记Jacobi迭代法的收敛性第八页，共三十九页，编辑于2023年，星期四易知，Jacobi迭代有第九页，共三十九页，编辑于2023年，星期四练习讨论用雅可比(Jacobi)迭代法求解下列线性方程组的收敛性。若收敛，求其解；若发散，作适当变换使其收敛并求解。第十页，共三十九页，编辑于2023年，星期四G的谱半径(G)=4.0197>1.Jacobi迭代不收敛。迭代矩阵为G的特征值为：1=4.02408,2=-2.012043.10115i,1=4.02408；2,3=3.69668第十一页，共三十九页，编辑于2023年，星期四将方程组变形，化为：第十二页，共三十九页，编辑于2023年，星期四G的谱半径(G)=0.308507<1.Jacobi迭代收敛。此时迭代矩阵为G的特征值分别为：0.308507,-0.154254+0.18304i,-0.154254-0.18304i第十三页，共三十九页，编辑于2023年，星期四收敛条件迭代格式收敛的充要条件是G的谱半径<1。对于Jacobi迭代，我们有一些保证收敛的充分条件定理：若线性方程组AX=b的系数矩阵A满足下列条件之一，则Jacobi迭代收敛。①A为行对角占优阵②A为列对角占优阵③A满足④若A对称正定阵，且2D-A也为对称正定阵，则Jacobi迭代收敛。第十四页，共三十九页，编辑于2023年，星期四证明：②A为列对角占优阵，则AT为行对角占优阵，有＃证毕第十五页，共三十九页，编辑于2023年，星期四在Jacobi迭代中，使用最新计算出的分量值Gauss－Seidel迭代第十六页，共三十九页，编辑于2023年，星期四1、输入系数矩阵A和向量b，和误差控制eps2、x2={1,1,…..,1}//赋初值3、while(||A*x2-b||>eps){for(i=0;i<n;i++){for(j=0;j<i;j++){x2[i]+=A[i][j]*x2[j]}for(j=i+1;j<n;j++){x2[i]+=A[i][j]*x2[j]}x2[i]=-(x2[i]-b[i])/A[i][i]}}4、输出解x2Gauss-Siedel迭代算法第十七页，共三十九页，编辑于2023年，星期四

迭代矩阵是否是原来的方程的解？A=(D-L)-UGauss-Siedel迭代法的收敛性第十八页，共三十九页，编辑于2023年，星期四收敛条件迭代格式X=GX+g对任意的初值X0和向量g，收敛的充要条件是G的谱半径

(G)<1。下面我们看一些充分条件：定理：若线性方程组AX=b的系数矩阵A，②若A对称正定阵，则Gauss-Seidel迭代收敛；③若A对称正定阵，且2D-A也为对称正定阵，则Jacobi迭代收敛。①若A为行或列强对角占优阵，则Jacobi和Gauss-Seidel迭代都收敛；第十九页，共三十九页，编辑于2023年，星期四证明：设G的特征多项式为，则为对角占优阵，则时为对角占优阵即即＃证毕注：二种方法都存在收敛性问题。有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛。第二十页，共三十九页，编辑于2023年，星期四练习：判定用Jacobi和Gauss-Seidel迭代解方程组：AX=b时的收敛情况，其中第二十一页，共三十九页，编辑于2023年，星期四1、Jacobi迭代特征值为2、Gauss－Seidel迭代G的谱半径(G)=1.118>1.Jacobi迭代不收敛。G的谱半径(G)=0.5<1.Gauss-Seidel迭代收敛。第二十二页，共三十九页，编辑于2023年，星期四分别用Jacobi，Gauss-Seidel迭代法解方程组AX=b，其中例题第二十三页，共三十九页，编辑于2023年，星期四1、预处理2、格式：Jacobi迭代：Gauss-Seidel迭代：取初值矩阵A按行严格对角占优，都收敛第二十四页，共三十九页，编辑于2023年，星期四m=1x1=0.777778x2=0.875000x3=0.888889error=0.888889m=2x1=0.973765x2=0.972222x3=0.975309error=0.195988m=3x1=0.994170x2=0.996721x3=0.997085error=0.024498m=4x1=0.999312x2=0.999271x3=0.999352error=0.005142m=5x1=0.999847x2=0.999914x3=0.999924error=0.000643m=6x1=0.999982x2=0.999981x3=0.999983error=0.000135m=7x1=0.999996x2=0.999998x3=0.999998error=0.000017m=8x1=1.00000x2=1.00000x3=1.00000error=0.000004Jacobi迭代3、结果第二十五页，共三十九页，编辑于2023年，星期四m=1x1=0.777778x2=0.972222x3=0.975309error=0.975309m=2x1=0.994170x2=0.999271x3=0.999352error=0.216392m=3x1=0.999847x2=0.999981x3=0.999983error=0.005677m=4x1=0.999996x2=1.00000x3=1.00000error=0.000149m=5x1=1.00000x2=1.000000x3=1.000000error=0.000004Gauss-Seidel迭代第二十六页，共三十九页，编辑于2023年，星期四练习用雅可比(Jacobi)迭代法和高斯－赛德尔(Gauss-Seidel)迭代法求解线性方程组：第二十七页，共三十九页，编辑于2023年，星期四记则可以看作在前一步上加一个修正量。若在修正量前乘以一个因子w，则有对Gauss－Seidel迭代格式松弛迭代第二十八页，共三十九页，编辑于2023年，星期四写成分量形式，有第二十九页，共三十九页，编辑于2023年，星期四松弛迭代算法1、输入系数矩阵A、向量b和松弛因子omega，和误差控制eps2、x2={1,1,…..,1}//赋初值3、while(||A*x2-b||>eps){for(i=0;i<n;i++){temp-0for(j=0;j<i;j++){temp+=A[i][j]*x2[j]}for(j=i+1;j<n;j++){temp+=A[i][j]*x2[j]}temp=-(x2[i]-b[i])/A[i][i]x2[i]=(1-omega)*x2[i]+omega*temp}}4、输出解x2第三十页，共三十九页，编辑于2023年，星期四

迭代矩阵定理：松弛迭代收敛定理：A对称正定，则松弛迭代收敛是否是原来的方程的解？第三十一页，共三十九页，编辑于2023年，星期四

SOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即选取=*,使(G)达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.4<<1.6.当松弛因子<1时，称该算法为低松弛因子法；当松弛因子>1时，称该算法为超松弛因子法；第三十二页，共三十九页，编辑于2023年，星期四

定理若SOR方法收敛,则0<<2.

证设SOR方法收敛,则(G)<1,所以|det(G)|=|12…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,或0<<2第三十三页，共三十九页，编辑于2023年，星期四

定理用SOR法解方程组Ax=b，

证设是G的任一特征值,y是对应的特征向量,则[(1-)D+U]y=(D-

L)y于是(1-

)(Dy,y)+(Uy,y)=[(Dy,y)-

(Ly,y)]1）若A是对称正定矩阵,则当0<<2时收敛；2）若矩阵A按行(列)严格对角占优,则当0<1时收敛；第三十四页，共三十九页，编辑于2023年，星期四由于A=D-

L-

U是对称正定的,所以D是正定矩阵,且L=UT.若记(Ly,y)=+i,则有(Dy,y)=>0(Uy,y)=(y,Ly)=(Ly,y)=-i0<(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y)=-2所以第三十五页，共三十九页，编辑于2023年，星期四当0<<2时,有(-+)2-(-)2=(2-)(2-)=(2-)(2-)<0所以||2<1,因此(G)<1,即S0R方法收敛.可得=2/设是B的任一特征值,y是对应的特征向量,则