Jacobi迭代法PPT课件

1、( )kX 迭代法是解线性代数方程组的另一类重要方法，特别迭代法是解线性代数方程组的另一类重要方法，特别适于求解系数矩阵为稀疏阵的大型线性代数方程组。它适于求解系数矩阵为稀疏阵的大型线性代数方程组。它 的的基本思想是，从任一初始向量基本思想是，从任一初始向量 出发，按某一规则，逐出发，按某一规则，逐次构造一个向量序列次构造一个向量序列 ，当，当 收敛于收敛于 时，使时，使 是所给方程组的解。于是，就有下列问题需要计论：是所给方程组的解。于是，就有下列问题需要计论：(0)X( )kX*X*X (1) 构造迭代格式；构造迭代格式；(2) 收敛性及误差估计。收敛性及误差估计。一、引言一、引言第1页/

2、共22页 任取任取 代入（代入（1.1）的右端，算得的结果记为）的右端，算得的结果记为 ，再以，再以 代入（代入（1.1）的右端，算得的结果记为）的右端，算得的结果记为 ，如此进行下去，如此进行下去，便得到迭代格式便得到迭代格式 (0)nXR(1)X(1)X(2)X 其中，其中， 是是 阶方阵，阶方阵， 是已知身量是已知身量, 是未知向量。是未知向量。 BnFX二、二、 迭代格式的构造迭代格式的构造 XBXF设所给方程组为（1.1）第2页/共22页(1)( ),0,1,kkXBXF k (1.2) 显然，若显然，若 存在，则有存在，则有 ( )*limkkXX*XBXF(1.3)此格式称为此格

3、式称为 迭代格式迭代格式，称，称 为为迭代矩阵迭代矩阵。 JacobiB由此迭代格式可构造出一个向量序列：012,kXXXX即即 为（为（1.1）的解。）的解。 *X第3页/共22页11,BMN FM b令令 ，即得（，即得（1.1）. 注注：若方程组由下面形式给出：若方程组由下面形式给出 1.4AXb 则需要把它改写成便于迭代的形则需要把它改写成便于迭代的形 式（式（1.1），），其其 方方 法是多种多样的，最一般的方法是将法是多种多样的，最一般的方法是将 分分解为两个矩阵之差解为两个矩阵之差 A1.5AMN 其中矩阵其中矩阵M可逆，于是可逆，于是(1.4)成为成为 11XMNXM b(1.

4、6)第4页/共22页 必须指出，必须指出，(1.5)中的中的 应是便于求逆的，应是便于求逆的， 的最简单选择是把它选为对角阵，通常，当的最简单选择是把它选为对角阵，通常，当 的的 对角线元素全不为对角线元素全不为 零时，就把零时，就把 选为选为 的对角的对角 线，于是线，于是MMAAMADE11XD EXD b 其中其中 是具有是具有 的对角线元素的对角阵的对角线元素的对角阵 ，而，而 在对角线上的元素为零。此时关系式在对角线上的元素为零。此时关系式(1.6)成为成为DAE 式中，式中， 是简单的对角阵，是简单的对角阵， 它的对角线元它的对角线元素是素是 的元素的倒数。的元素的倒数。 1DD第

5、5页/共22页例1、将方程组：123123123202324,812,231530 xxxxxxxxx:AXb化成便于迭代的形式.XBXF最直观的方法是，将方程组改写为：11232123312323240,20202011120,88823300151515xxxxxxxxxxxx 11223313501020411308822210155xxxxxx第6页/共22页三三 、 迭代法的收敛性迭代法的收敛性 Jacobi 若由迭代格式若由迭代格式所构成的向量序列所构成的向量序列 收敛，则称收敛，则称 迭代格式迭代格式(1.2)收敛，或称收敛，或称 迭代法收敛。迭代法收敛。( )kXJacobi(

6、1)( ),0,1,kkXBXF k (1.2)由关系式：(1)( )*,kkXBXFXBXF可得(1)*( )2(1)*(1)(0)*()()()kkkkXXB XXBXXBXX 第7页/共22页(0)X 定理定理 对任意右端向量对任意右端向量F和初始向量和初始向量 ， 迭代格式迭代格式(1.2)收敛于（收敛于（1.1）的解）的解 的充要条的充要条件是件是 *X( ) 1B 所以，为使所以，为使 Jacobi迭代法收敛，即要使迭代法收敛，即要使( )*kXXk 0()kBk必要且只要0kB 。而 的( )1B充要条件是矩阵B的谱半径，故有. 由定理由定理1可以看出，迭代是否收敛只与迭代矩阵可

