《高斯-塞德尔迭代法ppt课件.ppt》由会员分享，可在线阅读，更多相关《高斯-塞德尔迭代法ppt课件.ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目第第6 6章章 解线性方程组的迭代法解线性方程组的迭代法1认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目6.1 引引 言言 考虑线性方程组（1.1）其中 为非奇异矩阵，当 为低阶稠密矩阵时，第5章所讨论的选主元消去法是有效方法.但对于 的阶数 很大，零元素较多的大型稀疏矩阵方程组，例如求某些偏微分方程数值解所产生的线性方程组来说，利用迭代法求解则更为合适.迭代法通常都可利用 中有大量零元素的特点.2认识到了
2、贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 例例1 1（1.2）记为 ,方程组的精确解是 .求解方程组 其中 现将(1.2)改写为 3认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目（1.3）或写为 ,其中 4认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 将这些值代入(1.3)式右边(若(1.3)式为等式即求得方程组的解，但一般不满足).任取初始值，例如取 .再将 分量代入(1.3)式
3、右边得到 ，反复利用这个计算程序，得到一向量序列和一般的计算公式(迭代公式)得到新的值 5认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目（1.4）简写为 其中 表示迭代次数 迭代到第10次有 6认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 从此例看出，由迭代法产生的向量序列 逐步逼近方程组的精确解 .对于任何由 变形得到的等价方程组 ，迭代法产生的向量序列 不一定都能逐步逼近方程组的解 .如对方程组7认识到了贫困户贫困的根本原因，才能开始对症下药，然
4、后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目构造迭代法则对任何的初始向量，得到的序列都不收敛.对于给定方程组 ，设有唯一解 ，（1.5）又设 为任取的初始向量，（1.6）其中 表迭代次数.则 按下述公式构造向量序列 8认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 定义定义1 1(1)对于给定的方程组 ，逐步代入求近似解的方法称为迭代法迭代法(或称为一阶定常迭代法，这里 与 无关).(2)如果 存在(记为 )，显然 就是方程组的解，否则称此迭代法发散迭代法发散.用公式(1.6)称此迭代法收敛迭代法收
5、敛，研究 的收敛性.引进误差向量 由(1.6)减去(1.5)式，得 ，9认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 要考察 的收敛性,就要研究 在什么条件下有亦即要研究 满足什么条件时有递推得 10认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目6.2 基本迭代法基本迭代法 设有（2.1）其中，为非奇异矩阵.将 分裂为（2.2）其中，为可选择的非奇异矩阵，且使 容易求解，一般选择为 的某种近似，称 为分裂矩阵分裂矩阵.11认识到了贫困户贫困的根本原因
6、，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 于是，求解 转化为求解 ，即求解可构造一阶定常迭代法（2.3）其中 称 为迭代法的迭代矩阵.12认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 选取 阵，就得到解 的各种迭代法.设 ,并将 写为三部分（2.4）13认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 6.2.1 雅可比迭代法雅可比迭代法 由 ，选取 为 的对角元素部分，解 的雅可比(Jacobi)迭代
7、法 即选取 (对角阵)，（2.5）其中 称 为解 的雅可比迭代法的迭代阵.由(2.3)式得到14认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 研究雅可比迭代法(2.5)的分量计算公式.记 由雅可比迭代公式(2.5),有 或 于是，解 的雅可比迭代法的分量计算公式为 15认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目（2.6）由(2.6)式可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵 始终不变.16认识到了
8、贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目(下三角阵)，6.2.2 高斯高斯-塞德尔迭代法塞德尔迭代法 选取分裂矩阵 为 的下三角部分，即选取 于是由(2.3)式得到解（2.7）其中 称 为解 的高斯-塞德尔迭代法的迭代阵.的高斯-塞德尔(Gauss-Seidel)迭代法 17认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 研究高斯-塞德尔迭代法的分量计算公式.由(2.7)式有 或 即 记 18认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。
9、近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目于是解 的高斯-塞德尔迭代法计算公式为（2.8）或（2.9）19认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目而由高斯-塞德尔迭代公式可知，雅可比迭代法不使用变量的最新信息计算 ，计算 的第 个分量 时，利用了已经计算出的最新分量 .由(2.8)可知，高斯-塞德尔迭代法每迭代一次只需计算一次矩阵与向量的乘法.高斯-塞德尔迭代法可看作雅可比迭代法的一种改进.算法算法1 1(高斯-塞德尔迭代法)设 ，其中 为非奇异矩阵且本算法用高斯-塞德尔迭代法解 ，20认识到了贫困户贫
10、困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 迭代一次，这个算法需要的运算次数至多与矩阵 的非零元素的个数一样多.数组 开始存放 ,后存放为最大迭代次数.21认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 例例2 2按高斯-塞德尔迭代公式迭代7次，得 ，（1.2）用高斯-塞德尔迭代法解线性方程组(1.2).取 ，22认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 由此例可知，用高斯-塞德尔迭代法
11、，雅可比迭代法解线性方程组(1.2)(且取 )均收敛.而高斯-塞德尔迭代法比雅可比迭代法收敛较快(即取 相同，达到同样精度所需迭代次数较少).但这结论只当 满足一定条件时才是对的.且 23认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 6.2.3 解大型稀疏线性方程组的逐次超松弛迭代法解大型稀疏线性方程组的逐次超松弛迭代法 选取分裂矩阵 为带参数的下三角阵 其中 为可选择的松弛因子.于是，由(2.3)可构造一个迭代法，其迭代矩阵为 从而得到解 的逐次超松弛迭代法(Successive Over Relaxation Met
12、hod,简称SOR方法).24认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 解 的SOR方法为（2.10）其中 研究解 的SOR迭代法的分量计算公式.记 25认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目或 由(2.10)式可得 由此，得到解 的SOR方法的计算公式（2.11）26认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目或（2.12）关于SOR迭代法，有 (1)显然，当 时
13、，SOR方法即为高斯-塞德尔迭代法.27认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 (2)SOR方法每迭代一次主要运算量是计算一次矩阵与向量的乘法.(3)当 时，称为超松弛法；当 时，称为低松弛法.(4)在计算机实现时可用 控制迭代终止，或用 控制迭代终止.SOR迭代法是高斯-塞德尔迭代法的一种修正.28认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 设已知 及已计算 的分量 (1)首先用高斯-塞德尔迭代法定义辅助量（2.13）(2)再由 与 加权
14、平均定义 ，将(2.13)代入(2.14)得到解 的SOR迭代(2.11)式.即（2.14）29认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 例例3 3它的精确解为 取 ，迭代公式为 用SOR方法解方程组 解解30认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目取 ，取其他 值，迭代次数如下表.第11次迭代结果为 31认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 从此例看到，松弛
15、因子选择得好，会使SOR迭代法的收敛大大加速.本例中 是最佳松弛因子.32认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目6.3 迭代法的收敛性迭代法的收敛性 6.3.1 一阶定常迭代法的基本定理一阶定常迭代法的基本定理 设（3.1）其中 为非奇异矩阵，记 为(3.1)精确解，于是（3.2）且设有等价的方程组33认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 设有解 的一阶定常迭代法（3.3）问题是：迭代矩阵 满足什么条件时，由迭代法产生的向量序列 收敛
16、到 引进误差向量 由(3.3)式减(3.2)式得到误差向量的递推公式 34认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 由6.1节可知，研究迭代法(3.3)收敛性问题就是要研究迭代矩阵 满足什么条件时，有 定义定义2 2设有矩阵序列 及 ,如果 个数列极限存在且有 则称 收敛于 ，记为 35认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 例例4 4且设 ，考查其极限.解解由于，当 时，有 设有矩阵序列 所以36认识到了贫困户贫困的根本原因，才能开始对
17、症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 矩阵序列极限概念可以用矩阵算子范数来描述.定理定理1 1 证明证明再利用矩阵范数的等价性，可证定理对其他算子范数亦对.定理定理2 2 对任何向量 都有其中为矩阵的任意一种算子范数.显然有（证明略）37认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 定理定理3 3 设 ,则 (零矩阵)的充分必要条件是矩阵 的谱半径 证明证明由矩阵 的若当标准型，存在非奇异矩阵 使 其中若当块 38认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年
18、来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目且 ，其中 于是 下面考查 的情况.显然有引进记号 39认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 显然有，由于 ,因此 40认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目其中 利用极限 ，所以 的充要条件是 ，得到即 41认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 定理定理4 4（3.4）(迭代法基本定理)设有方程组 及
19、一阶定常迭代法（3.5）对任意选取初始向量 ，矩阵 的谱半径 迭代法(3.5)收敛的充要条件是 证明证明设 ，易知 )有唯一解，记为 ，充分性.(其中则 42认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目误差向量 由设 ，应用定理3，有 于是对任意 ,有 ，必要性.设对任意 有 其中 即 显然，极限 是方程组(3.4)的解，且对任意 有 43认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目由定理2知 再由定理3，即得 推论推论设 ，其中 为非奇异矩阵且
20、非奇异，则 (1)解方程组的雅可比迭代法收敛的充要条件是 ，其中 (2)解方程组的高斯-塞德尔迭代法收敛的充要条件是其中 (3)解方程组的SOR方法收敛的充要条件是 ，其中 44认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 例例5 5迭代矩阵 的特征方程为 解得 考察用雅可比方法解方程组（1.2）的收敛性.（1.2）即 .所以用雅可比迭代法解方程组(1.2)是收敛的.45认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 例例6 6的收敛性，解解考察用迭
21、代法解方程组 其中特征方程为特征根 即 .这说明用迭代法解此方程组不收敛.46认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 定理定理5 5及一阶定常迭代法 如果有 的某种算子范数 ，(1)迭代法收敛，即对任取 有(迭代法收敛的充分条件)设有方程组 则 47认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 证明证明 (2)由关系式 及 反复利用(b)即得(2).(1)由基本定理4结论(1)是显然的.有 48认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 (3)考查 即 (4)反复利用(a),则得到(4).49