线性方程组的迭代法.ppt

《线性方程组的迭代法.ppt》由会员分享，可在线阅读，更多相关《线性方程组的迭代法.ppt（46页珍藏版）》请在三一办公上搜索。

1、数值分析,第6章 方程与方程组的迭代解法,基本迭代法,迭代法的收敛性,6.2 解线性方程组的迭代法,超松弛迭代法,6.2 线性方程组的迭代法,在用直接法解线性方程组时要对系数矩阵不断变换,如果方程组的阶数很高,则运算量将会很大,并且大量占用计算机资源,因此对线性方程组,要求找寻更经济、适用的数值解法,-(1),如果能将线性方程组(1)变换为,-(2),显然,(1)式和(2)式同解,我们称(1)(2)等价,对线性方程组(2),采用以下步骤:,依此类推,-(3),这种方式就称为迭代法,以上过程称为迭代过程,迭代法产生一个序列,如果其极限存在,即,则称迭代法收敛,否则称为发散,一、简单迭代法(基本迭

2、代法),设线性方程组(1)的一般形式为,依此类推,线性方程组(1)可化为,-(4),-(5),对(4)作迭代过程,则(5)式转化为矩阵形式,-(6),令,故迭代过程(6)化为,等价线性方程组为,-(7),称(5)式和(7)式为解线性方程组(1)的Jacobi迭代法(J法),例1.,用Jacobi迭代法求解方程组,误差不超过1e-4,解:,依此类推,得方程组满足精度的解为x12,迭代次数为12次,x4=3.0241 1.9478 0.9205 d=0.1573 x5=3.0003 1.9840 1.0010 d=0.0914 x6=2.9938 2.0000 1.0038 d=0.0175 x7

3、=2.9990 2.0026 1.0031 d=0.0059 x8=3.0002 2.0006 0.9998 d=0.0040 x9=3.0003 1.9999 0.9997 d=7.3612e-004x10=3.0000 1.9999 0.9999 d=2.8918e-004x11=3.0000 2.0000 1.0000 d=1.7669e-004x12=3.0000 2.0000 1.0000 d=3.0647e-005,分析Jacobi迭代法(5)的迭代过程,将(5)式细化,考虑迭代式(7),即,将上式改为,-(8),-(9),上式称为Gauss-Seidel迭代法,简称G-S法,利用

4、(8)式展开Gauss-Seidel迭代法也可表示成,例2.,用Gauss-Seidel迭代法求解例1.,解:,x1=2.5000 2.0909 1.2273 d=3.4825x2=2.9773 2.0289 1.0041 d=0.5305x3=3.0098 1.9968 0.9959 d=0.0465x4=2.9998 1.9997 1.0002 d=0.0112x5=2.9998 2.0001 1.0001 d=3.9735e-004x6=3.0000 2.0000 1.0000 d=1.9555e-004x7=3.0000 2.0000 1.0000 d=1.1576e-005,通过迭代

5、,至第7步得到满足精度的解x7,从例1和例2可以看出,Gauss-Seidel迭代法的收敛速度比Jacobi迭代法要高,二、迭代法的收敛性,设解线性方程组的迭代格式,-(10),-(11),将(10)与(11)相减,得,则,因此迭代法收敛的充要条件,可转变为,定理1.迭代格式(10)收敛的充要条件为,-(12),根据矩阵与其Jordan标准形及特征值的关系,可知,即,因此,定理2.,迭代格式(10)收敛的充要条件为,-(13),又因为矩阵的谱半径不超过其任一种算子范数,即,于是又可得到,定理3.,-(14),且,证明:,只证(14)式,所以,-(14),即,(14)可以用来估计迭代法的精度,理

6、论上只要,在计算时,迭代终止的条件可以用上式判别,例3.,判别下列方程组用J法和G-S法求解是否收敛,解:,(1)求Jacobi法的迭代矩阵,因此不能用定理3,只能用定理2判断,所以,即Jaobi迭代法收敛,(2)求Gauss-Seidel法的迭代矩阵,同样用定理2判断,所以Gauss-Seidel迭代法发散,在例1和例2中,G-S法收敛速度比J法要高,但例3却说明G-S法发散时而J法却收敛,因此,不能说G-S法比J法更好,另外,给出系数矩阵对角占优线性方程组的一个结论,定理4.,证:,(1)对于Jacobi迭代法,其迭代矩阵为,根据定理3,Jacobi迭代法收敛,(2)对于GS迭代法,其迭代

7、矩阵为,不能使用定理3,而用定理2,即,从而,因此,由于,可得,矛盾,由定理2,GS迭代法收敛,3 解线性方程组的超松弛迭代法,超松弛迭代法(简称SOR方法)是高斯-塞德尔方法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之一，,设有方程组 其中 为非奇异矩阵，且设 0(=1，2，n),设已知第 次迭代向量，及第k+1次迭代向量 的分量,要求计算分量,首先 用迭代法定义辅助量,再把 取为 与 某个平均值(即加权平均)，即,超松弛迭代公式,其中 称为松弛因子，或写为,显然，当=1时，SOR方法就是高斯-塞德尔迭代法。,当 时，称为低松弛法，当 时，称为高松弛法。,例11:用SOR方法解方程组,

8、它的精确解为,解:取，迭代公式为,取，第11次迭代结果为,0.4610-5,下面我们写出SOR迭代公式的矩阵形式。迭代公式亦可写为,用分解式A=D-L-U，则,即,显然对任何一个 值，非奇异（由设 于是,这就是说（设 SOR方法迭代公式为,其中,矩阵 为SOR方法的迭代矩阵。这说明SOR方法相当于对方程组，应用一般迭代法。于是关于一般迭代法的理论可得到下述定理：,定理 设有线性方程组Ax=b，且 0(i=1，2，n)，则解方程组的SOR方法收敛的充要条件是,定理 设解Ax=b(O，i=1，2，n)的SOR方法收敛，则,下面研究对于一般方程组(O，i=1，2，n)，松弛因子 在什么范围内取值，SOR方法才可能收敛。现给出SOR方法收敛的必要条件。,证明 由设SOR方法收敛，,设 的特征值为，则,而,所以,即,定理 如果A为对称正定矩阵，且，则解Ax=b的 SOR方法收敛。,证明 在上述假定下,若能证明,那么定理得证(其中 为 的任一特征值).,事实上，设y为对应 的 的特征向量，即,亦即,为了找出 的表达式，考虑数量积,则,显然,记，由于 A=AT，所以 U=LT。,所以,当O 2时，有,从而,即 的任一特征值满足，故SOR方法收敛(注意当O 2时，可以证明()。,