第三章 迭代方法

1、第3章 解線性方程組的迭代法 1 引 言 本章將介紹迭代法的一些基本理論及雅可比迭代法，高斯=塞德爾迭代法，超松弛迭代法，而超松弛迭代法應用很廣泛。 下面舉簡例，以便了解迭代法的思想。 ,361236;33114;20238321321321xxxxxxxxx記為 bAx 12361114238A321xxxx363320b 方程組的精確解是 ?，F(xiàn)將(1.2)式改寫為 Tx) 1 , 2 , 3(*),3636(121);334(111);2023(81213312321xxxxxxxxx或?qū)憺?fxBx0.12361133820,012312611101148283011bDfADIA 我們

2、任取初始值，例如取 。將這些值代入(1.3)式右邊(若(1.3)式為等式即求得方程組的解，但一般不滿足)，得到新的值 再將 分量代入(1.3)式右邊得到 ，反復利用這個計算程序，得到一向量序列和一般的計算公式(迭代公式) Tx)0 , 0 , 0()0(TTxxxx)3 , 3 , 5 , 2(),()1(2)1(2)1(1)1()1(x)2(x,)(3)(2)(1)()1(3)1(2)1(1)1()0(3)0(2)0(1)0(kkkkxxxxxxxxxxxx,12/ )3636(;11/ )334(; 8/ )2023()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkk

3、kkkxxxxxxxxx簡寫為 其中 表示迭代次數(shù)( =O，1，2，)。 fxBxkk)(0)1(kk迭代到第10次有 ).(000187. 0;)9998813. 0 ,999838. 1 ,000032. 3(*)10()10()10()10(xxxT從此例看出，由迭代法作出的向量序列 逐步逼近方程組的精確解 。對于任何一個方程組 (由 變形得到的等價方程組)，按迭代法作出的向量序列 是否一定逐步逼近方程組的解 呢?回答是不一定。請讀者考慮，用迭代法解下述方程組 )(kx*xfBxxbAx )(kx*x. 53; 521221xxxx對于給定方程組 ，設有唯一解 ，則 fBxx*xfBxx

4、*又設 為任取的初始向量，按下述公式構造向量序列 )0(x;)()1()1()2()0()1(fBxxfBxxfBxxkk其中 表迭代次數(shù)。 k定義1 (1)對于給定的方程組 ，用公式(1.6)逐步代入 求近似解的方法稱為迭代法(或稱為一階定常迭代法，這 里 與 無關)。 xBxfBk(2)如果 存在(記為 )，稱此迭代法收斂，顯然 就是方程組的 解，否則稱此迭代法發(fā)散。 )(limkkx*x*x)(kx*)1()1(xxkk),2 , 1 , 0()()1(kBkk 由上述討論，需要研究 的收斂性。引進誤差向量 由(1.6)式減去(1.5)式，得 ，遞推得 )0()()1()(kkkBB 要

5、考察 的收斂性，就要研究 在什么條件下有 亦即要研究 滿足什么條件時有 (零矩陣) )(kxB)(0)(kkB)(kB)(k2 雅可比迭代法與高斯-塞德爾迭代法 2-1雅可比迭代法 設有方程組 ，記為 ), 2 , 1(1nibxainjjijbAx 為非奇異陣且 。將 分裂為 ， 其中 A), 2 , 1(0niaijAULDA.0000000,22311312213231212211nnnnnnaaaaaUaaaaaLaaaD 將(2.1)式第 個方程( =1，2，n)用 去除再移項，得到等價方程組 iiija), 2 , 1()(11nixabaxnijjjijiiji簡記為 ，其中 f

6、xBx0bDfULDADIB1110),( 對方程組(2.2)應用迭代法，得到解(2.1)的雅可比(Jacobi)迭代公式 ,(1);(),()(1)1()0()0(1)0(kjnijiijiiikiTnxabaxxxx初始向量其中 為第 次迭代向量，設 已經(jīng)算出，由(2.3)式可計算下一次迭代向量 Tknkkxxx),()()(1)(k)(kx)., 2 , 1;2 , 1 , 0()1(nixxk 顯然迭代公式(2.3)的矩陣形式為 ,);()(0)1()0(fxBxxkk初始向量 其中 稱為雅可比方法迭代矩陣。 0B2-2高斯-塞德爾迭代法 由雅可比方法迭代公式(2.4)可知，在迭代的每

7、=步計算過程中是用 的全部分量來計算 的所有分量，顯然在計算第 個分量 時，已經(jīng)計算出的最新分量 沒有被利用。從直觀上看，最新計算出的分量可能比舊的分量要好些。 )(kx)1( kxi)1( kix)1(1)1(1,kikxx因此，對這些最新計算出來的第 次近似 的分量 加以利用，就得到所謂解方程組的高斯-塞德爾(Seidel)迭代法(簡稱G-S方法)： 1k)1( kx)1( kjx為初始值， Tnxxxx),()0()0(2)0(1)0(), 2 , 1;, 2 , 1 , 0()(11)()1(11)1(nikxaxabaxnijkjijkjijijiiiki或?qū)憺?nijkjijkji

8、jijiiiiikikixaxabaxnikxxx1)()1(11)()1()(1), 2 , 1;, 2 , 1 , 0(, 上面第2個式子利用了最新計算出的分量 ，第 個式子利用了計算出的最新分量 。(2.5)還可寫成矩陣形式 )1(1kxi) 1, 2 , 1()1(ijxkj,)(,)()1()()1()1(kkkkkUxbxLDUxLxbDx設 存在，則 1)( LD,)()()1()(1)1(bLDUxLDxkk 于是高斯-塞德爾迭代公式的矩陣形式為 ;)()1(fGxxkkbLDfULDG)1(1)(,)(例2 用高斯-塞德爾迭代法解例1.取 ，迭代公式為 0)0(x.12/ )

