计算方法第六章print课件

第六章解线性方程组的迭代法6.1引言6.2基本迭代法6.3迭代法的收敛性6.4分块迭代法第六章解线性方程组的迭代法6.1引言16.1引言本章介绍求解线性方程组的迭代求解方法，其中，。假设非奇异，则方程组有唯一解。本章介绍迭代法的一些基本理论及Jacobi迭代法，Gauss-Seidel迭代法，超松弛迭代法等常用迭代法。迭代法的例例：用迭代法求解线性方程组：记为：，其中：6.1引言本章介绍求解线性方程组的迭代求26.1引言已知其精确解为：。现将方程组改写成如下的等价形式：或写为，其中：

6.1引言已知其精确解为：。现将方程36.1引言由此建立迭代格式（公式）：

给定初始向量：，则可得：当时，有：，得近似解：，由此可以看出由迭代法产生的向量序列逐步逼近方程组的精确解。k1234x10.7780.9630.9930.999x20.8000.9640.9930.999x30.8670.9720.9950.9996.1引言k1234x10.7780.9630.9930.46.1引言例2：考虑方程组：，取初值，则有：可见不收敛。因此，我们得到：对于任何一个方程组，由迭代法产生的向量序列不一定收敛。为做进一步研究，我们假设方程组有唯一解，则，又设为任意初始向量，按下列公式构造向量序列：其中表示迭代次数，我们给出如下的定义：定义1：上述求解方法称为迭代法，如果存在，则称迭代法收敛，否则称为迭代法发散。6.1引言例2：考虑方程组：56.1引言为讨论收敛性，引进误差向量，从而可得：，递推得到：要研究的收敛性，就要研究在满足什么条件时有，实际就是6.1引言为讨论收敛性，引进误差向量66.2基本迭代法设有方程组，其中为非奇异矩阵下面研究如何建立解方程组的各种迭代法。将分裂为，其中为可选择的非奇异矩阵，且使容易求解，一般选择为的某种近似称为分裂矩阵。于是，求解转化为求解，即求解：这样，可构造迭代法：其中：称为迭代法的迭代矩阵，选取阵，就得到解的各种迭代法。6.2基本迭代法设有方程组，其中76.2基本迭代法设，并将写为三部分：Jacobi迭代法由，选取为的对角元素部分，即选取，，可得Jacobi迭代公式：其中称为解的Jacobi迭代法的迭代矩阵。6.2基本迭代法设86.2基本迭代法Jacobi迭代法的分量表示记由Jacobi迭代公式可得：，写成分量形式即为：于是，解的Jacobi迭代法的计算公式为：由此可知，Jacobi迭代法计算公式简单，每次迭代只需计算一次矩阵和向量的乘法且计算过程中不变。6.2基本迭代法Jacobi迭代法的分量表示96.2基本迭代法Gauss-Seidel迭代法我们再来分析前面的例子，其实在求时，我们已经求得了，然而我们此时并没有用到来计算，这使我们想到，应该尽可能利用已经计算出来得新的值，因此，可将上面的迭代公式改为：这就是所谓的Gauss-Seidel迭代法，用分裂矩阵的语言，这时选取的分裂矩阵为的下三角部分，即选取，于是由得到Gauss-Seidel迭代法：6.2基本迭代法Gauss-Seidel迭代法106.2基本迭代法其中称为解方程组的Gauss-Seidel迭代矩阵。至于Gauss-Seidel迭代法的分量表示，我们可由矩阵表示得到：即：写成分量形式得到：6.2基本迭代法116.2基本迭代法Jacobi迭代法和Gauss-Seidel迭代法的异同：Jacobi迭代法公式简单，每次只需做矩阵和向量的一次乘法，特别适合于并行计算；不足之处是需要存放和的两个存储空间。Gauss-Seidel方法只需要一个向量存储空间，一旦计算出立即存入的位置，可节约一套存储单元这是对Jacobi方法的改进，在某些情况下，它能起到加速收敛的作用。但它是一种典型的串行算法，每一步迭代中，必须依次计算解的各个分量。6.2基本迭代法Jacobi迭代法和Gauss-Seide126.2基本迭代法解大型稀疏线性方程组的逐次超松弛法选取分裂矩阵为带参数的下三角矩阵其中为可选择的松弛因子，于是构造迭代法如下：其中：这就是解的逐次超松弛迭代法(SOR方法)。其分量形式为：6.2基本迭代法解大型稀疏线性方程组的逐次超松弛法136.2基本迭代法关于SOR方法的几点注释：(1)显然，当时，SOR方法就是Gauss-Seidel方法。(2)SOR方法每一次迭代的主要运算量是计算一次矩阵与向量的乘法。(3)时称为超松弛方法，时称为低松弛方法。(4)计算机实现时可用控制迭代终止，或用控制终止。(5)SOR方法可以看成是Gauss-Seidel方法的一种修正。6.2基本迭代法关于SOR方法的几点注释：146.3

