解线性方程组的迭代法资料

1解线性方程组的迭代法Haha送给需要的学弟学妹摘要:因为理论的分析表明，求解病态的线性方程组是困难的，但是实际情况是否如此，需要我们来具体检验。系数矩阵H为Hilbert矩阵，是著名的病态问题。因而决定求解Hxb此线性方程组来验证上述问题。详细过程是通过用Gauss消去法、J迭代法、GS迭代法和SOR迭代法四种方法求解Hxb线性方程组。关键词：病态方程组、Gauss消去法、J迭代法、GS迭代法、SOR迭代法目录：一、问题背景介绍二、建立正确额数学模型三、求解模型的数学原理1、Gauss消去法求解原理2、Jacobi迭代法求解原理3、G-S迭代法求解原理4、SOR迭代法求解原理5、Jacobi和G-S两种迭代法收敛的充要条件四、计算过程（一）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迭代法的误差比较七、心得体会正文：一、问题背景介绍。理论的分析表明，求解病态的线性方程组是困难的。实际情况是否如此，会出现怎样的现象呢？二、建立正确的数学模型。考虑方程组Hxb的求解，其中系数矩阵H为Hilbert矩阵，,,1(),,,1,2,,1ijnnijHhhijnij这是一个著名的病态问题。通过首先给定解（为方便计算，笔者取x的各个分量等于1），再计算出右端,bHx这样Hxb的解就明确了，再用Gauss消去法、J迭代法、GS迭代法和SOR迭代法四种方法分别求解,Hxb将求解结果与给定解比较，而后求出上述四种方法的误差，得出哪种方法比较好。三、求解模型的数学原理。1、Gauss消去法求解原理对于Axb（A非奇异）求解时，可以先将A分解成一个下三角矩阵L和一个上三角矩阵U的乘积，即ALU，就可以通过2,,LybUxy(1.1)求解出x的值。接下来就具体讲讲如何将A分解成L和U，也就是Gauss消去法。欲把一个给定的矩阵A分解为一个下三角阵L与一个上三角阵U的乘积，最自然的做法便是通过一系列的初等变换，逐步将A约化为一个上三角阵，而又能保证这些变换的乘积是一个下三角阵。这可归结为：对于一个任意给定的向量,nxR找一个尽可能简单的下三角阵，使x经这一矩阵作用之后的第1k至第n个分量均为零。能够完成这一任务的最简单的下三角阵便是如下形式的初等下三角阵：,TkkkLIle其中1,0,,0,,,,Tkkknklll即1,,1111kkknkLll这种类型的初等下三角阵称作Gauss变换，而称向量kl为Gauss向量。对于一个给定的向量1,,,TnnxxxR我们有111,,,,,,.TkkkkkknknkLxxxxxlxxl由此立即可知，只要取,1,,,iikkxliknx便有1,,,0,,0.TkkLxxx当然，这里我们要求0.kx而后经过多次变换可以得到11,nnLLLAU(1.2)从而求出上三角阵U，而后通过11,nnLAULLLL求得下三角阵1.LUA(1.3)将(1.2)和(1.3)带入到(1.1)式中求出x的值即可。2、J迭代法求解原理考虑非奇异线性代数方程组.Axb令,ADLU(1.4)其中1122,,,,,ijnnAaDdiagaaa321313212,1000,0nnnnaaaLaaa121312321,00,00nnnnaaaaaUa那么(1.4)式和Axb合并后可以写成,xBxg其中11,.BDLUgDb(1.5)若给定初始向量000012,,,,Tnxxxx并代入(1.4)式右边，又可得到一个向量2x；一次类推，有1,1,2,.kkxBxgk(1.6)这就是所谓的Jacobi迭代法，其中B叫做Jacobi迭代法的迭代矩阵，g叫做Jacobi迭代法的常数项。3、GS迭代法求解原理注意到Jacobi迭代法中各分量的计算顺序是没有关系的，先算那个分量都一样。现在，假设不按Jacobi迭代格式，而是在计算kx的第一个分量用1kx的各个分量计算，但当计算kx的第二个分量2kx时，因1kx已经算出，用它代替11kx，其他分量仍用1kix。类似地，计算klx时，因11,,kklxx都已算出，用它们代替1111,,,kklxx其他分量仍用1kx的分量，于是有111,1,2,.kkkxDLxDUxgk(1.7)我们称这种迭代格式为Gauss-Seidel迭代法，简称为G-S迭代法。它的一个明显的好处是在编写程序是存储量减少了。如果1DL存在，G-S迭代法可以改写成111.kkxDLUxDLb(1.8)我们把11LDLU叫做G-S迭代法的迭代矩阵，而把1DLb叫做G-S迭代法的常数项。4、SOR迭代法求解原理我们知道，G-S迭代法的迭代格式为11111.kkkxDLxDUxDb现在令1,kkxxx则有1.kkxxx(1.9)这就是说，对G-S迭代法来说，1kx可以看作在向量kx上加上修正项x而得到的。若修正项的前面加上一个参数，便得到松弛迭代法的迭代格式111111,kkkkkxxxxDLxDUxDb(1.10)4用分量形式表示即为111111,inkkkkiiijjijjijjixxbxbxg(1.11)其中叫做松弛因子。当1时，相应的迭代法叫做超松弛迭代法；当1时，叫做低松弛迭代法；当1时，就是G-S迭代法。我们把超松弛迭代法简称为SOR迭代法。因为11IDL存在，所以(1.10)式可以改写为11,kkxLxDLb其中11LDLDU叫做松弛迭代法矩阵。而SOR迭代法收敛的充要条件是1.L(1.12)由(1.12)式知，SOR迭代法的谱半径依赖于，当然会问：能否适当选取使收敛速度最快？这就是选择最佳松弛因子的问题。经过相关计算可知，随着从0增加，L减少，直至2211optBB为Jacobi迭代矩阵(1.13)时，L达到极小2211;11optBLB(1.14)再增加时，L开始增加。因此，opt称为最佳松弛因子。5、Jacobi和G-S两种迭代法收敛的充要条件Jacobi迭代法和G-S迭代法两种迭代法有一个共同的特点，那就是新的近似解kx是已知近似解-1kx的线性函数，并且只与-1kx有关，即它们都可以表示成如下形式：-1.kkxMxg(1.15)事实上，对Jacobi迭代法，有11,.MDLUgDb对G-S迭代法，有11,.MDLUgDLb故要求出上述两个迭代法中kx有确定的解，且与-1kx相对误差较小，就必须说明kx用上述两种迭代法求解时收敛。下面就给出关于上述两种迭代法收敛的证明原理解方程组的单步线性定常迭代法(1.15)收敛的充分必要条件是其迭代矩阵M的谱半径小于1，即1.M(1.16)从上述的(1.16)可知，迭代序列收敛取决于迭代矩阵的谱半径，而与初始向量的选取和常数项无关。四、计算过程。方程组Hxb的求解，其中系数矩阵H为Hilbert矩阵，,,1(),,,1,2,,1ijnnijHhhijnij（一）求解Hxb，我们暂时选择系数矩阵H的维数6n，所以511111123456111111234567111111345678,111111456789111111567891011111167891011H令x的各分量都为1,，即111111,Tx根据Hxb得2.4501.5931.218.0.9960.8460.737bHx而后我们接下来就用Gauss消去法、J迭代法、GS迭代法和SOR迭代法四种迭代法求解111111234561111112.4502345671.5931111111.2183456781111110.9964567890.8461111110.737567891011111167891011x(1.17)的解x。1、Gauss消去法求解因为611111123456111111234567111111345678111111456789111111567891011111167891011H所以由(1.2)式知H分解的上三角矩阵333344455610.50.3330.250.20.1670.0830.0830.0750.0670.065.556108.333109.524109.92110,3.571107.143109.921102.268105.669101.43210U由(1.3)式求出H的下三角矩阵110.510.33311,0.250.91.510.20.81.714210.1670.7141.7862.7782.51LAU再通过(1.1)求出x的值13562.450.3680.033,2.063107.937101.43210yLb11.0001.0001.000.1.0001.0001.000xUy所以1.0001.0001.0001.0001.0001.000.Tx72、Jacobi迭代法求解将系数矩阵H用(1.4)方法分解成111111,,,,,,357911Ddiag010211034,1110456111105678111110678910L111110234561111045671110.6781108910100U所以由(1.5)式知1111110234563331302452755555034678.7777704568999999056781011111111110678910BDLU(1.18)在用Jacobi迭代法求解前，我们先计算迭代矩阵B的谱半径，B的特征值为84.3090.380.932,0.99711所以14.309116.iBmaxi(1.19)由(1.16)知迭代矩阵B发散，所以无法用Jacobi迭代法解x的值。3、G-S迭代法求解由(1.8)式知1100.50.3330.250.20.16700.750.250.2250.20.17900.1040.