《研究线性方程组迭代收敛速度.doc》由会员分享，可在线阅读，更多相关《研究线性方程组迭代收敛速度.doc（15页珍藏版）》请在三一办公上搜索。
1、研究解线性方程组迭代收敛速度一 实验目的科学研究与生产实践中许多问题都可归结为线性方程组的求解，高效求解线性方程组成为了许多科学与工程计算的核心迭代法就是用某种极限过程去逼近线性方程组精确解的方法，该方法具有对计算机的存贮单元需求少，程序计算简单，原始系数矩阵在计算过程中不变等优点，是求解大型稀疏矩阵方程组的重要方法。常用的迭代法有Jacobi迭代法、Gaussseidel迭代法、逐次超松驰法(SOR法)等。二 实验摘要由迭代法平均收敛速度与渐进收敛速度的关系引入近似估计法，即通过对迭代平均收敛速度取对数，然后利用Mathematica软件对其进行拟合，给出拟合函数，最终得到了Jacobi迭代
2、法、Gaussseidel法的平均收敛速度收敛到渐进收敛速度的近似收敛阶，以及逐次超松驰法(SOR法)的渐进收敛速度，且该法适用于其他迭代法收敛速度的估计。三 迭代法原理1 Jacobi迭代法(J法)设方程组，其中，为可逆矩阵，可分裂为其中，从而由得到，令 , ,由此可构造出迭代公式：令初始向量，即可得到迭代序列，从而逼近方程组的解这种方法称为Jacobi迭代法，其中称为Jacobi迭代矩阵。2. Gauss-Seidel迭代法(GS法)与Jacobi迭代法类似，将方程组中的系数矩阵分裂为,其中与前面相同。与Jacobi迭代法所不同的是，Gauss-Seidel迭代法将Jacobi迭代公式中的
3、 改为 从而可写成矩阵形式，若设存在，则，其中， ,，于是GaussSeidel迭代公式的矩阵形式为。其中，称为式（1）的GaussSeidel迭代法的迭代矩阵。注：由于Gauss-Seidel迭代充分利用了迭代过程的新信息，一般来说，它的迭代效果要比Jacobi迭代好。3.逐次超松弛方法（SOR法）根据Gauss-Seidel迭代法的迭代原理，我们将其修改为，即对和加入一个权因子，在这里我们称为迭代公式的松弛系数。令（GaussSeidel迭代法），则从而 ，所以将其写成分量的形式我们称该公式为基于GaussSeidel迭代下的超松弛迭代公式。注：1) 关于松弛系数的选取，我们有以下性质：（
4、i）.设方程组，其中，则解方程的SOR迭代法收敛的必要条件是；（ii）若为正定的对称矩阵，且，则方程组关于SOR迭代法是收敛的；（iii）若为正定的对称三对角矩阵，为Jacobi迭代矩阵，若的谱半径，记，则SOR法的最优松弛因子为且2) 由松弛系数的性质可知，通常只有当方程组的系数矩阵为正定的对称矩阵时我们才使用SOR法；3) 当松弛系数时，SOR法记为GS方法；4) 关于（iii）提到的谱半径定义为：假设为阶可逆矩阵，是它的个特征值，我们称为的谱半径。容易证明的谱半径是的所有诱导范数的下确界，即其中，矩阵的范数如：， 。下面我们就来讨论以上方法的迭代收敛速度，首先我们介绍收敛速度快慢的比较方
5、法。四 迭代法收敛速度的比较1.这两种迭代方法收敛性与是否成立有关，且收敛速度与的速度有关。当时， 趋于零矩阵的速度有赖于的大小。一般说来，越小，则趋于零矩阵的速度越快，反之就越慢。通常，当时，可以用正数的大小作为迭代法渐进收敛速度的度量。这时越大，迭代法的收敛速度愈大。2.平均收敛速度与渐进收敛速度之间的联系对于收敛的迭代法，称为平均收敛速度(它与所用的范数以及k有关)；称为渐进收敛速度。可以证明，因此当时假设成立下列渐近关系式 (常数)，为估计平均收敛速度收敛到渐进收敛速度的阶，当充分大时有如下近似形式：两边取对数得： 此式说明当k比较大时，与有近似的线性关系，而它们的斜率刚好为收敛阶P，
6、这样可以通过当k比较大时作出与 的拟合曲线来估计出P值。五 实验举例例1：考虑五阶方程组1. 其Jacobi迭代法的迭代矩阵为渐进收敛速度为：则迭代平均收敛速度（见表1）以及取对数后作最小二乘拟合图像（见图1）如下所示：表110.22314355-1.4999400020.29891850-1.2075843030.35473695-1.0363787040.35677909-1.0306385050.37710417-0.9752338260.37622879-0.9775578370.38679290-0.9498658680.38586107-0.95227789 图1即从而得到收敛阶为
7、 p=0.442264432. 该方程组的GaussSeidel迭代矩阵为：其渐进收敛速度为则迭代平均收敛速度 (见表2)以及取对数后作最小二乘拟合图像(见图2)如下所示：表2 10.22314355-1.4999400020.35667494-1.0309304030.52300533-0.6481636240.60617053-0.5005939350.65606964-0.4214883360.68933572-0.3720268770.71309721-0.3381375380.73091832-0.31345356图2即从而得到收敛阶为 p=0.58472143。注：在本例中，由于方
8、程组的系数矩阵严格对角占优，故前述两种迭代过程均收敛，依实际迭代过程：对Jacobi迭代有而GaussSeidel迭代有，即二者均收敛，但后者更快一些。这与收敛阶p=0.5850.442之间关系一致。例2：考虑方程组用SOR迭代公式可得取初试量为，迭代至第14次后的结果为当时 ，当时，可见取时的收敛速度比时的收敛速度要快。若要精确到小数后7位，当 (GS法)时需迭代31次，而当（SOR法）时只需迭代14次，它表明松弛因子选取的好坏，对收敛速度影响很大。六 程序设计及实验结果1. Jacobi迭代法，用mathematica编写程序如下：（i）计算迭代矩阵ClearEvaluateContext
9、*A=5,0,0,-3,-1,-1,4,0,0,-1,0,0,2,-1,0,-1,0,0,4,-2,0,0,0,-1,2;b=2,3,-1,0,-1;L=TableIfij,Ai,j,0,i,LengthA,j,LengthTransposeA;D1=TableIfi=j,Ai,j,0,i,LengthA,j,LengthTransposeA;U=TableIfi10-6,x1=BJ.x0+fJ;x0=x1;s=AppendTos,x1;k+s=Deletes,1,2;n=LengthssnNormsn-sn-1,2/Normsn,2运行结果为迭代次数为n=32最后一次迭代结果为最后两次的相对
10、误差（iii）计算平均收敛速度以及渐进收敛速度u=MaxEigenvaluesBJ;R=-Logu/NRk=Table-LogPowerNormMatrixPowerBJ,k,1/k/N,k,8;Rk=Table-LogPowerNormMatrixPowerBJ,k,1/k/N,k,8;date1=Tablei,Rki,LogRki,i,LengthRk;TableFormdate1,TableHeadings1,2,3,4,5,6,7,8,k,Rk,lnRk,TableSpacing2,4,TableAlignmentsCenter运行结果为渐进收敛速度为平均收敛速度如表所示10.2231
11、4355-1.4999400020.29891850-1.2075843030.35473695-1.0363787040.35677909-1.0306385050.37710417-0.9752338260.37622879-0.9775578370.38679290-0.9498658680.38586107-0.95227789（iv）对平均收敛速度取对数后作最小二乘拟合图像date2=TableLogRki,LogRki+1,i,LengthRk-1;line=Fitdate2,1,t,tP=Dline,tp1=ListPlotdate2,PlotStylePointSize0.01
12、8;p2=Plotline,t,MinLogRk-10-1,MaxLogRk+10-1,PlotRange-MinLogRk-10-2,MaxLogRk+10-2;Showp1,p2运行结果如图所示2. GaussSeidel迭代法，用mathematica编写程序如下：（i）计算迭代矩阵ClearEvaluateContext*A=5,0,0,-3,-1,-1,4,0,0,-1,0,0,2,-1,0,-1,0,0,4,-2,0,0,0,-1,2;b=2,3,-1,0,-1;L=TableIfij,Ai,j,0,i,LengthA,j,LengthTransposeA;D1=TableIfi=
13、j,Ai,j,0,i,LengthA,j,LengthTransposeA;U=TableIfi10-6,x1=BG.x0+fG;x0=x1;s=AppendTos,x1;k+s=Deletes,1,2;n=LengthssnNormsn-sn-1,2/Normsn,2运行结果为迭代次数为n=18最后一次迭代结果为最后两次的相对误差（iii）计算平均收敛速度以及渐进收敛速度u=MaxEigenvaluesBG;R=-Logu/NRk=Table-LogPowerNormMatrixPowerBG,k,1/k/N,k,8;date1=Tablei,Rki,LogRki,i,LengthRk;Ta
14、bleFormdate1,TableHeadings1,2,3,4,5,6,7,8,k,Rk,lnRk,TableSpacing2,4,TableAlignmentsCenter运行结果为渐进收敛速度为平均收敛速度如表所示10.22314355-1.4999400020.35667494-1.0309304030.52300533-0.6481636240.60617053-0.5005939350.65606964-0.4214883360.68933572-0.3720268770.71309721-0.3381375380.73091832-0.31345356（iv）对平均收敛速度取对
15、数后作最小二乘拟合图像如图所示date2=TableLogRki,LogRki+1,i,LengthRk-1;line=Fitdate2,1,t,tP=Dline,tp1=ListPlotdate2,PlotStylePointSize0.018;p2=Plotline,t,MinLogRk-10-1,MaxLogRk+10-1,PlotRange-MinLogRk-10-2,MaxLogRk+10-2;Showp1,p2运行结果如图所示3. SOR迭代法，用mathematica编写程序如下：（i）当 (GS法)时，计算其渐进收敛速度以及方程组的解精确到小数点后7位时的迭代次数、最后一次迭代
16、的结果、最后两次的相对误差。ClearEvaluateContext*A=4,3,0,3,4,-1,0,-1,4;b=24,30,-24;L=TableIfij,Ai,j,0,i,LengthA,j,LengthTransposeA;D1=TableIfi=j,Ai,j,0,i,LengthA,j,LengthTransposeA;U=TableIfi10-6,x1=BG.x0+fG;x0=x1;s=AppendTos,x1;k+s=Deletes,1,2;n=LengthssnNormsn-sn-1,2/Normsn,2运行结果为渐进收敛速度为迭代次数为n=31最后一次迭代结果为最后两次的相
17、对误差（ii）当（SOR法）时，计算其渐进收敛速度以及方程组的解精确到小数点后7位时的迭代次数、最后一次迭代的结果、最后两次的相对误差。ClearEvaluateContext*A=4,3,0,3,4,-1,0,-1,4;b=24,30,-24;L=TableIfij,Ai,j,0,i,LengthA,j,LengthTransposeA;D1=TableIfi=j,Ai,j,0,i,LengthA,j,LengthTransposeA;U=TableIfij,Ai,j,0,i,LengthA,j,LengthTransposeA;I1=IdentityMatrixLengthA;BJ=I1-
18、InverseD1.A/N;u=MaxEigenvaluesBJ;wb=2/(1+Sqrt1-u2)pw_:=Piecewisew u+Sqrtw2 u2-4(w-1)2/4,0wwb,w-1,wbw10-6,Dox1i=(1-wb)*x0i+wb*InverseD1ii*(bi-SumAij*x1j,j,1,i-1-SumAij*x0j,j,i+1,Lengthb),i,1,Lengthb; x0=x1; s=AppendTos,x1;k+s=Deletes,1,2;n=LengthssnNormsn-sn-1,2/Normsn,2运行结果为渐进收敛速度为迭代次数为n=14最后一次迭代结果为
19、最后两次的相对误差七 实验小结1对于一般的线性方程组，我们常采用Jacobi迭代法和Gauss-Seidel迭代法对其进行求解。通过例1，我们知道在一般情况下，Gauss-Seidel迭代法比Jacobi迭代法的收敛速度要快；2对于正定的对称矩阵，我们则可以采用SOR迭代法，由例2我们知道其收敛速度比Gauss-Seidel迭代法的收敛速度还要来的快；3对于SOR迭代法，优点是收敛速度快，缺点是适用范围窄，一般仅限于正定矩阵，特别的，当系数矩阵为对称的三对角矩阵时，最优松弛系数可选取为 而对于一般正定矩阵，的选取一般介于之间，我们可以通过取一系列值进行演算，然后进行比较，从中选择较有松弛系数。
