第5章01迭代公式的建立

1、第五章第五章 線性代數(shù)方程組的迭代法線性代數(shù)方程組的迭代法 5.1 5.1 迭代公式的建立迭代公式的建立 5.2 5.2 向量和矩陣的范數(shù)向量和矩陣的范數(shù) 5.3 5.3 迭代過程的收斂性迭代過程的收斂性 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 寫成矩陣形式寫成矩陣形式 Ax=b 其中其中1112111212222212, bnnnnnnnnaaaxbaaaxbAxaaaxb5.1 5.1 迭代公式的建立迭代公式的建立 設(shè)設(shè)線性代數(shù)方程組線性代數(shù)方程組迭代法就是用某種迭代法就是用某種極限過程極限過程去去逐步逼近逐步逼近線性方程組精

2、確解的方法。線性方程組精確解的方法。 基本思想基本思想：對給定的方程組：對給定的方程組Axb，寫成等價的形式，寫成等價的形式 xGxd 構(gòu)造一個迭代公式構(gòu)造一個迭代公式 (1)( )kkxGxd 當(dāng)給定初始向量當(dāng)給定初始向量 (0)x，進(jìn)行迭代，生成向量序列進(jìn)行迭代，生成向量序列 (1)(2)( ),kxxx 當(dāng)向量序列當(dāng)向量序列收斂到某個收斂到某個極限向量極限向量 x，即，即( )limkkxx 則則x是方程組是方程組Axb的的精確解精確解，即滿足，即滿足 *Axb 對給定的方程組對給定的方程組Axb，如何寫成等價的形式，如何寫成等價的形式xGxd 例如：設(shè)例如：設(shè)AMN，則有，則有()MN

3、 xb，MxNxb，11xMNxMb，寫成，寫成迭代公式迭代公式(1)( )kkxGxd 其中其中1GMN，1dM b。 又 ， 如又 ， 如 方 程 組方 程 組Axb， 寫 成， 寫 成0,AxbxxAxb，()xIA xb寫成寫成迭代公式迭代公式(1)( )kkxGxd 其中其中GIA，db 。 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111設(shè)設(shè)線性方程組線性方程組其中系數(shù)矩陣其中系數(shù)矩陣非奇異非奇異，且主對角元，且主對角元aii0，(i =1,2,n)，由第，由第i 個方程解出個方程解出xi，有，有111221331111 122

4、111()1()nnnnnnnnnnnxba xa xa xaxba xa xaxa5.1.1 雅可比迭代公式雅可比迭代公式11() , (1,2, )niiijjjiij ixba xina建立迭代格式建立迭代格式(1)( )( )( )11122133111(1)( )( )( )2221 1233222(1)( )( )( )1 122111()1()1()kkkknnkkkknnkkkknnnnnnnnnxba xa xa xaxba xa xa xaxba xa xaxa寫成寫成取初值取初值 ，進(jìn)行迭代。，進(jìn)行迭代。這種方法稱為這種方法稱為雅可比雅可比(Jacobi)迭代公式迭代公式

