数值分析几种常用的迭代法学习教案.pptx
数值分析数值分析(fnx)几种常用的迭代法几种常用的迭代法第一页，共24页。华长生华长生(chngshng)(chngshng)制作制作2 2 记记 ，A非奇异非奇异(qy)，且对角元，且对角元 ，可以把，可以把 A 分解为分解为 其中其中(qzhng)雅可比迭代法第1页/共24页第二页，共24页。华长生华长生(chngshng)(chngshng)制作制作3 3方程组方程组Ax=b等价等价(dngji)于于由此构造由此构造(guzo)迭代公迭代公式：式：其中迭代距阵其中迭代距阵 和向量和向量 为为 称之为称之为Jacobi 迭代法迭代法（简称（简称 J 法）法），称，称 为雅可比迭代矩阵。为雅可比迭代矩阵。第2页/共24页第三页，共24页。华长生华长生(chngshng)(chngshng)制作制作4 4雅可比法的分量(fn ling)形式为由前面的定理知雅可比迭代关于(guny)任意初始向量收敛的充要条件为 ，充分条件为 利用这些判别 J 法的收敛性，有时不太方便，对于大型方程组，要求出迭代矩阵谱半径 是不容易的。下面给出一些容易验证收敛性的充分条件，先讨论对角占优矩阵的性质。第3页/共24页第四页，共24页。华长生华长生(chngshng)(chngshng)制作制作5 5定义定义(dngy)1 若若 满足满足则称则称 A 为严格对角为严格对角(du jio)占优矩阵。若满足占优矩阵。若满足且其中至少有一个严格不等式成立，则称且其中至少有一个严格不等式成立，则称 A 为为弱对角占优矩阵弱对角占优矩阵。第4页/共24页第五页，共24页。华长生华长生(chngshng)(chngshng)制作制作6 6定义定义(dngy)2 设设 ，若，若A不能经过行置换与相应的列不能经过行置换与相应的列置换置换 化为化为其中其中 和和 均为方阵，则称均为方阵，则称 A 为为不可约的，不可约的，否则称否则称 A 为为可约的可约的。定理定理 若若A为严格对角为严格对角(du jio)占优矩阵，或不可约的弱占优矩阵，或不可约的弱对角对角(du jio)占优矩阵，则解占优矩阵，则解 方程组方程组 的的 J 法关于任意初始向量收敛。法关于任意初始向量收敛。设设 ，这里只给出，这里只给出A为严格对角占优阵时的证明。为严格对角占优阵时的证明。对对 J法，迭代矩阵法，迭代矩阵 ，易得，易得。由由A的严格对角占优性，得到的严格对角占优性，得到 ，所以，所以 J 法收敛。法收敛。证证第5页/共24页第六页，共24页。华长生华长生(chngshng)(chngshng)制作制作7 7与雅可比法相应与雅可比法相应(xingyng)(xingyng)的高斯的高斯-赛德尔迭代法赛德尔迭代法 在在J 法中，计算法中，计算(j sun)时，分量时，分量 已经算出，所以可考虑已经算出，所以可考虑在在J法中的求和分成两部分，从而得到与雅可比迭代法相应的高法中的求和分成两部分，从而得到与雅可比迭代法相应的高斯斯-赛德尔迭代法为赛德尔迭代法为这就是这就是Gauss-Seidel 迭代法迭代法，简称，简称 GS 法。法。第6页/共24页第七页，共24页。华长生华长生(chngshng)(chngshng)制作制作8 8 将上式写成距阵形式将上式写成距阵形式(xngsh)整理为简单迭代整理为简单迭代(di di)的形的形式式其中迭代矩阵其中迭代矩阵 和向量和向量 为为 Jacobi 迭代法和迭代法和 Gauss-Seidel 迭代法的分量形式供计算编程用，它们迭代法的分量形式供计算编程用，它们的矩阵形式供研究迭代序列是否收敛等理论分析用。的矩阵形式供研究迭代序列是否收敛等理论分析用。第7页/共24页第八页，共24页。华长生华长生(chngshng)(chngshng)制作制作9 9例用法和法分别求解方程组例用法和法分别求解方程组。解解 用用 J 法计有法计有第8页/共24页第九页，共24页。华长生华长生(chngshng)(chngshng)制作制作1010用用 GS 法计算有法计算有 取取 ，J 法迭代法迭代4次的计算结果是次的计算结果是GS 法迭代法迭代(di di)4次的计算结果是次的计算结果是精确解为（精确解为（1，1，1），从计算结果看，本例用），从计算结果看，本例用 GS 法显然比用法显然比用 J 法法收敛快，但并不是任何时候收敛快，但并不是任何时候GS法都比法都比J法快，甚至法快，甚至(shnzh)有有J法收法收敛而敛而GS法不收敛的例子。法不收敛的例子。第9页/共24页第十页，共24页。华长生华长生(chngshng)(chngshng)制作制作1111显然，高斯-赛德尔法关于任意(rny)初始向量收敛的充要条件是另外与雅可比法相仿有如下结论：定理定理 若若A为严格对角占优矩阵，或不可约的弱对角占优矩为严格对角占优矩阵，或不可约的弱对角占优矩阵，则解阵，则解 方程组方程组Ax=b 的的G S 法关于任意法关于任意(rny)初始向量收敛。初始向量收敛。第10页/共24页第十一页，共24页。华长生华长生(chngshng)(chngshng)制作制作1212例.判别下列方程组用J法和G-S法求解(qi ji)是否收敛解:(1)求Jacobi法的迭代(di di)矩阵第11页/共24页第十二页，共24页。华长生华长生(chngshng)(chngshng)制作制作1313因此(ync)不能用范数判断所以(suy)即Jaobi迭代法收敛(2)求Gauss-Seidel法的迭代矩阵第12页/共24页第十三页，共24页。华长生华长生(chngshng)(chngshng)制作制作1414所以(suy)Gauss-Seidel迭代法发散第13页/共24页第十四页，共24页。华长生华长生(chngshng)(chngshng)制作制作1515无论是解线性方程组的Jacobi迭代法和GS迭代法都涉及到收敛(shulin)速度问题如何(rh)加快迭代法的速度呢？如何改善迭代法的适用范围呢？逐次超松弛（SOR）迭代法第14页/共24页第十五页，共24页。华长生华长生(chngshng)(chngshng)制作制作1616考虑(kol)解线性方程组的Gauss-Seidel迭代法-(1)第15页/共24页第十六页，共24页。华长生华长生(chngshng)(chngshng)制作制作1717令因此(ync)-(2)第16页/共24页第十七页，共24页。华长生华长生(chngshng)(chngshng)制作制作1818上式称为(chn wi)逐次超松弛法(SOR迭代法),逐次(zh c)超松弛法(SOR迭代法)的矩阵形式为两边乘上D，整理为简单迭代法的形式为第17页/共24页第十八页，共24页。华长生华长生(chngshng)(chngshng)制作制作1919令第18页/共24页第十九页，共24页。华长生华长生(chngshng)(chngshng)制作制作2020SOR法化为G-S迭代法G-S法为SOR法的特例(tl),SOR法为G-S法的加速例1.用G-S法和SOR法求下列(xili)方程组的解,要求精度1e-6,取初值（0，0，0）第19页/共24页第二十页，共24页。华长生华长生(chngshng)(chngshng)制作制作2121解:(1)G-S迭代法第20页/共24页第二十一页，共24页。华长生华长生(chngshng)(chngshng)制作制作2222gauss_seidel.mx,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=71x=0.9999950.9999941.999995满足(mnz)精度的解迭代(di di)次数为71次第21页/共24页第二十二页，共24页。华长生华长生(chngshng)(chngshng)制作制作2323(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=24x=1.0000001.0000002.000000满足(mnz)精度的解迭代(di di)次数为24次sor.mSOR法的收敛速度比G-S法要快得多第22页/共24页第二十三页，共24页。华长生华长生(chngshng)(chngshng)制作制作2424SOR法都收敛(shulin)吗？1.SOR迭代法收敛(shulin)的充要条件是对于SOR迭代法(7),有如下结论另外,松弛因子的选取是很困难的,一般采用试算进行第23页/共24页第二十四页，共24页。
