第七章 线性代数方程组的迭代法

第七章线性代数方程组的迭代法第一页，共二十一页，编辑于2023年，星期四§1迭代法基础

问题

在实际应用中遇到的系数矩阵多为大型稀疏矩阵，如用求解线性方程组的直接法求解，在计算机上会耗费大量的时间和存储单元。在许多应用问题中使用迭代法。第二页，共二十一页，编辑于2023年，星期四思路将改写为等价形式，建立迭代,从初值出发，得到序列。研究内容：

如何建立迭代格式？

收敛速度？

向量序列的收敛条件？

误差估计？第三页，共二十一页，编辑于2023年，星期四一般迭代法定义1对方程组，化为等价方程组，设为任取的初值，将上式写为迭代过程这种迭代过程称为逐次逼近法，B称为迭代矩阵。若称逐次逼近法收敛，否则，称逐次逼近法不收敛或发散。第四页，共二十一页，编辑于2023年，星期四问题：按上述思想迭代产生的向量序列在什么条件下收敛于方程组Ax=b的解？引进误差向量：，其中为方程组的解，即有所以，要使收敛到，则需研究在什么条件下有。第五页，共二十一页，编辑于2023年，星期四迭代法的收敛条件与误差估计引理

当k

时，Bk0

(B)<1定理1

设有线性方程组，那么逐次逼近法对任意初始向量收敛的充分必要条件是迭代矩阵B的谱半径(B)<1。注：要检验一个矩阵的谱半径小于1比较困难，

所以我们希望用别的办法判断收敛性。

第六页，共二十一页，编辑于2023年，星期四注:1.因为矩阵范数都可以直接用矩阵的元素计算，因此用定理2，很容易判别逐次逼近法的收敛性。2.定理2是充分条件，当找不到矩阵的某一范数小于1时，并不能判断迭代法不收敛。①②定理2设线性方程组有惟一解，若存在一个矩阵范数使得||B||<1,则迭代收敛,且有下列误差估计：第七页，共二十一页，编辑于2023年，星期四（7.1）

1．雅克比（Jacobi）迭代法设有n阶方程组§2几种常用的迭代法第八页，共二十一页，编辑于2023年，星期四若系数矩阵非奇异，且(i=1,2,…,n)，将方程组（7.1）改写成第九页，共二十一页，编辑于2023年，星期四然后写成迭代格式（7.2）（7.2）式也可以简单地写为（7.3）第十页，共二十一页，编辑于2023年，星期四记,其中则雅克比迭代法的矩阵形式为：(7.4)称为雅克比迭代矩阵。第十一页，共二十一页，编辑于2023年，星期四第十二页，共二十一页，编辑于2023年，星期四…………写成矩阵形式：2．高斯――赛得尔(Gauss-Seidel)迭代法(7.5)(7.6)其中称为高斯―赛得尔迭代矩阵。第十三页，共二十一页，编辑于2023年，星期四定理4n阶矩阵A是严格对角占优矩阵的充分必要条件是Jacobi迭代法的迭代矩阵满足‖BJ‖∞<1。3．Jacobi迭代法和Gauss-Seidel迭代法的收敛性定理5如果A是严格对角占优矩阵，那么Jacobi和G－S迭代法都收敛。定理6若A是n阶正定矩阵，那么G-S迭代法收敛。定理3n阶矩阵A是严格对角占优矩阵，则A非奇异，且所有对角元。第十四页，共二十一页，编辑于2023年，星期四注意的问题（1）Jacobi迭代法和Gauss-Seidel迭代法的迭代矩阵不同：BJ=D-1(L+U),BG-S=(D-L)-1U（2）Jacobi迭代法和Gauss-Seidel迭代法收敛性没有必然的联系。即当Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛（3）Jacobi迭代和Gauss-Seidel迭代的特征方程：第十五页，共二十一页，编辑于2023年，星期四Jacobi迭代：Gauss-Seidel迭代：第十六页，共二十一页，编辑于2023年，星期四用Jacobi迭代法求解收敛，但用Gauss-Seidel法不收敛。BJ的特征值为0，0，0，BG－S的特征值为0，2，2（4）举例：用Jacobi迭代法求解不收敛，但用Gauss-Seidel法收敛。第十七页，共二十一页，编辑于2023年，星期四系数矩阵A是正定矩阵，因此用Gauss-Seidel法收敛。线性方程组的系数矩阵为是严格对角占优的，所以Jacobi和Gauss-Seidel迭代格式均收敛。第十八页，共二十一页，编辑于2023年，星期四（1）迭代（2）加速（7.7）即§3超松驰迭代法（SOR法）

（SequentialOver-Relaxation)矩阵形式：第十九页，共二十一页，编辑于2023年，星期四注：1.称为超松弛迭代矩阵。2.称为松弛因子。3.当时，就是G-S迭代法；当时，称为低

松弛迭代法；当时，称为超松弛迭代法。4.SOR法也称为G-S迭代法的一种加速方法。5.研究SOR法就是需要找到最佳松弛因子，使得迭代过程的收敛速度最快，即。6.在找最佳松弛因子之前，先要解决在什么范围内取值，才能保证SOR法收敛。第二十页，共二十一页，编辑于2023年，星期四定理7对Ax=b,