迭代法的收敛性与稳定性ppt课件.ppt
,插 值 法,主讲教师：刘春凤,线性方程组的迭代解法,第 六章,五、 迭代法的收敛性与稳定性,一阶定常迭代法的基本定理,关于解某些特殊方程组迭代法的收敛性,迭代法的收敛性与稳定性,设 为 阶方阵的特征值， 的谱半径定义为：,的谱定义为：,事实上：对 的 及特征向量,由 的任意性：,当 对称时，,由 的任意性,迭代法的收敛性与稳定性,精确解，且设有等价的方程组,于是,设有解 的一阶定常迭代法,迭代法的收敛性与稳定性,有意义的问题是：迭代矩阵 满足什么条件时，由迭代法产生的向量序列 收敛到 .,误差向量的递推公式,研究迭代法(3.3)收敛性问题就是要研究迭代矩阵 满足什么条件时，有,迭代法的收敛性与稳定性,设有矩阵序列 及 ，如果,个数列极限存在且有,，则 称收敛于,记为,其中|为矩阵的任意一种,算子范数.,都有,迭代法的收敛性与稳定性,设有矩阵序列 ，其中 而,且设 ，考查矩阵序列极限.,解析,显然, 当 时, 则有,迭代法的收敛性与稳定性,设 ，则 （零矩阵）的充要条件：,证明,必要性,充分性,而,，于是,即,迭代法的收敛性与稳定性,证明,迭代法基本原理,迭代法的收敛性与稳定性,定理3和定理4的结论和起来即为,(1)迭代法 收敛,(2)迭代法 收敛,设 ，其中 为非奇异矩阵且 为非奇异矩阵,则有,(1) Jacobi迭代法收敛 ，其中,(2) G-S迭代法收敛 ，其中,(3) SOR迭代法收敛 ，其中,迭代法的收敛性与稳定性,考察用Jacobi方法解方程组 的收敛性.,解析,因为方程组的矩阵 及迭代矩阵 为,得迭代矩阵 的特征方程为,解得,迭代法的收敛性与稳定性,考察用Jacobi方法解方程组 的收敛性.,解析,解得,即 所以用Jacobi方法解方程组是收敛的.,迭代法的收敛性与稳定性,解析,考察用迭代法解方程组的收敛性. 其中,方程组的迭代矩阵B的特征方程为,这说明用迭代法解此方程组不收敛.,矩阵B的特征值为 ，即,迭代法的基本定理在理论上是重要的，根据谱半径的性质，下面利用矩阵 的范数建立判别迭代法收敛的充分条件.,迭代法的收敛性与稳定性,(迭代法收敛的充分条件),及一阶定常迭代法,设有方程组,如果有 的某种算子范数 ，则,迭代法收敛，即对任取 有,且,迭代法的收敛性与稳定性,证明,(1) 由基本定理4结论(1)是显然的.,(2) 显然有关系式 及,反复利用(b)即得(2).,于是有,(3) 考查,即得,迭代法的收敛性与稳定性,证明,(4) 利用(3)的结果反复利用(a)，则得到(4). 即,迭代法的收敛性与稳定性,关于解某些特殊方程组迭代法的收敛性,在科学及工程计算中，要求解方程组 ，其矩阵 常常具有某些特性. 例如， 具有对角占优性质或 为不可约阵，或 是对称正定阵，下面讨论用基本迭代法解这些方程组的收敛性.,(1) 如果A的元素满足,称A为严格(按行)对角占优阵.,对角占优阵,设,(2) 如果A的元素满足,且上式至少有一个不等式成立，称A为弱(按行)对角占优阵.,迭代法的收敛性与稳定性,关于解某些特殊方程组迭代法的收敛性,可约与不可约矩阵,其中 为 阶方阵， 为 阶方阵 ，则称 为可约矩阵. 否则，如果不存在这样置换阵 使上式成立，则称 为不可约矩阵.,为可约矩阵意即 可经过若干行列重排化为上式或 可化为两个低阶方程组求解(如果 经过两行交换的同时进行相应两列的交换，称对 进行一次行列重排).,迭代法的收敛性与稳定性,关于解某些特殊方程组迭代法的收敛性,于是，求解 化为求解,由上式第2个方程组求出 ,再代入第1个方程组求出 .,显然，如果 所有元素都非零，则 为不可约阵.,(对角占优定理) 如果A=(aij)nn为严格对角占优矩阵或A为不可约弱对角占优矩阵，则A为非奇异矩阵.,证明,只就A为严格对角占优矩阵证明此定理. 采用反证法，如果det(A)=0，则Ax=0有非零解，记为 ，则,即,这与假设矛盾，故det(A)0.,设方程组Ax=b，如果,(1) A为严格对角占优阵，则解Ax=b的Jacobi迭代法, Gauss-Seidel 迭代法均收敛.,(2) A为弱对角占优阵，且A为不可约矩阵, 则解Ax=b的Jacobi迭代法, Gauss-Seidel 迭代法均收敛.,证明,只证(1)，(2)作为练习,因为A是严格对角占优阵，所以,Jacobi迭代阵,则|J|1，所以 Jacobi 迭代法收敛.,下面证明GaussSeidel 迭代法收敛.,下面证明|1. 若不然, 即|1, 则,由于,所以,由 ，得,即矩阵,是严格对角占优矩阵，故可逆，这与(*) 式矛盾，所以|1, 从而 (G)1，即GaussSeidel迭代法收敛.,若A为正定矩阵，则方程组 Ax=b的Gauss-Seidel 迭代法收敛.,则内积,从而,因为A正定，所以D正定，故,证明,因为 ，设为G 的特征值，y为对应的特征(复)向量，即,所以|1, 从而(G)1, 故Gauss-Seidel迭代法收敛.,下面研究对于解方程组Ax=b的SOR方法中松弛因子在什么范围内取值，SOR方法才可能收敛.,令 ，则由复向量内积的性质有,(SOR方法收敛的必要条件) 设解方程组 Ax=b的SOR迭代法收敛，则02.,证明,由于SOR迭代法收敛，则 设迭代矩阵L的特征值为i (i=1,n)，则有,于是,所以|1-|1，即 02.,定理8说明解Ax=b的SOR迭代法，只有在(0, 2)范围内取松弛因子，才可能收敛.,(SOR方法收敛的充分条件) 设有方程组 Ax=b，如果：,(2) 02.,则解方程组 Ax=b的SOR迭代法收敛.,在上述假定下，设迭代矩阵L的任一特征值为，只要证明|1即可.,(1) A为对称正定矩阵， ;,证明,事实上，设y为对应的L的特征向量，即,亦即,有内积,则,因为A正定，所以D正定，记,令 ，则由复向量内积的性质有,当02时，有(分子减分母),即L的任一特征值满足|1, 故SOR迭代法收敛.,因为,及一阶定常迭代法,则,且设迭代法收敛，即对任取 ，记,由定理3证明中可知，如果 且 越小时，迭代法收敛越快. 现设有方程组,由基本定理有 ，且误差向量 满足,故,现设B为对称矩阵，则有,下面确定使初始误差缩小 所需的迭代次数, 即使,取对数，得到所需最少迭代次数为,此式说明，满足精度所需迭代次数与 成反比，当 越小， 越大，则满足所需迭代次数越少，即迭代法收敛越快.,称 为迭代法 的渐近收敛速度，简称迭代法收敛速度.,对于SOR迭代法希望选择松弛因子 使迭代过程收敛较快，在理论上即确定最佳因子opt使,对某些特殊类型的矩阵，建立了SOR方法最佳因子理论. 例如，对所谓具有“性质A”等条件的线性方程组建立了最佳松弛因子公式,其中 为解 的Jacobi迭代法的迭代矩阵的谱半径.,若Jacobi 迭代矩阵J 为非负矩阵，则下列关系有一个且仅有一个成立：,(1) (J)=(G)=0； (2) 0(G)(J)1；,(3) (J)=(G)=1； (4) 1(J)(G).,说明：当Jacobi 迭代矩阵J为非负矩阵时, Jacobi方法和 GaussSeidel 方法同时收敛或同时发散, 若为同时收敛, 则后者比前者收敛快.,已知方程组,判断雅可比迭代法和高斯塞德尔法的敛散性？,因为雅可比迭代矩阵,解析,故Jacobi 迭代法收敛.,再由定理的(2)或由 A 对称正定知 GaussSeidel迭代法也收敛，且比 Jacobi 迭代法收敛得快.,
