没有幻灯片标题中原工学院

1、3.3 3.3 超松弛法超松弛法1| )(|max)(1 BBini 定理定理3.13.1 )(0kBk1| )(|max)()3(1 BBini kBk, 0)2(定理定理3.23.2 下列三个下列三个命题等价命题等价 )1()()1(gBxxkk 真真解解都都收收敛敛于于线线性性方方程程组组的的对对)0(x ),2,1(ni 111)()1()()1( ijnijkjijkjijiiikikixaxabaxx如果如果该修正量乘上一个因子该修正量乘上一个因子 , ,则有迭代式则有迭代式: : 11)()1()()1( ijnijkjijkjijiiikikixaxabaxx )1( kix

2、)(kix 高斯高斯塞德尔迭代法是塞德尔迭代法是 在在 的基础上的基础上加上一个修正量加上一个修正量, ,即即 1 时时, ,低低( (亚亚) )松弛松弛, ,可使不收敛的迭代收敛可使不收敛的迭代收敛; ; 松弛因子松弛因子, =1 , =1 ,正好正好松弛松弛即即SeidelSeidel方法方法 1 时时, ,超松弛超松弛, ,可使迭代的收敛速度加快可使迭代的收敛速度加快. .统称统称超松弛超松弛 ),2,1(ni 11)()1()()1( ijnijkjijkjijiiikikixaxabaxx ),2,1(ni 11)()1()()1( ijnijkjijkjijiiikikixaxab

3、axx )1(111)()1()()1( ijnijkjijkjijiiikikixaxabaxx 将上式改为将上式改为 ),2,1,0;,2,1( kni若若 超松弛法的矩阵形式为超松弛法的矩阵形式为)()1()()1(1)()1(kkkkUxLxbDxx bxULDAx )(bLDxUDLDxkk 1)(1)1()()1()( bLDxUDLDxkk 1)(1)1()()1()( 则则超松弛迭代法的迭代矩阵超松弛迭代法的迭代矩阵为为)1()(1UDLDB 超松弛迭代法收敛的充要条件是超松弛迭代法收敛的充要条件是1)( Bp)0(x20 定理定理3.43.4 SOR SOR方法对任意方法对任

4、意 都收敛的都收敛的必要条件必要条件是是证明证明 设设 为为 的特征值的特征值, ,则则 n ,21 B Bn21)1()(1UDLD )1(1UDLD nnnnaaaaaa)1()1()1()(221112211 n)1( 要使超松弛迭代法收敛要使超松弛迭代法收敛, ,必须必须n)1( 1)(21 nnBp 20 )0(x定理定理3.53.5 若系数矩阵若系数矩阵A A实实对称正定，则对称正定，则超松弛迭代超松弛迭代法法对任意对任意 都收敛都收敛的的充要条件充要条件是：是：)0(x推论推论 若系数矩阵若系数矩阵A 对称正定，则线性方程组的对称正定，则线性方程组的SeidelSeidel迭代迭

5、代法对任意法对任意 收敛。收敛。 （证略）（证略）opt 最佳松弛因子最佳松弛因子 选取问题选取问题: : 取何值时取何值时, ,收敛速度最快收敛速度最快? ?例例 用用SOR 方法解方程组方法解方程组111141111411114111144321xxxx解解 精确解精确解Tx) 1, 1, 1, 1(*Tx)0 .0 , 0 .0 , 0 .0 , 0 .0()0(取初始向量取初始向量SOR 迭代公式：迭代公式：), 1 , 0()41 (4)41 (4)41 (4)41 (4)(4)1(3)1(2)1(1)(4)1(4)(4)(3)1(2)1(1)(3)1(3)(4)(3)(2)1(1)

6、(2)1(2)(4)(3)(2)(1)(1)1(1kxxxxxxxxxxxxxxxxxxxxxxxxkkkkkkkkkkkkkkkkkkkkkkkkTx)99999912. 0,999999953. 0,00000310. 1,99999646. 0()11(1) 取松弛因子取松弛因子 计算结果为：计算结果为：3 . 1 且且52)11(*2)11(1046. 0 xx迭代次数迭代次数 k=110 . 1 (2)(2) 当取当取 时，初始向量相同，达到同时，初始向量相同，达到同样精度所需要迭代次数样精度所需要迭代次数 k=22. . 7 . 1 (3)(3) 当取当取 时，初始向量相同，达到同

7、时，初始向量相同，达到同样精度，则需要迭代样精度，则需要迭代k=33次。次。0.13.1 op 对于此例，最佳松弛因子对于此例，最佳松弛因子 ，即达到同样精度所需迭代次数最少。即达到同样精度所需迭代次数最少。由此可知，用由此可知，用SOR 方法解线性方程组时，松弛方法解线性方程组时，松弛因子选择得当，常会使因子选择得当，常会使 S O R迭代收敛加速。迭代收敛加速。 B(3) (3) 松弛迭代矩阵松弛迭代矩阵 的谱半径的谱半径1)( Bp定理定理3.93.9 若系数矩阵若系数矩阵A A是是三对角三对角对称正定矩阵对称正定矩阵，有，有opt 最佳松弛因子最佳松弛因子 选取问题选取问题, ,通常是

8、选取不通常是选取不同的同的 , ,根据迭代过程收敛的快慢根据迭代过程收敛的快慢, ,不断修改不断修改 , ,直到满意为止直到满意为止. . ; 1)()()1(2 JSBpBp(2)(2) 最佳松弛因子最佳松弛因子)(112SoptBp ( (例题见教材例题见教材P90P90页页) )系数矩阵非奇异时直接法可求解；系数矩阵非奇异时直接法可求解；迭代法要求迭代法要求aii求不为零。求不为零。 非零元素分布不规则，阶数很高时非零元素分布不规则，阶数很高时, ,直接法求直接法求解时解时存储困难存储困难; ;舍入误差积累舍入误差积累, ,是近似解，答案不是近似解，答案不可靠，可靠，直接法主要求解阶数不很高的线性方程组直接法主要求解阶数不很高的线性方程组. . 迭代法迭代法 按某种规则产生按某种规则产生近似解序列近似解序列x(k) ，使其极限逼近精确解使其极限逼近精确解( (好坏主要集中体现在此迭好坏主要集中体现在此迭代序列的收敛速度上代序列的收敛速度上) )算法简单，因而编程比较算法简单，因而编程比较容易容易. 舍入误差仅积累了最后迭代的误差舍入误差仅