数值分析--第6章 解线性方程组的迭代法

《数值分析--第6章 解线性方程组的迭代法》由会员分享，可在线阅读，更多相关《数值分析--第6章 解线性方程组的迭代法（15页珍藏版）》请在装配图网上搜索。

1、第6章 解线性方程组的迭代法直接方法比拟适用于中小型方程组。对高阶方程组，即使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等缺乏。迭代法那么能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。故能有效地解一些高阶方程组。1 迭代法概述迭代法的根本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规那么。由不同的计算规那么得到不同的迭代法。迭代法的一般格式式中与有关，称为多步迭代法。假设只与有关，即称为单步迭代法。再设是线性的，即式中，称为单步线性迭代法。称为迭代矩阵。假设和与无关，即称为单步定常线性迭代法。本章主要讨论具有这种

2、形式的各种迭代方法。1.1 向量序列和矩阵序列的极限由于中的向量可与的点建立对应关系，由点列的收敛概念及向量范数的等价性，可得到向量序列的收敛概念。定义6.1 设为中的向量序列，如果其中为向量范数，那么称序列收敛于，记为。定理6.1 中的向量序列收敛于中的向量当且仅当其中。证明 由定义6.2，收敛于，即而对任意，有由极限存在准那么得即定义6.2 设为中的矩阵序列，如果其中为矩阵范数，那么称序列收敛于，记为。定理6.2 中的矩阵序列收敛于中的矩阵的充要条件为证明留给读者。定理6.1和6.2说明，向量序列和矩阵序列的收敛可以归结为对应分量或对应元素序列的收敛。定理6.3 的充分必要条件是其中两个极

3、限的右端分别指零矩阵和零向量。证明 对任一种算子范数，有，从而可证必要性。假设依次取个单位向量，其中的第个分量为1，其它分量为零。得所以。充分性得证。1.2 迭代公式的构造将非奇异线性方程组变形为等价方程组 (6-1)由此构造迭代公式 (6-2)给定初始向量后，按此迭代公式产生向量序列，当充分大时，以作为方程组的近似解，这就是求解线性方程组的单步定常线性迭代法。称为迭代矩阵。定义6.3 如果对任意的初始向量及，迭代法(6-2)得出的向量序列都有成立，其中为一确定的向量，它不依赖于的选取，那么称迭代法(6-2)是收敛的，否那么称迭代法(6-2)是发散的。显然，假设按式(6-2)产生的向量序列收敛

4、于向量，那么有即是方程组(6-1)的解。2 根本迭代法2.1 Jacobi雅可比迭代法考虑方程组，即 (6-3)其中非奇异，故不妨设。(6-3)等价变形为有 (6-4)由此构造迭代公式 (6-5)记那么。由式(6-3)到式(6-4)的过程用矩阵形式表示为因此式(6-5)的矩阵形式为 (6-6)其中。式(6-5)为迭代法的分量形式，它可用于计算迭代近似解；式(6-6)为迭代法的矩阵形式，它主要用于验证迭代法是否收敛及定性分析。算法6.11输入，维数，最大容许迭代次数。2置3对4假设，输出，停机，否那么转5。5假设，置，转3；否那么，输出失败信息，停机。2.2 Gauss-Seidel高斯-赛德尔

5、迭代法在Jacobi迭代法中，是用的全局部量来计算的全局部量的，然而在计算分量时，都已经算出，如果Jacobi迭代法收敛，试想用多迭代一次的代替来计算，可望取得更好的结果。这就是Gauss-Seidel迭代法的根本思想。其迭代公式为 (6-7)式(6-7)的矩阵形式为因此迭代法的矩阵形式为 (6-8)其中。算法6.21输入，维数，最大容许迭代次数。2置3计算4假设，输出，停机，否那么转5。5假设，置，转3；否那么，输出失败信息，停机。2.3 SOR迭代法解线性方程组的超松弛法，也叫SOR法，是目前求解大型方程组的一种最常用的方法。是Gauss- Seidal迭代法的一种加速方法。对一个收敛的G

