解线性方程组迭代法

1、解线性方程组的迭代法Haha送给需要的学弟学妹摘要:因为理论的分析表明，求解病态的线性方程组是困难的，但是实际情况是否如此，需要我们来具体检验。系数矩阵H为Hilbert矩阵，是著名的病态问题。因而决定求解此线性方程组来验证上述问题。详细过程是通过用Gauss消去法、J迭代法、GS迭代法和SOR迭代法四种方法求解线性方程组。关键词：病态方程组、Gauss消去法、J迭代法、GS迭代法、SOR迭代法目录：一、问题背景介绍二、建立正确额数学模型三、求解模型的数学原理1、Gauss消去法求解原理2、Jacobi迭代法求解原理3、G-S迭代法求解原理4、SOR迭代法求解原理5、Jacobi和G-S两种迭

2、代法收敛的充要条件四、计算过程（一）Hilbert矩阵维数n=6时1、Gauss消去法求解2、Jacobi迭代法求解3、G-S迭代法求解4、SOR迭代法求解（二）Hilbert矩阵维数n=20、50和100时1、G-S迭代法求解图形2、SOR迭代法求解图形五、编写计算程序六、解释计算结果1、Gauss消去法误差分析2、G-S迭代法误差分析3、SOR迭代法误差分析G-S迭代法与SOR迭代法的误差比较七、心得体会正文：一、问题背景介绍。理论的分析表明，求解病态的线性方程组是困难的。实际情况是否如此，会出现怎样的现象呢？二、建立正确的数学模型。考虑方程组的求解，其中系数矩阵H为Hilbert矩阵，这

3、是一个著名的病态问题。通过首先给定解（为方便计算，笔者取x的各个分量等于1），再计算出右端这样的解就明确了，再用Gauss消去法、J迭代法、GS迭代法和SOR迭代法四种方法分别求解将求解结果与给定解比较，而后求出上述四种方法的误差，得出哪种方法比较好。三、求解模型的数学原理。1、Gauss消去法求解原理对于（A非奇异）求解时，可以先将A分解成一个下三角矩阵L和一个上三角矩阵U的乘积，即，就可以通过求解出的值。接下来就具体讲讲如何将A分解成L和U，也就是Gauss消去法。欲把一个给定的矩阵A分解为一个下三角阵L与一个上三角阵U的乘积，最自然的做法便是通过一系列的初等变换，逐步将A约化为一个上三角

4、阵，而又能保证这些变换的乘积是一个下三角阵。这可归结为：对于一个任意给定的向量找一个尽可能简单的下三角阵，使经这一矩阵作用之后的第至第个分量均为零。能够完成这一任务的最简单的下三角阵便是如下形式的初等下三角阵：其中即这种类型的初等下三角阵称作Gauss变换，而称向量为Gauss向量。对于一个给定的向量我们有由此立即可知，只要取便有当然，这里我们要求而后经过多次变换可以得到从而求出上三角阵U，而后通过求得下三角阵将(1.2)和(1.3)带入到(1.1)式中求出的值即可。2、J迭代法求解原理考虑非奇异线性代数方程组令其中那么(1.4)式和合并后可以写成其中若给定初始向量并代入(1.4)式右边，又可

5、得到一个向量；一次类推，有 这就是所谓的Jacobi迭代法，其中叫做Jacobi迭代法的迭代矩阵，叫做Jacobi迭代法的常数项。3、GS迭代法求解原理注意到Jacobi迭代法中各分量的计算顺序是没有关系的，先算那个分量都一样。现在，假设不按Jacobi迭代格式，而是在计算的第一个分量用的各个分量计算，但当计算的第二个分量时，因已经算出，用它代替，其他分量仍用。类似地，计算时，因都已算出，用它们代替其他分量仍用的分量，于是有我们称这种迭代格式为Gauss-Seidel迭代法，简称为G-S迭代法。它的一个明显的好处是在编写程序是存储量减少了。如果存在，G-S迭代法可以改写成我们把叫做G-S迭代法

6、的迭代矩阵，而把叫做G-S迭代法的常数项。4、SOR迭代法求解原理我们知道，G-S迭代法的迭代格式为现在令则有这就是说，对G-S迭代法来说，可以看作在向量上加上修正项而得到的。若修正项的前面加上一个参数，便得到松弛迭代法的迭代格式用分量形式表示即为 其中叫做松弛因子。当时，相应的迭代法叫做超松弛迭代法；当时，叫做低松弛迭代法；当时，就是G-S迭代法。我们把超松弛迭代法简称为SOR迭代法。因为存在，所以(1.10)式可以改写为 其中叫做松弛迭代法矩阵。而SOR迭代法收敛的充要条件是由(1.12)式知，SOR迭代法的谱半径依赖于，当然会问：能否适当选取使收敛速度最快？这就是选择最佳松弛因子的问题。

