6.3.doc

解线性方程组的迭代法 SOR迭代法考虑Gauss-Seidel迭代法的改进-松弛法.以矩阵记号描述.在Gauss-Seidel迭代法中从x(k)到x(k+1)的增量是Lx(k+1)+Ux(k)+g- x(k)引进参数,并令x(k+1)= x(k)+(Lx(k+1)+Ux(k)+g- x(k)即x(k+1)=(1-)x(k)+(Lx(k+1)+Ux(k)+g)这就是松弛法的迭代公式(后一式可解释为x(k)与用它作一次Gauss-Seidel迭代的值加权平均).任给x(0)后,就可算x(1), x(2),直至x(k+1)-x(k) (试写出其分量形式).松弛法中参数叫做松弛因子,1时叫超松弛, =1就是Gauss-Seidel迭代.超松弛(SOR)在解一些微分方程离散化所得线性方程组时很有用.松弛法的x(k+1)与x(k)有如下线性关系x(k+1)=(I-L)-1(1-)I+U)x(k) + (I-L)-1gSOR迭代法的流程图为:在流程图中：A 是线性方程组的系数矩阵B 常数向量X 是初始值eps 判断条件是在SOR 迭代公式中程序控制条件 dM 是最大循环次数w 是SOR 迭代法的松弛因子，它的取值范围是 0w2;N是 方程组的阶数。迭代矩阵前面三个x(k+1)与x(k)都有线性关系,是x(k)的线性函数. J:x(k+1)=Bx(k)+gG-S:x(k+1)=(I-L)-1Ux(k)+(I-L)-1gSOR:x(k+1)=(I-L)-1(1-)I+U)x(k) + (I-L)-1g其中x(k)前的矩阵B,(I-L)-1U和(I-L)-1(1-)I+U)分别称为相应方法的迭代矩阵.一般地,一个迭代法两次近似值可表成x(k+1)=Mx(k)+f则称之为单点线性迭代,M则称为该方法的迭代矩阵.而迭代法是否收敛依赖于迭代矩阵的谱半径.6.2迭代法的收敛性 收敛性定理对任何初值x(0),迭代格式x(k+1)=Mx(k)+f确定的序列x(k)收敛并且极限与初值无关的充分必要条件是迭代矩阵的谱半径小于1,(M)1.证明: 必要性.设x(k)x*,则有x*=Mx*+f.令k=x(k)-x*,则k0,k+1=x(k+1)-x*=Mx(k)-Mx*=M(x(k)-x*)=Mk于是k =Mk-1= M2k-2=Mk0由0的任意性推出Mk0.因此, (M)1.充分性. 设(M)1,则(I-M)x=f解存在惟一,设为x*仍有k=Mk0,并且Mk0.因此,k0.例4. 讨论的收敛性.解: 迭代矩阵的特征多项式是可得特征值-0.1,0.33722813232690,-0.23722813232690,即迭代收敛.例5. 考察用迭代法解方程组的收敛性,其中 解: 特征方程为,特征根,即这说明用迭代法解此方程组不收敛. 误差估计如果迭代格式x(k+1)=Mx(k)+f的迭代矩阵的范数M1,则迭代收敛,并且有误差估计:x(k)-x*q/(1- q) x(k)-x(k-1)qk/(1- q) x(1)-x(0)证明. (M)M1,迭代收敛.又因x(k+1)-x(k)= M(x(k)-x(k-1)故x(k+1)-x(k)qx(k)-x(k-1)qkx(1)-x(0)又由x(k+1)-x*=Mx(k)-Mx*=M(x(k)-x*)x(k)-x*=x(k)-x(k+1)+x(k+1)-x*=x(k)-x(k+1)+ M(x(k)x*)得到x(k)-x*x(k+1)-x(k)+qx(k)x*于是x(k)-x*1/(1-q)x(k+1)-x(k)q/(1-q)x(k) -x(k-1)qk/(1-q)x(1)-x(0)证毕.如果用上面的结果事先估计迭代次数可能偏于保守,而在计算过程中用以估计当前迭代结果是否合用则比较贴切.以后我们会知道,理论上,从x(k+1)-x(k)= M(x(k)-x(k-1)可以估计(M). 对角占优方程组在第二章习题13讲过严格对角占优矩阵,指出它可逆.现在用以给出它的另一性质.设方程组Ax=b,A是严格对角占优矩阵,则J法,G-S法收敛证明.A是严格对角占优矩阵,则I-L-U也是.于是当1时I-L-U也是,因而可逆,于是1不可能有B=L+U的特征值,J法收敛.同样当1时I-L-U也是严格对角占优矩阵,1不可能有(I-L)-1U的特征值,G-S法收敛.应当指出A是严格对角占优矩阵可以放松为不可约对角占优矩阵,从略. 正定矩阵现在考虑SOR的应用对象正定的实对称矩阵和Hermite矩阵,给出若干结果而略去证明.1. 松弛法收敛的必要条件是022. 若A是实对称矩阵或Hermite矩阵,对角元素为正,则当00, k充分大时(M)Mk1/k(M)+左边不等式由(M)k= (M k)Mk即得.为得右边不等式可令B=M/(M)+)则(B)1,Bk0,因而k充分大时Bk1,Bk1/k1,即得右边不等式.二 实验部分本章实验内容：实验题目：Jacobi迭代法，Gauss-Saidel迭代法，SOR迭代法。实验内容：利用MATLAB ,编制求Ax=b的各迭代计算方法的程序。实验目的：了解迭代法的运用性，进行各迭代法数值结果的比较，并找出一个计算量小的，使迭代法加速收敛的迭代方法。编程要求：利用迭代法，初始向量为x(0)同时利用Jacobi法和Gauss-Seidel法来进行对比。利用SOR迭代法来进行对比。计算算法：Jacobi迭代法的算法为: Gauss-Saidel迭代法的算法为：SOR迭代法的算法为：实验例题： 条件：取实验例题：条件：取选择适当的松弛因子。程序：function X,Y=JacobiGS(A,b,p,p1,del,max)% A为线性方程组的系数矩阵，b为自由项，p和p1为两种迭代法的初始解，del为限制数，max为循环的限制次数。n=length(b);for k1=1:maxfor j=1:nY(j)=(b(j)-A(j,1:j-1)*p1(1:j-1)-A(j,j+1:n)*p1(j+1:n)/A(j,j); if j=1 X(1)=(b(1)-A(1,2:n)*p(2:n)/A(1,1); elseif j=n X(n)=(b(n)-A(n,1:n-1)*(X(1:n-1)/A(n,n); else X(j)=(b(j)-A(j,1:j-1)*(X(1:j-1)-A(j,j+1:n)*p(j+1:n)/A(j,j); end err=abs(norm(X-p); reerr=err/(norm(X)+eps); p=X; if (errdel)|(reerrdel) break end err1=abs(norm(Y-p1); reerr1=err1/(norm(Y)+eps); p1=Y; if (err1del)|(reerr1del) break end enddisp(sprintf(k X(k) Y(k);for i=0:ndisp(sprintf(%d %f %f,i,X(i+1),Y(i+1);end数值结果:X,Y=JacobiGS(A,b,p,p1,10(-5),7)k X(k) Y(k)0 3.000002 2.9990291 1.999999 2.0026212 0.999999 1.003131程序：function X=SOR(A,b,p,w,del,max)% A为线性方程组的系数矩阵，b为自由项,p为迭代初始值，w为松弛因子，del为限制数，max为循环的限制次数。n=length(b);for k=1:max for j=1:n if j=1 X(1)=p(j)+w*(b(1)-A(1,1:n)*p(1:n)/A(1,1); elseif j=n X(n)=p(n)+w*(b(n)-A(n,1:n-1)*(X(1:n-1)-A(n,n)*p(n)/A(n,n); else X(j)=p(j)+w*(b(j)-A(j,1:j-1)*(X(1:j-1)-A(j,j:n)*p(j:n)/A(j,j); end end err=abs(norm(X-p); reerr=err/(norm(X)+eps); p=X; if (errdel)|(reerrdel) break end enddisp(sprintf( k X(k);for i=0:n disp(sprintf( %d %f ,i,X(i+1);end数值结果: X=SOR(A,b,p,1.3,10(-5),11)k X(k)0 -0.999997 1 -1.000003 2 -1.000000 3 -0.999999总结：迭代法具有需要计算机的存贮单元较少,程序设计简单,原始系数矩阵在计算过程中始终不变等优点.迭代法在收敛性及收敛速度等方面存在问题.注:A必须满足一定的条件下才能运用以下三种迭代法之一。在Jacobi中不用产生的新数据信息，每次都要计算一次矩阵与向量的乘法，而在Gauss利用新产生的信息数据来计算矩阵与向量的乘法。在SOR中必须选择一个最佳的松弛因子，才能使收敛加速。经过计算可知Gauss-Seidel方法比Jacobi方法剩点计算量，也是Jacobi方法的改进。可是精确度底，计算量高，费时间，需要改进。SOR是进一步改进Gauss-Seidel而得到的比Jacobi，Gauss-Seidel方法收敛速度快，综合性强。改变松弛因子的取值范围来可以得到Jacobi，Gauss-Seidel方法。选择一个适当