第六章 线性方程组迭代法.ppt

1、,Ch4 解线性方程组的迭代法,直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3数量级，存储量为n2量级，这在n比较小的时候还比较合适，但是对很多实际问题，往往要我们求解很大型的矩阵，而且这些矩阵含有大量的0元素。对于这类矩阵，在用直接法时就会耗费大量的时间和存储单元。因此我们有必要引入一类新的方法：迭代法。,对方程组,做等价变换,如：令,，则,则，我们可以构造序列,若,同时：,所以，序列收敛,与初值的选取无关,定义：（收敛矩阵）,定理：,即：矩阵B为收敛矩阵当且仅当B的谱半径1,由,知，若有某种范数,则迭代收敛.,1. Jacobi迭代法,格式很简单：,2. Gauss

2、Seidel迭代法,在Jacobi迭代中，使用最新计算出的分量值,迭代矩阵,记,-L,-U,D,易知，Jacobi迭代有,迭代矩阵,迭代公式:,例 用Gauss-seidel 迭代法解方程组 Ax=b,计算结果:,3 逐次超松弛迭代法(SOR),记,则,可以看作在前一步上加一个修正量。若在修正量前乘以一个因子,，有,对GaussSeidel迭代格式,整理得,引入松弛因子,写成分量形式，有,迭代矩阵,SOR方法收敛的快慢与松弛因子的选择有密切关系. 但是如何选取最佳松弛因子,即选取=*,使(B)达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.41.6

3、.,4 迭代法的收敛性,定义 设有矩阵序列 及 ，如果 则称 收敛于 ，记为,一些关于收敛的定义及定理,定理 定理 设 ，则 其中 为 的谱半径。 定理(迭代法基本定理）设有方程组 对于任意初始向量 及任意 ，解此方程组的迭 代法 收敛的充要条件是,定义 称 为迭代法的收敛速度. 定理(迭代法收敛的充分条件) 如果方程组 的迭代公式为 ，且迭代矩阵的某一种范数 ，则 1）迭代法收敛，即对任取 ，有 2） 3）,实际计算中,通常利用,作为控制迭代的终止条件.不过要注意,当 时, 较大,尽管 已非常小,但误差向量的模 可能很大,迭代法收敛将是缓慢的.,特别的,Jacobi 迭代法收敛,G-S迭代法

4、收敛,SOR迭代法收敛,定理 若SOR方法收敛, 则02.,证 设SOR方法收敛, 则(B)1,所以 |det(B)| =|12 n|1,而 det(B) =det(D-L)-1 (1-)D+U),=det(E-D-1L)-1 det(1-)E+D-1U),=(1-)n,于是 |1-|1, 或 02,定理 设A是对称正定矩阵, 02时,则解方程组 Ax=b的SOR方法收敛.,注意的问题,（2）Jacobi迭代法和Gauss-Seidel迭代法的收敛性没有必然的联系：,即当Gauss-Seidel法收敛时，Jacobi法可能不收敛； 而Jacobi法收敛时， Gauss-Seidel法也可能不收敛。,（1）Jacobi迭代法和Gauss-Seidel迭代法的 迭代矩阵不同：,BJ =D-1(L+U), B G-S = (D-L) -1U,用Jacobi迭代法求解不收敛，但用 G-S法收敛。,用Jacobi迭代法求解收敛， 但用 G-S法不收敛。,BJ的特征值为0，0，0， 而BGS的特征值为 0，2，2,系数矩阵A是正定矩阵，因此用 Gauss-Seidel法收敛,不是正定矩阵，因此用 Jacobi迭代法不收敛,A是有正对角元的 n阶对称矩阵,本章小结,掌握基本的迭代法:Jacobi迭代法,Gauss-Seid