7、以看出，迭代是否收敛只与迭代矩阵的谱半径有关，而迭代矩阵的谱半径有关，而迭代矩阵 是由系数矩阵是由系数矩阵 演变过演变过来的，所以迭代是否收敛是与系数矩阵来的，所以迭代是否收敛是与系数矩阵 以及演变的以及演变的方式有关，方式有关， 与与 右右 端向量和初始迭代向量的选择无关。端向量和初始迭代向量的选择无关。BAA第8页/共22页 在具在具 体问体问 题题 中中 ， 谱谱 半半 径径 是是 很很 难计算的，难计算的，但由于有但由于有 ，所，所 以可以以可以 用用 来来 作作 为为 的的 一种估计。一种估计。 当当 时迭代格式一定收时迭代格式一定收敛，不敛，不 过这过这 只是只是 收敛收敛 的充分

8、条件。的充分条件。( )BBB( )B1B 定理定理 2 若若 则迭代格式（则迭代格式（1.2）收敛于）收敛于（1.1）的解）的解 , 且有误差估计且有误差估计 1B *X( )*( )(1),1kkkBXXXXB（1.7）或或( )*(1)(0),1kkBXXXXB(1.8)第9页/共22页( )*(1)*()kkXXB XX证明证明 因为因为 ，所以迭代格式，所以迭代格式 （1.2）收敛。其次，由关系式）收敛。其次，由关系式( )1BB从而有从而有( )*( )(1)(1).,kkkXXBBXX有有( )*(1)*.kkXXBXX(1)( )( )*.()kkkBXXXX( )(1)( )

9、*.,kkkBXXBXX因此有因此有 ( )*( )(1),1kkkBXXXXB（1.7）第10页/共22页( )(1)(1)(2)1(1)(0)()(),kkkkkXXB XXBXX所以所以1( )(1)(1)(0).kkkXXBXX又从迭代格式又从迭代格式 (1)( ),0,1,kkXBXF k有 将此式代入（将此式代入（1.7）式，便有）式，便有 ( )*( )(1)11010111kkkkkBXXXXBBBXXBBXXB这就证明了定理2。第11页/共22页1max1nijijBb或或时，时， 迭代法收敛。迭代法收敛。 Jacobi11max1nijjiBb依依 定定 理理 2 可知，当

10、可知，当例2、用Jacobi迭代法解方程组123123123202324,812,231530 xxxxxxxxx:AXb第12页/共22页取 00,0,0TX,问Jacobi迭代法是否收敛？若收敛，需要迭代多少次，才能保证各分量的误差绝对值小于610？11223313501020411308822210155xxxxxx解：解：由例1知，此方程组可改写为 1112312123131231360,102051130,8822102155kkkkkkkkkkkkxxxxxxxxxxxx 其迭代格式为第13页/共22页由于迭代矩阵：130102011088210155B的范数113B，所以用Jac

11、obi迭代法解此方程组一定收敛。经一次迭代得： 1111123,63,252TTXxxx于是有， 102XX第14页/共22页由误差估计式( )*(1)(0),1kkBXXXXB可知，若使610kXX只须(1)(0)6101kBXXB 610101lnlnBkBXX亦只须 610101lnlnBXXkB第15页/共22页由于113B 102XX故611013ln2131ln3k所以，要保证各分量误差绝对值小于610，需要迭代14次。第16页/共22页 除了用定理除了用定理1、定理、定理2来判别迭代法的来判别迭代法的收敛性外，还可根据方程组的系数矩阵的特收敛性外，还可根据方程组的系数矩阵的特点给

12、出一些点给出一些收敛性的判别条件收敛性的判别条件。JacobiA 1) 若若 是严格对角占优阵（各行非对角元是严格对角占优阵（各行非对角元 绝对值之和小于对角元绝对值的矩阵），则绝对值之和小于对角元绝对值的矩阵），则 迭代法收敛。迭代法收敛。 设线性代数方程组的形式为设线性代数方程组的形式为 ,则则AX b2）若A为对称正定矩阵，1112121222122nnnnnnaaaaaaDAaaa也为对称正定矩阵，则 迭代法收敛；Jacobi第17页/共22页例例3 用用Jacobi迭代法解下列方程组（精确到迭代法解下列方程组（精确到 ） 310 ( 其中其中 为为 A 的对角元组成的对角阵，所以的对

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