计算方法和软件应用5.docVIP

三、逐次超松弛迭代法 对于大规模的稀疏方程组，迭代和迭代是两种基本迭代方法，并且代表了两种典型的算法：平行算法和串行算法.不足之处是在很多情况下这两种算法的收敛速度较慢，需要进行改进，常见的做法是加入参数（松弛因子）使算法起到加速作用。常见的算法有算法（逐次超松弛法），及算法（同步迭代法）。这两种算法一个是在迭代法基础上发展得到的，一个是在迭代基础上发展得到的。 1、算法（逐次超松弛法） 由上面的讨论可知，迭代的格式是 现在在上式的每个方程中假如，得到 其一般式是： 上式可以将看成是由加上一个校正量得到。如果在这个校正量前乘上一个因子，则得到： (4.9) 或等价于 上式右端的括号内正是迭代格式，只是多了个系数，注意到前的系数为，因此迭代法可以看成是迭代法与计算值的一种算术加权平均。如果因子选取的比较合适，它可以起到加速收敛的作用。当=1时，迭代法就是迭代。如果采用矩阵分裂记号(4.9)可以得到： 从而得到算法矩阵表示的紧凑形式 (4.10) 其中迭代矩阵= 称具有上述迭代格式的迭代法为逐次超松弛法,简称迭代,其中参数称为松弛因子. 注: (1)可以证明, 迭代收敛的必要条件是,当时称为亚松弛迭代,而当 时,称为超松弛迭代. 证明:因迭代的迭代矩阵为 = 设矩阵的个特征值为,则 == = = = 注意到的定义,有 ≤＜1 (2) 算法收敛的充分必要条件是.当方程组的系数阵是对称正定时,对的任意算法都收敛,但收敛的速度并不一样,此时我们可以找到最佳的松弛因子 而对一般的线性方程组则要通过反复试验才能求得比较满意的，选得恰当的才能使方法起到加速作用，一般的取值在1与1.7之间. (3) 用简单的编制算法程序如下： 建立文件名，内容为： %using SOR iterative to solve linear algebraic equations ax=b function [y,r,n]=sor(a,b,x0,w,e,N) D=diag(diag(a));U=-triu(a,1);L=-tril(a,-1); G=(D-w*L)\((1-w)*D+w*U);f=w*((D-w*L)\b); y=G*x0+f;n=1; while (norm(y-x0,inf)=e nN) x0=y;y=G*x0+f;n=n+1; end n; y; r=norm(y-x0,inf); 为了找到最佳的松弛因子，可以用下面的循环语句： %Finding better relaxation factor w for i=1:15 w=0.95+i/20;N=8; [y,r,n]=sor(a,b,x0,w,1e-15,N); h(i)=r; end [s,j]=min(h); w=0.95+j/20 给定 a=[78 -2 -12 -14;-2 86 -4 6;-12 -4 72 -8;-14 6 -8 74];b=[76;8;112;68]; x0=[0;0;0;0];e=1e-8试用求解线性方程组ax=b，并给出最佳的松弛因子. 解 a=[78 -2 -12 -14;-2 86 -4 6;-12 -4 72 -8;-14 6 -8 74]; b=[76;8;112;68];x0=[0;0;0;0];e=1e-8; for i=1:15 w=0.95+i/20;N=8; [y,r,n]=sor(a,b,x0,w,1e-15,N); h(i)=r; end [s,j]=min(h); w=0.95+j/20 w = 1.0500 [x,r,n]=sor(a,b,x0,w,e,20) x = 1.5350 0.1220 1.9752 1.4130 r = 2.8979e-009 n = 8 2、算法简介 在迭代中,新向量的分量计算次序是从第1个到第个逐个进行的,即 , 在迭代过程中也可以将这个过程倒过来,即从第个到第1个进行计算,其形式为 , 如果将这两种迭代过程交叉使用,即对 称这种迭代法为迭代法，因相应的迭代矩阵较繁，这里不再写出。 设有线性方程组 试写出迭代，迭代，迭代格式 解：迭代格式 迭代格式