线性方程组的迭代解法及收敛分析

河南科技学院2015届本科毕业论文论文题目：线性方程组的三种迭代解法及收敛分析学生姓名：韦成州所在院系：数学科学学院所学专业：信息与计算科学导师姓名：李巧萍完成时间：2015年5月20日线性方程组的三种迭代解法及收敛分析摘要对于线性方程组的迭代解法，本文重点讨论雅可比迭代法，高斯塞德尔迭代法和超松弛迭代法三种迭代解法。主要讨论内容有：首先，写出三种迭代解法的基本思想，基本算法及收敛条件；其次，针对这三种迭代解法进行举例分析，通过MATLAB程序，求得三种迭代法各自的迭代次数、每次迭代的结果及误差；最后，在满足设定精度的情况下，对每个迭代方法所用的迭代次数进行通过分析比较，得出了在选择适当的松弛因子后，三种迭代法的收敛速度：超松弛迭代法＞高斯塞德尔迭代法＞雅可比迭代法，对于方程组Axb，迭代法的收敛性只与系数矩阵A有关，而与右端项b无关。同时，本文又对算法设计，收敛速度的判定等问题提出了改进意见。关键词：MATLAB,数学模型,迭代解法,收敛,线性方程组ThreekindsofsolutionsofsystemsoflinearequationsiterativemethodandconvergenceanalysisAbstractForiterativesolutionoflinearequations,thisarticlefocusesontheJacobiiterationmethod,gaussseideliterationmethodandoverrelaxationiterationmethodofthreekindsofiterativemethod.Maindiscussion:firstofall,writedownthreeiterativemethod,thebasicideaofthebasicalgorithmandconvergencecondition;Secondly,inviewofthethreekindsofiterativesolutionmethodsforanalysis,throughtheMATLABprogram,getthreeiterativemethodrespectivenumberofiterations,theresultsofeachiterationanderror;Finally,inthecaseofmeetthesettingprecision,foreachiterationmethodtocarrythroughanalysisandcomparison,thenumberofiterationsusedinselectingtheappropriaterelaxationfactorisobtained,theconvergencerateofthethreetypesofiterativemethod:overrelaxationiterationmethod,gaussseideliterationmethod,Jacobiiterationmethodforthesystemofequations,theconvergenceofiterativemethodisonlyrelatedtothecoefficientmatrix,andhasnothingtodowiththerightitems.Andatthesametime,thispaper,thealgorithmdesign,andtheconvergencerateofdecisionproblems,suchasimprovementopinionsareputforward.Keywords：MATLAB,Mathematicalmodel,Iterativemethod,ConvergenceSystemoflinearequations目录1引言..........................................................................................................12迭代法的基本思想.................................................................................13三种迭代法的思想，算法及收敛条件.................................................13.1雅可比迭代法...............................................................................13.1.1雅可比迭代法的思想与算法..............................................13.1.2雅格比迭代法的收敛条件..................................................23.2高斯塞德尔迭代法.......................................................................23.2.1高斯塞德尔迭代法的思想和算法......................................23.2.2高斯塞德尔迭代法的收敛条件..........................................33.3超松弛迭代法................................................................................33.3.1松弛法思想和算法..............................................................33.3.2超松弛迭代法的收敛条件..................................................44数学模型..................................................................................................44.1雅可比迭代法求解........................................................................54.2高斯赛德尔方法求解....................................................................74.3超松弛迭代法求解......................................................................105小结........................................................................................................13致谢...........................................................................................................15参考文献...............................................................................................1511引言在实际生活中，存在着大量求解线性方程组的问题。这些方程组具有数据量大，系数矩阵稀疏，在一定精度保证下，只需要求解近似解等特点。线性方程组的迭代解法特别适合于这类方程组的求解，它具有程序设计简单，需要计算机的贮存单元少等特点，但也有收敛性与收敛速度问题。因此，研究线性方程组的迭代解法及收敛分析对于解决实际问题具有非常重要的作用。2迭代法的基本思想将方程组Axb写成等价的形式xMxb，定一个初值向量0x,可以得到迭代公式:1,0,1,kkxMxgk这样构造一个向量序列{}kx，使其极限向量kx是方程组的精确解。3三种迭代法的思想，算法及收敛条件3.1雅可比迭代法3.1.1雅可比迭代法的思想与算法1基本思想：如果方程组bAx的系数矩阵()ijnxnAa，满足条件0(1,2,...,)ijain。把A分解成ADLU。其中1122(,,...)nnDdiagaaa，L为主对角线为零的下三角矩阵，U为主对角线为零的上三角矩阵，于是方程组bAx等价于()DLUXb整理得：11()xDLUxDb由此可得迭代公式：()1()1()(0,1,2,...)kkxDLUxDbk其中(0)x任选，由上式所表示的迭代法就是雅可比迭代法，其中1()jMDLU就是该迭代法的迭代矩阵，其分量式为：2111,1~,0,1,nkkiiijjjiijixbaxinka2基本算法：步一.取初始向量'[00000]x,精度6erle；步二.计算初始误差，并进入while循环，运算迭代公式步三.如果误差er小于精度，则输出x，否则，转步二3.1.2雅格比迭代法的收敛条件1.雅可比迭代法收敛的充要条件是该迭代法的迭代矩阵的谱半径()jM小于1。2.若系数矩阵A为对称正定矩阵，且对角元0(1,2,...),iiain则有雅可比迭代法收敛的充要条件是A及(2)DA都是正定矩阵。3.若方程组bAx的系数矩阵A是主对角线按行(或按列)严格占优矩阵,即1,1,2,...nijijiijaain则有雅可比迭代法收敛。3.2高斯塞德尔迭代法3.2.1高斯塞德尔迭代法的思想和算法1基本思想：高斯塞德尔迭代法是在雅可比迭代法的基础上得到的迭代算法,主要不同是在计算(1)kix时,前面的(1)i个值(1)(1)(1)121,,...,kkkixxx已经算出,用这些新值代替上次迭代的旧值()()()121,,...,kkkixxx,用矩阵表示为(1)1(1)1()1(0,1,2,...)kkkxDLxDUxDbk两边左乘D,整理得(1)()()(0,1,2,...)kkDLxUxbk于是可得迭代公式为:3(1)1()1()()(0,1,2,...)kkxDLUxDLbk其中迭代矩阵GSM为:1()GSMDLU，其分量式为：,2,1,0,~11,,11111002010knixaxabaxxxxxijnijkjijkjijiiikiTn2基本算法：步一.取初始向量'[00000]x;精度6erle；步二.计算初始误差er，并进入while循环，运算迭代公式(1)1()1()()(0,1,2,...)kkxDLUxDLbk步三.如果误差er小于精度，则输出x，否则，转步二3.2.2高斯塞德尔迭代法的收敛条件1高斯塞德尔迭代法收敛的充要条件是该迭代法的迭代矩阵的谱半径()GSM小于12若系数矩阵A为对称正定矩阵，且对角元0(1,2,...),iiain则有高斯塞德尔迭代法收敛的充要条件是A是正定矩阵。3若方程组bAx的系数矩阵A是主对角线按行(或按列)严格占优矩阵,即1,1,2,...nijijiijaain则有高斯塞德尔迭代法收敛。3.3超松弛迭代法3.3.1松弛法思想和算法1基本思想：超松弛迭代法一种加速收敛的新的迭代算法,与高斯塞德尔迭代法相比,它明显地提高了收敛的速度，具体来说就是采用加权平均的算