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