第5章-线性方程组的迭代法.ppt

* 第二章 线性方程组的迭代解法 第二节 迭代法的收敛性 第三节 超松弛迭代法 第一节 基本迭代方法 * §1 基本迭代方法 一、问题的提出 1．直接方法的缺陷(以Gauss消去法为代表)： 对于低中阶数（n≤100）的线性方程组十分有效，但n很大时，特别是由某些微分方程数值解所提出来的线性方程组，由于舍入误差的积累以及计算机的存贮困难，直接方法却无能为力。 2．解决方法：（利用迭代方法） 迭代方法：把线性方程组的数值求解问题化为一个迭代序列来实现。 * 具体做法 (2) 取任意初始向量x(0)构成迭代序列: 由于迭代方法能避免系数矩阵中零元的存贮与计算，特别适用于解系数矩阵阶数很高而非零元极少（即大型稀疏）的线性方程组。 * 迭代格式： 定义： 迭代矩阵： 迭代过程收敛： 若序列{x(k)}极限存在，称此迭代过程收敛，否则称为发散。 迭代 法计算精度可控，特别适用于求解系数为大型稀疏矩阵 /* sparse matrices */ 的方程组。 * 迭代法要解决的主要问题如下 ： 1.如何构造迭代格式？ 2.构造的格式所产生的序列在什么情况下收敛？ 3.如果收敛，收敛的速率如何？ 4.近似解的误差估计。 迭代方程 迭代格式 方程 迭代初值 收敛 如何构造迭代方程 * 二、Jacobi （雅可比）迭代法 建立迭代格式： 可以缩写为： 按此格式迭代求解的方法称为雅可比迭代法,简称J法。 * 例1 用雅可比迭代法解线性方程组 解 生成雅可比迭代格式： k x1(k) x2(k) x3(k) 1 0.72 0.83 0.84 2 0.971 1.07 1.15 …… …… ……. …… 11 1.099993 1.199993 1.299991 12 1.099998 1.199998 1.299997 从上表可以看出，迭代序列收敛于x*，若取x(12)作为近似解，则误差不超过 10-5 * 写成矩阵形式： B Jacobi 迭代阵，简记为BJ * 三、Gauss – Seidel（高斯—塞德尔）迭代法 … … … … 写成矩阵形式： B Gauss-Seidel 迭代阵，简记为BGS * Gauss-Seidel迭代法的分量形式为： 例2 分别给出以下线性方程组的Jacobi迭代格式和Gauss-Seidel迭代格式： 解 原方程等价于 * 建立Jacobi迭代格式如下 建立Gauss-Seidel迭代格式如下 * 例4 用高斯-塞德尔迭代法求解例1中的方程组 建立Gauss-Seidel迭代格式 解 迭代8次可得 在本例中Gauss-Seidel迭代法比Jacobi迭代法收敛快。这个结论在多数情况下成立，但高斯-塞德尔的收敛更快是有条件的。 注：两种方法都存在收敛性问题。 有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时， Gauss-Seidel法也可能不收敛。 * §2 迭代法的收敛性 的收敛条件 迭代法收敛的充要条件: 定理 一、一般迭代法的收敛性 * ①上述定理只是判别迭代格式收敛的充分条件，但若 ，则不能下结论说迭代法发散，只能用 进行判断。 ②由上述定理知‖B‖=q 越小，收敛越快。 同时可获得迭代解的事后误差估计，当 （即迭代法收敛较快）时，可用如下停机准则控制迭代结束： 注意： * 二、Jacobi迭代法和Gauss-Seidel迭代法的收敛性 1、Jacobi方法收敛的条件 充要条件： 充分条件： 2、Gauss-Seidel方法收敛的条件 充要条件： 充分条件： * 定理 （充分条件）若A 为严格对角占优阵 ，则解 的Jacobi 和 Gauss - Seidel 迭代法均收敛。 3、其它判别条件 * 上一页 下一页 返回 * 上一页 下一页 返回 2. Gauss-Seidel方法收敛的条件 * （1）列出求解该方程组的Jacobi迭代格式，并判别是否收敛； （2）列出求解该方程组的Gauss-Seidel迭代格式，并判别是否收敛； （3）取x(0)=(0,0,0)T，求Gauss-Seidel迭代法的前两次迭代值x(1) , x(2) . 上一页 下一页 返回 * 上一页 下一页 返回 考察系数矩阵A及2D-A 由于A及2D-A都正定，故Jacobi迭代法收敛。 * 上一页