第七章 解线性方程组的迭代法

第七章解线性方程组的迭代法第一页，共二十八页，2022年，8月28日※

求解线性方程组的迭代法与消去法不同，不能通过有限次算术运算求得方程组的精确解，而是逐次逼近它，直到满足精度要求为止。因此，凡是迭代法都有其收敛性与误差估计的问题。迭代法的迭代格式很多，这里我们只介绍最基本的且是常用的简单迭代法和塞德尔迭代法。§7.1简单迭代法及其收敛性一、引例：首先用一个具体例子来说明简单迭代法的基本思想。第二页，共二十八页，2022年，8月28日[例]解方程组第三页，共二十八页，2022年，8月28日用任意一组近似值代入（7.2）式右端就可以得出一组新的近似值于是，对于给定的初值，是用迭代格式（7.3）可以产生一个近似解的序列下面我们取初值，由格式（7.3）迭代计算的结果列于表7－1中。——7.3第四页，共二十八页，2022年，8月28日表7－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第五页，共二十八页，2022年，8月28日当迭代次数增加时，迭代结果会越来越逼近方程组（7.1）的解，从这个简单的例子可以看出，用迭代法解线性方程组，基本思想是将联立线性方程组的求解归结为重复计算一组彼此独立的线性表达式，这就使问题得到了简化。但迭代法是否能达到化繁为简的目的，还要看它是否收敛于方程组的精确解。我们再观察一下例（7.1）。若分别从中分离出第六页，共二十八页，2022年，8月28日相应的建立迭代格式：若仍取初值代入（7.4），逐次得出——7.4第七页，共二十八页，2022年，8月28日继续算下去，其结果的绝对值越来越大，不可能逼近于任何常数，当然更不可能逼近于方程组（7.1）的解。我们称这样的迭代格式是发散的。二、简单迭代格式：下面我们对一般情形的方程组第八页，共二十八页，2022年，8月28日建立简单迭代格式，并讨论其收敛条件。——7.5设按一定方式从方程组（7.5）中分离出未知数将（7.5）改写成下列等价形式第九页，共二十八页，2022年，8月28日——7.6或简写为——7.7由此建立迭代格式——7.8第十页，共二十八页，2022年，8月28日任意选一组初值代入（7.8）进行迭代计算，就可得出一个近似解序列（7.8）收敛。这时其极限值则称迭代格式显然就是（7.6）的解，从而也是方程组（7.5）的解。按格式（7.6）进行迭代以求式（7.5）解的方法称为简单迭代法。三、收敛条件：第十一页，共二十八页，2022年，8月28日下面讨论其收敛条件：迭代序列在什么条件下收敛于方程组（7.5）的精确解。记根据（7.8）于是第十二页，共二十八页，2022年，8月28日则有上式对一切成立，所以有于是于是有★定理：则迭代格式（7.8）对任意给定的初值均收敛。第十三页，共二十八页，2022年，8月28日§7.2塞德尔（Seidel）迭代法及收敛性在实际计算中，通常采用一种稍加改进的迭代方案——塞德尔迭代法。仍考察例（7.1）。设将近似值这样求出的新值准确些，将他替换老值作进一步计算，将代入（7.2）的右端得到一、引例：第十四页，共二十八页，2022年，8月28日出于同样的考虑，这种充分利用新值建立起来的迭代公式——7.9称作塞德尔（Seidel）格式。仍取初值格式（7.9）的迭代结果如下：第十五页，共二十八页，2022年，8月28日表7－2K000010.30001.56002.684020.88041.94452.953930.98431.99232.993840.99781.99892.999150.99971.99992.9999第十六页，共二十八页，2022年，8月28日由上述结果可明显看出，塞德尔的迭代格式（7.9）比简单迭代格式（7.4）收敛速度快。对一般形式的方程组（7.5）其塞德尔格式是——7.10相当于简单迭代法的定理7.1，这里有二、塞德尔迭代格式：三、收敛条件：第十七页，共二十八页，2022年，8月28日★定理：（7.10）对任意给定的初值均收敛。

一般地说，塞德尔的迭代格式（7.10）的收敛速度比简单迭代法的格式（7.8）快。但两种迭代法的收敛范围并不完全重合，而只是部分相交。有时候简单迭代法可能比塞德尔迭代法收敛还快些，甚至可以举出简单迭代法收敛而塞德尔迭代法发散的例子。第十八页，共二十八页，2022年，8月28日所以在编制程序时，塞德尔格式（7.10）常常用下面的形式表示：第十九页，共二十八页，2022年，8月28日第二十页，共二十八页，2022年，8月28日§7.3高斯—塞德尔（Gauss-Seidel）迭代法及其收敛条件一、高斯－塞德尔迭代格式：通常求解的方程组形如（7.5），为要使用迭代法，需先将（7.5）化成便于迭代的形式（7.6），可供选择的方法很多，常用的一种是从（7.5）的第i个方程第二十一页，共二十八页，2022年，8月28日——7.11方程组（7.11）具有（7.6）的形式，相应于（7.10）式，这里有——7.12迭代格式（7.12）称为求解线性方程组（7.5）的高斯－塞德尔（Gauss-Seidel）格式。第二十二页，共二十八页，2022年，8月28日二、收敛条件：则方程组（7.5）总可以化成等价的形式（7.11）。为了保证（7.12）的收敛性，需对（7.5）的系数矩阵提出某些要求。应用定理7.1可得★定理：则高斯－塞德尔迭代格式（7.12）对任意给定的初值均收敛。第二十三页，共二十八页，2022年，8月28日最后需要指出，用迭代法求方程组（7.5）的近似解，究竟算到哪一步为止？一般常用条件——7.13来终止计算（ε是事先给定的精度要求）。第二十四页，共二十八页，2022年，8月28日§线性方程组的数值解法小结№1迭代法：优点：计算简单，编程容易。缺点：求解方程组时，要求系数矩阵具有某些特性。因此，随意构造一种迭代格式很可能不收敛，或者收敛太慢，使计算量太大而失去实际使用价值。№2消去法：优点：可预估计算时间，理论上可求得精确解。缺点：对于较高阶的方程组，计算量太大。第二十五页，共二十八页，2022年，8月28日松弛法例题：给定线性方程组AX=b，其中求解AX=b。问取什么实数ω可使迭代收敛？什么ω可使迭代收敛最快？复习：p1