第五章 第一节 Jacobi迭代法

1、整理ppt第一节第一节 迭代法迭代法 Jacobi三三 、 迭代法的收敛性迭代法的收敛性 Jacobi一、引言一、引言二、二、 迭代格式的构造迭代格式的构造 四、小结四、小结整理ppt( )kX 迭代法是解线性代数方程组的另一类重要方法，特别迭代法是解线性代数方程组的另一类重要方法，特别适于求解系数矩阵为稀疏阵的大型线性代数方程组。它适于求解系数矩阵为稀疏阵的大型线性代数方程组。它 的的基本思想是，从任一初始向量基本思想是，从任一初始向量 出发，按某一规则，逐出发，按某一规则，逐次构造一个向量序列次构造一个向量序列 ，当，当 收敛于收敛于 时，使时，使 是所给方程组的解。于是，就有下列问题需要

2、计论：是所给方程组的解。于是，就有下列问题需要计论：(0)X( )kX*X*X (1) 构造迭代格式；构造迭代格式；(2) 收敛性及误差估计。收敛性及误差估计。一、引言一、引言整理ppt 任取任取 代入（代入（1.1）的右端，算得的结果记为）的右端，算得的结果记为 ，再以，再以 代入（代入（1.1）的右端，算得的结果记为）的右端，算得的结果记为 ，如此进行下去，便得到迭代格式如此进行下去，便得到迭代格式 (0)nXR(1)X(1)X(2)X 其中，其中， 是是 阶方阵，阶方阵， 是已知身量是已知身量, 是未知向量。是未知向量。 BnFX二、二、 迭代格式的构造迭代格式的构造 XBXF设所给方程

3、组为（1.1）整理ppt(1)( ),0,1,kkXBXF k (1.2) 显然，若显然，若 存在，则有存在，则有 ( )*limkkXX*XBXF(1.3)此格式称为此格式称为 迭代格式迭代格式，称，称 为为迭代矩阵迭代矩阵。 JacobiB由此迭代格式可构造出一个向量序列：012,kXXXX即即 为（为（1.1）的解。）的解。 *X整理ppt11,BMN FM b令令 ，即得（，即得（1.1）. 注注：若方程组由下面形式给出：若方程组由下面形式给出 1.4AXb 则需要把它改写成便于迭代的形则需要把它改写成便于迭代的形 式（式（1.1），），其其 方方 法是多种多样的，最一般的方法是将法是

4、多种多样的，最一般的方法是将 分分解为两个矩阵之差解为两个矩阵之差 A1.5AMN 其中矩阵其中矩阵M可逆，于是可逆，于是(1.4)成为成为 11XMNXM b(1.6)整理ppt 必须指出，必须指出，(1.5)中的中的 应是便于求逆的，应是便于求逆的， 的最简单选择是把它选为对角阵，通常，当的最简单选择是把它选为对角阵，通常，当 的的 对角线元素全不为对角线元素全不为 零时，就把零时，就把 选为选为 的对角的对角 线，于是线，于是MMAAMADE11XD EXD b 其中其中 是具有是具有 的对角线元素的对角阵的对角线元素的对角阵 ，而，而 在对角线上的元素为零。此时关系式在对角线上的元素为

5、零。此时关系式(1.6)成为成为DAE 式中，式中， 是简单的对角阵，是简单的对角阵， 它的对角线元它的对角线元素是素是 的元素的倒数。的元素的倒数。 1DD整理ppt例1、将方程组：123123123202324,812,231530 xxxxxxxxx:AXb化成便于迭代的形式.XBXF最直观的方法是，将方程组改写为：11232123312323240,20202011120,88823300151515xxxxxxxxxxxx 11223313501020411308822210155xxxxxx整理ppt三三 、 迭代法的收敛性迭代法的收敛性 Jacobi 若由迭代格式若由迭代格式所构

6、成的向量序列所构成的向量序列 收敛，则称收敛，则称 迭代格式迭代格式(1.2)收敛，或称收敛，或称 迭代法收敛。迭代法收敛。( )kXJacobi(1)( ),0,1,kkXBXF k (1.2)由关系式：(1)( )*,kkXBXFXBXF可得(1)*( )2(1)*(1)(0)*()()()kkkkXXB XXBXXBXX 整理ppt(0)X 定理定理 对任意右端向量对任意右端向量F和初始向量和初始向量 ， 迭代格式迭代格式(1.2)收敛于（收敛于（1.1）的解）的解 的充要条的充要条件是件是 *X( ) 1B 所以，为使所以，为使 Jacobi迭代法收敛，即要使迭代法收敛，即要使( )*