6、auss-Seidel迭代法，第次的迭代结果一般要比第次的好。第次的迭代结果可看作第次根底上的修正，现在我们引入一个参数，来改变这个修正量。这就是SOR方法的根本思想。记，其中由Gauss-Seidel迭代公式算得。于是有可以把看作Gauss-Seidel迭代的修正项，即第次近似解以此项修正后得到的近似解。松弛法是将乘上一个参数因子作为修正项而得到新的近似解，其具体公式为即 (6-9)按式(6-9)计算方程组的近似解序列的方法称为松弛法，称为松弛因子。当为低松弛，是Gauss-Seidel迭代，当时称为超松弛法，简称SOR法。式(6-9)的矩阵形式为即注意到，有 (6-10)其中。算法6.31

7、输入，维数，最大容许迭代次数。2置3计算4假设，输出，停机，否那么转5。5假设，置，转3；否那么，输出失败信息，停机。例1 用Jacobi和Gauss-Seidel迭代法求解线性方程组解 Jacobi迭代法的迭代公式为(算法语言)取，迭代9次的近似解。容易验证，方程组的精确解为。G-S法的迭代公式为迭代6次的近似解。例2 取，用超松弛法求解方程组解 迭代公式为3 迭代法的收敛性6.1 一阶定常迭代法的根本定理定理6.4 设，那么零矩阵的充分必要条件是矩阵的谱半径。证明 根据Jordan标准形定理，恒有非奇异方阵，使其中假设当块且，显然有，其中于是。引进记号表示阶方阵，其元素仅在对角线右上方第条

8、平行线上的值为1，其余为0，即当时，。不难证得即具有特点：每乘一次，相当于把元素为1的那条斜线向右上方推一步。以为例由于，其中为阶单位阵。因此其中。利用极限，得到所以的充要条件是，即。定理6.5 对任意的初始向量和右端项，由迭代格式 (6-11)产生的向量序列收敛的充要条件。证明 必要性。设存在向量，使得，那么由此及迭代公式(6-12)，有于是因为为任意维向量，因此上式成立必须由定理6.4，即得。充分性。假设，那么不是的特征值，因而有，于是对任意维向量，方程组有唯一解，记为，即并且又因为所以，对任意初始向量，都有即由迭代公式(6-11)产生的向量序列。推论1 对任一种矩阵范数，假设，那么收敛。

9、推论2 SOR法收敛的必要条件是。证明 设有特征值。因为由定理6.5，SOR法收敛必有，又因为于是有所以。定理6.5说明，迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向量以方程组的右端项无关。对同一方程组，由于不同的迭代法迭代矩阵不同，因此可能出现有的方法收敛，有的方法发散的情形。例3 研究用Jacobi和Gauss-Seidel迭代法解方程组的敛散性。(1) ； (2) 解 (1) Jacobi法的迭代矩阵为其特征方程为由得，所以，因此Jacobi迭代法收敛。如果用Gauss-Seidel法，迭代矩阵为特征方程由得特征值，所以，因此Gauss-Seidel迭代法发散。(2) J法的特征方程

10、为令，因为所以在中有一根，于是因此Jacobi迭代法发散。G法的特征方程为得特征根，所以因此G-S迭代法收敛。注：1在求G-S法和SOR法的特征方程时，注意到事实可防止求逆矩阵。2J法和G法的收敛性没有必然联系。3定理6.5虽然给出了判别迭代法收敛的充要条件，但实际使用时很不方便。因为求谱半径却是比拟困难的事，因此常利用，作为上界的一种估计式。需要指出的是：矩阵范数可以是任何一种矩阵范数，不限于算子范数，常用的范数有；其次，使用矩阵范数判别只是充分条件，而非必要条件。6.2特殊方程组迭代法的收敛性定义6.4 假设满足且至少有一个，使上式中不等式严格成立，那么称为弱对角占优。假设所有的不等式均成

11、立，那么称为严格对角占优。定义6.5 假设，能找到排列矩阵，使得其中均为方阵，称为可约，否那么，称为不可约。定义 假设，当时，如果存在一个下标的非空子集，使得当而时有那么称为可约阵。 例如就是可约矩阵，因为取定义中的，当，而，即时，有，即另一方面，从定义6.5判断，将其第二行和第三行对换，同时也把第二列和第三列对换，就可化为定理6.6 假设严格对角占优或为不可约弱对角占优矩阵，那么，且非奇异。证明 从严格对角占优可知。假设奇异，那么有满足。设，那么方程组的第个方程为由此得与为严格对角占优矛盾。我们有如下结论：1假设为严格对角占优阵或不可约弱对角占优，那么Jacobi迭代法和Gauss-Seid