迭代法的收敛性例：分别用Jacobi迭代法和Gauss-Seidel迭代法计算下列方程组，均取同样的初值，观察其计算结果。解：对方程组1，其精确解Jacobi迭代得：Gauss-Seidel迭代得：对方程组2，其精确解Jacobi迭代得：125次迭代可得精度为0.01的解；Gauss-Seidel迭代得：9次迭代可得精度为0.01的解；对方程组3，其精确解Jacobi迭代得：

Gauss-Seidel迭代得：6.3迭代法的收敛性例：分别用Jacobi迭代法156.3

迭代法的收敛性设，其中为非奇异矩阵，记为方程的精确解，的等价方程组为：，于是：设有解方程组的一阶定常迭代法：我们希望研究的问题是：迭代矩阵满足什么条件时，迭代法产生的迭代序列收敛到。引进误差向量其递推公式为：由本章引言可知：我们要研究的问题就是满足什么条件时，有6.3迭代法的收敛性设，其中166.3

迭代法的收敛性定义2：设有矩阵序列及，如果个数列极限存在且有则称收敛于，记为。例：设有矩阵序列且设，考查其极限。解：显然，当时，有矩阵序列极限概念可以用矩阵算子范数来描述。定理1：，其中为矩阵的任意一种算子范数。6.3迭代法的收敛性定义2：设有矩阵序列17

6.3

迭代法的收敛性证明：显然有再利用矩阵范数的等价性，可证定理对其他算子范数亦对。定理2：对任何向量都有定理3：设，则的充分必要条件是矩阵的谱半径。证明：由矩阵的若当标准型，存在非奇异矩阵使其中若当块6.3迭代法的收敛性证明：显然有186.3

迭代法的收敛性且，显然有：，其中：于是下面考查的情况，引进记号：显然有：，由于因此：6.3迭代法的收敛性且，显然有：196.3

迭代法的收敛性利用极限得到所以的充要条件是，即定理4：（迭代法基本定理）设有方程组，对于任意的初始向量，一阶定常迭代法收敛的充要条件是迭代矩阵的谱半径。6.3迭代法的收敛性206.3

迭代法的收敛性证：的特征值，故的特征值从而有：，因此有唯一解。定义为误差向量，则有：故对任意的和，有：即：：设对任意的和，均有：且于是有，即，所以对任意的有故，从而由定理3，有。定理4是一阶定常迭代法的基本理论。6.3迭代法的收敛性证：216.3

迭代法的收敛性推论：设，其中为非奇异矩阵且非奇异，则：(1)解方程组的Jacobi迭代法收敛的充要条件是其中(2)解方程组的Gauss-Seidel迭代法收敛的充要条件是，其中(3)解方程组的SOR迭代法收敛的充要条件是其中6.3迭代法的收敛性推论：设，其226.3

迭代法的收敛性迭代法的基本定理在理论上有重要意义。在具体使用上，由于，因此，我们利用范数可以建立判别迭代法收敛的充分条件。定理5：（迭代法收敛的充分条件）设方程组的一阶定常迭代法为如果有的某种算子范数，则(1)迭代法收敛，即对任取有且(2)(3)(4)6.3迭代法的收敛性迭代法的基本定理在理论上有重236.3

