线性方程组的迭代解法_赖志柱.doc

第三章 线性方程组的迭代解法教学目标：1.了解线性代数方程组迭代解法的基本思想，向量序列和矩阵序列收敛的基本思想及相关定理；2.掌握迭代法的构造思想、收敛性和速度（率）以及相关定理；3.在理解Jacobi迭代法和Gauss-Seidel迭代法的原理的基础上，掌握两种迭代法的计算步骤和相互关系，并掌握两种迭代法的收敛性相关定理。4.初步了解超松弛（SOR）迭代法的基本思想。教学重点： 1.迭代法的原理、基本思想和序列收敛的概念；2.迭代法的构造、收敛和速率；3. Jacobi迭代法和Gauss-Seidel迭代法的原理、实现步骤和收敛性；教学难点：1.迭代法的构造、收敛和速率；2. Jacobi迭代法和Gauss-Seidel迭代法的原理、实现步骤和收敛性；线性方程组的直接解法，用于阶数不太高的线性方程组效果较好。实际工作中有的线性方程组的阶数很高，用直接法求解效果不是很好。而迭代法与直接法不同，它是通过从某些初始向量出发，用设计好的步骤逐次计算出近似解向量，从而得到向量序列。一般的计算公式为式中与有关，称为多步迭代法。若只与有关，即则称为单步迭代法。现再设是线性的，即其中，称为单步线性迭代法，称为迭代矩阵。若和与无关，即称为单步定常线性迭代法。迭代法的基本思想是用逐次逼近的方法去求线性代数方程组的解。迭代法的关键有：（1）如何构造迭代公式？（2）迭代法产生的向量序列的收敛条件是什么？收敛速度如何？3.1 迭代法的基本概念3.1.1 向量序列和矩阵序列的极限为分析迭代法的收敛性，先讨论向量和矩阵序列极限的概念。中向量序列记为，在不引起混淆时就简记为。同理，中矩阵的序列记为或。定义3.1 定义了范数的向量空间中，若存在满足，则称收敛于，记为。不难看出，上述向量序列极限的定义形式上依赖于所选择的范数，注意到向量范数的等价性，若对一种范数而言收敛于，则可证明对其它范数而言也是收敛于的，这说明的收敛性与所选择的范数无关。设，若收敛于，且选用范数，则有从而有即等价于。向量序列的收敛性等价于由向量分量构成的个数列的收敛性，此时也称按分量收敛。定义3.2 定义了范数的空间中，若存在使，则称收敛于，记为。同理，的收敛性与所选择的范数无关，而且若记，则有，定理3.1 ，。证明：必要性 只要注意到对任一种矩阵从属范数都有即可。充分性 若取为单位向量，其第个分量为1，其它分量为零。则意味着第列各元素极限为零，依次取即可。证毕下面讨论有矩阵的幂所构成的矩阵序列，即序列，其中。定理3.2 设，则下面三个命题等价：（1）；（2），其中为的谱半径；（3）至少存在一种从属的矩阵范数，使。证明： 用反证法，假设有一个特征值，满足，则存在特征向量，使得。由此可得，当时向量序列不收敛于零向量，据定理3.1有不收敛于零矩阵，与命题（1）矛盾。 若，则，存在一种从属的矩阵范数，使，适当选择，便可使。 若，则由可得，从而。定理3.3设，为任一种范数，则。证明：由定理知，从而，而，所以有，对一切成立另一方面，记，显然有。由定理3.2有，所以存在，使得当时，有即当时，而是任意的，即得定理结论。证毕 3.1.2 迭代公式的构造设，非奇异，满足方程组。如果能找到矩阵，向量，使可逆，而且方程组的唯一解就是的解，则可以从构造一个定常的线性迭代公式 （3.1）给出，由（3.1）式可以产生，若它有极限，显然就是和的解。定义3.3 若迭代公式（3.1）产生的序列满足，则称迭代法（3.1）是收敛的。从出发可以由不同的途径得到各种不同的等价方程组，从而得到不同的迭代法（3.1）。例如，设可以分解为，其中非奇异，则有令，则有，这里的和依赖不同的分解方法。 3.1.3 迭代法的收敛性设是的解，即有，用与其相减得若记误差向量为，则有由此可推得其中与无关，所以迭代法（3.1）收敛就意味着定理3.4 下面三个命题等价：（1）迭代法收敛；（2）；（3）至少存在一种从属的矩阵范数，使。证明：从以上分析，命题（1）中迭代法收敛等价于，有定理3.1，上式成立的充要条件是，再由定理3.2即可。证毕有时实际判别一个迭代法是否收敛，条件是较难检验的。由于，等可以用的元素来表示，故我们可以考虑用，或来作为收敛的判定，这就是下面的定理：定理3.5 设是方程的唯一解，是一种向量范数，对应的从属矩阵范数，则由（3.1）产生的向量序列满足 （3.2） （3.3）证明：因为所以有。因为，由定理3.4知迭代法是收敛的，。从可得是非奇异的，且 即得（3.2）式。由于再反复运用即可得（3.3）。证毕利用定理3.5做误差估计，一般可取。从（3.2）式可以看到，只要不是很接近1，若相邻两次迭代向量与已近很接近，则与已经相当接近，所以可以用来控制迭代终止。例如，则有。但是若，即使很小，也不能判定很小。例如，若，则只能估计到。3.1.4 迭代法的收敛速度设迭代法（3.1）收敛，即。由得。现设，则有这里的矩阵范数均从属于向量范数。根据范数的性质有 所以给出了迭代次后误差向量范数与初始误差向量范数之比的上确界。这样经过迭代次后，平均每次迭代误差范数的压缩率就可以看成是。如果要求迭代次后有 （3.4）其中因子是个较小的数，例如。因为，所以，我们可以选择足够大的使，使得（3.4）成立。对于所有使的，等价于 （3.5）所以达到（3.4）式要求的最小迭代次数反比于。定义3.4 称为迭代法（3.1）的平均收敛率。定义3.4中的是平均压缩率的对数值再取负号，它依赖于所选择的范数和迭代次数，作理论分析时会带来一些不便。由定理3.3有，从而我们可以引入下面的定义定义3.5 称为迭代法（3.1）的渐进收敛率，或渐进收敛速度。显然有，且与取何种范数及迭代次数无关，它反映的是迭代次数趋于无穷时迭代法（3.1）的渐进性质。为了达到的要求，可以用 （3.6）代替（3.5）作为所需迭代次数的估计。 从上面的讨论可以看到，对于不同的迭代法，其迭代矩阵的谱半径较小者收敛要快些。3.2 Jacobi迭代法和Gauss-Seidel迭代法3.2.1 Jacobi迭代法设方程组为，其中，且非奇异，将分解为，其中，和分别为的严格下、上三角部分（不包括对角线）。现设非奇异，即，。对应于，可令，则有 由此构造迭代法 （3.7）其中 （3.8） （3.9）迭代法（3.7）称为简单迭代法，也称为雅可比（Jacobi）迭代法，简称J法。将方程组写为，并设，从第个方程解出，得等价的方程组： ，从而Jacobi迭代法又可以写作 ， （3.10） 从（3.10）可以看出，用Jacobi迭代法计算向量序列，要用两组单元分别存放向量和。例3.1 用Jacobi迭代法解方程组解：解出：按下式进行迭代： （）任取一初始向量，例如，得到迭代序列，列表如下01234567800.30000.80000.91800.97160.98040.99620.99850.999801.50001.76001.92601.97001.98971.99611.99861.999802.00002.66002.86402.95402.98232.99382.99772.9997不难验证，原方程组的精确解为，从上面的计算可以看出，收敛于精确解的。3.2.2 Gauss-Seidel迭代法在Jacobi迭代法中，在计算时要使用，而此时已计算出来了，看来可以提前使用代替。一般地，计算时，使用代替，这样可能收敛速度会快一点，而且整个迭代过程只要使用一组单元存放迭代向量，这就是所谓的Gauss-Seidel（高斯-赛德尔）迭代法，简称GS法，其计算公式为， （3.11）将（3.11）式写成矩阵形似，得其中，进一步整理成 这样，Gauss-Seidel迭代法的迭代矩阵就是 对比一般的分解形式，可以看成，从而有，。例3.2 用Gauss-Seidel迭代法计算例3.1并做比较。解：迭代公式为：用它计算得到的序列列表如下：012345600.30000.88040.98430.99780.99971.000001.56001.94481.99221.99891.99982.000002.68402.95392.99382.99912.99993.0000可见它对这一方程组比Jacobi迭代法收敛快一些。3.2.3 Jacobi和Gauss-Seidel迭代法的收敛性从定理3.4可得以下结论：定理3.6 Jacobi迭代法收敛的充分必要条件是，其中；Gauss-Seidel迭代法收敛的充分必要条件是，其中。注意到，则可以得到上述两种迭代法的收敛的一个充分条件：定理3.7 Jacobi迭代法收敛的一个充分条件是，其中；Gauss-Seidel迭代法收敛的一个充分条件是，其中。定义3.6 设矩阵每一行对角元素的绝对值都大于同行其它元素绝对值之和，即，则称为严格（行）对角占优矩阵。若的每一行对角元素的绝对值都大于等于同行其它元素绝对值之和，即，且其中至少有一个严格不等式成立，则称为弱（行）对角占优矩阵。定义3.7 若，不能找到排列矩阵，使 （3.12）其中与均为方阵，称为不可约的。显然，若是可约的，则可通过行与列的置换成（3.12）的形式，方程组就可以化为低阶的方程组。对可类似讨论。定理3.8 若严格对角占优，则，且非奇异。定理3.9 若不可约且弱对角占优，则，且非奇异。定理3.10 设为严格对角占优矩阵，或为不可约的弱对角占优矩阵，则方程组的Jacobi迭代法和Gauss-Seidel迭代法均收敛。定理3.11 设对称，且有正的对角元，即，。方程组的Jacobi迭代法收敛的充分必要条件为和均正定，其中。定理3.12 设对称正定，则的 Gauss-Seidel迭代法收敛。由定理3.11和定理3.12，若对称正定，则Gauss-Seidel迭代法收敛一定收敛，而Jacobi迭代法却不一定。对于一般的矩阵，解方程组，有可能Jacobi迭代法和Gauss-Seidel迭代法都收敛，或者是一者收敛另一者不收敛。3.3 超松弛（SOR）迭代法3.3.1 超松弛（SOR）迭代法在很多情况下，J法和GS法收敛较慢，需要考虑GS法的改进。假设计算第个近似解时，分量已经算好，可以像GS法那样计算 （3.13）再用某个参数作加权平均，即 （3.14）或者整理成， （3.15）这称为逐次超松弛迭代法，简记为SOR（Succesise Over-Relaxation）方法，其中称为松弛因子。当时，（3.15）就是GS法。记，则（3.15）式可写成矩阵形式再整理成 （3.16）其中为SOR方法的迭代矩阵： （3.17）对应于的分解式，有 例3.3 方程组的准确解为。如果用的SOR迭代法（即GS法），计算公式是 用的SOR迭代法，计算公式是如果都取，时迭代7次得 而用有 继续计算下去，要达到7位有效数字的精