3e基本的矩阵迭代法

1第三章线性方程组的迭代解法计算方法——基本的矩阵分裂迭代法2本讲内容Jacobi迭代算法Gauss-Seidel迭代算法SOR迭代算法收敛性分析矩阵分裂迭代法的典型代表3Jacobi迭代考虑线性方程组Ax=b其中A=(aij)nn非奇异，且对角线元素全不为0。1122diag(,,,)nnDaaa211,100,0nnnaLaa将A分裂成A=D-L-U，其中1211,000nnnaaUa4Jacobi迭代(1)1()1()kkxDLUxDbk=0,1,2,…令M=D，N=L+U，可得雅可比(Jacobi)迭代方法Jacobi迭代迭代矩阵记为：1()JDLU分量形式：1(1)11inkiiijjijjiijjixbaxaxai=1,2,…,n，k=0,1,2,…5开始³输出迭代失败标志结束,b,n,,ijiN读入a方程阶数1k1max?iiinxy?kN11,2,,iikkyxin12,,,nyy输出y=≠图3-3雅可比迭代法框图11,2,,niijjiiijjibaxayin6Gauss-Seidel迭代在计算时，如果用代替，则可能会得到更好的收敛效果。(1)kix(1)(1)11,,kkixx()()11,,kkixx(1)()()()11122133111(1)()()()22211233222(1)()()()1122,11kkkknnkkkknnkkkknnnnnnnnnxbaxaxaxaxbaxaxaxaxbaxaxaxa(1)()()()11122133111(1)(1)()()22211233222(1)(1)(1)(1)1122,11kkkknnkkkknnkkkknnnnnnnnnxbaxaxaxaxbaxaxaxaxbaxaxaxa7Gauss-Seidel迭代(1)1(1)()kkkxDbLxUx写成矩阵形式:此迭代方法称为高斯-塞德尔(Gauss-Seidel)迭代法k=0,1,2,…11(1)()kkxDLUxDLb可得1GDLU迭代矩阵记为：8SOR迭代为了得到更好的收敛效果，可在修正项前乘以一个松弛因子，于是可得迭代格式在G-S迭代中(1)(1)(1)()()11,11,11,kkkkkiiiiiiiiiinniixbaxaxaxaxa1(1)()1()inkkiijjijjiijjikibaxaxax(1)1(1)()1()inkkiijjijjiijkiijikbaxaaxxx9SOR迭代(1)()1(1)()()kkkkkxxDbLxUxDx11(1)()(1)kkxDLDUxDLb写成矩阵形式:可得——SOR(SuccessiveOver-Relaxation)迭代方法1(1)LDLDU迭代矩阵记为：SOR的优点：通过选取合适的，可获得更快的收敛速度SOR的缺点：最优参数的选取比较困难10Jacobi、G-S、SORJacobi迭代(1)1()1()kkxDLUxDb1(1)()()11inkkkiiijjijjiijjixbaxaxaSOR迭代11(1)()(1)kkxDLDUxDLb1(1)()(1)()1inkkkkiiiijjijjiijjixxbaxaxa11,(1)MDLNDUG-S迭代11(1)()kkxDLUxDLb1(1)(1)()11inkkkiiijjijjiijjixbaxaxa,MDLNU,MDNLU11举例例：分别用Jacobi、G-S、SOR迭代解线性方程组123210113180125xxx取初始向量x(0)=(0,0,0)，迭代过程中小数点后保留4位。解：Jacobi迭代：(1)()12(1)()()213(1)()32128352kkkkkkkxxxxxxx迭代可得：x(1)=(0.5000,2.6667,-2.5000)Tx(21)=(2.0000,3.0000,-1.0000)T2*31x12举例G-S迭代：(1)()12(1)(1)()213(1)(1)32128352kkkkkkkxxxxxxxx(1)=(0.5000,2.8333,-1.0833)Tx(9)=(2.0000,3.0000,-1.0000)T迭代可得：13举例SOR迭代：(1)()()()1112(1)()(1)()()22123(1)()(1)()3323122833522kkkkkkkkkkkkkxxxxxxxxxxxxx取=1.1，迭代可得x(1)=(0.5500,3.1350,-1.0257)Tx(7)=(2.0000,3.0000,-1.0000)T如何确定SOR迭代中的最优松弛因子是一件很困难的事1415收敛性分析(1)()kkxBxf定理：对任意初始向量x(0)，上述迭代格式收敛的充要条件是()1B定理：若存在算子范数||·||，使得||B||1，对任意的初始向量x(0)，上述迭代格式收敛。16Jacobi迭代收敛的充要条件(J)1G-S迭代收敛的充要条件(G)1SOR迭代收敛的充要条件(L)1收敛性(A)A收敛性定理Jacobi迭代收敛的充分条件||J||1G-S迭代收敛的充分条件||G||1SOR迭代收敛的充分条件||L||1谱半径1(A)maxiin1718收敛性分析(1)()kkxBxfB=M-1N定理：若存在算子范数||·||，使得||B||=q1，则证明：P112()(0)kkxxqxx(1)迭代法收敛(2)(3)(4)()()(1)1kkkqxxxxq()(1)(0)1kkqxxxxq19系数矩阵法---对角占优矩阵且至少有一个不等式严格成立，则称A为弱对角占优；若所有不等式都严格成立，则称A为严格对角占优。(i=1,2,...,n)定义：设ARnn，若1,||||niiijjjiaa20Jacobi、G-S收敛性引理3-2：若A严格对角占优，则A非奇异定理3-25：若A严格对角占优，则Jacobi迭代和G-S迭代均收敛定理：若A对称，且对角线元素均大于0，则(1)Jacobi迭代收敛的充要条件是A与2D-A均正定；(2)G-S迭代收敛的充要条件是A正定。21SOR收敛性定理：若SOR迭代收敛，则02。SOR收敛的必要条件定理：若A对称正定，且02，则SOR迭代收敛。SOR收敛的充分条件定理：若A严格对角占优，且01，则SOR迭代收敛。22举例例：设，给出Jacobi和G-S收敛的充要条件111aaAaaaa解：A对称，且对角线元素均大于0，故(1)Jacobi收敛的充要条件是A和2D-A均正定(2)G-S收敛的充要条件是A正定A正定2212310,10,(1)(12)0DDaDaa0.51a2D-A正定2212310,10,(1)(12)0DDaDaa0.50.5aJacobi收敛的充要条件是：-0.5a0.5G-S收敛的充要条件是：-0.5a123举例解法二：Jacobi的迭代矩阵为设是J的特征值，则由det(I-J)=0可得111aaJaaaa(-a)2(+2a)=0Jacobi收敛的充要条件是(J)1||1，即-0.5a0.524作业1.教材页，习题2.教材页，习题