迭代法的收敛性证明：(1)由定理4，结论(1)是显然的；(2)由及得：(a)(b)反复利用(b)即得(2)；(3)注意到即得：(4)反复利用(a)即得(4)。6.3迭代法的收敛性证明：(1)由定理4，结论(1)是显246.3

迭代法的收敛性关于解某些特殊方程组迭代法的收敛性定义3：(对角占优阵)设(1)如果元素满足称为严格对角占优阵(2)如果元素满足且上式至少有一个不等式严格成立，称为弱对角占优阵。6.3迭代法的收敛性关于解某些特殊方程组迭代法的收敛性25

6.3

迭代法的收敛性定义4：(可约与不可约矩阵)设，如果存在置换阵使其中为阶方阵，为阶方阵，则称为可约矩阵，否则，如果不存在这样的置换阵使得上式成立，则称为不可约矩阵。6.3迭代法的收敛性定义4：(可约与不可约矩阵266.3

迭代法的收敛性定理6：(对角占优定理)如果为严格对角占优矩阵或为不可约弱对角占优矩阵，则为非奇异矩阵。证明：我们只就严格对角占优证明定理。采用反证法。，则有非零解，记为则，由齐次方程组第个方程得到，即与对角占优的假设矛盾，故。6.3迭代法的收敛性定理6：(对角占优定理)如果276.3

迭代法的收敛性定理7：设，如果：(1)为严格对角占优，则解的Jacobi迭代法，Gauss-Seidel迭代法均收敛。(2)为弱对角占优，且为不可约矩阵，则解的Jacobi迭代法，Gauss-Seidel迭代法均收敛。证明：这里我们仅证(1)的Gauss-Seidel迭代法。由假设可知：，Gauss-Seidel迭代矩阵为，因此由于于是的特征值为的根，记6.3迭代法的收敛性定理7：设，如286.3

迭代法的收敛性下面证明：当时，，即的特征值均满足，由基本定理，则有Gauss-Seidel迭代法收敛。事实上，当时，由A为严格对角占优，有这说明，当时，矩阵为严格对角占优，再由对角占优定理有。定理8：(SOR方法收敛的必要条件)设解方程组的SOR迭代法收敛，则。证明：由SOR迭代法收敛，则可得，设的特征值为，则从而6.3迭代法的收敛性下面证明：当时，296.3

迭代法的收敛性另一方面从而，即。定理9：设，如果：(1)为对称正定矩阵，(2)则解的SOR迭代法收敛。证明：我们只需在上述假设下，证明即可。事实上，设为对应于的特征向量，即亦即：为了找到的表达式，考虑数量积6.3迭代法的收敛性另一方面306.3

迭代法的收敛性则显然记：由于，所以，故所以从而6.3迭代法的收敛性则316.3

迭代法的收敛性当时，有即的任一特征值满足，故SOR方法收敛(注意当时，可以证明)定理10：设，如果：(1)为严格对角占优矩阵(或不可约弱对角占优矩阵)(2)则解的SOR迭代法收敛。（证明略）6.3迭代法的收敛性当时，326.3

迭代法的收敛性迭代法的收敛速度我们已经知道，如果且越小时，迭代法收敛越快，现考虑方程组及一阶定常迭代法且设迭代法收敛，记，则。由基本定理有，且误差向量满足，故现设为对称矩阵，则有6.3迭代法的收敛性迭代法的收敛速度336.3

迭代法的收敛性下面确定欲使初始误差缩小所需的迭代次数，即使取对数，得到所需最少迭代次数为：故所需迭代次数与成反比，越小，越大，从而所需迭代次数越少，收敛越快定义5：称为迭代法的渐进收敛速度，简称收敛速度。对于SOR迭代法来说，希望通过的选择使得收敛速度较快，但具体计算时，并非都可实现。6.3迭代法的收敛性下面确定欲使初始误差缩小所需346.3

迭代法的收敛性SOR迭代法的算法设，其中为对称正定矩阵或为严格对角占优或为不可约弱对角占优，本算法用SOR迭代法求解，数组存放及，用控制迭代终止，用表示最大迭代次数。1.2.3.4.5.对于(1)(2)如果，则(3)6.输出7.如果，则输出停止；8.如果，则转3；9.输出及有关信息。6.3迭代法的收敛性SOR迭代法的算法356.4分块迭代法前面讨论的迭代法，从的计算过程，是逐个计算的分量，因此这种方法又被称为点迭代法。现在介绍分块迭代法，就是一组未知量同时被改进。设，其中为大型稀疏矩阵且将分块为三个部分，其中6.4分块迭代法前面讨论的迭代法，从366.4分块迭代法其中为非奇异矩阵，，对及同样分块其中，在上述定义的基础上，我们来讨论分块迭代法。(1)块Jacobi迭代法(BJ)选取分裂矩阵为的对角块部分，即选取6.4分块迭代法其中376.4分块迭代法于是，得到块Jacobi迭代法其中迭代矩阵，或由分块矩阵乘法，得到块Jacobi迭代法的具体形式：其中：这说明，块Jacobi迭代法每迭代一步需要求解个低阶方程组6.4分块迭代法于是，得到块Jacobi迭代法386.4分块迭代法(2)块SOR迭代法(BSOR)选取分裂矩阵为带松弛因子的块下三角部分，即：得到块SOR迭代法其中迭代矩阵由分块矩阵乘法得到块SOR迭代法的具体形式：于是，可通过解一组低阶的方程组来代替原来的解。6.4分块迭代法(2)块SOR迭代法(BSOR)396.4分块迭代法定理：设，其中(1)如果为对称正定矩阵；(2)则解的块SOR迭代法收敛。6.4分块迭代法定理：设，其中40第六章解线性方程组的迭代法6.1引言6.2基本迭代法6.3迭代法的收敛性6.4分块迭代法第六章解线性方程组的迭代法6.1引言416.1引言本章介绍求解线性方程组的迭代求解方法，其中，。假设非奇异，则方程组有唯一解。本章介绍迭代法的一些基本理论及Jacobi迭代法，Gauss-Seidel迭代法，超松弛迭代法等常用迭代法。迭代法的例例：用迭代法求解线性方程组：记为：，其中：6.1引言本章介绍求解线性方程组的迭代求426.1引言已知其精确解为：。现将方程组改写成如下的等价形式：或写为，其中：

6.1引言已知其精确解为：。现将方程436.1引言由此建立迭代格式（公式）：

给定初始向量：，则可得：当时，有：，得近似解：，由此可以看出由迭代法产生的向量序列逐步逼近方程组的精确解。k1234x10.7780.9630.9930.999x20.8000.9640.9930.999x30.8670.9720.9950.9996.1引言k1234x10.7780.9630.9930.446.1引言例2：考虑方程组：，取初值，则有：可见不收敛。因此，我们得到：对于任何一个方程组，由迭代法产生的向量序列不一定收敛。为做进一步研究，我们假设方程组有唯一解，则，又设为任意初始向量，按下列公式构造向量序列：其中表示迭代次数，我们给出如下的定义：定义1：上述求解方法称为迭代法，如果存在，则称迭代法收敛，否则称为迭代法发散。6.1引言例2：考虑方程组：456.1引言为讨论收敛性，引进误差向量，从而可得：，递推得到：要研究的收敛性，就要研究在满足什么条件时有，实际就是6.1引言为讨论收敛性，引进误差向量466.2基本迭代法设有方程组，其中为非奇异矩阵下面研究如何建立解方程组的各种迭代法。将分裂为，其中为可选择的非奇异矩阵，且使容易求解，一般选择为的某种近似称为分裂矩阵。于是，求解转化为求解，即求解：这样，可构造迭代法：其中：称为迭代法的迭代矩阵，选取阵，就得到解的各种迭代法。6.2基本迭代法设有方程组，其中476.2基本迭代法设，并将写为三部分：Jacobi迭代法由，选取为的对角元素部分，即选取，，可得Jacobi迭代公式：其中称为解的Jacobi迭代法的迭代矩阵。6.2基本迭代法设486.2基本迭代法Jacobi迭代法的分量表示记由Jacobi迭代公式可得：，写成分量形式即为：于是，解的Jacobi迭代法的计算公式为：由此可知，Jacobi迭代法计算公式简单，每次迭代只需计算一次矩阵和向量的乘法且计算过程中不变。6.2基本迭代法Jacobi迭代法的分量表示496.2基本迭代法Gauss-Seidel迭代法我们再来分析前面的例子，其实在求时，我们已经求得了，然而我们此时并没有用到来计算，这使我们想到，应该尽可能利用已经计算出来得新的值，因此，可将上面的迭代公式改为：这就是所谓的Gauss-Seidel迭代法，用分裂矩阵的语言，这时选取的分裂矩阵为的下三角部分，即选取，于是由得到Gauss-Seidel迭代法：6.2基本迭代法Gauss-Seidel迭代法506.2基本迭代法其中称为解方程组的Gauss-Seidel迭代矩阵。至于Gauss-Seidel迭代法的分量表示，我们可由矩阵表示得到：即：写成分量形式得到：6.2基本迭代法516.2基本迭代法Jacobi迭代法和Gauss-Seidel迭代法的异同：Jacobi迭代法公式简单，每次只需做矩阵和向量的一次乘法，特别适合于并行计算；不足之处是需要存放和的两个存储空间。Gauss-Seidel方法只需要一个向量存储空间，一旦计算出立即存入的位置，可节约一套存储单元这是对Jacobi方法的改进，在某些情况下，它能起到加速收敛的作用。但它是一种典型的串行算法，每一步迭代中，必须依次计算解的各个分量。6.2基本迭代法Jacobi迭代法和Gauss-Seide526.2基本迭代法解大型稀疏线性方程组的逐次超松弛法选取分裂矩阵为带参数的下三角矩阵其中为可选择的松弛因子，于是构造迭代法如下：其中：这就是解的逐次超松弛迭代法(SOR方法)。其分量形式为：6.2基本迭代法解大型稀疏线性方程组的逐次超松弛法536.2基本迭代法关于SOR方法的几点注释：(1)显然，当时，SOR方法就是Gauss-Seidel方法。(2)SOR方法每一次迭代的主要运算量是计算一次矩阵与向量的乘法。(3)时称为超松弛方法，时称为低松弛方法。(4)计算机实现时可用控制迭代终止，或用控制终止。(5)SOR方法可以看成是Gauss-Seidel方法的一种修正。6.2基本迭代法关于SOR方法的几点注释：546.3

迭代法的收敛性例：分别用Jacobi迭代法和Gauss-Seidel迭代法计算下列方程组，均取同样的初值，观察其计算结果。解：对方程组1，其精确解Jacobi迭代得：Gauss-Seidel迭代得：对方程组2，其精确解Jacobi迭代得：125次迭代可得精度为0.01的解；Gauss-Seidel迭代得：9次迭代可得精度为0.01的解；对方程组3，其精确解Jacobi迭代得：

Gauss-Seidel迭代得：6.3迭代法的收敛性例：分别用Jacobi迭代法556.3

迭代法的收敛性设，其中为非奇异矩阵，记为方程的精确解，的等价方程组为：，于是：设有解方程组的一阶定常迭代法：我们希望研究的问题是：迭代矩阵满足什么条件时，迭代法产生的迭代序列收敛到。引进误差向量其递推公式为：由本章引言可知：我们要研究的问题就是满足什么条件时，有6.3迭代法的收敛性设，其中566.3

迭代法的收敛性定义2：设有矩阵序列及，如果个数列极限存在且有则称收敛于，记为。例：设有矩阵序列且设，考查其极限。解：显然，当时，有矩阵序列极限概念可以用矩阵算子范数来描述。定理1：，其中为矩阵的任意一种算子范数。6.3迭代法的收敛性定义2：设有矩阵序列57

6.3

迭代法的收敛性证明：显然有再利用矩阵范数的等价性，可证定理对其他算子范数亦对。定理2：对任何向量都有定理3：设，则的充分必要条件是矩阵的谱半径。证明：由矩阵的若当标准型，存在非奇异矩阵使其中若当块6.3迭代法的收敛性证明：显然有586.3

迭代法的收敛性且，显然有：，其中：于是下面考查的情况，引进记号：显然有：，由于因此：6.3迭代法的收敛性且，显然有：596.3

迭代法的收敛性利用极限得到所以的充要条件是，即定理4：（迭代法基本定理）设有方程组，对于任意的初始向量，一阶定常迭代法收敛的充要条件是迭代矩阵的谱半径。6.3迭代法的收敛性606.3

迭代法的收敛性证：的特征值，故的特征值从而有：，因此有唯一解。定义为误差向量，则有：故对任意的和，有：即：：设对任意的和，均有：且于是有，即，所以对任意的有故，从而由定理3，有。定理4是一阶定常迭代法的基本理论。6.3迭代法的收敛性证：616.3

迭代法的收敛性推论：设，其中为非奇异矩阵且非奇异，则：(1)解方程组的Jacobi迭代法收敛的充要条件是其中(2)解方程组的Gauss-Seidel迭代法收敛的充要条件是，其中(3)解方程组的SOR迭代法收敛的充要条件是其中6.3迭代法的收敛性推论：设，其626.3

迭代法的收敛性迭代法的基本定理在理论上有重要意义。在具体使用上，由于，因此，我们利用范数可以建立判别迭代法收敛的充分条件。定理5：（迭代法收敛的充分条件）设方程组的一阶定常迭代法为如果有的某种算子范数，则(1)迭代法收敛，即对任取有且(2)(3)(4)6.3迭代法的收敛性迭代法的基本定理在理论上有重636.3

迭代法的收敛性证明：(1)由定理4，结论(1)是显然的；(2)由及得：(a)(b)反复利用(b)即得(2)；(3)注意到即得：(4)反复利用(a)即得(4)。6.3迭代法的收敛性证明：(1)由定理4，结论(1)是显646.3

迭代法的收敛性关于解某些特殊方程组迭代法的收敛性定义3：(对角占优阵)设(1)如果元素满足称为严格对角占优阵(2)如果元素满足且上式至少有一个不等式严格成立，称为弱对角占优阵。6.3迭代法的收敛性关于解某些特殊方程组迭代法的收敛性65

6.3

迭代法的收敛性定义4：(可约与不可约矩阵)设，如果存在置换阵使其中为阶方阵，为阶方阵，则称为可约矩阵，否则，如果不存在这样的置换阵使得上式成立，则称为不可约矩阵。6.3迭代法的收敛性定义4：(可约与不可约矩阵666.3

迭代法的收敛性定理6：(对角占优定理)如果为严格对角占优矩阵或为不可约弱对角占优矩阵，则为非奇异矩阵。证明：我们只就严格对角占优证明定理。采用反证法。，则有非零解，记为则，由齐次方程组第个方程得到，即与对角占优的假设矛盾，故。6.3迭代法的收敛性定理6：(对角占优定理)如果676.3

迭代法的收敛性定理7：设，如果：(1)为严格对角占优，则解的Jacobi迭代法，Gauss-Seidel迭代法均收敛。(2)为弱对角占优，且为不可约矩阵，则解的Jacobi迭代法，Gauss-Seidel迭代法均收敛。证明：这里我们仅证(1)的Gauss-Seidel迭代法。由假设可知：，Gauss-Seidel迭代矩阵为，因此由于于是的特征值为的根，记6.3迭代法的收敛性定理7：设，如686.3

迭代法的收敛性下面证明：当时，，即的特征值均满足，由基本定理，则有Gauss-Seidel迭代法收敛。事实上，当时，由A为严格对角占优，有这说明，当时，矩阵为严格对角占优，再由对角占优定理有。定理8：(SOR方法收敛的必要条件)设解方程组的SOR迭代法收敛，则。证明：由SOR迭代法收敛，则可得，设的特征值为，则从而6.3迭代法的收敛性下面证明：当时，696.3

迭代法的收敛性另一方面从而，即。定理9：设，如果：(1)为对称正定矩阵，(2)则解的SOR迭代法收敛。证明：我们只需在上述假设下，证明即可。事实上，设为对应于的特征向量，即亦即：为了找到的表达式，考虑数量积6.3迭代法的收敛性另一方面706.3

迭代法的收敛性则显然记：由于，所以，故所以从而6.3迭代法的收敛性则716.3

迭代法的收敛性当时，有即的任一特征值满足，故SOR方法收敛(注意当时，可以证明