解线性方程组的迭代法

1、第3章 解线性方程组的迭代法清华大学工程硕士数学课程-数值分析 数值方法§1 Jacobi迭代法和Gauss-Seidel迭代法（I）迭代概念 （1） ， ， ， ， ，M非奇异如果令 ，那么上式写成（2） 此方程组等价于任给，（3） 由（3）可以确定，当，即 时，有同样满足 定义 式（3） 称为求解 （1） 的简单形式迭代法，B称为迭代矩阵。（II）Jacobi迭代法写成分量形式有假定 ，那么有迭代法为任给 即：上式迭代方法称为Jacobi迭代例1.1用Jacobi迭代法解方程组解 Jacobi迭代方法为取 方程组 的准确解为。 若取 那么 。可取 为方程组的近似解。为进行收敛性分

2、析，把迭代方法写成向量形式。 ，称为Jacobi迭代的迭代矩阵（III）Gauss-Seidel迭代法Jacobi迭代有可以看出，当计算时，已经计算出来了，一般可以认为要比更接近于。由此可以设想把已经计算出来的分量在计算公式中立刻应用，这样就有这个迭代公式称为Gauss-Seidel迭代公式例1.2取可见，Gauss-Seidel迭代法比Jacobi迭代法“好” 把Gauss-Seidel迭代方法写成令 称为Gauss-Seidel迭代的迭代矩阵， 例1.3 用Jacobi 迭代法和Gauss-Seidel迭代法解此方程组有唯一解 Jacobi 事实上， Gauss-Seidel:§

3、2 迭代方法收敛性（I）向量序列和矩阵序列的极限中向量序列 ， 简单记为 。同样，中序列 定义2.1 设 为上的向量范数。如果存在 满足那么称收敛于，记由于范数等价性，所以收敛性与所选择范数无关。定义2.1 设为上矩阵范数，如果存在满足那么称收敛于A，记为收敛性与所择范数无关。定理2.1 充分必要条件是证：必要性。对任一种矩阵算子范数有充分性， 取 ，其第个分量为1，其它分量为零的向量。那么表示的第列各元素极限为零，取 表示的全部元素极限为零。定理2.2 设 ， 那么下面三个命题等价（1） （2） （3）至少存在一种从属的矩阵范数，使。证明 用反证法：设B有一特征值，。那么存在特征向量，所以当

4、，不收敛到零向量。根据定理2.1，不收敛到零矩阵，矛盾于（1）。对任，存在一种从属的矩阵范数使由（2），适当选择，使 从而有 从而有 （II）迭代法的收敛性 ，A非奇异， 满足（1） 等价（2） 迭代公式（3） 定义2.3 由迭代公式（3）产生的序列 满足那么称迭代法（3）是收敛的。设 为（2） 的解，即由（3）减去上式有其中 由此可以递推得其中与无关，所以迭代法（3）收敛相当于定理2.3 下面三个命题等价（1） 迭代法 收敛（2） 至少存在一种从属的矩阵范数，使得。证明：命题（1）等价于根据定理2.1 这条件等价于。由定理2.2，此定理证得最常用的定理叙述如下：定理2.4 迭代法 ；对任 收

5、敛的充分必要条件是 。实际判别一个迭代法是否收敛，条件 较难验证。但 可以用B的元素来表示，所以用来作为收敛的充分条件较为方便。例子2.4 其中 试讨论用Jacobi 迭代法和Gauss-Seidel迭代法求解上述方程组的收敛性解 Jacobi迭代收敛 Gauss-Seidel迭代不收敛。例 2.5 其中试讨论用Jacobi迭代法和Gauss-Seidel迭代法求解方程组的收敛性解 ， Jacobi迭代不收敛。 Gauss-Seidel迭代收敛例2.6 设方程组（1） 写出解方程组的Jacobi迭代矩阵，讨论迭代收敛条件。（2） 写出解方程组的Gauss-Seidel迭代矩阵，讨论迭代收敛条件

6、。解（1）； Jacobi迭代收敛充要条件为 ，即 （2） ， 即Gauss-Seidel迭代收敛的充要条件为， 即 。（III）迭代的误差估计定理2.5 设是方程组 的唯一解， 为上的向量范数，对应的从属矩阵范数。那么由产生的向量序列 满足 ，证明： ，迭代收敛， ； 由 非奇异。并由迭代格式重复运用可得（IV）特殊方程组迭代法的收敛性如果A具有特殊性质，那么可利用这些性质来判别迭代法的收敛性。定义2.4 （1）如果A的元素满足则称A是严格对角占优（2）如果A的元素满足且上式中至少有一个不等号严格成立，那么称A为（弱）对角占优定理2.6 设 为严格对角占优，那么A是非奇异的证：用反证法。设A