7、经过相关计算可知，随着从0增加，减少，直至时，达到极小再增加时，开始增加。因此，称为最佳松弛因子。5、Jacobi和G-S两种迭代法收敛的充要条件Jacobi迭代法和G-S迭代法两种迭代法有一个共同的特点，那就是新的近似解是已知近似解的线性函数，并且只与有关，即它们都可以表示成如下形式：事实上，对Jacobi迭代法，有对G-S迭代法，有故要求出上述两个迭代法中有确定的解，且与相对误差较小，就必须说明用上述两种迭代法求解时收敛。下面就给出关于上述两种迭代法收敛的证明原理解方程组的单步线性定常迭代法(1.15)收敛的充分必要条件是其迭代矩阵的谱半径小于1，即从上述的(1.16)可知，迭代序列收敛取

8、决于迭代矩阵的谱半径，而与初始向量的选取和常数项无关。四、计算过程。方程组的求解，其中系数矩阵H为Hilbert矩阵，（一）求解，我们暂时选择系数矩阵H的维数，所以令x的各分量都为1,，即根据得而后我们接下来就用Gauss消去法、J迭代法、GS迭代法和SOR迭代法四种迭代法求解的解x。1、Gauss消去法求解因为所以由(1.2)式知H分解的上三角矩阵由(1.3)式求出H的下三角矩阵再通过(1.1)求出x的值所以2、Jacobi迭代法求解将系数矩阵H用(1.4)方法分解成所以由(1.5)式知 在用Jacobi迭代法求解前，我们先计算迭代矩阵B的谱半径，B的特征值为所以 由(1.16)知迭代矩阵B

9、发散，所以无法用Jacobi迭代法解x的值。3、G-S迭代法求解由(1.8)式知通过计算得迭代矩阵的特征值为所以由(1.16)式知迭代矩阵收敛。令初始值 将其代入(1.8)式中，直到得 此时即为的解。4、SOR迭代法求解根据(1.18)和(1.19)知 再代入(1.13)式，得因为为一个虚数，从而说明其最佳松弛因子不存在，故取所以，其特征值为故的谱半径为由(1.12)知SOR迭代法收敛。令初始值 将其代入(1.10)式中，直到得 此时即为的解。（二）现在逐步增大问题的维数，因为由（一）可知，四种方法只能有Gauss消去法、G-S迭代法和SOR迭代法求解，故下面只列出这三种求解方法。1、当n=2

10、0时，Gauss消去法通过计算知道，此时上三角矩阵U的第十八行全部变成0了，从而导致结果无法计算，故此方法无法求解。因为n=20时，Gauss消去法求解无法算出结果，故以下计算不用此方法了。G-S迭代法SOR迭代法2、当n=50时G-S迭代法：SOR迭代法3、当n=100时G-S迭代法：SOR迭代法：五、编写计算程序。（一） 1、Gauss消去法求解 2、Jacobi迭代法求解 3、G-S迭代法求解部分程序在上面2（Jacobi迭代法求解）的里面 4、SOR迭代法求解部分程序在上面2（Jacobi迭代法求解）的里面 （二）Gauss消去法前面部分算法和（一）中的1（Gauss消去法）类似，此处

11、就不列出了。G-S迭代法此处程序基本上（一）中的3（G-S迭代法求解）基本类似，此处就不累赘了。SOR迭代法此处程序基本上（一）中的4（SOR迭代法求解）基本类似，此处就不累赘了。六、解释计算结果。（一）Gauss消去法误差分析：虽然保留三位小数的情况下，此方法求出的结果和标准结果是一样的，但是误差还是有的，下面给出用此方法求解保留十二位小数后的结果由此结果可知，误差是存在的，只是很小而已。G-S迭代法误差分析：用此方法计算的结果的相对误差：可见，此误差在允许范围。（二）G-S迭代法误差分析：当n=20时当n=50时当n=100时由上述图形可知，使用G-S迭代法求解方程组时，在绝对误差相同的情

12、况下，即矩阵H的维数越大，求出的结果的相对误差就越小。SOR迭代法误差分析当n=20时当n=50时当n=100时由上述图形可知，使用SOR迭代法求解方程组时，在绝对误差相同的情况下，即矩阵H的维数越大，求出的结果的相对误差就越小。两种迭代方法虽然都能计算出结果，但是由图可知，SOR迭代法的计算结果相对G-S迭代法计算的结果准确，但是迭代次数远远高于G-S迭代法（相同的绝对误差，在系数矩阵H维数n=6时，G-S迭代法迭代次数是997次，而SOR迭代法迭代次数却是5635次）。因此对于求解方程组，用G-S迭代法更为适合。七、心得体会通过本次课程设计，我更清楚地了解了如何使用Mathcad这个数学软件，并且能够灵活的运用。在做本次课程设计的过程中，又一次地认真的学习了Gauss消去法、Jacobi迭代法、G-S迭代法和SOR迭代法这四种求解线性方程组的方法，自己用更深