12、el均收敛。2假设为严格对角占优阵或不可约弱对角占优，那么SOR法收敛。3假设为对称正定矩阵，那么SOR收敛的充要条件为。例4 考虑系数矩阵，的方程组。显然，为严格对角占优，故J和G-S法均收敛。非严格对角占优，但为对称正定矩阵，故取，SOR法收敛。例5 假设计算可得，所以J和G-S法均发散。如果改变方程的次序，有显然为严格对角占优，故J和G-S法均收敛。说明，改变方程组中方程的次序，即将系数矩阵作行交换会改变迭代法的收敛性。定理6.7 假设为严格对角占优阵或不可约弱对角占优，那么J法和GS法均收敛。证明 我们只给出严格对角占优情形的证明。只需证明和。J法的迭代阵显然有，故，从而J法收敛。GS

13、法的特征方程为令，有。现在证明。采用反证法，假设，那么由为严格对角占优阵有因此为严格对角占优阵，故，矛盾，因此只能，即，从而GS法收敛。定理6.8 假设为对称正定矩阵，那么解的SOR法收敛的充要条件为。证明 只需证明充分性。设是的任一特征值可能是复数，假设能证明，那么定理得证。设是的相应于的特征向量可能是复向量，即也就是上式两边与作复内积，有那么利用正定阵的对角元素大于0，有由于为对称正定阵，所以对，有，特别取，有记由于，所以，故于是，而注意到及的正定性可知的分子小于分母，即，从而，SOR法收敛。定理6.9 假设为严格对角占优阵或不可约弱对角占优，那么SOR法收敛。证明 SOR法的特征方程为即

14、设是上述方程的任一根，我们只需证明。采用反证法，假设，由，那么，于是令，有。由于所以也为严格对角占优矩阵，故，与矛盾。因而只能，即，于是SOR法收敛。6.3 误差估计定理6.10 设有方程组及一阶定常迭代法如果有的某种算子范数，那么(1) 迭代法收敛，即对任意的有且(2) (3) (4) 证明 由定理6.5，结论(1)是显然的事实。(2) 由关系式及，有(a) (b) 反复利用(b)即得(2)。(3) 利用(b)得于是(4) 反复利用(a)，那么得到(4)。注：1利用定理6.10作误差估计，一般可取1，2或范数。结论3是近似解的误差事后估计式，对于给定的精度当然应中选得恰当，小于或接近于机器精

15、度可能会造成死循环，只要不是很接近1，那么可用来控制迭代终止。假设，即使很小，也不能判定很小。2结论4可用作迭代次数的估计。根据事先给定的精度，可以估算出迭代的次数：迭代法是否收敛虽与初始向量的选取无关，但由上面的公式看出对迭代次数却有很大的影响，因而应重视初始向量的选取。6.4 迭代法的收敛速度及最正确松弛因子为非奇异矩阵，设是(6-1)的解，即以(6-2)式减去上式，并记误差向量为，那么有由此递推得 (6-12)设迭代格法(6-2)收敛，即，从(6-12)知，现设，那么有这里的矩阵范数均附属于向量范数，根据范数的性质有所以给出了迭代次后误差向量范数与初始误差向量范数之比的上确界。这样，迭代

16、次后，平均每次迭代误差范数的压缩率就可以看成是。如果要求迭代次后有 (6-13)其中因子是个小数。因为，所以，我们可选择足够大的使这样便可使上面的不等式(6-13)成立。对于所有使的，上式等价于 (6-14)所以到达(6-13)要求的最小迭代次数反比于。定义6.6 称为迭代法的平均收敛率。以上定义的是平均压缩率的对数值再取负号。它是依赖于所选择的范数和迭代次数。这样给一些理论分析带来不便。由于，我们再给出下面的定理。定义6.7 称为迭代法的渐近收敛率，或称渐近收敛速度。显然，且与取何种范数及迭代次数无关。它反映的是迭代次数趋于无穷时迭代法的渐近性质。为了到达(19)的要求，可以用代替(20)作为所需迭代次数的估计。下面定理6.10给出了三对角形正定矩阵的最正确松弛因子。定理6.10 如果为三对角形正定矩阵，和分别是Jacobi和Seidel迭代法的迭代矩阵，那么(1) (2) 最正确松弛因子(3) 松弛迭代矩阵的谱半径。