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

解线性方程组的迭代法,直接法得到的解是理论上准确的，但是它们的计算量都是n3数量级，存储量为n2量级，这在n比较小的时候还比较合适（n400），但是在很多实际问题中，我们要求解的方程组n很大，而系数矩阵中含有大量的0元素。对于这类的矩阵，在用直接法时就会耗费大量的时间和存储单元。因此我们有必要引入一类新的方法：迭代法。,迭代法是一种逐次逼近的方法，其基本思想是：使用某个固定的公式，对解的近似值进行反复校正，从而得到一个近似解序列，使之收敛于方程组的解。,迭代法具有算法简单、运算速度快的特点。但这种方法获得的是方程组解的近似值。,对方程组,做等价变换,从某一初值 x(0) 出发，我们可以构造序列,若,同时：,所以，序列收敛,与初值的选取无关,如令A=D-L-U，于是 x=D-1(L+U)x+D-1b,定义5.1：设G为n阶方阵，若Gk0，则称G为收敛矩阵,定理：,即矩阵G为收敛矩阵，当且仅当G的谱半径1,迭代法的收敛性,定理：迭代法X(m+1)=GX(m)+g 收敛的充分必要条件是迭代矩阵G为收敛矩阵，即G的谱半径 (G)1。,定理： 迭代法X(m+1)=GX(m)+g 的迭代矩阵G的某种范数 |G|q1,那么： 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).,Jacobi迭代,格式很简单：,1、输入系数矩阵A和向量b，和误差控制eps 2、x1=0,0,0 , x2=1,1,1 /赋初值 3、while( |A*x2-b|eps) x1=x2; for(i=0;i=n;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,Jacobi迭代算法,迭代矩阵,记,Jacobi迭代法的收敛性,易知，Jacobi迭代有,练习,讨论用雅可比(Jacobi)迭代法求解下列线性方程 组的收敛性。若收敛，求其解；若发散，作适当 变换使其收敛并求解。,G的谱半径(G)=4.01971. Jacobi迭代不收敛。,迭代矩阵为,G的特征值为：1=4.02408, 2=-2.01204 3.10115 i, 1=4.02408； 2,3=3.69668,将方程组变形，化为：,G的谱半径(G)= 0.308507 1.Jacobi迭代收敛。,此时迭代矩阵为,G的特征值分别为： 0.308507, - 0.154254 + 0.18304 i, -0.154254 - 0.18304 i,收敛条件,迭代格式收敛的充要条件是G的谱半径1。对于Jacobi迭代， 我们有一些保证收敛的充分条件,定理：若线性方程组AX=b的系数矩阵A满足下列条件之一，则Jacobi迭代收敛。, A为行对角占优阵, A为列对角占优阵, A满足, 若A对称正定阵，且2D-A也为对称正定阵，则Jacobi迭代收敛。,证明：, A为列对角占优阵，则AT为行对角占优阵，有,证毕,在Jacobi迭代中，使用最新计算出的分量值,GaussSeidel迭代,1、输入系数矩阵A和向量b，和误差控制eps 2、x2=1,1,1 /赋初值 3、while( |A*x2-b|eps) for(i=0;in;i+) for(j=0;ji;j+) x2i += Aij*x2j for(j=i+1;jn;j+) x2i += Aij*x2j x2i=-(x2i-bi)/Aii 4、输出解x2,Gauss-Siedel迭代算法,迭代矩阵,是否是原来的方程的解？,A=(D-L)-U,Gauss-Siedel迭代法的收敛性,收敛条件,迭代格式X=GX+g 对任意的初值X0和向量g，收敛的充要条件是G的谱半径 (G)1。 下面我们看一些充分条件：,定理：若线性方程组AX=b的系数矩阵A，, 若A对称正定阵，则Gauss-Seidel迭代收敛；, 若A对称正定阵，且2D- A也为对称正定阵，则Jacobi迭代收敛。,若A为行或列强对角占优阵，则Jacobi和Gauss-Seidel迭代都收敛；,证明：,设G的特征多项式为,，则,为对角占优阵，则,时,为对角占优阵,即,即,证毕,注：二种方法都存在收敛性问题。 有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时， Gauss-Seidel法也可能不收敛。,练习：判定用Jacobi和Gauss-Seidel迭代解方程组：AX=b 时的收敛情况，其中,1、Jacobi迭代,特征值为,2、GaussSeidel迭代,G的谱半径(G)=1.1181.Jacobi迭代不收敛。,G的谱半径(G)=0.51.Gauss-Seidel迭代收敛。,分别用Jacobi，Gauss-Seidel迭代法解方程组AX=b，其中,例题,1、预处理,2、格式：Jacobi迭代：,Gauss-Seidel迭代：,取初值,矩阵A按行严格对角占优，都收敛,m=1 x1=0.777778 x2=0.875000 x3=0.888889 error=0.888889 m=2 x1=0.973765 x2=0.972222 x3=0.975309 error=0.195988 m=3 x1=0.994170 x2=0.996721 x3=0.997085 error=0.024498 m=4 x1=0.999312 x2=0.999271 x3=0.999352 error=0.005142 m=5 x1=0.999847 x2=0.999914 x3=0.999924 error=0.000643 m=6 x1=0.999982 x2=0.999981 x3=0.999983 error=0.000135 m=7 x1=0.999996 x2=0.999998 x3=0.999998 error=0.000017 m=8 x1=1.00000 x2=1.00000 x3=1.00000 error=0.000004,Jacobi迭代,3、结果,m=1 x1=0.777778 x2=0.972222 x3=0.975309 error=0.975309 m=2 x1=0.994170 x2=0.999271 x3=0.999352 error=0.216392 m=3 x1=0.999847 x2=0.999981 x3=0.999983 error=0.005677 m=4 x1=0.999996 x2=1.00000 x3=1.00000 error=0.000149 m=5 x1=1.00000 x2=1.000000 x3=1.000000 error=0.000004,Gauss-Seidel迭代,练习,用雅可比(Jacobi)迭代法和高斯赛德尔(Gauss-Seidel) 迭代法求解线性方程组 ：,可以看作在前一步上加一个修正量。若在修正量前乘以一个 因子w ，则有,对GaussSeidel迭代格式,松弛迭代,写成分量形式，有,松弛迭代算法,1、输入系数矩阵A、向量b和松弛因子omega，和误差控制eps 2、x2=1,1,1 /赋初值 3、while( |A*x2-b|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,迭代矩阵,定理：,松弛迭代收敛,定理：,A对称正定，则松弛迭代收敛,是否是原来的方程的解？,SOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即选取=*,使(G)达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.41.6.,当松弛因子1时，称该算法为低松弛因子法；,当松弛因子1时，称该算法为超松弛因子法；,定理 若SOR方法收敛, 则02.,证 设SOR方法收敛, 则(G)1,所以 |det(G)| =|12 n|1,而 det(G) =det(D - L)-1 (1 - )D+U),=det(E - D - 1L) - 1det(1 - )E+D-1U),=(1-)n,于是 |1 - |1, 或 02,定理 用SOR法解方程组Ax=b，,证 设是G的任一特征值, y是对应的特征向量, 则,(1-)D+Uy= (D - L)y,于是 (1 - )(Dy,y)+(Uy,y)=(Dy,y) - (Ly,y),1）若A是对称正定矩阵, 则当02时收敛；,2）若矩阵A按行(列)严格对角占优, 则当01时收敛；,由于A=D - L - U是对称正定的, 所以D是正定矩阵, 且L=UT. 若记(Ly,y)=+i, 则有,(Dy,y)=0,(Uy,y)=(y,Ly)=(Ly,y),= - i,0(Ay,y)=(Dy,y) -(Ly,y) -(Uy,y) = - 2,所以,当02时,有,( - +)2 -( - )2= (2 - )(2 - ) = (2 - )(2 - )0,所以|21, 因此(G)1,即S0R方法收敛.,可得 =2/,设是B的任一特征值, y是对应的特征向量, 则,(L+U)y=Dy,于是 (Ly,y)+(Uy,y)=(Dy,y),当A对称正定时,即2 - 0,而 (2D - A)y,y)=(Dy,y)+(Ly,y)+(Uy,y) =+2,即,当A对称正定时,Jacobi迭代法收敛2D-A正定.,共轭梯度法,给定对称正定矩阵ARnn，求解方程组AX=b的共轭梯度法如下：,1.选定初值X(0) Rn, 设r(0)=d(0)=b-AX(0);,2. r(k+1)= r(k) - (k) A d(k); 其中,3. d(k+1)= r(k+1) + (k) d(k); 其中,4. X(k+1)= X(k)+ (k) d(k) ;,定理：设矩阵ARnn对称正定，X(k)为用共轭梯度法求解方程组AX=b所产生的迭代序列，并取条件数,那么：,1)用不超过n次迭代即可获得精确解；,2)对每次迭代结果的误差估计为：,其中范数|X|A=(AX , X),