第七章解线性方程组的迭代法精选PPT.ppt

第七章 解线性方程组的迭代法第1页，本讲稿共28页 求解线性方程组的迭代法与消去法不同，不能通过有限次算术运算求得方程组的精确解，而是逐次逼近它，直到满足精度要求为止。因此，凡是迭代法都有其收敛性与误差估计的问题。迭代法的迭代格式很多，这里我们只介绍最基本的且是常用的简单迭代法和塞德尔迭代法。7.1 简单迭代法及其收敛性简单迭代法及其收敛性一、引例：一、引例：首先用一个具体例子来说明简单迭代法的基本思想。第2页，本讲稿共28页 例例 解方程组第3页，本讲稿共28页用任意一组 近似值代入（7.2）式右端就可以得出一组新的近似值于是，对于给定的初值 ，是用迭代格式（7.3）可以产生一个近似解的序列下面我们取初值 ，由格式（7.3）迭代计算的结果列于表71中。7.37.3第4页，本讲稿共28页表表7 71 1K000010.30001.50002.000020.80001.76002.660030.91801.92602.864040.97161.97002.954050.98941.98972.982360.99631.99612.993870.99861.99862.997780.99951.99952.999290.99981.99982.9998第5页，本讲稿共28页当迭代次数增加时，迭代结果会越来越逼近方程组（7.1）的解，从这个简单的例子可以看出，用迭代法解线性方程组，基本思想是将联立线性方程组的求解归结为重复计算一组彼此独立的线性表达式，这就使问题得到了简化。但迭代法是否能达到化繁为简的目的，还要看它是否收敛于方程组的精确解。我们再观察一下例（7.1）。若分别从中分离出第6页，本讲稿共28页相应的建立迭代格式：若仍取初值 代入（7.4），逐次得出7.47.4第7页，本讲稿共28页继续算下去，其结果的绝对值越来越大，不可能逼近于任何常数，当然更不可能逼近于方程组（7.1）的解。我们称这样的迭代格式是发散发散的。二、简单迭代格式：二、简单迭代格式：下面我们对一般情形的方程组第8页，本讲稿共28页建立简单迭代格式简单迭代格式，并讨论其收敛条件。7.57.5设按一定方式从方程组（7.5）中分离出未知数将（7.5）改写成下列等价形式第9页，本讲稿共28页7.67.6或简写为7.77.7由此建立迭代格式7.87.8第10页，本讲稿共28页任意选一组初值 代入（7.8）进行迭代计算，就可得出一个近似解序列（7.8）收敛收敛。这时其极限值则称迭代格式显然就是（7.6）的解，从而也是方程组（7.5）的解。按格式（7.6）进行迭代以求式（7.5）解的方法称为简单简单迭代法迭代法。三、收敛条件：三、收敛条件：第11页，本讲稿共28页下面讨论其收敛条件：迭代序列在什么条件下收敛于方程组（7.5）的精确解。记根据（7.8）于是第12页，本讲稿共28页则有上式对一切成立，所以有于是于是有定理：定理：则迭代格式（7.8）对任意给定的初值均收敛。第13页，本讲稿共28页7.2 7.2 塞德尔（塞德尔（SeidelSeidel）迭代法）迭代法及收敛性及收敛性在实际计算中，通常采用一种稍加改进的迭代方案塞德尔迭代法。仍考察例（7.1）。设将近似值这样求出的新值 准确些，将他替换老值作进一步计算，将 代入（7.2）的右端得到一、引例：一、引例：第14页，本讲稿共28页出于同样的考虑，这种充分利用新值建立起来的迭代公式7.97.9称作塞德尔（塞德尔（SeidelSeidel）格式。仍取初值格式（7.9）的迭代结果如下：第15页，本讲稿共28页表表7 72 2K000010.30001.56002.684020.88041.94452.953930.98431.99232.993840.99781.99892.999150.99971.99992.9999第16页，本讲稿共28页由上述结果可明显看出，塞德尔的迭代格式（7.9）比简单迭代格式（7.4）收敛速度快。对一般形式的方程组（7.5）其塞德尔格式是7.107.10相当于简单迭代法的定理7.1，这里有二、塞德尔迭代格式：二、塞德尔迭代格式：三、收敛条件：三、收敛条件：第17页，本讲稿共28页定理：定理：（7.10）对任意给定的初值均收敛。一般地说，塞德尔的迭代格式（7.10）的收敛速度比简单迭代法的格式（7.8）快。但两种迭代法的收敛范围并不完全重合，而只是部分相交。有时候简单迭代法可能比塞德尔迭代法收敛还快些，甚至可以举出简单迭代法收敛而塞德尔迭代法发散的例子。第18页，本讲稿共28页所以在编制程序时，塞德尔格式（7.10）常常用下面的形式表示：第19页，本讲稿共28页第20页，本讲稿共28页7.3 7.3 高斯高斯塞德尔（塞德尔（Gauss-Gauss-SeidelSeidel）迭代法及其收敛条件）迭代法及其收敛条件一、高斯塞德尔迭代格式：一、高斯塞德尔迭代格式：通常求解的方程组形如（7.5），为要使用迭代法，需先将（7.5）化成便于迭代的形式（7.6），可供选择的方法很多，常用的一种是从（7.5）的第i个方程第21页，本讲稿共28页7.117.11方程组（7.11）具有（7.6）的形式，相应于（7.10）式，这里有7.127.12迭代格式（7.12）称为求解线性方程组（7.5）的高斯塞德尔（高斯塞德尔（Gauss-SeidelGauss-Seidel）格式）格式。第22页，本讲稿共28页二、收敛条件：二、收敛条件：则方程组（7.5）总可以化成等价的形式（7.11）。为了保证（7.12）的收敛性，需对（7.5）的系数矩阵提出某些要求。应用定理7.1可得定理：定理：则高斯塞德尔迭代格式（7.12）对任意给定的初值均收敛。第23页，本讲稿共28页最后需要指出，用迭代法求方程组（7.5）的近似解，究竟算到哪一步为止？一般常用条件7.137.13来终止计算（是事先给定的精度要求）。第24页，本讲稿共28页线性方程组的数值解法线性方程组的数值解法小结小结1 1 迭代法：迭代法：优点：优点：计算简单，编程容易。缺点：缺点：求解方程组时，要求系数矩阵具有某些特性。因此，随意构造一种迭代格式很可能不收敛，或者收敛太慢，使计算量太大而失去实际使用价值。2 2 消去法：消去法：优点：优点：可预估计算时间，理论上可求得精确解。缺点：缺点：对于较高阶的方程组，计算量太大。第25页，本讲稿共28页松弛法例题：给定线性方程组AX=b，其中求解AX=b。问取什么实数可使迭代收敛？什么可使迭代收敛最快？复习：p126定义6（矩阵的谱半径（B）为其最大特征根）及p132定理7（迭代矩阵谱半径小于1，收敛）第26页，本讲稿共28页第27页，本讲稿共28页1-44-11-11/41/21212(B)第28页，本讲稿共28页