《计算方法第六章print》由会员分享，可在线阅读，更多相关《计算方法第六章print（40页珍藏版）》请在金锄头文库上搜索。
1、第六章 解线性方程组的迭代法6.1 引言6.2 基本迭代法6.3 迭代法的收敛性6.4 分块迭代法6.1 引言本章介绍求解线性方程组 的迭代求解方 法，其中 ， 。假设 非奇 异，则方程组有唯一解 。本章介绍迭代法的一些基本理论及Jacobi迭代法，Gauss-Seidel迭代法，超松弛迭代法等常用迭代法。n迭代法的例 例：用迭代法求解线性方程组：记为： ，其中：6.1 引言已知其精确解为： 。现将方程组改写成如下的 等价形式：或写为 ，其中： 6.1 引言由此建立迭代格式（公式）：给定初始向量： ，则可得：当 时，有： ，得近似解：，由此可以看出由迭代法产生 的向量序列 逐步逼近方程组的精确
2、解 。k1234 x10.7780.9630.9930.999 x20.8000.9640.9930.999 x30.8670.9720.9950.9996.1 引言例2：考虑方程组： ，取初值 ，则有： 可见不收敛。因此，我们得到：对于任何一个方程组 ， 由迭代法产生的向量序列 不一定收敛。 为做进一步研究，我们假设方程组 有唯一解，则 ， 又设 为任意初始向量，按下 列公式构造向量序列： 其中 表示迭代次数，我们给出如下的定义：定义1：上述求解方法称为迭代法，如果 存 在，则称迭代法收敛，否则称为迭代法发散。6.1 引言为讨论收敛性，引进误差向量 ，从而可 得： ，递推得到：要研究 的收敛
3、性，就要研究 在满足什么条 件时有 ，实际就是6.2 基本迭代法设有方程组 ，其中 为非奇异矩阵 下面研究如何建立解方程组 的各种迭代法。将 分裂为 ，其中 为可选择的非奇异矩 阵，且使 容易求解，一般选择为 的某种近似 称 为分裂矩阵。于是，求解 转化为求解 ，即求解：这样，可构造迭代法：其中： 称 为迭代法的迭代矩阵，选取 阵，就得到解 的各 种迭代法。6.2 基本迭代法设 ，并将 写为三部分：nJacobi迭代法由 ，选取 为 的对角元素部分， 即选取 ， ，可得Jacobi迭代公式：其中 称 为解 的Jacobi迭代法的迭代矩阵。6.2 基本迭代法nJacobi迭代法的分量表示记 由J
4、acobi迭代公式可得： ，写成分量形式即为：于是，解 的Jacobi迭代法的计算公式为：由此可知，Jacobi迭代法计算公式简单，每次迭代只 需计算一次矩阵和向量的乘法且计算过程中 不变。6.2 基本迭代法nGauss-Seidel迭代法 我们再来分析前面的例子，其实在求 时，我们 已经求得了 ，然而我们此时并没有用到 来计算，这使我们想到，应该尽可能利用已经计算出 来得新的值 ，因此，可将上面的迭代公式改为：这就是所谓的Gauss-Seidel迭代法，用分裂矩阵的语 言，这时选取的分裂矩阵 为 的下三角部分，即选 取 ， 于是由得到Gauss-Seidel迭代法：6.2 基本迭代法其中 称
5、 为 解方程组 的Gauss-Seidel迭代矩阵。至于Gauss-Seidel迭代法的分量表示，我们可由矩阵 表示得到：即： 写成分量形式得到：6.2 基本迭代法nJacobi迭代法和Gauss-Seidel迭代法的异同：Jacobi迭代法公式简单，每次只需做矩阵和向量的一次乘法，特别适合于并行计算；不足之处是需要存放 和 的两个存储空间。Gauss-Seidel方法只需要一个向量存储空间，一旦计算出 立即存入 的位置，可节约一套存储单元这是对Jacobi方法的改进，在某些情况下，它能起到加速收敛的作用。但它是一种典型的串行算法，每一步迭代中，必须依次计算解的各个分量。6.2 基本迭代法n解
6、大型稀疏线性方程组的逐次超松弛法选取分裂矩阵 为带参数的下三角矩阵 其中 为可选择的松弛因子，于是构造迭代法如 下：其中： 这就是解 的 逐次超松弛迭代法(SOR方法)。其 分量形式为：6.2 基本迭代法n关于SOR方法的几点注释： (1) 显然，当 时，SOR方法就是Gauss-Seidel方法。 (2) SOR方法每一次迭代的主要运算量是计算一次矩阵 与向量的乘法。 (3) 时称为超松弛方法， 时称为低松弛方法。 (4) 计算机实现时可用 控制迭代终止，或用 控制终止。 (5) SOR方法可以看成是Gauss-Seidel方法的一种修正。6.3 迭代法的收敛性例：分别用Jacobi迭代法和
7、Gauss-Seidel迭代法计 算下列方程组，均取同样的初值 ，观察其计 算结果。解：对方程组1，其精确解Jacobi迭代得：Gauss-Seidel迭代得：对方程组2，其精确解Jacobi迭代得：125次迭代可得精度为0.01的解；Gauss-Seidel迭代得： 9次迭代可得精度为0.01的解；对方程组3，其精确解Jacobi迭代得：Gauss-Seidel迭代得：6.3 迭代法的收敛性设 ，其中 为非奇异矩阵，记 为方程 的精确解， 的等价方程组为： ，于是：设有解方程组 的一阶定常迭代法：我们希望研究的问题是：迭代矩阵满足什么条件时， 迭代法产生的迭代序列 收敛到 。引进误差向量其递
8、推公式为：由本章引言可知：我们要研究的问题就是 满足什么 条件时，有6.3 迭代法的收敛性定义2：设有矩阵序列 及 ， 如果 个数列极限存在且有则称 收敛于 ，记为 。例：设有矩阵序列且设 ，考查其极限。解：显然，当 时，有矩阵序列极限概念可以用矩阵算子范数来描述。定理1： ，其中 为矩阵的 任意一种算子范数。6.3 迭代法的收敛性证明：显然有再利用矩阵范数的等价性，可证定理对其他算子范数 亦对。定理2： 对任何向量 都有定理3：设 ，则 的充分必要条件 是矩阵 的谱半径 。证明：由矩阵 的若当标准型，存在非奇异矩阵 使其中若当块6.3 迭代法的收敛性且 ，显然有： ，其中：于是下面考查 的情
9、况，引进记号：显然有： ，由于因此：6.3 迭代法的收敛性利用极限 得到所以 的充要条件是 ，即 定理4：（迭代法基本定理）设有方程组 ，对于任意的初始向量 ， 一阶定常迭代法 收敛的充要条件是迭代 矩阵 的谱半径 。6.3 迭代法的收敛性证： 的特征值 ，故 的特征值 从而有：，因此 有唯一解 。定义 为误差向量，则有：故对任意的 和 ，有： 即：设对任意的 和 ，均有： 且 于是有 ，即 ，所以对任意 的 有 故 ，从而由定理3， 有 。定理4是一阶定常迭代法的基本理论。6.3 迭代法的收敛性推论：设 ，其中 为非奇异矩阵且 非奇异，则：(1) 解方程组的Jacobi迭代法收敛的充要条件是
10、 其中(2) 解方程组的Gauss-Seidel迭代法收敛的充要条件 是 ，其中(3) 解方程组的SOR迭代法收敛的充要条件是 其中6.3 迭代法的收敛性迭代法的基本定理在理论上有重要意义。在具体使 用上，由于 ，因此，我们利用范数可以建立 判别迭代法收敛的充分条件。定理5：（迭代法收敛的充分条件）设方程组 的一阶定常迭代法为 如果有 的某种算子范数 ，则(1) 迭代法收敛，即对任取 有且(2)(3)(4)6.3 迭代法的收敛性证明：(1)由定理4，结论(1)是显然的；(2)由 及 得：(a) (b)反复利用(b)即得(2)；(3)注意到即得：(4)反复利用(a)即得(4)。6.3 迭代法的收敛性n关于解某些特殊方程组迭代法的收敛性定义3：(对角占优阵)设 (1) 如果 元素满足称 为严格对角占优阵(2) 如果 元素满足且上式至少有一个不等式严格成立，称 为弱对角占优阵。6.3 迭代法的收敛性定义4：(可约与不可约矩阵)设 ， 如果存在置换阵 使其中 为 阶方阵， 为 阶方阵 ，则称 为可约矩阵，否则，如果不存在这样的置换阵 使得 上式成立，则称 为不可约矩阵。6.3 迭代法的收敛性定理6：(对角占优定理) 如果 为严格对角占 优矩阵或 为不可约弱对角占优矩阵，则 为非奇异 矩阵。证明：我们只就严格对角占优证明定理。采用反证 法。 ，则
