第五章 第三节 SOR迭代法

1、SOR迭代法迭代法第三节第三节一、一、 迭代格式迭代格式 SOR 二二 迭代法的收敛性迭代法的收敛性 SOR一、一、 迭代格式迭代格式 SOR是是 ( 逐次超松弛逐次超松弛 )SOR的缩写。的缩写。SOR 迭代法是解大型稀疏矩阵方程组的有效迭代法是解大型稀疏矩阵方程组的有效方法之一。它可以看作是方法之一。它可以看作是 迭迭 代代 法法 的加的加GaussSeidel 迭代法是迭代法是 迭代的一种特殊形式。迭代的一种特殊形式。eSuccesiveOverR laxationGaussSeidel速，速，SOR将方程组将方程组 写成写成AXb1 122,11,(1,2, )iii iiiiiinn

2、ia xa xaxa xa xbin(0)iia GaussSeidel其其 迭迭 代代 格格 式式 可写为可写为 ： 1 122,11,111()iiiiii iiiiiiii iiinnxxba xa xaxaa xaxa x1 122,11,111 122,11,11()iiiiiii iii iiinniiiiiiiiii iiiiii iiinna xba xa xaxaxa xa xa xba xa xaxa xaxa x则有若记若记 1( )(1)( )1(),inkkkiiijjijjjj irba xa x1,2,in(1)( )(1)(1)( )( )1 1,1,11kkk

3、kkkiiiii iiiiiinniixxba xaxa xa xa3.11( )(1)( )11inkkkiiijjijjjj iiixba xa xa则则 式可写为式可写为3.1(1)( )( )1kkkiiiiixxra3.2 由此可以看出，由此可以看出， 迭代法的第迭代法的第GaussSeidel1k ( )1kiiira一个修正量一个修正量 。现在，为了获得更快的收敛。现在，为了获得更快的收敛k步步 ，相当于在第，相当于在第 步的基础上每一个分量增加步的基础上每一个分量增加效果，在修正项的前面乘以一个参数效果，在修正项的前面乘以一个参数 ，便得到，便得到逐次超松弛迭代格式逐次超松弛迭

4、代格式3.3(1)( )( ),1,2,kkkiiiiixxrina 称称 为松弛因子，称为松弛因子，称 的的 迭迭 代代 过过 程程 为低松弛方法，对于一些方程组，用为低松弛方法，对于一些方程组，用 迭代迭代法得不到收敛解或不收敛，但用低松弛方法却是收敛法得不到收敛解或不收敛，但用低松弛方法却是收敛的的 。称称 的迭代过程的迭代过程 为超为超 松松 弛弛 方法方法, 此法此法3.3GaussSeidel可以加速可以加速 迭迭 代代 方方 法法 的收敛。的收敛。 的迭的迭代过程代过程 就是就是 迭代公式。迭代公式。 13.3GaussSeidelGaussSeidel13.30111( )(1

5、)( )11inkkkkiiiijjijjjj iiixxba xa xa由迭代格式（3.3）有 11( )(1)( )11inkkkkkiiiiijjijjjj iiixxxba xa xa 格式（格式（3.4）的矩阵形式为）的矩阵形式为 (1)1( )(1),kkkkXXDbLXUX3.5 SOR迭代法常以这种形式进行计算。迭代法常以这种形式进行计算。 11( )(1)( )11(1),inkkkkiiiijjijjjj iiixxba xa xa 1,2,in3.4即有其中其中 11220,0nnaaDa211,1000nn naLaa1211,0000nnnaaUa显然，显然， .AD

6、LU 二二 迭代法的收敛性迭代法的收敛性 SOR由由 式有式有 3.5 111kkkkDXDXbLXUX即 111kkkkDXLXDXUXb 1111() 1() 1()kkkkDL XDU XbXDLDU XDLb于是有记记11 1BDLDUFDLb3.6则有则有 1kkXB XF3.7其中，称其中，称 为为 迭代矩阵。迭代矩阵。 BSOR 由定理由定理1及定理及定理2直接得知：直接得知：SOR1B（2） 迭代法收敛的充分条件是迭代法收敛的充分条件是 。1BSOR（1） 迭代法收敛的充要条件是迭代法收敛的充要条件是 。子子 有关有关 。 关于关于 的范围，有如下定理。的范围，有如下定理。 迭

7、代法收敛与否或收敛快慢都与松弛因迭代法收敛与否或收敛快慢都与松弛因SOR因子因子 应满足条件应满足条件 。定理定理6 迭代法收敛的必要条件是松弛迭代法收敛的必要条件是松弛SOR02B证明证明 因因 法收敛，故法收敛，故 。记。记 的的 特征值特征值 为为 。因为。因为n阶矩阵的阶矩阵的n个个 特征值之积等于其行列式之值，即特征值之积等于其行列式之值，即 SOR1B1,2,n 1,2det,nB 而iB1,2det,1nnBB 从而另一方面另一方面 由关系式：1 1BDLDU有1detBdetdet1DLDU 上述定理说明，对于任何系数矩阵上述定理说明，对于任何系数矩阵 ，若要，若要ASOR0,

8、202ASOR阵来说，这一条件是充分的。阵来说，这一条件是充分的。阵阵 来说，来说， 法都是收敛的。但是，对一些特殊矩法都是收敛的。但是，对一些特殊矩弛因子满足条件弛因子满足条件 时，并不是对所有系数矩时，并不是对所有系数矩法收敛，必须选取松弛因子法收敛，必须选取松弛因子 ， 然而，当松然而，当松因此有因此有 ，或者，或者 ，即，即 。定理证完定理证完。11n1102det1det1detnDUBDL即 这一定理说明，这一定理说明， 对于对称正定矩阵对于对称正定矩阵 ，只要，只要 ， 迭代法总是收敛的。迭代法总是收敛的。02SORSOR 用用 法计算方程组时，选取合适的松弛因法计算方程组时，选

9、取合适的松弛因子很重要，松弛因子选取得好，可能使得收敛速子很重要，松弛因子选取得好，可能使得收敛速度大大加快，下面举例来说明松弛因子的选取对度大大加快，下面举例来说明松弛因子的选取对收敛速度的影响。收敛速度的影响。 定理定理7 如果矩阵如果矩阵 是对称正定的，则是对称正定的，则 法法对于对于 是收敛的。是收敛的。 02ASOR设给定方程组设给定方程组 12340.780000.02000.120000.140000.856530.020000.860000.040000.06000.420760.120000.040000.720000.080000.239480.140000.060000.

10、080000.740000.60632xxxx 用用 法进行迭代，取不同的松弛因子法进行迭代，取不同的松弛因子 ，收，收敛速度不同，见下表敛速度不同，见下表 SOR0.60.811.11.151.251.31.51.8迭代次数迭代次数161087811151515近 似 解 与近 似 解 与准 确 解 重准 确 解 重复合位数复合位数555555541 使使 法收敛最快的松弛因子通常称为法收敛最快的松弛因子通常称为最最 优优 松松弛因子弛因子。目前，只有少数特殊类型的矩阵，才有确定。目前，只有少数特殊类型的矩阵，才有确定的最优松弛因子的理论公式，但实际使用时也有一定的最优松弛因子的理论公式，但实际使用时也有一定困难。通常的办法，是选不同的困难。通常的办法，是选不同的 进行试算，以确定进行试算，以确定最佳最佳 的近似值，或者先取一个的近似值，或者先取一个 ，然后根，然后根据迭代过程的收敛快慢，不断修正据迭代过程的收敛