7、kXXk 0()kBk必要且只要0kB 。而 的( )1B充要条件是矩阵B的谱半径，故有. 由定理由定理1可以看出，迭代是否收敛只与迭代矩阵可以看出，迭代是否收敛只与迭代矩阵的谱半径有关，而迭代矩阵的谱半径有关，而迭代矩阵 是由系数矩阵是由系数矩阵 演变过演变过来的，所以迭代是否收敛是与系数矩阵来的，所以迭代是否收敛是与系数矩阵 以及演变的以及演变的方式有关，方式有关， 与与 右右 端向量和初始迭代向量的选择无关。端向量和初始迭代向量的选择无关。BAA整理ppt 在具在具 体问体问 题题 中中 ， 谱谱 半半 径径 是是 很很 难计算的，难计算的，但由于有但由于有 ，所，所 以可以以可以 用用

8、 来来 作作 为为 的的 一种估计。一种估计。 当当 时迭代格式一定收时迭代格式一定收敛，不敛，不 过这过这 只是只是 收敛收敛 的充分条件。的充分条件。( )BBB( )B1B 定理定理 2 若若 则迭代格式（则迭代格式（1.2）收敛于）收敛于（1.1）的解）的解 , 且有误差估计且有误差估计 1B *X( )*( )(1),1kkkBXXXXB（1.7）或或( )*(1)(0),1kkBXXXXB(1.8)整理ppt( )*(1)*()kkXXB XX证明证明 因为因为 ，所以迭代格式，所以迭代格式 （1.2）收敛。其次，由关系式）收敛。其次，由关系式( )1BB从而有从而有( )*( )

9、(1)(1).,kkkXXBBXX有有( )*(1)*.kkXXBXX(1)( )( )*.()kkkBXXXX( )(1)( )*.,kkkBXXBXX因此有因此有 ( )*( )(1),1kkkBXXXXB（1.7）整理ppt( )(1)(1)(2)1(1)(0)()(),kkkkkXXB XXBXX所以所以1( )(1)(1)(0).kkkXXBXX又从迭代格式又从迭代格式 (1)( ),0,1,kkXBXF k有 将此式代入（将此式代入（1.7）式，便有）式，便有 ( )*( )(1)11010111kkkkkBXXXXBBBXXBBXXB这就证明了定理2。整理ppt1max1niji

10、jBb或或时，时， 迭代法收敛。迭代法收敛。 Jacobi11max1nijjiBb依依 定定 理理 2 可知，当可知，当例2、用Jacobi迭代法解方程组123123123202324,812,231530 xxxxxxxxx:AXb整理ppt取 00,0,0TX,问Jacobi迭代法是否收敛？若收敛，需要迭代多少次，才能保证各分量的误差绝对值小于610？11223313501020411308822210155xxxxxx解：解：由例1知，此方程组可改写为 1112312123131231360,102051130,8822102155kkkkkkkkkkkkxxxxxxxxxxxx 其迭

11、代格式为整理ppt由于迭代矩阵：130102011088210155B的范数113B，所以用Jacobi迭代法解此方程组一定收敛。经一次迭代得： 1111123,63,252TTXxxx于是有， 102XX整理ppt由误差估计式( )*(1)(0),1kkBXXXXB可知，若使610kXX只须(1)(0)6101kBXXB 610101lnlnBkBXX亦只须 610101lnlnBXXkB整理ppt由于113B 102XX故611013ln2131ln3k所以，要保证各分量误差绝对值小于610，需要迭代14次。整理ppt 除了用定理除了用定理1、定理、定理2来判别迭代法的来判别迭代法的收敛性

12、外，还可根据方程组的系数矩阵的特收敛性外，还可根据方程组的系数矩阵的特点给出一些点给出一些收敛性的判别条件收敛性的判别条件。JacobiA 1) 若若 是严格对角占优阵（各行非对角元是严格对角占优阵（各行非对角元 绝对值之和小于对角元绝对值的矩阵），则绝对值之和小于对角元绝对值的矩阵），则 迭代法收敛。迭代法收敛。 设线性代数方程组的形式为设线性代数方程组的形式为 ,则则AX b2）若A为对称正定矩阵，1112121222122nnnnnnaaaaaaDAaaa也为对称正定矩阵，则 迭代法收敛；Jacobi整理ppt例例3 用用Jacobi迭代法解下列方程组（精确到迭代法解下列方程组（精确到

13、） 310 ( 其中其中 为为 A 的对角元组成的对角阵，所以的对角元组成的对角阵，所以 与与 只是非对角元的符号不同只是非对角元的符号不同 ）。）。 AJacobi2DA2DAADA若若 为对称正定阵而为对称正定阵而 为非正定阵，则为非正定阵，则迭代法不收敛。迭代法不收敛。12340.240.0880.0930.1590.040.08420 xxx解、显然，系数矩阵A是一个严格对角占优矩阵， 所以Jacobi迭代法收敛。整理ppt 先将方程组化成（先将方程组化成（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）整理ppt(0)(2,3,5) ,TX 因为在所要求的精度内因为在所要求的精度内 ，故停止计，故停止计 算算, 即为所求近似解即为所求近似解 。(3)(2)XX(3)X 从条件从条件 中，也可以看出，对任意中，也可以看出，对任意初始向量初始向量 ， 迭代法收敛。取迭代法收敛。取 0.081,B(0)XJa