数值分析线性方程组迭代法分享资料

1、 数值分析 4.1 Jacobi4.1 Jacobi迭代法迭代法 4.2 Gauss-Seidel4.2 Gauss-Seidel迭代法迭代法 4.3 SOR4.3 SOR（逐次超松弛迭代法）（逐次超松弛迭代法） 4.4 4.4 迭代法的收敛性迭代法的收敛性Ch4 Ch4 解线性方程组的迭代法解线性方程组的迭代法 数值分析 直接法得到的解是理论上准确的，但是我们可以看直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是得出，它们的计算量都是n3 3数量级，存储量为数量级，存储量为n2 2量级，量级，这在这在n比较小的时候还比较合适，但是对很多实际问比较小的时候还比较合适，但是对很

2、多实际问题，往往要我们求解很大型的矩阵，而且这些矩阵含题，往往要我们求解很大型的矩阵，而且这些矩阵含有大量的有大量的0 0元素。对于这类大型稀疏矩阵，在用直接元素。对于这类大型稀疏矩阵，在用直接法时就会耗费大量的时间和存储单元。因此，我们有法时就会耗费大量的时间和存储单元。因此，我们有必要引入一类新的方法：必要引入一类新的方法：迭代法迭代法. . 数值分析对方程组bAx 做等价变换gBxxbMNxMxNxbMxbxNMbAx11)(如：令NMA，则我们可以构造序列gxBxkk)()1( 若*)(xxkbAxgxBx* *同时：*)(*)()()1(xxBBxBxxxkkk*)()0(1xxBk

3、0kB所以，序列收敛与初值的选取无关 数值分析定义定义 （收敛矩阵）（收敛矩阵） 称称B为收敛矩阵为收敛矩阵.0kB定理：定理：即：矩阵即：矩阵B为收敛矩阵为收敛矩阵当且仅当当且仅当B的谱半径的谱半径11)( 0BBk由由BB )(知，若有某种范数知，若有某种范数1B则迭代收敛则迭代收敛. 数值分析4.1 Jacobi迭代法迭代法nnnnnnnbxaxabxaxa1111111)(1)(1)(1 11 ,111323121222212121111nnnnnnnnnnnnxaxabaxxaxaxabaxxaxabax 数值分析)(1)(1)(1 )(11 ,)(11)1()(1)(323)(12

4、1222)1(2)(1)(212111)1(1knnnknnnnknknnkkkknnkkxaxabaxxaxaxabaxxaxabax格式很简单：)(11)(11)()1(nijkjijijkjijiiikixaxabax 数值分析)(1)(1)(1 )1(11 )1(11)1(2)(1)(323)1(12122)1(21)(1)(21211)1(1nknnnknnnknknnkkkknnkkbxaxaaxbxaxaxaaxbxaxaax4.2 GaussSeidel 迭代法迭代法)(11)(11)1()1(inijkjijijkjijiikibxaxaax在在Jacobi迭代中，使用最新计

5、算出的分量值迭代中，使用最新计算出的分量值,即即 数值分析 迭代矩阵迭代矩阵ULDA记nnaaD0011000001121nnnaaaL000001112nnnaaaUA =-L-UD 数值分析bDgADIULDBJ111 , )( 易知，Jacobi迭代有bxULD)(bxULDx)(bDxULDx11)( 数值分析 迭代矩阵迭代矩阵)()()1(1)1(bUxLxDxkkkbDUxDxLDIkk1)(1)1(1)(bDLDIUxDLDIxkk111)(111)1()()(bLDUxLDxkk1)(1)1()()(bLDgULDBG11)( , )( 数值分析Jacobi iteration

6、Gauss-Seidel iteration计算x(k+1)时需要x(k)的所有分量，因此需开两组存储单元分别存放x(k)和x(k+1)计算xi(k+1)时只需要x(k)的i+1n个分量，因此x(k+1)的前i个分量可存贮在x(k)的前i个分量所占的存储单元，无需开两组存储单元. 数值分析9117180,71098Ab 迭代公式迭代公式:(1)( )( )123(1)(1)11(1)(1)111/9(7)1/8(7)1/9(8)kkkkkkkxxxxxxx例例 用用Gauss-seidel 迭代法解方程组迭代法解方程组 Ax=b)0(x给初始向量, 1 , 0k(1)(2)(3)(4)(0.7

7、778,0.9722,0.9753)(0.9942,0.9993,0.9994)(0.9999,0.9999,0.9999)(1.0000,1.0000,1.0000)xxxx计算结果计算结果: 数值分析4.3 逐次超松弛迭代法逐次超松弛迭代法(SOR)记记)()1()(kkkxxx则则)()()1(kkkxxx可以看作在前一步上加一个修正量。若在修正量前乘以一个因子可以看作在前一步上加一个修正量。若在修正量前乘以一个因子，有，有)()()1(kkkxxx)()()1(1)1(bUxLxDxkkk对对GaussSeidel迭代格式迭代格式)()()1()()1(kkkkxxxx)()(1)(1

8、)1(1)()1(kkkkkxbDUxDLxDxx)()1 (1)(1)1(1)()1(bDUxDLxDxxkkkk整理得整理得引入松弛因子引入松弛因子 数值分析)(1)1 ()()1 ()(1)1 ()(11 )(11)()1(2)(1)(323)(12122)(2)1(21)(1)(21211)(1)1(1nknnnknnnknknknnkkkkknnkkkbxaxaaxxbxaxaxaaxxbxaxaaxx写成分量形式，有写成分量形式，有 数值分析)()1 (1)(1)1(1)()1(bDUxDLxDxxkkkk迭代矩阵迭代矩阵bDxUDIxLDIkk1)(1)1(1)1()(bDLDI

9、xUDILDIxkk111)(111)1()()1()(bDLDIgUDILDIBSOR111111)( )1()( 数值分析 SOR方法收敛的快慢与松弛因子方法收敛的快慢与松弛因子 的选择有密切关系的选择有密切关系. . 但是如何选取最但是如何选取最佳松弛因子佳松弛因子, ,即选取即选取 = = * *, ,使使 ( (B ) )达到达到最小最小, ,是一个尚未很好解决的问题是一个尚未很好解决的问题. . 实实际上可采用试算的方法来确定较好的际上可采用试算的方法来确定较好的松弛因子松弛因子. . 经验上可取经验上可取1.41.4 1.6.1.6. 数值分析123123123110272 10

10、283542 10010100101200.10.210100011020.100.2100011150.20.201005 xxxJacobixxxxxxBIDA例：用迭代法求解解：1(0)(0)(2)(1)(9) (7.2,8.3,8.4)(0,0,0) ,(7.2,8.3,8.4)(9.71,10.70,11.5)(10.9994,11.9994,12.9992)(11,12,13) .TTTTTgD bxBxgxBxgxx(1)取代入迭代式，得x精确解为 数值分析123123123(0)1(0)(0)12311(1)(0)21321310272 10283542(0,0,0) ,11

11、(2)727.2000101011 (2)(7.200083)9.02001010 TxxxGaussSeidelxxxxxxxxxxbxxxbx（ ）（ ）（ ）例：用迭代法求解解：仍取代入迭代式，得(1)(1)123(5)11()7.20009.020042)11.644055(10.9989,11.9993,12.9996)(11,12,13) .Txxbxx（如此继续下去，精确解为 数值分析 GauseseidelJacobiGauseseidelJacobiGauseseidelJacobiJacobiGauseseidelJacobi上例计算结果表明，迭代法比迭代法效果好。事实上，

