沒有幻燈片標(biāo)題中原工學(xué)院

1、3.3 3.3 超松弛法超松弛法1| )(|max)(1 BBini 定理定理3.13.1 )(0kBk1| )(|max)()3(1 BBini kBk, 0)2(定理定理3.23.2 下列三個(gè)下列三個(gè)命題等價(jià)命題等價(jià) )1()()1(gBxxkk 真真解解都都收收斂斂于于線線性性方方程程組組的的對(duì)對(duì))0(x ),2,1(ni 111)()1()()1( ijnijkjijkjijiiikikixaxabaxx如果如果該修正量乘上一個(gè)因子該修正量乘上一個(gè)因子 , ,則有迭代式則有迭代式: : 11)()1()()1( ijnijkjijkjijiiikikixaxabaxx )1( kix

2、)(kix 高斯高斯塞德爾迭代法是塞德爾迭代法是 在在 的基礎(chǔ)上的基礎(chǔ)上加上一個(gè)修正量加上一個(gè)修正量, ,即即 1 時(shí)時(shí), ,低低( (亞亞) )松弛松弛, ,可使不收斂的迭代收斂可使不收斂的迭代收斂; ; 松弛因子松弛因子, =1 , =1 ,正好正好松弛松弛即即SeidelSeidel方法方法 1 時(shí)時(shí), ,超松弛超松弛, ,可使迭代的收斂速度加快可使迭代的收斂速度加快. .統(tǒng)稱統(tǒng)稱超松弛超松弛 ),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方法對(duì)任意方法對(duì)任

4、意 都收斂的都收斂的必要條件必要條件是是證明證明 設(shè)設(shè) 為為 的特征值的特征值, ,則則 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 若系數(shù)矩陣若系數(shù)矩陣A A實(shí)實(shí)對(duì)稱正定，則對(duì)稱正定，則超松弛迭代超松弛迭代法法對(duì)任意對(duì)任意 都收斂都收斂的的充要條件充要條件是：是：)0(x推論推論 若系數(shù)矩陣若系數(shù)矩陣A 對(duì)稱正定，則線性方程組的對(duì)稱正定，則線性方程組的SeidelSeidel迭代迭

5、代法對(duì)任意法對(duì)任意 收斂。收斂。 （證略）（證略）opt 最佳松弛因子最佳松弛因子 選取問題選取問題: : 取何值時(shí)取何值時(shí), ,收斂速度最快收斂速度最快? ?例例 用用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) 取松弛因子取松弛因子 計(jì)算結(jié)果為：計(jì)算結(jié)果為：3 . 1 且且52)11(*2)11(1046. 0 xx迭代次數(shù)迭代次數(shù) k=110 . 1 (2)(2) 當(dāng)取當(dāng)取 時(shí)，初始向量相同，達(dá)到同時(shí)，初始向量相同，達(dá)到同樣精度所需要迭代次數(shù)樣精度所需要迭代次數(shù) k=22. . 7 . 1 (3)(3) 當(dāng)取當(dāng)取 時(shí)，初始向量相同，達(dá)到同

7、時(shí)，初始向量相同，達(dá)到同樣精度，則需要迭代樣精度，則需要迭代k=33次。次。0.13.1 op 對(duì)于此例，最佳松弛因子對(duì)于此例，最佳松弛因子 ，即達(dá)到同樣精度所需迭代次數(shù)最少。即達(dá)到同樣精度所需迭代次數(shù)最少。由此可知，用由此可知，用SOR 方法解線性方程組時(shí)，松弛方法解線性方程組時(shí)，松弛因子選擇得當(dāng)，常會(huì)使因子選擇得當(dāng)，常會(huì)使 S O R迭代收斂加速。迭代收斂加速。 B(3) (3) 松弛迭代矩陣松弛迭代矩陣 的譜半徑的譜半徑1)( Bp定理定理3.93.9 若系數(shù)矩陣若系數(shù)矩陣A A是是三對(duì)角三對(duì)角對(duì)稱正定矩陣對(duì)稱正定矩陣，有，有opt 最佳松弛因子最佳松弛因子 選取問題選取問題, ,通常是

8、選取不通常是選取不同的同的 , ,根據(jù)迭代過程收斂的快慢根據(jù)迭代過程收斂的快慢, ,不斷修改不斷修改 , ,直到滿意為止直到滿意為止. . ; 1)()()1(2 JSBpBp(2)(2) 最佳松弛因子最佳松弛因子)(112SoptBp ( (例題見教材例題見教材P90P90頁(yè)頁(yè)) )系數(shù)矩陣非奇異時(shí)直接法可求解；系數(shù)矩陣非奇異時(shí)直接法可求解；迭代法要求迭代法要求aii求不為零。求不為零。 非零元素分布不規(guī)則，階數(shù)很高時(shí)非零元素分布不規(guī)則，階數(shù)很高時(shí), ,直接法求直接法求解時(shí)解時(shí)存儲(chǔ)困難存儲(chǔ)困難; ;舍入誤差積累舍入誤差積累, ,是近似解，答案不是近似解，答案不可靠，可靠，直接法主要求解階數(shù)不很高的線性方程組直接法主要求解階數(shù)不很高的線性方程組. . 迭代法迭代法 按某種規(guī)則產(chǎn)生按某種規(guī)則產(chǎn)生近似解序列近似解序列x(k) ，使其極限逼近精確解使其極限逼近精確解( (好壞主要集中體現(xiàn)在此迭好壞主要集中體現(xiàn)在此迭代序列的收斂速度上代序列的收斂速度上) )算法簡(jiǎn)單，因而編程比較算法簡(jiǎn)單，因而編程比較容易容易. 舍入誤差僅積累了最后迭代的誤差舍入誤差僅