第五章解线性代数方程组的迭代法.doc
文本预览下载声明
第五章 解线性代数方程组的迭代法
迭代法是解线性代数方程组的另一类重要方法，特别适于求解系数矩阵为稀疏阵的大型线性代数方程组．它的基本思想是，从任一初始向量出发，按某一规则，逐次构造一个向量序列，当收敛于，使是所给方程组的解．于是，就有下列问题需要讨论：
（１）构造迭代格式
（２）收敛性及误差估计
本章将介绍几种实用的迭代法，并讨论其收敛条件．
§１ 迭代法
１.１迭代格式的构造
设所给方程组为
其中，是阶方阵，是已知向量，是未知向量．
任取，代入的右端，算得的结果记为，再以代入的右端，算得的结果记为，如此进行下去，便得到迭代格式
此格式称为迭代法，称为迭代矩阵．
显然，若存在，则有
即为的解．
注：若方程组由下面形式给出
则需要把它改写成便于迭代的形式，其方法是多种多样的，最一般的方法是将分解为两个矩阵之差
，
其中矩阵可逆，于是成为
令，，即得．
必须指出，中的应是便于求逆的，的最简单选择是把它选为对角阵，通常，当的对角元素全不为零时，就把选为的对角线，于是
其中是具有的对角元素的对角阵，而在对角线上的元素为零．此时关系式成为
式中，是简单的对角阵，它的对角元素是的元素的倒数．
１.２ 迭代法
若由迭代法所构成的向量序列收敛，则称迭代格式收敛，或称迭代法收敛．
以式减去式得
所以，为使（当时），必要而且只要，而（）的充要条件是矩阵的谱半径．故有
定理１ 对任意右端向量和初始向量，迭代格式收敛于的解的充要条件是．
由定理１可以看出，迭代是否收敛只与迭代矩阵的谱半径有关，而迭代矩阵是由系数矩阵演变过来的，所以迭代是否收敛是与系数矩阵以及演变的方式有关，与右端向量和初始向量的选择无关．
在具体问题中，谱半径是很难计算的，但由于，所以可以用来作为的一种估计．当时迭代格式一定收敛，不过这只是收敛的充分条件．
定理２ 若，则迭代格式收敛于的解，且有误差估计
或
证明 因为，所以迭代格式收敛．其次，由关系式
有
从而有
因此式成立．
又从式有
,
所以
．
将此式代入中，便得到式．定理２证完．
依定理２可知，当
或
时，迭代法收敛．
除了用定理１、定理2来判别迭代法的收敛性外，还可根据方程组系数矩阵的特点给出一些收敛性的判别条件。
设线性代数方程组的形式为，则
１）若是严格对角占优阵（各行非对角元绝对值之和小于非对角元绝对值的矩阵），则迭代法收敛．
２）若为对称正定矩阵，也为对称正定矩阵，则迭代法收敛；若是对称正定矩阵而非对称正定矩阵，则迭代法不收敛．（其中为的对角元组成的对角阵，所以与只是非对角元的符号不同）．
例１ 用迭代法解下列方程组（精确到）：
解 先将方程组化成的形式，以４，３，４分别除三个方程两边得
从而有
由于，故对任意初始向量，迭代法收敛．取，反复使用上式，则得
因为在所要求的精度内，故停止计算，即为所求近似解．
§２ 迭代法
２.１迭代格式
对方程组
，
作迭代时，取定初始近似值，，以后，把它们代入中第一个方程算出
显然，迭代格式收敛的话，则比更接近于的第一个分量．所以在计算时，我们不再象迭代法那样以，，代入中第二式的右边，而是把新算出的及，，代入该式右边，得到
即计算下一个分量时，要用到刚算出的新分量，这样或许能收到更好的效果．按这样方式建立的迭代格式称为迭代格式，其一般形式为
用矩阵表示就是
，
其中，，
，
因存在，所以迭代格式也可表示为
我们称为迭代法的迭代矩阵．
由式可见，对方程组作迭代，等价于对方程组
作迭代．
２.２迭代法的收敛性
由于对方程组作迭代同对方程组作简单迭代是一回事，故由定理１有
定理３ 对于任意右端向量和初始向量，迭代法收敛的充要条件是
（其中）
即特征方程
或
的根的绝对值均小于１．
类似与定理２，我们还可以给出如下收敛的充分条件．
定理４ 对任意右端向量和初始向量，迭代法收敛的充分条件是
１）
２）
由此定理可知，若条件１）或２）被满足时，则迭代法与迭代法都收敛．
可以证明，当条件２）被满足时， 迭代法比迭代法收敛得快些．
例２ 分别用和迭代法解方程组
解 由于，故迭代法和迭代法都收敛．取，首先使用迭代法，计算求得
，
，
．
与其精确解相比，其误差为
再利用迭代格式，计算求得
，
，
．
其误差为
从此例可以看出，当充分条件２）被满足时，迭代法确实比迭代法收敛得快些．
然而，迭代法并不总比迭代法好．有时迭代法还比迭代法收敛得慢些，有时甚至在迭代法收敛时，它却不收敛．
例３ 设方程组的系数矩阵为
试证明迭代法收敛，而迭代法不收敛．
证明 显然，迭代法的迭代矩阵为
因为，令，则有
由定理１可知，迭代法收敛．
又，其中
令
则有
故迭代法不收敛．
类似的方法，可以证明，若系数矩
显示全部