数值分析第六章解线性方程组的迭代法课件.ppt

数值分析第六章解线性方程组的迭代法第1页，此课件共70页哦2/68郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis第六章 解线性代数方程组的迭代法 6.1 6.1 引言引言6.2 6.2 几种常用的迭代格式几种常用的迭代格式6.3 6.3 迭代法的收敛性及误差估计迭代法的收敛性及误差估计6.4 6.4 判别收敛的几个常用条件判别收敛的几个常用条件6.5 6.5 迭代法收敛判定的应用举例迭代法收敛判定的应用举例第2页，此课件共70页哦3/68郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.1 引言q 线性方程组的数值解法有：线性方程组的数值解法有：直接法直接法和和迭代法迭代法。直接法直接法：在假定没有舍入：在假定没有舍入误差的情况下，差的情况下，经过有限次运算可有限次运算可以求得方程以求得方程组的精确解；的精确解；迭代法迭代法：从一个初始向量出：从一个初始向量出发，按照一定的迭代格式，按照一定的迭代格式，构造出一个构造出一个趋向于真解的无向于真解的无穷序列。序列。第3页，此课件共70页哦4/68郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.1 引言当A为稀疏矩阵时，直接法将破坏矩阵A的稀疏性。系数矩阵的分类第一类：低阶稠密方程组，即系数矩阵的阶数不高，含零元素很少，在线性代数等课程学习中通常见到的，都属这类方程组；第二类：高阶稀疏方程组，系数矩阵的阶数很高，如几百阶、甚至成千上万阶，其中零元素成片分布，数量上绝对占优。第4页，此课件共70页哦5/68郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis迭代法适用于解迭代法适用于解大型稀疏方程组大型稀疏方程组(万阶以上的方程组万阶以上的方程组,系数矩阵中零元素占很大比系数矩阵中零元素占很大比例例,而非零元按某种模式分布而非零元按某种模式分布)问题问题:(1)如何构造迭代格式如何构造迭代格式？(2)迭代格式是否收敛迭代格式是否收敛？(3)如何进行误差估计如何进行误差估计？6.1 引言第5页，此课件共70页哦6/68郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.1 引言迭代法的基本思想迭代法的基本思想 迭代法的基本思想是将线性方程组转化为便于迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值迭代的等价方程组，对任选一组初始值 ，按某种计算规则，不断地，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要对所得到的值进行修正，最终获得满足精度要求的方程组的近似解求的方程组的近似解。第6页，此课件共70页哦7/68郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis设设 非奇异，非奇异，则线性方程组，则线性方程组 有惟一解有惟一解 ，经过变换构造出，经过变换构造出一个等价同解方程组一个等价同解方程组将上式改写成将上式改写成迭代式迭代式选定初始向量选定初始向量 ,反复不断地使反复不断地使用迭代式逐步逼近方程组的精确解用迭代式逐步逼近方程组的精确解,直到满足精直到满足精度要求为止。这种方法称为度要求为止。这种方法称为迭代法迭代法第7页，此课件共70页哦8/68郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis 如果向量序列如果向量序列 存在极限存在极限则称迭代法是则称迭代法是收敛的收敛的，否则就是，否则就是发散的发散的。收敛时，在迭代公式收敛时，在迭代公式中当中当 时，时，,则则 故故 是方程组是方程组 的解。的解。对于给定的方程组可以构造各种迭代公式。对于给定的方程组可以构造各种迭代公式。并非全部收敛并非全部收敛。第8页，此课件共70页哦9/68郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式雅可比(Jacobi)迭代格式例例6.2.16.2.1 建立迭代格式求解方程组建立迭代格式求解方程组 方程组的精确解方程组的精确解x x*=(3,2,1)=(3,2,1)T T。第9页，此课件共70页哦1068郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式建立迭代公式建立迭代公式 第10页，此课件共70页哦1168郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis取初始向量取初始向量进行迭代进行迭代,可以逐步得出一个近似解的序列：可以逐步得出一个近似解的序列：（k=1,2,）直到求得的近似解能达到预先要求的精度，直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线则迭代过程终止，以最后得到的近似解作为线性方程组的解。性方程组的解。当迭代到第当迭代到第10次有次有计算结果表明，此迭代过程收敛于方程组的精计算结果表明，此迭代过程收敛于方程组的精确解确解x*=(3,2,1)T。第11页，此课件共70页哦1268郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis考察一般的考察一般的n n元线性方程组元线性方程组 写成写成 第12页，此课件共70页哦1368郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis若若 ,分离出变量分离出变量 第13页，此课件共70页哦1468郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式 （Jacobi迭代公式）(k=0,1,2,)第14页，此课件共70页哦1568郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式 （Jacobi迭代公式）据此建立迭代公式据此建立迭代公式 上式称为解方程组的上式称为解方程组的JacobiJacobi迭代公式迭代公式。也称为也称为 简单迭代法简单迭代法。第15页，此课件共70页哦1668郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis雅可比迭代法的矩阵表示雅可比迭代法的矩阵表示 设方程组设方程组 的系数矩阵的系数矩阵A A非奇异，且主对非奇异，且主对角元素角元素 ，则可将，则可将A A分裂成分裂成 记作记作 A=L+D+U 第16页，此课件共70页哦1768郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis则则 等价于等价于因为因为 ，则则这样便得到一个迭代公式这样便得到一个迭代公式6.2 几种常用的迭代格式 （Jacobi迭代公式）第17页，此课件共70页哦1868郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis其中其中 令令则有则有（k=0,1,2）称为称为雅可比迭代公式雅可比迭代公式,B称为称为雅可比迭代矩阵雅可比迭代矩阵6.2 几种常用的迭代格式 （Jacobi迭代公式）第18页，此课件共70页哦1968郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis 雅雅可可比比迭迭代代法法的的算算法法实实现现 第19页，此课件共70页哦2068郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式 （Jacobi迭代公式）function X=jacobi(A,B,P,delta,max)%求解AX=B，A是非奇N阶方阵dleta是误差界，max是最大迭代次数N=length(B);for t=1:max for k=1:N X(k)=(B(k)-A(k,1:k-1,k+1:N)*P(1:k-1,k+1:N)/A(k,k);end err=abs(norm(X-P);if(errdelta)break;end endX=X;第20页，此课件共70页哦2168郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式高斯-塞德尔（Gauss-Seidel）迭代法在在Jacobi迭迭代代法法中中，每每次次迭迭代代只只用用到到前前一一次次的的迭迭代代值值，若若每每次次迭迭代代 充充 分分 利利 用用 当当 前前 最最 新新 的的 迭迭 代代 值值，即即 在在 求求 时时 用用 新新 分分 量量 代替旧分量代替旧分量 第21页，此课件共70页哦2268郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式Gauss-Seidel迭代法(i=1,2,=1,2,n k=0,1,2,=0,1,2,)高斯高斯-赛德尔迭代法的迭代法格式为：赛德尔迭代法的迭代法格式为：第22页，此课件共70页哦2368郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式GaussSeidel 迭代法的矩阵表示将将A分裂成分裂成A=L+D+U，则，则 等价于等价于 (L+D+U)(L+D+U)x=b=b 于是于是,则高斯则高斯塞德尔迭代过程塞德尔迭代过程 第23页，此课件共70页哦2468郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式GaussSeidel 迭代法的矩阵表示因为因为 ,所以所以 故故 则高斯则高斯-塞德尔迭代形式为：塞德尔迭代形式为：令令 第24页，此课件共70页哦2568郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式高斯-塞德尔迭代法高斯高斯塞德尔迭代算法实现塞德尔迭代算法实现 高高斯斯-塞塞德德尔尔迭迭代代算算法法的的计计算算步步骤骤与与流流程程图图与与雅雅可可比迭代法大致相同，只是一旦求出变元比迭代法大致相同，只是一旦求出变元的某个新值的某个新值 后后,就改用新值就改用新值 替代老值替代老值 进行这一步剩下的计算。进行这一步剩下的计算。第25页，此课件共70页哦2668郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式function X=gseid(A,B,P,delta,max)%求解AX=B，A是非奇N阶方阵dleta是误差界，max是最大迭代次数N=length(B);for t=1:max for k=1:N if k=1 X(1)=(B(1)-A(1,2:N)*P(2:N)/A(1,1);elseif k=N X(N)=(B(N)-A(N,1:N-1)*(X(1:N-1)/A(N,N);else X(k)=(B(k)-A(k,1:k-1)*X(1:k-1)-A(k,k+1:N)*P(k+1:N)/A(k,k);end end err=abs(norm(X-P);if(errdelta)break;end end X=X;高斯-塞德尔迭代法第26页，此课件共70页哦2768郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis例例6.2.2，按高斯-塞德尔迭代公式迭代7次，得，用高斯-塞德尔迭代法解下面线性方程组第27页，此课件共70页哦2868郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis 由此例可知，用高斯-塞德尔迭代法，雅可比迭代法解线性方程组(且取)均收敛.而高斯-塞德尔迭代法比雅可比迭代法收敛较快(即取相同，达到同样精度所需迭代次数较少).但这结论只当满足一定条件时才是对的.且第28页，此课件共70页哦2968郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式超松弛迭代法（SOR方法）使用迭代法的困使用迭代法的困难在于在于难以估以估计其其计算量。有算量。有时迭迭代代过程程虽然收然收敛，但由于收，但由于收敛速度速度缓慢，使慢，使计算量算量变得很大而失去使用价得很大而失去使用价值。因此，迭代。因此，迭代过程的加速具有程的加速具有重要意重要意义。逐次超松弛迭代（逐次超松弛迭代（Successive Over relaxatic Method，简称称SOR方法）法方法）法，可以看作是，可以看作是带参数的高参数的高斯斯塞德塞德尔迭代法，迭代法，实质上是高斯上是高斯-塞德塞德尔迭代的一种迭代的一种加速方法。加速方法。第29页，此课件共70页哦3068郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式超松弛迭代法的基本思想超松弛迭代法的基本思想 超松弛迭代法目的是为了提高迭代法的收敛速度，在超松弛迭代法目的是为了提高迭代法的收敛速度，在高斯高斯塞德尔迭代公式的基础上作一些修改。这种方法是塞德尔迭代公式的基础上作一些修改。这种方法是将前一步的结果将前一步的结果 与高斯与高斯-塞德尔迭代方法的迭代值塞德尔迭代方法的迭代值 适当加权平均，期望获得更好的近似值适当加权平均，期望获得更好的近似值 。是解大型稀。是解大型稀疏矩阵方程组的有效方法之一，有着广泛的应用。疏矩阵方程组的有效方法之一，有着广泛的应用。第30页，此课件共70页哦3168郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式SOR方法用高斯用高斯塞德尔迭代法定义辅助量。塞德尔迭代法定义辅助量。把把 取为取为 与与 的加权平均，即的加权平均，即 合并表示为：合并表示为：第31页，此课件共70页哦3268郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式SOR方法式中系数式中系数称为称为松弛因子松弛因子，为了保证迭代过程收敛，为了保证迭代过程收敛，要求要求0 20 2。当当=1时，便为高斯时，便为高斯-塞德尔迭代法。塞德尔迭代法。当当0 1时，低松弛法；时，低松弛法；当当1 2时称为超松弛法。时称为超松弛法。但通常统称为但通常统称为超松弛法超松弛法(SOR)。第32页，此课件共70页哦3368郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式故故 令令则超松弛迭代公式可写成则超松弛迭代公式可写成 SOR迭代法的矩阵表示第33页，此课件共70页哦3468郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式显然对任何一个显然对任何一个值值,(D+L),(D+L)非奇异非奇异,(,(因为假设因为假设 )于是超松弛迭代公式为于是超松弛迭代公式为 (k=0,1,2,=0,1,2,)第34页，此课件共70页哦3568郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis例例6.2.36.2.3它的精确解为取，迭代公式为用SOR方法解方程组解解第35页，此课件共70页哦3668郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.2 几种常用的迭代格式取，取其他值，迭代次数如下表.第11次迭代结果为第36页，此课件共70页哦3768郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis 从此例看到，松弛因子选择得好，会使SOR迭代法的收敛大大加速.本例中是最佳松弛因子.第37页，此课件共70页哦3868郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis定义设有矩阵序列及,如果个数列极限存在且有则称收敛于，记为第38页，此课件共70页哦3968郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis例例且设，考查其极限.解解由于，当时，有设有矩阵序列所以第39页，此课件共70页哦4068郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis定理设,则(零矩阵)的充分必要条件是矩阵的谱半径（证明参见：关治，陈景良.数值计算方法,清华大学出版社，P410412）第40页，此课件共70页哦4168郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis矩阵的谱半径矩阵的谱半径第41页，此课件共70页哦4268郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis定理定理 对给定方阵对给定方阵G,若若 ,则则 为非奇异矩阵为非奇异矩阵,且且 证证:用反证法用反证法,若若 为奇异矩阵为奇异矩阵,则存在非零向则存在非零向 量量x,使使 ,即有即有 由相容性条件得由相容性条件得 由于由于 ,两端消去两端消去 ,有有 ,与已知条件与已知条件矛盾矛盾,假设不成立假设不成立,命题得证。命题得证。又由于又由于 有有 即即 将将G分别取成分别取成G和和-G，再取范数，再取范数 又已知又已知 ，有，有 第42页，此课件共70页哦4368郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.3 迭代法的收敛性及误差估计对于给定的方程组可以构造成雅可比迭代公式、对于给定的方程组可以构造成雅可比迭代公式、高斯高斯-塞德尔迭代公式和超松弛迭代公式，但塞德尔迭代公式和超松弛迭代公式，但并非并非一定收敛一定收敛。现在分析它们的收敛性。现在分析它们的收敛性。对于方程组对于方程组 经过等价变换构造出的等价方程组经过等价变换构造出的等价方程组 在什么条件下迭代序列在什么条件下迭代序列 收敛？收敛？第43页，此课件共70页哦4468郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis定理定理6.3.16.3.1 迭代公式迭代公式 收敛收敛的充分必要条件是迭代矩阵的充分必要条件是迭代矩阵G的谱半径的谱半径证证:必要性必要性 设迭代公式收敛设迭代公式收敛,当当kk时时,则在迭代公式两端同时取极限得则在迭代公式两端同时取极限得记记 ,则则 收敛于收敛于0(0(零向量零向量),),且有且有 于是于是 由于由于 可以是任意向量可以是任意向量,故故 收敛于收敛于0 0当且仅当且仅当当 收敛于零矩阵，即当收敛于零矩阵，即当 时时 所以必所以必 第44页，此课件共70页哦4568郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis充分性充分性:设设 ,则必存在正数则必存在正数,使使则存在某种范数则存在某种范数 ,使使 ,则则 ,所以所以 ,即即 。故。故 收敛于收敛于 0,收敛于收敛于 由此定理可知，不论是雅可比迭代法、高斯由此定理可知，不论是雅可比迭代法、高斯塞德尔迭代法还是超松弛迭代法，它们收敛的塞德尔迭代法还是超松弛迭代法，它们收敛的充要条件是其迭代矩阵的谱半径充要条件是其迭代矩阵的谱半径 。6.3 迭代法的收敛性及误差估计第45页，此课件共70页哦4668郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis定理定理6.3.26.3.2 (迭代法收敛的充分条件迭代法收敛的充分条件)若迭代矩阵若迭代矩阵G G的一种范数的一种范数 ,则迭代公式则迭代公式收敛收敛,且有误差估计式且有误差估计式,且有误差估计式且有误差估计式 及及 6.3 迭代法的收敛性及误差估计第46页，此课件共70页哦4768郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.3 迭代法的收敛性及误差估计证证:矩阵的谱半径不超过矩阵的任一种范数矩阵的谱半径不超过矩阵的任一种范数,已已知知 ,因此因此 ,根据定理根据定理6.3.16.3.1可知迭代可知迭代公式收敛公式收敛又因为又因为 ,则则det(I-G)0,I-G为非奇异矩阵为非奇异矩阵,故故xGxd有惟一解有惟一解 ,即即与迭代过程与迭代过程 相比较相比较,有有第47页，此课件共70页哦4868郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis 两边取范数两边取范数6.3 迭代法的收敛性及误差估计第48页，此课件共70页哦4968郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.3 迭代法的收敛性及误差估计由迭代格式，有由迭代格式，有 两边取范数，代入上式，得两边取范数，代入上式，得 证毕证毕 第49页，此课件共70页哦5068郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.3 迭代法的收敛性及误差估计 由定理知，当由定理知，当 时，其值越小，迭代收时，其值越小，迭代收敛越快，在程序设计中通常用相邻两次迭代敛越快，在程序设计中通常用相邻两次迭代 （为给定的精度要求）作为控制迭代结束的条件为给定的精度要求）作为控制迭代结束的条件 第50页，此课件共70页哦5168郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.4 判别收敛的几个常用条件迭代法收敛的判别条件：迭代法收敛的判别条件：1.Jacobi迭代法（简单迭代法）的收敛判定。2.Gauss-Seidel迭代法的收敛判定。3.SOR迭代法的收敛判定。第51页，此课件共70页哦5268郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis定理定理6.4.1 设设n阶方阵阶方阵 为对角占优阵为对角占优阵,则则 它是非奇异的。它是非奇异的。证证:因因A为对角占优阵为对角占优阵,其主对角元素的绝对值大其主对角元素的绝对值大 于同行其它元素绝对值之和于同行其它元素绝对值之和,且主对角元素且主对角元素 全不为全不为0,故对角阵故对角阵 为非奇异。为非奇异。作矩阵作矩阵 第52页，此课件共70页哦5368郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.4 判别收敛的几个常用条件利用对角占优知利用对角占优知 知知 非奇异非奇异,从而从而A非奇异非奇异,证毕证毕 系数矩阵为对角占优阵的线性方程组称作系数矩阵为对角占优阵的线性方程组称作对角对角占优方程组占优方程组。第53页，此课件共70页哦5468郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.4 判别收敛的几个常用条件定理定理6.4.2 对角占优线性方程组对角占优线性方程组 的雅可比的雅可比 迭代公式和高斯迭代公式和高斯-赛德尔迭代公式均收敛。赛德尔迭代公式均收敛。证证:雅可比迭代公式的迭代矩阵为雅可比迭代公式的迭代矩阵为 由定理由定理6.4.1知知,这时这时 ,再由再由定理定理6.3.2知迭代收敛知迭代收敛.再考察高斯再考察高斯-赛德尔迭代公式的迭代矩阵赛德尔迭代公式的迭代矩阵 第54页，此课件共70页哦5568郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.4 判别收敛的几个常用条件令令 ，则有，则有 即即 写出分量形式有写出分量形式有 设设 而而 由上式得由上式得 第55页，此课件共70页哦5668郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.4 判别收敛的几个常用条件由此整理得由此整理得 利用对角占优条件知上式右端小于利用对角占优条件知上式右端小于1,(1,(如果右端大于如果右端大于1,1,则得出与对角占优条件矛盾的结果则得出与对角占优条件矛盾的结果)故有故有据定理据定理6.3.26.3.2知知G-SG-S法收敛法收敛 第56页，此课件共70页哦5768郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis定理6.4.3 当系数矩阵当系数矩阵 A A 为正定矩阵，为正定矩阵，高斯高斯-塞德尔迭代收敛。塞德尔迭代收敛。定理6.4.4 松弛迭代收敛的必要条件是松弛迭代收敛的必要条件是00226.4 判别收敛的几个常用条件第57页，此课件共70页哦5868郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis 定理定理6.4.66.4.6 若A为对称正定矩阵时，则松弛迭代收敛的充要条件是 .定理定理 6.4.5 6.4.5 (松弛法收敛的充分条件)如果系数矩阵A为严格对角占优，当松弛因子 时，松弛迭代法收敛。6.4 判别收敛的几个常用条件第58页，此课件共70页哦5968郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.5 迭代法收敛判定的应用举例例例6.5.16.5.1 已知线性方程组已知线性方程组 考察用考察用JacobiJacobi迭代和迭代和G-SG-S迭代求解时的收敛性迭代求解时的收敛性解解:雅可比迭代矩阵雅可比迭代矩阵 第59页，此课件共70页哦6068郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.5 迭代法收敛判定的应用举例故故JacobiJacobi迭代收敛迭代收敛 第60页，此课件共70页哦6168郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.5 迭代法收敛判定的应用举例故高斯故高斯塞德尔迭代收敛。塞德尔迭代收敛。第61页，此课件共70页哦6268郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.5 迭代法收敛判定的应用举例例例6.5.26.5.2 设有迭代格式设有迭代格式 X(k+1)=B X(k)+g (k=0,1,2）其中其中B=I-A,如果如果A和和B的特征值全为正数，的特征值全为正数，试证：该迭代格式收敛。试证：该迭代格式收敛。分析分析:根据根据A，B和单位矩阵和单位矩阵I之间的特征值的关系之间的特征值的关系导出导出(B)1,从而说明迭代格式收敛。从而说明迭代格式收敛。第62页，此课件共70页哦6368郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.5 迭代法收敛判定的应用举例证证:因为因为B=I-A,故故(B)=(I)-(A)=1-(A)(A)+(B)=1 由于已知由于已知(A)和和 (B)全为正数，故全为正数，故 0(B)1,从而从而 (B)1 所以该迭代格式收敛。所以该迭代格式收敛。第63页，此课件共70页哦6468郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.5 迭代法收敛判定的应用举例例例6.5.36.5.3 设设 方程组方程组 写出解方程组的写出解方程组的Jacobi迭代公式和迭代矩阵迭代公式和迭代矩阵 并讨论迭代收敛的条件。并讨论迭代收敛的条件。写出解方程组的写出解方程组的Gauss-Seidel迭代矩阵迭代矩阵,并讨并讨 论迭代收敛的条件。论迭代收敛的条件。解解 Jacobi迭代公式和迭代公式和Jacobi矩阵分别为矩阵分别为 第64页，此课件共70页哦6568郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.5 迭代法收敛判定的应用举例当时当时 时时,Jacobi矩阵矩阵 G GJ J 1,1,对初值对初值x x(0)(0)均收敛均收敛第65页，此课件共70页哦6668郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis写出解方程组的写出解方程组的Gauss-Seidel迭代矩阵，并讨论迭代矩阵，并讨论 迭代收敛的条件。迭代收敛的条件。解解 Gauss-Seidel矩阵为矩阵为 当时当时 时时,Gauss-Seidel,Gauss-Seidel矩阵矩阵 G Gs s 1,1,所以对任意初值所以对任意初值x x(0)(0)均收敛。均收敛。6.5 迭代法收敛判定的应用举例第66页，此课件共70页哦6768郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis解：解：先计算迭代矩阵先计算迭代矩阵例例6.5.46.5.4 讨论用讨论用雅可比迭代法和雅可比迭代法和高斯高斯-塞德尔迭代塞德尔迭代 法解线性方程组法解线性方程组Ax=bAx=b的收敛性。的收敛性。第67页，此课件共70页哦6868郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis求特征值求特征值雅可比矩阵雅可比矩阵 (B)=1 用用雅可比迭代法求解时，迭代过程不收敛雅可比迭代法求解时，迭代过程不收敛 1=-1，2,3=1/2第68页，此课件共70页哦6968郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis求特征值求特征值高斯高斯-塞德尔迭代矩阵塞德尔迭代矩阵 (G1)=0.3536 1 用用高斯高斯-塞德尔迭代塞德尔迭代法求解时，迭代过程收敛法求解时，迭代过程收敛 1=0,第69页，此课件共70页哦7068郑州大学研究生2011-2012学年课程 数值分析 Numerical Analysis6.5 迭代法收敛判定的应用举例求解求解AX=b,AX=b,当当 取何取何值时迭代收敛？值时迭代收敛？解解:所给迭代公式的迭代矩阵为所给迭代公式的迭代矩阵为 例例6.5.56.5.5 给定线性方程组给定线性方程组 AX=bAX=b 用迭代公式用迭代公式 X X(K+1)(K+1)=X=X(K)(K)+(b-A(b-AX X(K)(K)(k=0,1,)(k=0,1,）第70页，此课件共70页哦