7、是奇异阵，那么存在 使得记 的第k个方程这与A严格对角占优矛盾。A非奇异定理2.7 设A严格对角占优。那么求解的Jacobi迭代和Gauss-Seidel迭代均收敛。证明： Jacobi迭代的迭代矩阵其中 Gauss-Seidel迭代收敛性A严格对角占优， 考虑G的特征值设为G的特征值。那么 。由于 ， （为G的特征值）令要证 ，从而有。Gauss-Seidel迭代收敛用反证法。设满足。利用A是严格对角占优这表明，矩阵C严格对角占优， 为非奇异， ，这说明满足时不是G的特征值例2.7 用Jacobi迭代法和Gauss-Seidel迭代法 求解其中解 Jacobi迭代Gauss-Seidel数值

8、结果看出。二个方法均收敛。事实上A为严格对角占优。此外，Gauss-Seidel迭代比Jacobi迭代收敛更快。（V）迭代法收敛速度，任取 称为误差向量。并有此外，注意到 是任取的，因此可以认为 是任取的。即 给出了迭代次后误差向量范数与初始误差向量范数之比的最小上界（上确界）一般要求其中 ，一般为一相当小的数。已经证明 采用算子范数有 。 那么当 时 有 从而有 改写上面条件 为两边取对数可以看出，收敛快慢与 有关定理2.8 设 为任一矩阵范数（算子范数），那么有定义2.5 称为迭代法 的渐近收敛速度；称为上述迭代法的平均收敛速度。一般都采用渐近收敛速度来讨论迭代的收敛速度。由定义可以看出，

9、迭代方法的谱半径越小，收敛速度越大。例2.8 讨论用Jacobi迭代法和Gauss-Seidel迭代法解方程组的收敛性。如果收敛，试比较哪种方法收敛较快。其中解（1）Jacobi迭代方法收敛（2）Gauss-Seidel迭代 ， Gauss-Seidel迭代法收敛 Gauss-Seidel方法收敛快。并有： §3 超松弛（SOR）迭代法（I）超松弛（Successive over-Relaxation. SOR）迭代法Gauss-Seidel： 求解过程中 Gauss-Seidel迭代（包括Jacobi迭代）收敛速度较小，为此可用加权来加速。上述Gauss-Seidel迭代结果不作为

10、此次迭代计算值，而仅作为中间值。记为，最后结果为与上次结果的加权平均由于是Gauss-Seidel迭代结果，因此上式写成分量形式有推导SOR的矩阵形式SOR的迭代法的迭代矩阵定理3.1 （Kahan） 设 ，其对角元素皆非零。那么对所有实数，有证： ，其中L为严格下三角阵，U为严格上三角阵， 非奇异 对任矩阵 有 det设 为的n个特征值，那么有推论。如果求解的SOR方法收敛，那么有证明：SOR收敛，定理3.2 （Ostrowski-Reich）设 ，A对称正定，且，那么求解的SOR方法收敛。证明 设分别为的特征值和特征向量。A对称但不是对称的。因此可以是复数和复向量。A对称，用对上式作内积有

11、A对称正定，D对称正定记 有 记 从而得出要求 ，即分子< 分母 分子分母由于； A对称，正定， 分子分母 。 SOR方法收敛。推论 设A对称，正定；那么求解 的Gauss-Seide迭代法收敛。定理3.3 设，对称正定。对称正定，那么求解 的Jacobi迭代收敛。例3.1 用 和的SOR迭代法求解方程组 ，其中方程组的准确解为A对称正定 ，因此迭代是收敛的。， 即为Gauss-Seidel迭代取 。SOR迭代公式为取 可以看出，时，SOR收敛较快。定理3.4 如果方程组 中矩阵A对称正定并是三对角阵，那么。SOR方法的最佳松弛因子。采用的这个选择， 随的变化而变化。存在使，称为最佳松弛因子。 变化如下图02在的右边呈线性变化，在的左边，变化非常剧烈。因此一般取稍大于。对于例子3.1 是对称、正定的三对角矩阵。；在计算中，取稍大于。在例子3.1中，取较好。例3.2 设方程组 ，其中（1） 写出Jacobi迭代法的分量形式，求出Jacobi迭代矩阵的谱半径；（2） 求出SOR迭代法的最佳松弛因子及解 （1）（2） 例3.3 设方程组 ，其中 试证明，当 时，用Gauss-Seidel求解收敛； 当时，Jacobi迭