【教学课件】第六章解线性方程组的迭代法.ppt

第六章 解线性方程组的迭代法,6.1 引言6.2 基本迭代法6.3 迭代法的收敛性6.4 分块迭代法,6.1 引言,本章介绍求解线性方程组 的迭代求解方法，其中，。假设 非奇异，则方程组有唯一解。本章介绍迭代法的一些基本理论及Jacobi迭代法，Gauss-Seidel迭代法，超松弛迭代法等常用迭代法。迭代法的例例：用迭代法求解线性方程组：记为：，其中：,6.1 引言,已知其精确解为：。现将方程组改写成如下的等价形式：迭代法的例例：用迭代法求解线性方程组：记为：，其中：,6.1 引言,已知其精确解为：。现将方程组改写成如下的等价形式：或写为，其中：,6.1 引言,由此建立迭代格式（公式）：给定初始向量：，则可得：或写为，其中：,6.1 引言,由此建立迭代格式（公式）：给定初始向量：，则可得：当 时，有：，得近似解：，由此可以看出由迭代法产生的向量序列 逐步逼近方程组的精确解。,6.1 引言,例2：考虑方程组：，取初值，则有：可见不收敛。因此，我们得到：对于任何一个方程组，由迭代法产生的向量序列 不一定收敛。当 时，有：，得近似解：，由此可以看出由迭代法产生的向量序列 逐步逼近方程组的精确解。,6.1 引言,例2：考虑方程组：，取初值，则有：可见不收敛。因此，我们得到：对于任何一个方程组，由迭代法产生的向量序列 不一定收敛。为做进一步研究，我们假设方程组 有唯一解，则，又设 为任意初始向量，按下列公式构造向量序列：其中表示迭代次数，我们给出如下的定义：定义1：上述求解方法称为迭代法，如果 存在，则称迭代法收敛，否则称为迭代法发散。,6.1 引言,为讨论收敛性，引进误差向量，从而可得：，递推得到：要研究 的收敛性，就要研究 在满足什么条件时有，实际就是为做进一步研究，我们假设方程组 有唯一解，则，又设 为任意初始向量，按下列公式构造向量序列：其中表示迭代次数，我们给出如下的定义：定义1：上述求解方法称为迭代法，如果 存在，则称迭代法收敛，否则称为迭代法发散。,6.1 引言,为讨论收敛性，引进误差向量，从而可得：，递推得到：要研究 的收敛性，就要研究 在满足什么条件时有，实际就是,6.2 基本迭代法,设有方程组，其中 为非奇异矩阵下面研究如何建立解方程组 的各种迭代法。将 分裂为，其中 为可选择的非奇异矩阵，且使 容易求解，一般选择为 的某种近似称 为分裂矩阵。于是，求解 转化为求解，即求解：这样，可构造迭代法：其中：称为迭代法的迭代矩阵，选取 阵，就得到解 的各种迭代法。,6.2 基本迭代法,设，并将 写为三部分：这样，可构造迭代法：其中：称为迭代法的迭代矩阵，选取 阵，就得到解 的各种迭代法。,6.2 基本迭代法,设，并将 写为三部分：Jacobi迭代法 由，选取 为 的对角元素部分，即选取，可得Jacobi迭代公式：其中 称 为解 的Jacobi迭代法的迭代矩阵。,6.2 基本迭代法,Jacobi迭代法的分量表示 记由Jacobi迭代公式可得：，写成分量形式即为：于是，解 的Jacobi迭代法的计算公式为：Jacobi迭代法 由，选取 为 的对角元素部分，即选取，可得Jacobi迭代公式：其中 称 为解 的Jacobi迭代法的迭代矩阵。,6.2 基本迭代法,Jacobi迭代法的分量表示 记由Jacobi迭代公式可得：，写成分量形式即为：于是，解 的Jacobi迭代法的计算公式为：由此可知，Jacobi迭代法计算公式简单，每次迭代只需计算一次矩阵和向量的乘法且计算过程中 不变。,6.2 基本迭代法,Gauss-Seidel迭代法 我们再来分析前面的例子，其实在求 时，我们已经求得了，然而我们此时并没有用到 来计算，这使我们想到，应该尽可能利用已经计算出来得新的值，因此，可将上面的迭代公式改为：由此可知，Jacobi迭代法计算公式简单，每次迭代只需计算一次矩阵和向量的乘法且计算过程中 不变。,6.2 基本迭代法,Gauss-Seidel迭代法 我们再来分析前面的例子，其实在求 时，我们已经求得了，然而我们此时并没有用到 来计算，这使我们想到，应该尽可能利用已经计算出来得新的值，因此，可将上面的迭代公式改为：这就是所谓的Gauss-Seidel迭代法，用分裂矩阵的语言，这时选取的分裂矩阵 为 的下三角部分，即选取，于是由得到Gauss-Seidel迭代法：,6.2 基本迭代法,其中 称 为解方程组 的Gauss-Seidel迭代矩阵。至于Gauss-Seidel迭代法的分量表示，我们可由矩阵这就是所谓的Gauss-Seidel迭代法，用分裂矩阵的语言，这时选取的分裂矩阵 为 的下三角部分，即选取，于是由得到Gauss-Seidel迭代法：,6.2 基本迭代法,其中 称 为解方程组 的Gauss-Seidel迭代矩阵。至于Gauss-Seidel迭代法的分量表示，我们可由矩阵表示得到：即：写成分量形式得到：,6.2 基本迭代法,Jacobi迭代法和Gauss-Seidel迭代法的异同：Jacobi迭代法公式简单，每次只需做矩阵和向量的一次乘法，特别适合于并行计算；不足之处是需要存放 和 的两个存储空间。表示得到：即：写成分量形式得到：,6.2 基本迭代法,Jacobi迭代法和Gauss-Seidel迭代法的异同：Jacobi迭代法公式简单，每次只需做矩阵和向量的一次乘法，特别适合于并行计算；不足之处是需要存放 和 的两个存储空间。Gauss-Seidel方法只需要一个向量存储空间，一旦计算出 立即存入 的位置，可节约一套存储单元这是对Jacobi方法的改进，在某些情况下，它能起到加速收敛的作用。但它是一种典型的串行算法，每一步迭代中，必须依次计算解的各个分量。,6.2 基本迭代法,解大型稀疏线性方程组的逐次超松弛法 选取分裂矩阵 为带参数的下三角矩阵其中 为可选择的松弛因子，于是构造迭代法如下：其中：这就是解 的 逐次超松弛迭代法(SOR方法)。其分量形式为：,6.2 基本迭代法,关于SOR方法的几点注释：(1)显然，当 时，SOR方法就是Gauss-Seidel方法。(2)SOR方法每一次迭代的主要运算量是计算一次矩阵 与向量的乘法。(3)时称为超松弛方法，时称为低松弛方法。(4)计算机实现时可用 控制 迭代终止，或用 控制终止。(5)SOR方法可以看成是Gauss-Seidel方法的一种修正。,6.3 迭代法的收敛性,例：分别用Jacobi迭代法和Gauss-Seidel迭代法计算下列方程组，均取同样的初值，观察其计算结果。解：对方程组1，其精确解 Jacobi迭代得：Gauss-Seidel迭代得：对方程组2，其精确解 Jacobi迭代得：125次迭代可得精度为0.01的解；Gauss-Seidel迭代得：9次迭代可得精度为0.01的解；对方程组3，其精确解 Jacobi迭代得：Gauss-Seidel迭代得：,6.3 迭代法的收敛性,设，其中 为非奇异矩阵，记 为方程的精确解，的等价方程组为：，于是：设有解方程组 的一阶定常迭代法：我们希望研究的问题是：迭代矩阵满足什么条件时，迭代法产生的迭代序列 收敛到。引进误差向量其递推公式为：由本章引言可知：我们要研究的问题就是 满足什么条件时，有,6.3 迭代法的收敛性,定义2：设有矩阵序列 及，如果 个数列极限存在且有则称 收敛于，记为。例：设有矩阵序列且设，考查其极限。解：显然，当 时，有 矩阵序列极限概念可以用矩阵算子范数来描述。定理1：，其中 为矩阵的任意一种算子范数。,6.3 迭代法的收敛性,证明：显然有再利用矩阵范数的等价性，可证定理对其他算子范数亦对。定理2：对任何向量 都有 定理3：设，则 的充分必要条件是矩阵 的谱半径。证明：由矩阵 的若当标准型，存在非奇异矩阵 使 其中若当块,6.3 迭代法的收敛性,且，显然有：，其中：于是 下面考查 的情况，引进记号：显然有：，由于因此：,6.3 迭代法的收敛性,利用极限 得到所以 的充要条件是，即定理4：（迭代法基本定理）设有方程组，对于任意的初始向量，一阶定常迭代法 收敛的充要条件是迭代矩阵 的谱半径。,6.3 迭代法的收敛性,证：的特征值，故 的特征值 从而有：，因此 有唯一解。定义 为误差向量，则有：故对任意的 和，有：即：设对任意的 和，均有：且于是有，即，所以对任意的 有 故，从而由定理3，有。定理4是一阶定常迭代法的基本理论。,6.3 迭代法的收敛性,推论：设，其中 为非奇异矩阵且 非奇异，则：(1)解方程组的Jacobi迭代法收敛的充要条件是其中(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 迭代法的收敛性,关于解某些特殊方程组迭代法的收敛性 定义3：(对角占优阵)设(1)如果 元素满足称 为严格对角占优阵(2)如果 元素满足且上式至少有一个不等式严格成立，称 为弱对角占优阵。,6.3 迭代法的收敛性,定义4：(可约与不可约矩阵)设，如果存在置换阵 使其中 为 阶方阵，为 阶方阵，则称 为可约矩阵，否则，如果不存在这样的置换阵 使得上式成立，则称 为不可约矩阵。,6.3 迭代法的收敛性,定理6：(对角占优定理)如果 为严格对角占优矩阵或 为不可约弱对角占优矩阵，则 为非奇异矩阵。证明：我们只就严格对角占优证明定理。采用反证法。，则 有非零解，记为 则，由齐次方程组第 个方程得到，即与对角占优的假设矛盾，故。,6.3 迭代法的收敛性,定理7：设，如果：(1)为严格对角占优，则解 的Jacobi迭代法，Gauss-Seidel迭代法均收敛。(2)为弱对角占优，且 为不可约矩阵，则解 的Jacobi迭代法，Gauss-Seidel迭代法均收敛。证明：这里我们仅证(1)的Gauss-Seidel迭代法。由假设可知：，Gauss-Seidel迭代矩阵为，因此由于 于是 的特征值为 的根，记,6.3 迭代法的收敛性,下面证明：当 时，即 的特征值均满足，由基本定理，则有Gauss-Seidel迭代法收敛。事实上，当 时，由 A 为严格对角占优，有这说明，当 时，矩阵 为严格对角占优，再由对角占优定理有。定理8：(SOR方法收敛的必要条件)设解方程组的SOR迭代法收敛，则。证明：由SOR迭代法收敛，则可得，设 的特征值为，则 从而,6.3 迭代法的收敛性,另一方面从而，即。定理9：设，如果：(1)为对称正定矩阵，(2)则解 的SOR迭代法收敛。证明：我们只需在上述假设下，证明 即可。事实上，设 为对应于 的特征向量，即亦即：为了找到 的表达式，考虑数量积,6.3 迭代法的收敛性,则显然记：由于，所以，故所以从而,6.3 迭代法的收敛性,当 时，有即 的任一特征值满足，故SOR方法收敛(注意当 时，可以证明)定理10：设，如果：(1)为严格对角占优矩阵(或不可约弱对角占优矩阵)(2)则解 的SOR迭代法收敛。（证明略）,6.3 迭代法的收敛性,迭代法的收敛速度 我们已经知道，如果 且 越小时，迭代法收敛越快，现考虑方程组及一阶定常迭代法且设迭代法收敛，记，则。由基本定理有，且误差向量 满足，故 现设 为对称矩阵，则有,6.3 迭代法的收敛性,下面确定欲使初始误差缩小 所需的迭代次数，即使取对数，得到所需最少迭代次数为：故所需迭代次数与 成反比，越小，越大，从而所需迭代次数越少，收敛越快 定义5：称 为迭代法的渐进收敛速度，简称收敛速度。对于SOR迭代法来说，希望通过 的选择使得收敛速度较快，但具体计算时，并非都可实现。,6.3 迭代法的收敛性,SOR迭代法的算法 设，其中 为对称正定矩阵或为严格对角占优或为不可约弱对角占优，本算法用SOR迭代法求解，数组 存放 及，用 控制迭代终止，用 表示最大迭代次数。1.2.3.4.5.对于(1)(2)如果，则(3)6.输出7.如果，则输出 停止；8.如果，则转3；9.输出 及有关信息。,6.4 分块迭代法,前面讨论的迭代法，从 的计算过程，是逐个计算 的分量，因此这种方法又被称为点迭代法。现在介绍分块迭代法，就是一组未知量同时被改进。设，其中 为大型稀疏矩阵且将 分块为三个部分，其中,6.4 分块迭代法,其中 为 非奇异矩阵，对 及 同样分块其中，在上述定义的基础上，我们来讨论分块迭代法。(1)块Jacobi迭代法(BJ)选取分裂矩阵 为 的对角块部分，即选取,6.4 分块迭代法,于是，得到块Jacobi迭代法其中迭代矩阵，或由分块矩阵乘法，得到块Jacobi迭代法的具体形式：其中：这说明，块Jacobi迭代法每迭代一步需要求解 个低阶方程组,6.4 分块迭代法,(2)块SOR迭代法(BSOR)选取分裂矩阵 为带松弛因子的 块下三角部分，即：得到块SOR迭代法其中迭代矩阵 由分块矩阵乘法得到块SOR迭代法的具体形式：于是，可通过解一组低阶的方程组来代替原来的解。,6.4 分块迭代法,定理：设，其中(1)如果 为对称正定矩阵；(2)则解 的块SOR迭代法收敛。,