第3章 线性方程组的解法—迭代法.ppt

　　定理8说明解Ax=b的SOR迭代法，只有在(0, 2)范围内取松弛因子?，才可能收敛. 　　定理9(SOR方法收敛的充分条件) 设有方程组 Ax=b，如果： 　　(1) A为对称正定矩阵，A=D-L-LT; 　　(2) 0?2. 则解方程组 Ax=b的SOR迭代法收敛. 　　证 在上述假定下，设迭代矩阵L?的任一特征值为?，只要证明|?|1即可. 　　事实上，设y为对应?的Lω的特征向量，即 亦即 有内积 则 因为A正定，所以D正定，记(Dy, y)=?0. 令 -(Ly, y)=a+ib，则由复向量内积的性质有 　　当0?2时，有(分子减分母) 即L?的任一特征值满足|?|1, 故SOR迭代法收敛. 　　由定理3证明中可知，如果?(B)1且?(B)越小时，迭代法收敛越快. 现设有方程组 　　下面讨论迭代法的收敛速度. x=Bx+f， B=(bij)∈Rn×n， 及一阶定常迭代法 x(k+1)=Bx(k)+f (k=0,1,?)， 由基本定理有0?(B)1，且误差向量ε(k)=x(k)-x*满足 且设迭代法收敛，即对任取x(0)，记 ε(k)=Bkε(0)， 故 　　现设B为对称矩阵，则有 下面确定使初始误差缩小10-s所需的迭代次数, 即使 取对数，得到所需最少迭代次数为 此式说明，满足精度所需迭代次数与R=-ln?(B)成反比，当?(B)1越小，R=-ln?(B)越大，则满足所需迭代次数越少，即迭代法收敛越快. 当迭代矩阵B为一般矩阵时的讨论可参考[7]. 　　定义5 称R(B)=-ln?(B)为迭代法 x(k+1)=Bx(k)+f (k=0,1,?)的渐近收敛速度，简称迭代法收敛速度. 　　对于SOR迭代法希望选择松弛因子?使迭代过程收敛较快，在理论上即确定最佳因子?opt使 　　对某些特殊类型的矩阵，建立了SOR方法最佳因子理论. 例如，对所谓具有“性质A”等条件的线性方程组建立了最佳松弛因子公式 其中?(J)为解Ax=b的jacobi迭代法的迭代矩阵的谱半径. 　　在实际应用中，对于某些椭圆型微分方程(模型问题)可以给出?opt的计算方法，但一般说来，计算?opt是有困难的，可用试算的办法来确定一个适当的?. 　　算法2(SOR迭代法)见书p255. 　　定理 若Jacobi 迭代矩阵J 为非负矩阵，则下列关系有一个且仅有一个成立： (1) ?(J)=?(G)=0； (2) 0?(G)?(J)1； (3) ?(J)=?(G)=1； (4) 1?(J)?(G). 　　说明：当Jacobi 迭代矩阵J为非负矩阵时, Jacobi方法和 Gauss—Seidel 方法同时收敛或同时发散, 若为同时收敛, 则后者比前者收敛快. 　　例如 已知方程组 判断雅可比迭代法和高斯—塞德尔法的敛散性？ 　　解 因为雅可比迭代矩阵 故Jacobi 迭代法收敛. 　　再由定理的(2)或由 A 对称正定知 Gauss—Seidel迭代法也收敛，且比 Jacobi 迭代法收敛得快. 6.4* 分块迭代法 　　这一节略，见书p256. 由上述讨论，需要研究{x(k)}的收敛性. 引进误差向量 由(1.6)减去(1.5)式，得ε(k+1)=Bε(k)(k=0,1,2,?)，递推得 要考察{x(k)}的收敛性，就要研究B在什么条件下有limε(k)=0 (k→∞)，亦即要研究B满足什么条件时有Bk→0(零向量) (k→∞) . * 雅可比迭代法与高斯—塞德尔迭代法 3.4.3 松弛迭代法(SOR方法) 我们取?0为松弛因子，建立迭代格式如下 即 或改写为 其逐次超松弛迭代矩阵为 逐次超松弛法可写为矩阵形式 称为逐次超松弛迭代法，简称SOR方法. 显然，?=1就是Gauss—Seidel 迭代法. 下面用矩阵方法推导，选取分裂矩阵M为带参数的下三角矩阵 从而得到解Ax=b的逐次超松弛迭代法 (Successive Over Relaxation Method，简称SOR方法). 其中?0为可选择的松弛因子. 于是，由(2.3)可构造一个迭代法，其迭代矩阵为 解Ax=b的SOR方法为. 其中 下面给出解Ax=b的SOR方法的分量计算公式. 记 由(2.10)式可得 由此，得到解Ax=b的SOR方法的计算公式 (1) 显然，当?=1时即为Gauss—Seidel 迭代法.