应用基础数值 7

应用数值分析第六讲线性方程组的迭代解法（二）3迭代法的收敛条件4教学小结提纲1问题引入2几种常用的迭代公式（2）教学目标与重难点教学目标SOR迭代法的应用，迭代法收敛的充要条件及充分条件。对SOR收敛法的必要条件进行证明。

2.能说出迭代法收敛的充要条件及充分条件；3.能描述某些特殊矩阵的迭代法收敛情况；教学重点教学难点

1.会用SOR迭代法求解实际问题。一问题引入一、问题引入上次课已学习线性方程组的常用迭代法，本次课将继续学习常用迭代法的SOR迭代法及研究迭代法的收敛性。二几种常用的迭代法公式（2）二、几种常用的迭代公式3.逐次超松弛法(SOR方法)逐次超松弛法(SuccessiveOverRelaxationMethod)可看成是Gauss-Seidel方法的加速，Seidel迭代法是SOR方法的特例。改写为记将Seidel法的迭代公式二、几种常用的迭代公式则为加快收敛，在增量前加一个因子，得称此公式为逐次超松弛法（0<ω<2）(SOR法)。当0<ω＜1时，称为低松弛法。当ω=1时，就是Gauss-Seidel迭代法。当1＜ω＜2时，称为超松弛法。二、几种常用的迭代公式故SOR方法的矩阵形式迭代公式为SOR方法的矩阵形式为例1用Seidel迭代法和取ω=1.15的SOR法求解方程组二、几种常用的迭代公式解

取初值x(0)=(0,0,0,0)T

，精度clc,clearall,formatlongA=[5,1,-1,-2;2,8,1,3;1,-2,-4,-1;-1,3,2,7];b=[-2;-6;6;12];omega=1.15;x0=[0;0;0;0];eps=1e-5;N=300;x=SOR(A,b,omega,x0,eps,N)（1）SOR法结果：迭代次数=8x=0.999996315914706-1.999997375285969-1.0000011130140602.999999137630378二、几种常用的迭代公式（2）Gauss-Seidel迭代法达到同样的精度，Gauss-Seidel迭代法需要迭代14步。而取ω=1.15的SOR法只需要迭代8步。由此可见选择适当的松弛因子，SOR方法收敛速度明显加快。clc,clearall,formatlongA=[5,1,-1,-2;2,8,1,3;1,-2,-4,-1;-1,3,2,7];b=[-2;-6;6;12];x0=[0;0;0;0];eps=1e-5;N=300;x=Gauss_Seidel(A,b,x0,eps,N)结果：迭代次数=14x=0.999996637507769-1.999997506074542-1.0000012767387212.999998815601262三迭代法的收敛条件三、迭代法的收敛条件设引进误差向量有基本定理

设迭代格式收敛，则二、迭代法的收敛条件定理1

对任意初始向量x(0)和f，由产生的迭代序列{x(k)}收敛的充要条件是ρ(B)<1.定理1是充分必要条件，既能判别迭代法收敛性，也可以判别迭代法不收敛。基本定理和定理1可以看到，迭代法收敛与否与迭代矩阵B的性态有关，与初始向量x(0)和右端向量f无关。但由于ρ(B)的计算常常比解方程组本身更困难，而由结论1又有ρ(B)≤||B||，所以当||B||<1时，必有ρ(B)<1。于是，有下述收敛的充分条件定理2。定理2

若||B||<1，则由迭代格式x(k+1)=Bx(k)+f

和任意初始向量x(0)产生的迭代序列{x(k)}收敛于准确解x*。且有误差估计三、迭代法的收敛条件定理2是迭代法收敛的充分条件，它只能判别收敛的情况，当||B||≥1时，不能由此断定迭代不收敛。常用||B||1<1或||B||∞<1判别迭代法收敛。常用结论1）来设置迭代终止的判别条件，即只要相邻两次的迭代结果之差达到误差精度时，迭代终止。由结论2）可知，当||B||的值越小，收敛就越快。也可以用||B||的值来近似估计迭代的次数，不过估计偏保守，次数一般偏大。三、迭代法的收敛条件例2

判别上一讲例中的Jacobi迭代法和Seidel迭代法的收敛性。解Jacobi迭代法收敛1）三、迭代法的收敛条件2)Gauss-Seidel迭代法收敛由于，所以Gauss-Seidel方法比Jacobi方法收敛快。例3

判别方程组的Jacobi迭代法的收敛性。三、迭代法的收敛条件解但Jacobi迭代法收敛三、迭代法的收敛条件定义1

若矩阵A=(aij)n×n

满足且至少一行成立严格不等式，则称A是对角占优的。定义2

若矩阵A=(aij)n×n

满足则称A是严格对角占优的。定义3

若矩阵A通过行交换和相应的列交换，能够变成

的形式，其中A11和A22为方阵，则称A是可约的，否则称A

是不可约的。三、迭代法的收敛条件例4方程组由于其系数矩阵是严格对角占优的，所以解该方程组的Jacobi迭代法和Seidel迭代法均收敛。定理31）若矩阵A严格对角占优，则A非奇异。

2）若A不可约，且具有对角占优，则A非奇异。定理4

若A

是严格对角占优或A是不可约对角占优，则解方程组Ax=b的Jacobi迭代法和Gauss-Seidel迭代法均收敛。三、迭代法的收敛条件定理5SOR方法收敛的必要条件是0<ω<2。证明松驰因子ω的选取将影响ρ(Bω)的大小，使ρ(Bω)最小的ω值称为最佳松弛因子，记为ω

opt。ω

opt的选取是一个相当复杂和困难的问题，目前还没有完善的方法，只有针对一些特殊矩阵有部分结果。三、迭代法的收敛条件

定理7

如果A是实对称正定矩阵，且0<ω<2，则SOR方法收敛由定理7，若A是实对称正定矩阵，则Gauss-Seidel方法收敛，但Jacobi方法不一定收敛。定理6若A是对称正定矩阵，且是三对角阵，则最佳松弛因子为

其中BJ是Jacobi迭代法的迭代矩阵。应用中常采取试算方法来确定最佳松弛因子。加速收敛的效果也随问题而有所改变。对有的问题，可加速很多倍，对有的问题则加速不明显.三、迭代法的收敛条件所以Seidel迭代法及SOR法(0<ω<2)都收敛，但A不是对角占优阵，就无法判断Jacobi迭代法收敛性，只有求ρ(BJ)。解例5若方程组的系数阵为试判断它对各种迭代法的收敛性.定理8

如果A严格对角占优矩阵，则当0<ω≤1时SOR方法收敛。三、迭代法的收敛条件所以对Jacobi迭代法不收敛。三、迭代法的收敛条件所以,Jacobi迭代法和Seidel迭代法均不收敛。但交换方程组中两个方程的顺序得解例6设有方程组为判别Jacobi和Seidel迭代法的收敛性。三、迭代法的收敛条件方程组的系数矩阵为是严格对角占优