5、。(0)(0)(0)12,nxxx), 2 , 1(, )(11)()1(nixabaxnijjkjijiiiki ), 2 , 1(, )(11)()1(nixabaxnijjkjijiiiki 雅可比迭代公式雅可比迭代公式即即(i=1,2,n)1(1)( )( )111() , (1,2, )inkkkiiijjijjjj iiixba xa xina )(11)()()1(njkjijiiikikixabaxx雅可比迭代雅可比迭代的的算法框圖算法框圖(1)( )11()(1,2, )nkkiiijjjiij ixba xain例例 用雅可比迭代法求解方程組用雅可比迭代法求解方程組 123

6、1231231023210152510 xxxxxxxxx解解 從從3個方程分離出個方程分離出1232133120.20.10.30.20.11.50.20.42xxxxxxxxx構(gòu)造雅可比迭代公式構(gòu)造雅可比迭代公式 (1)( )( )123(1)( )( )213(1)( )( )3120.20.10.30.20.11.5 ,0,1,2,0.20.42kkkkkkkkkxxxxxxkxxx(0)T00,0,0 x(1)10.3x(1)21.5x(1)32x迭代計算迭代計算(1)( )( )123(1)( )( )213(1)( )( )3120.20.10.30.20.11.50.20.42

7、kkkkkkkkkxxxxxxxxx(2)(1)(1)123(2)(1)(1)213(2)(1)(1)3120.20.10.30.80.20.11.51.760.20.422.66xxxxxxxxx k 0 1 2 3 4 5 x1(k)00.30.80 0.91800.97160.9894 x2(k)01.51.76 1.9260 1.97001.9897 x3(k)02.02.662.8640 2.95402.9823 5.1.2 高斯高斯- -塞德爾迭代塞德爾迭代 雅可比迭代收斂時，新值雅可比迭代收斂時，新值xi(k+1) 比老值比老值xi(k) 更準(zhǔn)確；更準(zhǔn)確；在雅可比迭代中，算出新值

8、在雅可比迭代中，算出新值xi(k+1)后，用新值后，用新值xi(k+1)代代替用于后面計算的老值替用于后面計算的老值xi(k) ，期望這樣會收斂得更，期望這樣會收斂得更快些，即為快些，即為高斯高斯- -塞德爾塞德爾(Gauss-Seidel)迭代。迭代。設(shè)計思想：設(shè)計思想：高斯高斯- -塞德爾迭代公式：塞德爾迭代公式： ), 2 , 1(, )(11)(11) 1() 1(nixaxabaxnijkjijijkjijiiiki 高斯高斯- -塞德爾迭代公式的塞德爾迭代公式的特點特點是：一旦求出變元是：一旦求出變元xi的的某個新值某個新值xi(k+1)后，就改用后，就改用新值新值xi(k+1)代

9、替代替老值老值xi(k)進(jìn)行進(jìn)行這一步以后剩下的計算。因此，可將新值存放在老這一步以后剩下的計算。因此，可將新值存放在老值所占用的單元內(nèi)，公式可表為下列動態(tài)形式：值所占用的單元內(nèi)，公式可表為下列動態(tài)形式： 11()/,(1,2, )iiijjiiijj iba xaxin用兩次迭代的用兩次迭代的偏差偏差 來控制迭來控制迭代過程的終止。代過程的終止。 1maxiii nyx ), 2 , 1(, )(11)(11) 1() 1(nixaxabaxnijkjijijkjijiiiki 高斯高斯-塞德爾塞德爾迭代迭代算法框圖算法框圖1(1)(1)( )111()(1,2, )inkkkiiijjij

10、jjj iiixba xa xain 例例 用高斯用高斯- -塞德爾迭代法求解方程組塞德爾迭代法求解方程組解解 方程組化為等價的方程組方程組化為等價的方程組 1231231231023210152510 xxxxxxxxx1232133120.20.10.30.20.11.50.20.42xxxxxxxxx構(gòu)造構(gòu)造高斯高斯- -塞德爾塞德爾迭代公式迭代公式 (1)( )( )123(1)(1)( )213(1)(1)(1)3120.20.10.30.20.11.5,0,1,2,0.20.42kkkkkkkkkxxxxxxkxxx(0)T00,0,0 x )1(1x )1(2x )1(3x迭代計

11、算：迭代計算：1.562.684 )2(1x(2)2x(2)3x2.953870.88041.94448高斯高斯- -塞德爾塞德爾迭代公式迭代公式 0.3(1)( )( )123(1)(1)( )213(1)(1)(1)3120.20.10.30.20.11.50.20.42kkkkkkkkkxxxxxxxxx計算結(jié)果計算結(jié)果: k 0 1 2 3 x1(k)00.30.8804 0.98428 x2(k)01.561.944481.99224 x3(k)02.6842.953872.99375 小結(jié)小結(jié)一般情況下高斯一般情況下高斯- -塞德爾迭代法比雅可比迭代法塞德爾迭代法比雅可比迭代法好；

12、好；但情況并不總是這樣，也有高斯但情況并不總是這樣，也有高斯- -塞德爾迭代法塞德爾迭代法比雅可比迭代法收斂得慢，甚至有雅可比迭代比雅可比迭代法收斂得慢，甚至有雅可比迭代法收斂而高斯法收斂而高斯- -塞德爾迭代法反而發(fā)散的例子。塞德爾迭代法反而發(fā)散的例子。5.1.3 超松弛法超松弛法(SORSuccessive Over-Relaxation)將高斯將高斯-塞德爾迭代前一步計算結(jié)果塞德爾迭代前一步計算結(jié)果()kix與這一步與這一步的計算結(jié)果的計算結(jié)果(1)kix適當(dāng)加權(quán)平均， 可期望得到更好的近似適當(dāng)加權(quán)平均， 可期望得到更好的近似值值(1)kix，即有，即有松弛法松弛法，其迭代格式，其迭代格

13、式 迭代迭代 )(1111)()1()1(ijnijkjijkjijiiikixaxabax 加速加速)()1()1()1(kikikixxx 1,2,in 或合或合并并寫成寫成迭代迭代- -加速加速的形式的形式 1(1)()(1)()11(1)()inkkkkiiiijjijjjj iiixxba xa xa 參數(shù)參數(shù)稱為稱為松弛因子。松弛因子。 可以證明，為了保證迭代過程收斂，必須要求可以證明，為了保證迭代過程收斂，必須要求02。 迭代迭代- -加速加速的形式的形式 1(1)()(1)()11(1)()inkkkkiiiijjijjjj iiixxba xa xa 1) 1時迭代格式就是高

