第五章 第一节 Jacobi迭代法

第一节迭代法Jacobi三、迭代法的收敛性Jacobi一、引言二、迭代格式的构造四、小结()kX迭代法是解线性代数方程组的另一类重要方法，特别适于求解系数矩阵为稀疏阵的大型线性代数方程组。它的基本思想是，从任一初始向量出发，按某一规则，逐次构造一个向量序列，当收敛于时，使是所给方程组的解。于是，就有下列问题需要计论：(0)X()kX*X*X(1)构造迭代格式；(2)收敛性及误差估计。一、引言任取代入（1.1）的右端，算得的结果记为，再以代入（1.1）的右端，算得的结果记为，如此进行下去，便得到迭代格式(0)nXR(1)X(1)X(2)X其中，是阶方阵，是已知身量,是未知向量。BnFX二、迭代格式的构造XBXF设所给方程组为（1.1）(1)(),0,1,kkXBXFk(1.2)显然，若存在，则有()*limkkXX**XBXF(1.3)此格式称为迭代格式，称为迭代矩阵。JacobiB由此迭代格式可构造出一个向量序列：012,,,,,kXXXX即为（1.1）的解。*X11,BMNFMb令，即得（1.1）.注：若方程组由下面形式给出1.4AXb则需要把它改写成便于迭代的形式（1.1），其方法是多种多样的，最一般的方法是将分解为两个矩阵之差A1.5AMN其中矩阵M可逆，于是(1.4)成为11XMNXMb(1.6)必须指出，(1.5)中的应是便于求逆的，的最简单选择是把它选为对角阵，通常，当的对角线元素全不为零时，就把选为的对角线，于是MMAAMADE11XDEXDb其中是具有的对角线元素的对角阵，而在对角线上的元素为零。此时关系式(1.6)成为DAE式中，是简单的对角阵，它的对角线元素是的元素的倒数。1DD例1、将方程组：123123123202324,812,231530xxxxxxxxx:AXb化成便于迭代的形式.XBXF最直观的方法是，将方程组改写为：11232123312323240,20202011120,88823300151515xxxxxxxxxxxx11223313501020411308822210155xxxxxx三、迭代法的收敛性Jacobi若由迭代格式所构成的向量序列收敛，则称迭代格式(1.2)收敛，或称迭代法收敛。()kXJacobi(1)(),0,1,kkXBXFk(1.2)由关系式：(1)()**,kkXBXFXBXF可得(1)*()2(1)*(1)(0)*()()()kkkkXXBXXBXXBXX(0)X定理对任意右端向量F和初始向量，迭代格式(1.2)收敛于（1.1）的解的充要条件是*X()1B所以，为使Jacobi迭代法收敛，即要使()*kXXk0()kBk必要且只要0kB。而的()1B充要条件是矩阵B的谱半径，故有.由定理1可以看出，迭代是否收敛只与迭代矩阵的谱半径有关，而迭代矩阵是由系数矩阵演变过来的，所以迭代是否收敛是与系数矩阵以及演变的方式有关，与右端向量和初始迭代向量的选择无关。BAA在具体问题中，谱半径是很难计算的，但由于有，所以可以用来作为的一种估计。当时迭代格式一定收敛，不过这只是收敛的充分条件。()BBB()B1B定理2若则迭代格式（1.2）收敛于（1.1）的解,且有误差估计1B*X()*()(1),1kkkBXXXXB（1.7）或()*(1)(0),1kkBXXXXB(1.8)()*(1)*()kkXXBXX证明因为，所以迭代格式（1.2）收敛。其次，由关系式()1BB从而有()*()(1)(1).,kkkXXBBXX有()*(1)*.kkXXBXX(1)()()*.()kkkBXXXX()(1)()*..,kkkBXXBXX因此有()*()(1),1kkkBXXXXB（1.7）()(1)(1)(2)1(1)(0)()(),kkkkkXXBXXBXX所以1()(1)(1)(0)..kkkXXBXX又从迭代格式(1)(),0,1,kkXBXFk有将此式代入（1.7）式，便有()*()(1)11010111kkkkkBXXXXBBBXXBBXXB这就证明了定理2。1max1nijijBb或时，迭代法收敛。Jacobi11max1nijjiBb依定理2可知，当例2、用Jacobi迭代法解方程组123123123202324,812,231530xxxxxxxxx:AXb取00,0,0TX,问Jacobi迭代法是否收敛？若收敛，需要迭代多少次，才能保证各分量的误差绝对值小于610？11223313501020411308822210155xxxxxx解：由例1知，此方程组可改写为1112312123131231360,102051130,8822102155kkkkkkkkkkkkxxxxxxxxxxxx其迭代格式为由于迭代矩阵：130102011088210155B的范数113B，所以用Jacobi迭代法解此方程组一定收敛。经一次迭代得：1111123,,63,,252TTXxxx于是有，102XX由误差估计式()*(1)(0),1kkBXXXXB可知，若使610kXX只须(1)(0)6101kBXXB610101lnlnBkBXX亦只须610101lnlnBXXkB由于113B102XX故611013ln2131ln3k所以，要保证各分量误差绝对值小于610，需要迭代14次。除了用定理1、定理2来判别迭代法的收敛性外，还可根据方程组的系数矩阵的特点给出一些收敛性的判别条件。JacobiA1)若是严格对角占优阵（各行非对角元绝对值之和小于对角元绝对值的矩阵），则迭代法收敛。设线性代数方程组的形式为,则AXb2）若A为对称正定矩阵，1112121222122nnnnnnaaaaaaDAaaa也为对称正定矩阵，则迭代法收敛；Jacobi例3用Jacobi迭代法解下列方程组（精确到）310(其中为A的对角元组成的对角阵，所以与只是非对角元的符号不同）。AJacobi2DA2DAADA若为对称正定阵而为非正定阵，则迭代法不收敛。12340.240.0880.0930.1590.040.08420xxx解、显然，系数矩阵A是一个严格对角占优矩阵，所以Jacobi迭代法收敛。先将方程组化成（1.1）的形式。以4，3，4分别除三个方程两边得12310.060.0220.0310.0530.010.0215xxx其迭代矩阵为00.060.020.0300.050.010.020B11112213300.060.0220.0300.0530.010.0205kkkkkkxxxxxx从而有Jacobi迭代格式：（1.9）(0)(2,3,5),TX因为在所要求的精度内，故停止计算,即为所求近似解。(3)(2)XX(3)X从条件中，也可以看出，对任意初始向量，迭代法收敛。取0.081,B(0)XJacobi则利用Jacobi迭代格式（1.9），可得(1)(1.92,3.19,5.04)TX(2)(1.909,3.194,5.045)TX(3)(1.909,3.194,5.045)TX四、小结(1)(),0,1,kkXBXFk(1.2)2、迭代法的收敛性Jacobi1、迭代格式的构造