数值分析几种常用的迭代法.ppt

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的GS法关于任意初始向量收敛。,华长生制作,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)1110.75000000.37500001.50000000.56250000.53125001.54166670.65104170.59635421.61458330.70182290.65820311.6727431.0.99999330.99999231.99999260.99999430.99999351.99999370.99999520.99999441.9999946k=71,x=0.9999950.9999941.999995,满足精度的解,迭代次数为71次,华长生制作,23,(1)SOR迭代法,1110.63750000.01218751.31990630.20042700.37175721.31228050.65503350.53401191.69228480.70584680.77334011.7771932.0.99999900.99999761.99999910.99999840.99999931.99999890.99999980.99999941.99999980.99999960.99999981.9999997k=24,x=1.0000001.0000002.000000,满足精度的解,迭代次数为24次,s