14、斯時迭代格式就是高斯- -塞塞德爾迭代格式德爾迭代格式。 2) 0 0 1叫叫低松弛因子。低松弛因子。 3) 由于迭代值由于迭代值(1)kix 通常比通常比kix精確，所以在加速精確，所以在加速公式中加大公式中加大(1)kix 的比重，盡可能擴(kuò)大它的效果，的比重，盡可能擴(kuò)大它的效果，取松弛因子取松弛因子12，叫，叫超松弛法超松弛法。 1(1)(1)( )( )11()(1)inkkkkiiijjijjijj iiixba xa xxa 松弛因子松弛因子的取值對迭代加速公式的收斂的取值對迭代加速公式的收斂速度影響極大。速度影響極大。 實際計算時，可以根據(jù)方程組的系數(shù)矩陣的實際計算時，可以根據(jù)方程

15、組的系數(shù)矩陣的性質(zhì)，并結(jié)合實踐計算的經(jīng)驗來選取合適的松弛性質(zhì)，并結(jié)合實踐計算的經(jīng)驗來選取合適的松弛因子。因子。 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 矩陣形式矩陣形式 Ax=b 其中其中1112111212222212, bnnnnnnnnaaaxbaaaxbAxaaaxb5.1.4 迭代公式的矩陣表示迭代公式的矩陣表示n個未知量個未知量n個方程的線性代數(shù)方程組個方程的線性代數(shù)方程組111212122212nnnnnnaaaaaaALDUaaa令系數(shù)矩陣令系數(shù)矩陣11121212221,1000000nnnn nnnaaaaaa

16、aaa其中其中D為為對角陣對角陣，L和和U分別為嚴(yán)格分別為嚴(yán)格下三角陣下三角陣和嚴(yán)格和嚴(yán)格上上三角陣三角陣。 L+U=A - D1212121,1111122122000000111nnnn nnnnnaaaaULaaaaaaDDaa雅可比迭代公式雅可比迭代公式分量形式分量形式(1)( )( )( )11122133111(1)( )( )( )2221 1233222(1)( )( )( )1 122111()1()1()kkkknnkkkknnkkkknnnnnnnnnxba xa xa xaxba xa xa xaxba xa xaxa1(1)( )( )111() , (1,2, )i

17、nkkkiiijjijjjj iiixba xa xina 矩陣形式矩陣形式(1)1( )( )()xxxkkkDbLU雅可比迭代的矩陣形式雅可比迭代的矩陣形式(1)1( )( )()xxxkkkDbLU雅可比雅可比迭代矩陣迭代矩陣 11( )()xkD bDLU將將L+U= A - D代入代入(1)11( )()xxkkD bDDA1( )1()kID AD bx(1)( )xxdkkG寫成寫成1GID A1dD b121311111111112123222222222212300,0dnnnnnnnnnnnnnnaaabaaaaaaabaaaaGaaabaaaa雅可比迭代的矩陣形式為雅可比

18、迭代的矩陣形式為(1)( )xxdkkGG為為雅可比迭代矩陣雅可比迭代矩陣。 1GID A1dD b高斯高斯- -塞德爾塞德爾法的迭代格式法的迭代格式 1(1)(1)( )111()inkkkiiijjijjjj iiixba xa xa 用分列式用分列式 A=D+L+U 則則 (1)(1)( )kkkDxbLxUx，(1)( )()kkDL xbUx， （1,2,kn） (1)1( )1()()kkxDLUxDLb 11(),()GDLU dDLb 松弛法的迭代格式松弛法的迭代格式 1(1)( )(1)( )11(1)()inkkkkiiiijjijjjj iiixxba xa xa 用分列式用分列式 A=D+L+U 則則 (1)( )(1)( )(1)()kkkkDx