12、对有些问题迭代法确实比迭代法收敛得快，但也有迭代比迭代收敛得慢，甚至还有迭代收敛，迭代发散的情形。评价：与相比，只需一组工作单元存放近似解。 数值分析4.4 4.4 迭代法的收敛性迭代法的收敛性定义定义 设有矩阵序列设有矩阵序列 及及 ，如果，如果 则称则称 收敛于收敛于 ，记为，记为( )( )()kkijn nAa), 2 , 1(knnijaA)(ijkijkaa)(lim),2, 1,(nji)(kAAAAkklim 数值分析一些关于收敛的定义及定理一些关于收敛的定义及定理定理定理定理定理 设设 ，则，则 其中其中 为为 的谱半径。的谱半径。定理定理( (迭代法基本定理）迭代法基本定理

13、）设有方程组设有方程组对于任意初始向量对于任意初始向量 及任意及任意 ，解此方程组的迭，解此方程组的迭 代法代法 收敛的收敛的充要条件充要条件是是0|lim)()(AAAAkkk)(knnRB0limkkB1)(B)(BBAxb)0(xffBXxkk)()1(1)(B 数值分析定义定义 称称 为迭代法的收敛速度为迭代法的收敛速度. .定理定理( (迭代法收敛的充分条件迭代法收敛的充分条件) ) 如果方程组如果方程组的迭代公式为的迭代公式为 ，且迭代矩阵的某一，且迭代矩阵的某一种范数种范数 ，则，则 1 1）迭代法收敛，即对任取）迭代法收敛，即对任取 ，有，有 2 2） 3 3）bAx )(ln

14、)(BBR1| qB)0(xfBxxkk)()1(*)(limxxkk|1|)1()()(*kkkxxqqxx|1|)0()1()(*xxqqxxkk实际计算中实际计算中,通常利用通常利用) 1()(kkxx作为控制迭代的终止条件作为控制迭代的终止条件.不过要注意不过要注意,当当 时时, 较大较大,尽管尽管 已非常小已非常小,但误差向量的模但误差向量的模 可能很大可能很大,迭代法收敛将是缓慢的迭代法收敛将是缓慢的.1qqq1) 1()(kkxx)(*kxx 数值分析特别的特别的,Jacobi 迭代法收敛迭代法收敛G-S迭代法收敛迭代法收敛SOR迭代法收敛迭代法收敛1)(JB1)(GSB1)(S

15、ORB 数值分析 定理定理 若若SORSOR方法收敛方法收敛, , 则则00 2.2. 证证 设SORSOR方法收敛, 则(B )1,所以 |det(B )| =|12 n|1而 det(B ) =det(D-L)-1 (1-)D+U) =det(E-D-1L)-1 det(1-)E+D-1U) =(1-)n于是 |1-|1, 或 02 数值分析 定理定理 设设A是是对称正定对称正定矩阵矩阵, , 00 22时时, ,则解方程组则解方程组 Ax=b的的SORSOR方法收敛方法收敛. . 数值分析注意的问题（2）Jacobi迭代法和迭代法和Gauss-Seidel迭代法迭代法的收敛性没有必然的联

16、系：的收敛性没有必然的联系：即当即当Gauss-Seidel法收敛时，法收敛时，Jacobi法可能不收法可能不收敛；敛；而而Jacobi法收敛时，法收敛时， Gauss-Seidel法也可能不收法也可能不收敛。敛。（1）Jacobi迭代法和迭代法和Gauss-Seidel迭代法的迭代法的迭代矩阵不同：迭代矩阵不同：BJ =D-1(L+U), B G-S = (D-L) -1U 数值分析12312312321121xxxxxxxxx例如用用Jacobi迭代法求解不收敛，但用迭代法求解不收敛，但用 G-S法收敛。法收敛。1231231232212223xxxxxxxxx用用Jacobi迭代法求解收

17、敛，迭代法求解收敛，但用但用 G-S法不收敛。法不收敛。022022101 ,023220002JG SBB BJ的特征值为0，0，0， 而BGS的特征值为 0，2，2 数值分析12123231221251xxxxxxx系数矩阵系数矩阵A是正定矩阵，因此用是正定矩阵，因此用 Gauss-Seidel法收敛法收敛1102102025D A 不是正定矩阵，因此用不是正定矩阵，因此用 JacobiJacobi迭代法不收敛迭代法不收敛A是有正对角元的是有正对角元的n阶对称矩阵阶对称矩阵 数值分析.111211111112 321并考察求解的收敛性迭代法的计算公式，迭代法和分别写出，对于方程组Seide

18、lGaussJacobixxx练练习习1 1 . 2/ ) 1( , 1 , 2/ ) 1( )(2)(1) 1(3)(3)(1) 1(2)(3)(2) 1(1kkkkkkkkkxxxxxxxxx式为解：雅可比迭代计算公 数值分析010100111011101)( 2121212121211ULD雅可比迭代矩阵为. 1)(, 0,11|252545321212121BiBI . 2/ ) 1( , 1 , 2/ ) 1( ) 1(2) 1(1) 1(3)(3) 1(1) 1(2)(3)(2) 1(1kkkkkkkkkxxxxxxxxx赛德尔迭代计算公式为高斯 数值分析赛德尔迭代矩阵为高斯212121212121212121110000010110 00100 010110 211112 )(ULD. 1)(, 02121Bi.