9、3636(;11/ )433(; ; 8/ )2320()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx 迭代到第5次， =(2.999843，2.000072，1.000061)T =0.00157.從此例看出，高斯=塞德爾迭代法比雅可比迭代法收斂快(達到同樣的精度所需迭代次數(shù)較少)。但這個結論，在=定條件下才是對的。甚至有這樣的方程組，雅可比方法收斂，而高斯=塞德爾迭代法卻是發(fā)散的)5(x)5(。例3 方程組 ; 122; 1; 122321321321xxxxxxxxx 能夠說明解此方程組的雅可比迭代法收斂而高斯-塞德爾迭代法發(fā)散。

10、3 迭代法的收斂性 定義2 設有矩陣序列 及 如果 ), 2 , 1()()(kaAnkijknnijaA)(), 2 , 1,(,lim)(njiaaijkijk 成立，則稱 收斂于A，記為 kAAAkklim例4 矩陣序列 , 01A22202AkkkkkA01當 時， (當 時）10000kAk定理l 充要條件是 。證明留給讀者。 AAkklim)(0kAAk)(ijbB 0kBk1)(B定理2 設 ，則 (零矩陣)( )的充要條件是 證明 由矩陣曰的Jordan標準型，存在非奇異陣P使 JJJJBPP3211,111iinmiiiiJ其中 ，顯然 故 其中 riinn11 PJPB1P

11、PJBkk), 2 , 1(21kJJJjkrkkk于是 )(0)(0kJkBkk), 2 , 1()(0)(0rikJkJkik引進記號 ttktkE001000100 int 其中 一般有 當 時， ;)(1tkktEEkt0tkE由于 iiiiJtkiEI 011010于是 tjjkitjtjjkikjkjjtjkiktikiEjkEjkEjkEIJ100011)()(ttkikiikikiikikiktkktkk11112121), 2 , 1(ri其中 .!) 1() 1()!( !,0jjkkkjkjkjkIEc利用極限 0)，得到f rcckkrk, 10(0lim1)(0kjk

12、jk所以 充要條件是 ，即 )(0kJki), 2 , 1( 1rii1)(B定理3(迭代法基本定理) 設有方程組 fBxx對于任意初始向量 及任意，解此方程組的迭代法(即 )收斂的 )0(xfBxxkk)()1(充要條件是 1)(B證明 充分性。設 .易知 (其中 )有唯 一解，記為 誤差向量 1)(BfAx BIAfBxx*.,*)0()0()0(*)()(xxBxxkkk設 ，應用定理2，有 ( )。于是對任意 及 有 （ ）即 1)(B0kBk)0(xf0kk)(*)(kxxk必要性 設對任意 及任意 皆有 ，其中 顯然 ：(1)極限 是方程組(3.1)的解，(2)對任意 及任意 有

13、)0(xf*)(limxckkfBxxkk)()1(*x)0(xf)(0)0(*)()(kBxxkkk由習題4知 再由定理2，即得 ).(0kBk1)(B 例5 考察用雅可比方法解例1方程組的收斂性。迭代矩陣 的特征方程為 0B, 039772727. 0034090909. 0)det(30BI,3245. 01541. 0,3245. 01541. 0,3082. 0321ii解得 1, 13592. 0132即 .所以用雅可比迭代法解方程組(3.1)是收斂的。 1)(0B例6 考察用迭代法解下述方程組的收斂性： 其中 fBxx特征方程為 55,0320fB06)det(2BI特征根 ，即

14、 .這說明用迭代法解此方程組不收斂。 62, 11)(B考察誤差向量 設B有 個線性無關的特征向量 相應的特征值為 。 )0(*)()(kkkBxxn,1nuu n,1 由 得iniiua1)0(ikiniiikniikkuauBaB11)0()()(可以看出當 愈小時， 愈快，即 愈快。 1)(B)(, 2 , 1(0kniki0)(k 定理4(迭代法收斂的充分條件) 如果方程組(3.1)的迭代公式為 為任意初始向量)，且迭代矩陣的某一種范數(shù) ，則 )0()()1(xfBxxkk1 qBv1.迭代法收斂； 2. vkxx)(*;1)1()(vkkxxqq3. vkxx)(*.1)0()1(v

15、kxxqq證明：利用定理3，1是顯然的，現(xiàn)證2，3顯然有 (1) ， )()(*)1(*kkxxBxx(2) vkkxx)()1(), 2 , 1(;)1()(kxxqvkk(3) vkxx)1(*.)(*vkxxqvkkvkkxxxxxx)1(*)(*)()1( vkvkxxxx)1(*)(* vkxxq)(*)1 (即vkxx)(* .11)()1(vkkxxq ).,2, 1(.1)1()(kxxqqvkk反復利用(2)即得到3. 例7：仍然考察例1，雅可比方法迭代矩陣 的 范數(shù)為 0B, 1129129,115,85max0B所以對例1應用雅可比迭代方法是收斂的。 例8：設有方程組 其

16、中 則 fBfx,21,8 .03 .009 .0fB. 54.1,021.1,2 .1, 1 .121FBBBB 雖然 的這些范數(shù)都大于1，但 的特征值為 =0.9， =0.8， 由定理3，對此方程組應用迭代法還是收斂的。 BB12 定理5 解方程組(2.1)的高斯=塞德爾迭代法收斂的充要條件是 其中G為高斯-塞德爾迭代法的迭代矩陣。 1)(G 證明 由(2.6)式再應用定理3即得定理5.在實際應用中常遇到一 些線性代數(shù)方程組，其系數(shù)矩陣具有某些性質(zhì)，如系數(shù)矩陣的對 角元素占優(yōu)勢，系數(shù)矩陣為對稱正定等。 定義4 (對角優(yōu)勢陣)設 (或) ， nnnijRaA)(nnC(1)如果矩陣 滿足條件

17、 A), 2 , 1(1niaanijiijii 即 的每=行對角元素的絕對值都嚴格大于同行其他元素絕對值 之和，則稱 為嚴格對角優(yōu)勢矩陣。 AA (2)如果 且至少有一個不等式嚴格成立，稱 為 ), 2 , 1(1niaanijiijiiA弱對角優(yōu)勢矩陣。 定義5：(可約與不可約矩陣)設 (或 )，當n2時，如果存在n階排列陣P使 nnnijRaA)(nnC2212110AAAAPPT成立，其中 為 階子矩陣， 為 階子矩陣(1 n)，則稱矩陣是 可約的。如果不存在排列陣 使(3.5)式成立，則稱 為不可約矩陣 11Ar22Arn rAPA 是可約矩陣，意味著 可經(jīng)過若干行列重排(若經(jīng)過兩行

18、交換的同時進行相應的兩列的交換，稱對 進行一次行列重排)，化為兩個低階方程組求解。 bAx AA 定理6: (對角占優(yōu)定理)如果 (或 )為嚴格 對角優(yōu)勢陣或為不可約弱對角優(yōu)勢陣，則 是非奇異矩陣。 nnnijRaA)(nnCA 證明: 首先設 為嚴格對角優(yōu)勢陣，采用反證法。若det( )=0， 則有 非零解，記為 又記 AA0AxTnxxxx),(210max1inikxx由齊次方程組的第 個方程 k01jnjkjxa1nkkkkjjjj ka xa x 1nkjjjj kax1,nkkjkkjj kxaa 1,nkkjjj kxa與假設矛盾，故det(A)0，即A非奇異。 定理7: 如果

19、為嚴格對角優(yōu)勢矩陣或為不可約弱對角優(yōu)勢 矩陣，則對任意的 ，解方程組(2.1)的雅可比迭代法，高斯-塞德爾迭代法均收斂。 nnRA)0(x證明：設 為不可約弱對角優(yōu)勢陣，現(xiàn)證明高斯-塞德爾迭代法收 斂。其他證明留作習題。 A 由題設知 。方程組(2.1)的高斯-塞德爾迭代 法的迭代矩陣為 ), 2 , 1(0niaiiULDG1)(又 0)(det(,)det()(det()(11ULDLDULDIGI即0)(det(ULD記nnnnnnnaaaaaaaaaaaaULDG32122322211131211)( 下面來說明當 1時detGO，如果這個結論是正確的，那么 detG=0的根均滿足 1

20、.這說明解(2.1)式的高斯-塞德爾迭代法收斂。 事實上，由 為不可約，則 亦是不可約矩陣，且又由 為弱對角優(yōu)勢陣得到 AGAiiiiacnijijijijaa111 且至少有一不等式嚴格成立，也就是說當 1時，G為不可約弱對角優(yōu)勢陣，于是由定理6(當 1時)det(G)0，故 1)(G4解線性方程組的超松弛迭代法 逐次超松弛迭代法(Successive Over Relaxation Method，簡稱SOR方法)是高斯-塞德爾方法的一種加速方法，是解大型稀疏矩陣方程組的有效方法之一，它具有計算公式簡單，程序設計容易，占用計算機內(nèi)存較少等優(yōu)點，但需要選擇好的加速因子(即最佳松弛因子)。 設有

21、方程組 其中 為非奇異矩陣，且設 0(=1，2，n)，分解 為 bAx nnRAiiaAULDA 設已知第 次迭代向量 ，及第 +1次迭代向量 的分量 k)(kxk)1( kx),1, 2 , 1() 1(ijxkj 要求計算分量 ) 1( kix首先 用迭代法定義輔助量 SG), 2 , 1(11)(11) 1() 1(nixaxabaxnijkjijijkjijiiiki 再把 取 為與； 某個平均值(即加權平均)，即 ) 1( kix)(kix) 1(kix)()1 ()() 1()() 1()() 1(kikikikikikixxxxxx 用(4.3)式代人(4.4)式得到解方程組 的

22、逐次超松弛迭代 公式 bAx ), 2 , 1;, 1 , 0(),(;()()(2)(1)(1)(11) 1()() 1(nikxxxxxaxabaxxTknkkknijkjijijkjijiiikiki（4.5） 其中 稱為松弛因子，或?qū)憺?)(), 2 , 1;, 1 , 0( ;)(11) 1()() 1(nijkjijijkjijiiiiikikixaxabaxnikxxx 顯然，當 =1時，解(4.1)式的SOR方法就是高斯-塞德爾迭代法。 在SOR迭代法中每迭代一次，主要的運算量是計算一次矩陣與向量的乘法.由(4.5)可知，在計算機上應用SOR方法解方程組時只須一組工作單元，以便

23、存放近似解，在電算時，可用 控制迭代終止. )()1(10maxmaxkikiniiixxxp 當 時，稱（4.5）式為低松弛法，當 時，稱（4.5）式為高松弛法。 11 例11: 用SOR方法解方程組 123441111141111141111141xxxx 它的精確解為 *( 1, 1, 1, 1)Tx 解: 取 ，迭代公式為 (0)0 x(1)()()()()()111234(1)()(1)()()()221234(1)()(1)(1)()()331234(1)()(1)(1)(1)()431234(14) 4;(14) 4;(14) 4;(14) 4;kkkkkkkkkkkkkkkkk

24、kkkkkkkxxxxxxxxxxxxxxxxxxxxxxxx 取 ，第11次迭代結果為 1.3(11)( 0.99999646, 1.00000310, 0.99999953, 0.99999912)Tx 0.4610-5 (11)2| 對 取其他值迭代次數(shù)如表3-1。從引例看到，松弛因子選擇得好，會使SOR迭代法的收斂大大加速。本例， 是最佳松弛因子。 1.3( )*52|10kxx表3-1松弛因子滿足誤差的迭代次數(shù)1.O1.11.21.31.41.51.61.71.81.9221 712ll(最少迭代次數(shù))1417233353109 下面我們寫出SOR迭代公式的矩陣形式。迭代公式（4.5

25、）亦可寫為 1(1)( )(1)( )11(1)() (1,2, )inkkkkiiiiiiiijjijjjj ia xa xba xa xin (4.7) 用分解式A=D-L-U，則 (1)(1)( )()kkkDxbLxUx( )(1)kDx即(1)()(1)kDL xD( )kU xb 顯然對任何一個 值， 非奇異（由設 于是 ()DLiia0,1,2, )in(1)1( )() (1)(kkxDLDU xD1)Lb 這就是說解（2.1）式（設 的SOR方法迭代公式 為 0,1,2,iiai, )n(1)( )kkxL xf其中 ， 11() (1),()LDLDUf DLb矩陣 稱為S

26、OR方法的迭代矩陣。這說明對(2.1)式應用SOR方法相當于對方程組 ，應用一般迭代法。于是關于一般迭代法的理論可應用到(4.8)式，得到下述定理： LxL xf定理8 設有線性方程組(4.1)，且 0(i=1，2，n)，則解方程組的SOR方法收斂的充要條件是iia()1L 引進超松弛迭代法的想法是希望能選擇松弛因子 使得迭代過程 (4.5)式收斂較快，也就是應選擇因子 使 ()minL下面研究對于一般方程組(2.1)( O，i=1，2，n)，松弛因子 在什么范圍內(nèi)取值，SOR方法才可能收斂?，F(xiàn)給出SOR方法收斂的必要條件。 iia 定理9 設解(2.1)式( O，i=1，2，n)的SOR方法收斂，則iia02證明 由設SOR方法收斂，根據(jù)定理8， ， ()1L 設 的特征值為 ，則 L12,n 12|det() | |,|nL ( ()nL1| d e t() |nL()1L, 而1det()det()det(1)(1)nLDLDU所以 |1|1 該定理說明對于解一般方程組(2.1)( O，i=1，2，n)， SOR方法只有取松弛因子 在(0，2)范圍內(nèi)才能收斂。給出當A是對稱正定矩陣， 滿足 時，SOR方法一定收斂。iia02 定理10 如果A為對稱正定矩陣，且 ，則解(4.1)的 SOR