资源描述
6.3 几种常用的迭代法,华长生制作,2,记 ,A非奇异,且对角元 ,可以把 A 分解为,其中,雅可比迭代法,华长生制作,3,方程组Ax=b等价于,由此构造迭代公式:,其中迭代距阵 和向量 为,称之为Jacobi 迭代法(简称 J 法),称 为雅可比迭代矩阵。,华长生制作,4,雅可比法的分量形式为,由前面的定理知雅可比迭代关于任意初始向量收敛 的充要条件为 ,充分条件为,利用这些判别 J 法的收敛性,有时不太方便,对于大型方程组,要求出迭代矩阵谱半径 是不容易的。下面给出一些容易验证收敛性的充分条件,先讨论对角占优矩阵的性质。,华长生制作,5,定义 1 若 满足,则称 A 为严格对角占优矩阵。若满足,且其中至少有一个严格不等式成立,则称 A 为弱对角占优矩阵。,华长生制作,6,定义2 设 ,若A不能经过行置换与相应的列置换 化为,其中 和 均为方阵,则称 A 为不可约的,否则称 A 为可约的。,定理 若A为严格对角占优矩阵,或不可约的弱对角占优矩阵,则解 方程组 的 J 法关于任意初始向量收敛。,设 ,这里只给出A为严格对角占优阵时的证明。,对 J法,迭代矩阵 ,易得,。,由A的严格对角占优性,得到 ,所以 J 法收敛。,证,华长生制作,7,与雅可比法相应的高斯-赛德尔迭代法,在J 法中,计算 时,分量 已经算出,所以可考虑,在J法中的求和分成两部分,从而得到与雅可比迭代法相应的高斯-赛德尔迭代法为,这就是Gauss-Seidel 迭代法,简称 GS 法。,华长生制作,8,将上式写成距阵形式,整理为简单迭代的形式,其中迭代矩阵 和向量 为,Jacobi 迭代法和 Gauss-Seidel 迭代法的分量形式供计算编程用,它们 的矩阵形式供研究迭代序列是否收敛等理论分析用。,华长生制作,9,解 用 J 法计有,华长生制作,10,GS 法迭代4次的计算结果是,精确解为(1,1,1),从计算结果看,本例用 GS 法显然比用 J 法收敛快,但并不是任何时候GS法都比J法快,甚至有J法收敛而GS法不收敛的例子。,华长生制作,11,显然,高斯-赛德尔法关于任意初始向量收 敛的充要条件是 另外与雅可比法相仿有如下结论:,定理 若A为严格对角占优矩阵,或不可约的弱对角占优矩阵,则解 方程组Ax=b 的G S 法关于任意初始向量收敛。,华长生制作,12,例.,判别下列方程组用J法和G-S法求解是否收敛,解:,(1) 求Jacobi法的迭代矩阵,华长生制作,13,因此不能用范数判断,所以,即Jaobi迭代法收敛,(2) 求Gauss-Seidel法的迭代矩阵,华长生制作,14,所以Gauss-Seidel迭代法发散,华长生制作,15,无论是解线性方程组的Jacobi迭代法和GS迭代法,都涉及到收敛速度问题,如何加快迭代法的速度呢?,如何改善迭代法的适用范围呢?,逐次超松弛(SOR)迭代法,华长生制作,16,考虑解线性方程组的Gauss-Seidel迭代法,-(1),华长生制作,17,令,因此,-(2),华长生制作,18,上式称为逐次超松弛法(SOR迭代法),逐次超松弛法(SOR迭代法)的矩阵形式为,两边乘上D,整理为简单迭代法的形式为,华长生制作,19,令,华长生制作,20,SOR法化为,G-S迭代法,G-S法为SOR法的特例, SOR法为G-S法的加速,例1.,用G-S法和SOR法求下列方程组的解,要求精度1e-6,取初值(0,0,0),华长生制作,21,解:,(1)G-S迭代法,华长生制作,22,gauss_seidel.m,x,k=gauss_seidel(a,b,1,1,1,1e-6) 1 1 1 0.7500000 0.3750000 1.5000000 0.5625000 0.5312500 1.5416667 0.6510417 0.5963542 1.6145833 0.7018229 0.6582031 1.6727431 . 0.9999933 0.9999923 1.9999926 0.9999943 0.9999935 1.9999937 0.9999952 0.9999944 1.9999946 k = 71,x= 0.999995 0.999994 1.999995,满足精度的解,迭代次数为71次,华长生制作,23,(1)SOR迭代法,1 1 1 0.6375000 0.0121875 1.3199063 0.2004270 0.3717572 1.3122805 0.6550335 0.5340119 1.6922848 0.7058468 0.7733401 1.7771932 . 0.9999990 0.9999976 1.9999991 0.9999984 0.9999993 1.9999989 0.9999998 0.9999994 1.9999998 0.9999996 0.9999998 1.9999997 k = 24,x= 1.000000 1.000000 2.000000,满足精度的解,迭代次数为24次,sor.m,SOR法的收敛速度比G-S法要快得多,华长生制作,24,SOR法都收敛吗?,1.SOR迭代法收敛的充要条件是,对于SOR迭代法(7),有如下结论,另外,松弛因子的选取是很困难的,一般采用试算进行,
展开阅读全文