第五章 第三節(jié) SOR迭代法

1、SOR迭代法迭代法第三節(jié)第三節(jié)一、一、 迭代格式迭代格式 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一個修正量一個修正量 ?，F(xiàn)在，為了獲得更快的收斂?，F(xiàn)在，為了獲得更快的收斂k步步 ，相當于在第，相當于在第 步的基礎上每一個分量增加步的基礎上每一個分量增加效果，在修正項的前面乘以一個參數(shù)效果，在修正項的前面乘以一個參數(shù) ，便得到，便得到逐次超松弛迭代格式逐次超松弛迭

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 上述定理說明，對于任何系數(shù)矩陣上述定理說明，對于任何系數(shù)矩陣 ，若要，若要ASOR0,

8、202ASOR陣來說，這一條件是充分的。陣來說，這一條件是充分的。陣陣 來說，來說， 法都是收斂的。但是，對一些特殊矩法都是收斂的。但是，對一些特殊矩弛因子滿足條件弛因子滿足條件 時，并不是對所有系數(shù)矩時，并不是對所有系數(shù)矩法收斂，必須選取松弛因子法收斂，必須選取松弛因子 ， 然而，當松然而，當松因此有因此有 ，或者，或者 ，即，即 。定理證完定理證完。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迭代次數(shù)迭代次數(shù)161087811151515近 似 解 與近 似 解 與準 確 解 重準 確 解 重復合位數(shù)復合位數(shù)555555541 使使 法收斂最快的松弛因子通常稱為法收斂最快的松弛因子通常稱為最最 優(yōu)優(yōu) 松松弛因子弛因子。目前，只有少數(shù)特殊類型的矩陣，才有確定。目前，只有少數(shù)特殊類型的矩陣，才有確定的最優(yōu)松弛因子的理論公式，但實際使用時也有一定的最優(yōu)松弛因子的理論公式，但實際使用時也有一定困難。通常的辦法，是選不同的困難。通常的辦法，是選不同的 進行試算，以確定進行試算，以確定最佳最佳 的近似值，或者先取一個的近似值，或者先取一個 ，然后根，然后根據(jù)迭代過程的收斂快慢，不斷修正據(jù)迭代過程的收斂