第六章线性方程组的迭代解法省公共课一等奖全国赛课获奖课件.pptx

第六章第六章 线性方程组迭代解线性方程组迭代解法法第二节第二节 迭代法收敛性迭代法收敛性上一页上一页 下一页下一页 返回返回 第三节第三节 超松弛迭代法超松弛迭代法第一节第一节 基本迭代方法基本迭代方法1第1页1 基本迭代方法基本迭代方法上一页上一页 下一页下一页 返回返回 一、问题提出一、问题提出1直接方法缺点直接方法缺点(以以Gauss消去法为代表消去法为代表)：对于低中阶数（对于低中阶数（n100）线性方程组十分有效，但）线性方程组十分有效，但n很很大时，尤其是由一些微分方程数值解所提出来线性方程组，大时，尤其是由一些微分方程数值解所提出来线性方程组，因为舍入误差积累以及计算机存贮困难，直接方法却无能为因为舍入误差积累以及计算机存贮困难，直接方法却无能为力。力。2处理方法：（利用迭代方法）处理方法：（利用迭代方法）迭代方法：把线性方程组数值求解问题化为一个迭代方法：把线性方程组数值求解问题化为一个迭代序列来实现。迭代序列来实现。2第2页上一页上一页 下一页下一页 返回返回 详细做法详细做法(2)取任意初始向量取任意初始向量x(0)组成迭代序列组成迭代序列:迭代格式：迭代格式：定义：定义：迭代矩阵：迭代矩阵：3第3页上一页上一页 下一页下一页 返回返回 迭代过程收敛：迭代过程收敛：若序列若序列x(k)极限存在，称此迭代过程极限存在，称此迭代过程收敛收敛，不，不然称为然称为发散发散。3.需要讨论问题：需要讨论问题：怎样建立迭代格式，迭代过程是否收敛，误怎样建立迭代格式，迭代过程是否收敛，误差分析，怎样加紧收敛速度等等。差分析，怎样加紧收敛速度等等。迭代迭代 法计算精度可控，尤其适合用于求解系数矩法计算精度可控，尤其适合用于求解系数矩阵为大型稀疏矩阵阵为大型稀疏矩阵/*sparse matrices*/方程组。方程组。因为迭代方法能因为迭代方法能防止防止系数矩阵中系数矩阵中零元存贮与计零元存贮与计算算，尤其适合用于解系数矩阵阶数很高而非零元极，尤其适合用于解系数矩阵阶数很高而非零元极少（即大型稀疏）线性方程组。少（即大型稀疏）线性方程组。4第4页二、二、Jacobi（雅可比）迭代法（雅可比）迭代法建立建立迭代格式迭代格式：能够缩写为：能够缩写为：按此格式迭代求解方按此格式迭代求解方法称为法称为雅可比迭代法雅可比迭代法,简称简称J法。法。上一页上一页 下一页下一页 返回返回 5第5页例例1 用雅可比迭代法解线性方程组用雅可比迭代法解线性方程组解解 生成雅可比迭代格式：生成雅可比迭代格式：kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15.111.0999931.1999931.299991121.0999981.1999981.299997上一页上一页 下一页下一页 返回返回 从上表能够看出，迭代序列收敛于从上表能够看出，迭代序列收敛于x*，若取，若取x(12)作为近似解，则误差不超出作为近似解，则误差不超出 10-56第6页写成写成矩阵形式矩阵形式：BJacobi 迭代阵，简记为迭代阵，简记为BJ上一页上一页 下一页下一页 返回返回 7第7页三、三、Gauss Seidel（高斯（高斯塞德尔）迭代法塞德尔）迭代法 写成写成矩阵形式矩阵形式：BGauss-Seidel 迭代阵，迭代阵，简记为简记为BGS上一页上一页 下一页下一页 返回返回 8第8页Gauss-Seidel迭代法分量形式为：迭代法分量形式为：上一页上一页 下一页下一页 返回返回 例例2 分别给出以下线性方程组分别给出以下线性方程组Jacobi迭代格式和迭代格式和Gauss-Seidel迭迭代格式：代格式：解解原方程等价于原方程等价于9第9页上一页上一页 下一页下一页 返回返回 建立建立Jacobi迭代格式以下迭代格式以下 建立建立Gauss-Seidel迭代格式以下迭代格式以下 10第10页上一页上一页 下一页下一页 返回返回 例例3 用高斯用高斯-塞德尔迭代法求解例塞德尔迭代法求解例1中方程组中方程组 建立建立Gauss-Seidel迭代格式迭代格式 解解迭代迭代8次可得次可得 在本例中在本例中Gauss-Seidel迭代法比迭代法比Jacobi迭代法收敛快。这个迭代法收敛快。这个结论在多数情况下成立，但高斯结论在多数情况下成立，但高斯-塞德尔收敛更加快是有条件。塞德尔收敛更加快是有条件。注：注：注：注：两种方法都存在两种方法都存在收敛性问题收敛性问题。有例子表明：有例子表明：Gauss-Seidel法收敛时，法收敛时，Jacobi法可能不收敛；法可能不收敛；而而Jacobi法收敛时，法收敛时，Gauss-Seidel法也可能不收敛。法也可能不收敛。11第11页2 迭代法收敛性迭代法收敛性收敛条件收敛条件迭代法收敛充要条件迭代法收敛充要条件:上一页上一页 下一页下一页 返回返回 定理定理 一、普通迭代法收敛性一、普通迭代法收敛性12第12页上一页上一页 下一页下一页 返回返回 例例4 设方程组系数矩阵为设方程组系数矩阵为 判别判别Jacobi迭代与迭代与Gauss-Seidel迭代是否收敛迭代是否收敛。解解 Jacobi迭代矩阵为迭代矩阵为 13第13页上一页上一页 下一页下一页 返回返回 所以，所以，Jacobi迭代法发散。迭代法发散。高斯高斯-塞德尔迭代矩阵为塞德尔迭代矩阵为 所以，高斯所以，高斯-塞德尔迭代法收敛。塞德尔迭代法收敛。困困 难难：详细问题中，：详细问题中，极难计算极难计算。14第14页定理定理 （充分条件）（充分条件）若存在一个矩阵范数使得若存在一个矩阵范数使得|B|1,则则迭代收敛，且有以下误差预计：迭代收敛，且有以下误差预计：证实：证实：上一页上一页 下一页下一页 返回返回 15第15页上一页上一页 下一页下一页 返回返回 上述定理只是判别迭代格式收敛上述定理只是判别迭代格式收敛充分条件充分条件，但若，但若 ，则不能下结论说迭代法发散，只能用，则不能下结论说迭代法发散，只能用进行判断。进行判断。由上述定理知由上述定理知B越小，收敛越快。越小，收敛越快。同时可取得迭代解事后误差预计，当同时可取得迭代解事后误差预计，当 （即迭代法（即迭代法收敛较快）时，可用以下停机准则控制迭代结束：收敛较快）时，可用以下停机准则控制迭代结束：注意：注意：16第16页上一页上一页 下一页下一页 返回返回 解：按照迭代公式有解：按照迭代公式有：所以，所以，J法和法和GS法必收敛，而且，法必收敛，而且，GS法比法比J法收敛快。法收敛快。17第17页上一页上一页 下一页下一页 返回返回 由此可见，实际计算结果也表明由此可见，实际计算结果也表明GS比比J法收敛快。法收敛快。18第18页上一页上一页 下一页下一页 返回返回 二、二、Jacobi迭代法和迭代法和Gauss-Seidel迭代法收敛性迭代法收敛性1 1、Jacobi方法收敛条件方法收敛条件 充要条件：充要条件：充分条件：充分条件：2 2、Gauss-Seidel方法收敛条件方法收敛条件充要条件：充要条件：充分条件：充分条件：19第19页定理定理 （充分条件）（充分条件）若若A 为为严格对角占优阵严格对角占优阵，则解，则解 Jacobi 和和 Gauss-Seidel 迭代法均收敛。迭代法均收敛。上一页上一页 下一页下一页 返回返回 3、其它判别条件、其它判别条件 定理定理 （充分条件）（充分条件）若若A 为为对称正定阵对称正定阵，则解，则解 Gauss-Seidel 迭代法收敛。迭代法收敛。定理定理 （充要条件）（充要条件）若若A 是是对角元为正实对称阵对角元为正实对称阵，则解，则解 Jacobi 迭代法收敛迭代法收敛20第20页例例6 6 给定给定Ax=b，其中，其中证实：证实：(1)(1)当当 时，时，A对称正定，从而对称正定，从而GS法收敛法收敛;考查考查A全部次序主子式全部次序主子式综上，当综上，当 时，时，A对称正定，由定理知对称正定，由定理知GS法收敛。法收敛。(2)(2)只有当只有当 时，时，J法收敛法收敛.证：证：(1)由题设知，由题设知，A为对称阵。为对称阵。A正定正定A全部次序主子式全大于零全部次序主子式全大于零.上一页上一页 下一页下一页 返回返回 21第21页综上，当综上，当 时，时，J法收敛。法收敛。(2)由由J法公式知法公式知J法收敛法收敛上一页上一页 下一页下一页 返回返回 22第22页上一页上一页 下一页下一页 返回返回 23第23页上一页上一页 下一页下一页 返回返回 2.Gauss-Seidel方法收敛条件方法收敛条件24第24页（1）列出求解该方程组）列出求解该方程组Jacobi迭代格式，并判别迭代格式，并判别是否收敛；是否收敛；（2）列出求解该方程组）列出求解该方程组Gauss-Seidel迭代格式，并迭代格式，并判别是否收敛；判别是否收敛；（3）取）取x(0)=(0,0,0)T，求，求Gauss-Seidel迭代法前两迭代法前两次迭代值次迭代值x(1),x(2).上一页上一页 下一页下一页 返回返回 25第25页上一页上一页 下一页下一页 返回返回 考查系数矩阵A及2D-A因为A及2D-A都正定，故Jacobi迭代法收敛。26第26页上一页上一页 下一页下一页 返回返回 考查系数矩阵A因为A对称正定，故Gauss-Seidel迭代法收敛。27第27页上一页上一页 下一页下一页 返回返回 28第28页上一页上一页 下一页下一页 返回返回 例例8.8.判别用判别用Jacobi迭代法与迭代法与Gauss-Seidel迭代法是否收敛，迭代法是否收敛，若收敛则写出其迭代格式。若收敛则写出其迭代格式。解解:(1).Jacobi迭代法迭代法 29第29页上一页上一页 下一页下一页 返回返回 所以所以Jacobi迭代法收敛。迭代法收敛。所求雅可比迭代格式为所求雅可比迭代格式为 30第30页上一页上一页 下一页下一页 返回返回 (2).Gauss-Seidel迭代法迭代法:Gauss-Seidel法迭代矩阵法迭代矩阵故故Gauss-Seidel迭代法发散。迭代法发散。31第31页3 超松弛迭代法超松弛迭代法换个角度看换个角度看Gauss-Seidel 方法：方法：其中其中ri(k+1)=余项余项相当于在相当于在 基础上基础上加个余项加个余项生成生成 。下面令下面令 ，希望经过选取适当，希望经过选取适当 来加来加速收敛，这就是速收敛，这就是逐次超松弛迭代法，逐次超松弛迭代法，简记简记SOR法法。iikikikiarxx)1()()1(+=称为称为松弛因子松弛因子 =1Gauss-Seidel 法法SOR法法/*Successive Over-Relaxation methods*/上一页上一页 下一页下一页 返回返回 32第32页写成写成矩阵形式矩阵形式：松弛迭代阵松弛迭代阵定理定理 设设 A 可逆，且可逆，且 aii 0，松弛法从任意松弛法从任意 出发对出发对某个某个 收敛收敛 (L )1)1。要计算要计算 (L）很很 复杂复杂 上一页上一页 下一页下一页 返回返回 33第33页定理定理 （必要条件）必要条件）设设 A 可逆，且可逆，且 aii 0，松弛法松弛法 从任意从任意 出发收敛出发收敛 0 0 2 2 。上一页上一页 下一页下一页 返回返回 定理定理 （充分条件）充分条件）若若A 对称正定，且有对称正定，且有 0 0 2 2，则，则松弛法从任意松弛法从任意 出发收敛出发收敛。例例9 建立下面方程组建立下面方程组SOR迭代格式迭代格式解：解：SOR迭代格式以下迭代格式以下34第34页上一页上一页 下一页下一页 返回返回 例例10 10 求方程组求方程组SOR迭代格式。迭代格式。解：原方程组等价方程组为解：原方程组等价方程组为SOR迭代格式以下迭代格式以下35第35页定理定理 若若 A 为为对称正定三对角阵对称正定三对角阵，则，则且且SOR最正确松弛因子最正确松弛因子/*optimal choice of for SOR method*/为为 ，此时，此时 。上一页上一页 下一页下一页 返回返回 对于对于SOR法，希望找法，希望找 使得使得 (L )最最小小。例例10 用用SOR法解方程组法解方程组36第36页上一页上一页 下一页下一页 返回返回 从上表可见，本例最正确松弛因子应该在从上表可见，本例最正确松弛因子应该在1和和1.1之间。之间。k0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1163 77 49 34 26 20 15 12 9 6 k1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.96 8 10 13 17 22 31 51 10537第37页