第六講： 解線性方程組的迭代法

1、第第6章章 解線性方程組的迭代方法解線性方程組的迭代方法 6.1 引言引言 6.2 基本迭代法基本迭代法 6.3 迭代法的收斂性迭代法的收斂性其中其中A為非奇異矩陣為非奇異矩陣, 當當A為為低階稠密矩陣低階稠密矩陣時時, 第第5章討論的選主元消去法是有效的章討論的選主元消去法是有效的. 但對于但對于大型稀大型稀疏矩陣方程組疏矩陣方程組(A的階數(shù)的階數(shù)n很大，但很大，但零元素較多零元素較多), 利利用迭代法求解是合適的用迭代法求解是合適的. 本章將介紹迭代法的一些基本理論及本章將介紹迭代法的一些基本理論及雅可比雅可比迭代法迭代法，高斯高斯-賽德爾迭代法賽德爾迭代法，超松弛迭代法超松弛迭代法，而，

2、而超松弛迭代法應(yīng)用很廣泛。超松弛迭代法應(yīng)用很廣泛。 下面舉簡例，以便了解迭代法的思想下面舉簡例，以便了解迭代法的思想. 對線性方程組對線性方程組 Ax=b， (1.1) 6.1 引言引言 例例1 求解方程組求解方程組)2 . 1(.361236,33114,20238321321321 xxxxxxxxx記為記為Ax=b，其中，其中.363330,12361114238321 bxxxxA方程組的精確解是方程組的精確解是x*=(3,2,1)T. 現(xiàn)將改寫為現(xiàn)將改寫為)3 . 1().3636(121),334(111),2023(81213312321 xxxxxxxxx或?qū)憺榛驅(qū)憺閤=B0

3、x+f，其中，其中.,0001236113382012312611111482830 fB 我們?nèi)稳〕跏贾?，例如取我們?nèi)稳〕跏贾?，例如取x(0)=(0, 0, 0)T. 將這些值將這些值代入代入(1.3)式右邊式右邊(若若(1.3)式為等式即求得方程組的解，式為等式即求得方程組的解，但一般不滿足但一般不滿足)，得到新的值，得到新的值x(1)=(x1(1), x2(1), x3(1)T=(3.5, 3, 3)T ，再將，再將x(1)分量代入分量代入(1.3)式右邊得到式右邊得到 x(2)，反復(fù)利用這個計算程序，得到一向量序列和一般的計反復(fù)利用這個計算程序，得到一向量序列和一般的計算公式算公式(迭

4、代公式迭代公式),)(3)(2)(1)()1(3)1(2)1(1)1()0(3)0(2)0(1)0( kkkkxxxxxxxxxxxx)4 . 1(.12/ )3636(,11/ )334(, 8/ )2023()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1 kkkkkkkkkxxxxxxxxx簡寫為簡寫為 x(k+1)=B0 x(k) +f，其中其中k表示迭代次數(shù)表示迭代次數(shù)(k=0,1,2,). 迭代到第迭代到第10次有次有;)999813. 0,999838. 1,000032. 3()10(Tx ).(000187. 0)10()10()10( xx 從此例看出，由迭代法

5、產(chǎn)生的向量序列從此例看出，由迭代法產(chǎn)生的向量序列x(k)逐步逐步逼近方程組的精確解是逼近方程組的精確解是x*=(3,2,1)T. 即有即有 對于任何一個方程組對于任何一個方程組x=Bx+f(由由Ax=b變形得到的變形得到的等價方程組等價方程組)，由迭代法產(chǎn)生的向量序列，由迭代法產(chǎn)生的向量序列x(k)是否一定是否一定逐步逼近方程組的解逐步逼近方程組的解x*呢？回答呢？回答是不一定是不一定. 請同學(xué)們請同學(xué)們考慮用迭代法解下述方程組考慮用迭代法解下述方程組 . 53, 521221xxxx xxkk)(lim對于給定方程組對于給定方程組x=Bx+f，設(shè)有唯一解，設(shè)有唯一解x*，則，則 x*=Bx*

6、+f .(1.5)又設(shè)又設(shè)x(0)為任取的初始向量為任取的初始向量, 按下述公式構(gòu)造向量序列按下述公式構(gòu)造向量序列 x(k+1)=Bx(k)+f , k=0,1,2,.(1.6)其中其中k表示迭代次數(shù)表示迭代次數(shù). 定義定義1 (1)對于給定的方程組對于給定的方程組x=Bx+f , 用公式用公式(1.6)逐步代入求近似解的方法稱為逐步代入求近似解的方法稱為迭代法迭代法(或稱為或稱為一階定一階定常迭代法常迭代法，這里，這里B與與k無關(guān)無關(guān)). B稱為稱為迭代矩陣迭代矩陣. (2) 如果如果limx(k) (k)存在存在(記為記為x*), 稱此稱此迭代法迭代法收斂收斂, 顯然顯然x*就是方程組的解

7、就是方程組的解, 否則稱此否則稱此迭代法發(fā)散迭代法發(fā)散. 由上述討論，需要研究由上述討論，需要研究x(k)的收斂性的收斂性. 引進誤引進誤差向量差向量,)1()1( xxkk 由由(1.6)減去減去(1.5)式，得式，得(k+1)=B(k)(k=0,1,2,)，遞推得遞推得.)0()1()( kkkBB 要考察要考察x(k)的收斂性，就要研究的收斂性，就要研究B在什么條件下在什么條件下有有l(wèi)im(k)=0 (k)，亦即要研究，亦即要研究B滿足什么條件時有滿足什么條件時有Bk00(零向量零向量) (k) . 6.2 基本迭代法基本迭代法其中，其中，A=(aij)Rnn為非奇異矩陣，下面研究任何建

8、為非奇異矩陣，下面研究任何建立立Ax=b的各種迭代法的各種迭代法. 設(shè)線性方程組設(shè)線性方程組 Ax=b， (2.1) 其中，其中，M為可選擇的非奇異矩陣，且使為可選擇的非奇異矩陣，且使Mx=d容易求容易求解，一般選擇解，一般選擇A的某種近似，稱的某種近似，稱M為為分裂矩陣分裂矩陣. 將將A分裂為分裂為 A=M- -N. (2.2) 于是，求解于是，求解Ax=b轉(zhuǎn)化為求解轉(zhuǎn)化為求解Mx=Nx+b ，即求解，即求解.11bMNxMxbAx 求解求解可構(gòu)造一階定常迭代法可構(gòu)造一階定常迭代法)3 . 2(), 1 , 0()()()1()0( kfBxxxkk，初始向量初始向量其中其中 B=M- -1

9、N=M- -1(M- -A)=I- -M- -1A ， f=M- -1b. 稱稱 B=I- -M- -1A為迭代法的為迭代法的迭代矩陣迭代矩陣，選取，選取M矩陣，就得矩陣，就得到解到解Ax=b的各種迭代法的各種迭代法. 設(shè)設(shè)aii 0 (i=1,2,n)，并將，并將A寫成三部分寫成三部分.00000000, 121,211, 1121,212, 11 , 1212211ULDaaaaaaaaaaaaaaaAnnnnnnnnnnnnnn 111212122212nnnnnnaaaaaaAaaa 1122nnaaDa 2112000nnaLaa1212000nnaaaU即即A=D- -L- -U6

10、.2.1 雅可比雅可比(Jacobi)迭代法迭代法 設(shè)設(shè)aii 0 (i=1,2,n)，選取，選取M為為A的對角元素部分的對角元素部分,即選取即選取M=D(對角陣對角陣)，A=D- -N，由，由(2.3)式得到解方式得到解方程組程組Ax=b的的雅可比雅可比(Jacobi)迭代法迭代法. 又稱又稱簡單迭代法簡單迭代法.其中其中B=I- -D- -1A=D- -1(L+U)=J, f=D- -1b. 稱稱J為解為解Ax=b的的雅可比迭代法的迭代矩陣雅可比迭代法的迭代矩陣.)5 . 2(), 1 , 0()()()1()0( kfBxxxkk，初始向量初始向量于是雅可比迭代法可寫為于是雅可比迭代法可

11、寫為矩陣形式矩陣形式bDxULDxkk1)(1)1()( 其其Jacobi迭代矩陣迭代矩陣為為 )(1ULDBJ 0002122222211111112nnnnnnnnaaaaaaaaaaaa下面給出雅可比迭代法下面給出雅可比迭代法(2.5)的分量計算公式的分量計算公式, 記記,),()()()(1)(Tknkikkxxxx 由雅可比迭代法由雅可比迭代法(2.5)有有,)()()1(bxULDxkk 每一個分量寫出來為每一個分量寫出來為)., 2 , 1(1)(11)()1(nibxaxaxainijkjijijkjijkiii 即當即當aii 0時，有時，有)., 2 , 1()(11)(1

12、1)()1(nibxaxaaxinijkjijijkjijiiki 等等價價方方程程組組其中其中 aii(i) 0 (i=1,2,n)11221111221122221122111nnnnnnnnnnxa xa xbaxa xa xbaxa xa xba 即由方程組即由方程組Ax=b得到的得到的建立的雅可比迭代格式為建立的雅可比迭代格式為 )(1)(1)(1)(11)(11) 1(2)(2)(323)(12122) 1(21)(1)(313)(21211) 1(1nknnnknnnknknnkkkknnkkkbxaxaaxbxaxaxaaxbxaxaxaax于是，解于是，解Ax=b的雅可比迭代

13、法的計算公式為的雅可比迭代法的計算公式為)6 . 2()., 1 , 0(), 2 , 1(,/ )(,),(1)()1()0()0(1)0( 表示迭代次數(shù)表示迭代次數(shù)kniaxabxxxxiinijjkjijikiTn 由由(2.6)式可知，雅可比迭代法計算公式簡單，式可知，雅可比迭代法計算公式簡單，每迭代一次只需計算一次矩陣和向量的乘法且計算每迭代一次只需計算一次矩陣和向量的乘法且計算過程中原始矩陣過程中原始矩陣A始終不變始終不變. 6.2.2 高斯賽德爾迭代法高斯賽德爾迭代法在在 Jacobi 迭代中，計算迭代中，計算 xi(k+1)(2 i n)時時，使用使用xj(k+1)代替代替xj

14、(k) (1 j i- -1)，即有即有 )(1)(1)(1) 1(11) 1(11) 1(2)(2)(323) 1(12122) 1(21)(1)(313)(21211) 1(1nknnnknnnknknnkkkknnkkkbxaxaaxbxaxaxaaxbxaxaxaax建建立立迭迭代代格格式式或縮寫為或縮寫為稱為稱為高斯高斯塞德爾塞德爾(Gauss Seidel)迭代法迭代法.bLDxULDxkk1)(1)1()()( 其其Gauss Seidel迭代矩陣迭代矩陣為為BG = (D- -L)- -1U于是高斯于是高斯塞德爾迭代法可寫為塞德爾迭代法可寫為矩陣形式矩陣形式)., 2 , 1(

15、)(11)(11)1()1(nibxaxaaxinijkjijijkjijiiki 這就是說，選取分裂矩陣這就是說，選取分裂矩陣M為為A的下三角部分的下三角部分,即選取即選取M= D- -L(下三角陣下三角陣)，A=M- -N，由，由(2.3)式得到式得到解解Ax=b的的高斯高斯塞德爾塞德爾(Gauss Seidel)迭代法迭代法.其中其中B=I- -(D- -L)- -1A= (D- -L)- -1U=G, f=(D- -L)- -1b. 稱矩稱矩陣陣G=(D- -L)- -1U為解為解Ax=b的的高斯高斯塞德爾塞德爾迭代法的迭迭代法的迭代矩陣代矩陣.)7 . 2(), 1 , 0()()(

16、)1()0( kfBxxxkk，初始向量初始向量由由高斯高斯塞德爾迭代法塞德爾迭代法(2.7)有有,)()()1(bUxxLDkk 每一個分量寫出來為每一個分量寫出來為)., 2 , 1(1)(11)1()1(nixaxabxanijkjijijkjijikiii 即當即當aii 0時，有時，有(與前面一樣的式子與前面一樣的式子)., 2 , 1()(11)(11)1()1(nixaxabaxnijkjijijkjijiiiki 或或,)()1()1(bUxLxDxkkk 于是，解于是，解Ax=b的的高斯高斯塞德爾塞德爾迭代法的計算公式為迭代法的計算公式為)8 . 2()., 1 , 0(),

17、 2 , 1(,/ )(),(),(1)(11)1()1()0()0(1)0( 表示迭代次數(shù)表示迭代次數(shù)初始向量初始向量kniaxaxabxxxxiinijkjijijkjijikiTn或或)9 . 2()., 1 , 0(), 2 , 1(,/ )(,),()(11)1()()1()0()0(1)0( kniaxaxabxxxxxxxiinijkjijijkjijiiikikiTn 雅可比迭代法雅可比迭代法不使用變量的最新信息計算不使用變量的最新信息計算xi(k+1)，而由而由高斯高斯塞德爾迭代公式塞德爾迭代公式(2.8)可知，計算可知，計算x(k+1)的的第第 i個分量個分量xi(k+1)

18、時，利用了已經(jīng)計算出的最新分量時，利用了已經(jīng)計算出的最新分量xj(k+1) (j=1,2,i- -1). 可看作可看作雅可比迭代法雅可比迭代法的一種改的一種改進進. 由由(2.8)可知，可知，高斯高斯塞德爾迭代公式塞德爾迭代公式每迭代一次每迭代一次只需計算一次矩陣與向量的乘法只需計算一次矩陣與向量的乘法.算法算法1(高斯高斯塞德爾迭代法塞德爾迭代法) 見書見書p189. 例例2 用用高斯高斯塞德爾迭代法塞德爾迭代法解例解例1的方程組的方程組(1.2).)., 2 , 1 , 0(.12/ )3636(,11/ )433(, 8/ )2320()1(2)1(1)1(3)(3)1(1)1(2)(3

19、)(2)1(1 kxxxxxxxxxkkkkkkkkk 解解 用用高斯高斯塞德爾迭代公式：塞德爾迭代公式：取取x(0)=(0, 0, 0)T.迭代到第迭代到第7次有次有;)9999930. 0,9999987. 1,000002. 3()7(Tx .1002. 24)7()7( xx 由此例可知，用由此例可知，用高斯高斯塞德爾迭代法塞德爾迭代法，雅可比雅可比迭代法迭代法解線性方程組解線性方程組(1.2)(且取且取x(0)=0)均收斂，而均收斂，而高高斯斯塞德爾迭代法塞德爾迭代法比比雅可比迭代法雅可比迭代法收斂較快收斂較快(即取相即取相同的同的x(0)，達到同樣精度所需迭代次數(shù)較少，達到同樣精度

20、所需迭代次數(shù)較少)，但這結(jié)，但這結(jié)論只當論只當A滿足一定條件時才是對的滿足一定條件時才是對的. 例例1 用雅可比迭代法解方程組用雅可比迭代法解方程組 2 . 453 . 82102 . 7210321321321xxxxxxxxx )2 . 4(51)3 . 82(101)2 . 72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx.3 . 12 . 11 . 1 x解解確確精精 解：解： Jacobi 迭代格式為迭代格式為 )2 . 4(51)3 . 82(101)2 . 72(101)(2)(1)1(3)(3)(1)1(2)(3)(2

21、)1(1kkkkkkkkkxxxxxxxxx取取 x(0)=(0,0,0)T 計算結(jié)果如下：計算結(jié)果如下： 解：解：Gauss-Seidel 迭代格式為迭代格式為 )2 . 4(51)3 . 82(101)2 . 72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx 例例2 用用GaussSeidel 迭代法解上題迭代法解上題. 2 . 453 . 82102 . 7210321321321xxxxxxxxx取取 x(0)=(0,0,0)T 計算結(jié)果如下：計算結(jié)果如下： )2 . 4(51)3 . 82(101)2 . 72(101

22、)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx6.2.3 解大型稀疏線性方程組的逐次超松弛法解大型稀疏線性方程組的逐次超松弛法(SOR方法方法) 我們?nèi)∥覀內(nèi)?0為為松弛因子松弛因子，建立迭代格式如下，建立迭代格式如下).,2,1(),()1 (,/ )()()1()()1()()1(1)(11)1()1(nixxxxxxaxaxabxkikikikikikiiinijkjijijkjijiki 即即./ )()(11)1()()1(iinijkjijijkjijikikiaxaxabxx 或改寫為或改寫為.)()1()(1)(1)1(b

23、LDxUDLDxkk 其其逐次超逐次超松弛迭代矩陣松弛迭代矩陣為為.)1()(1UDLDB 逐次超松弛法逐次超松弛法可寫為可寫為矩陣形式矩陣形式./ )()(11)1()()1(iinijkjijijkjijikikiaxaxabxx , 2 , 1 , 0), 2 , 1(./ )()1 ()(11)1()()1( kniaxaxabxxiinijkjijijkjijikiki 稱為稱為逐次超逐次超松弛迭代法松弛迭代法，簡稱，簡稱SOR方法方法. 顯然，顯然， =1就是就是GaussSeidel 迭代法迭代法. 下面用矩陣方法推導(dǎo)，選取分裂矩陣下面用矩陣方法推導(dǎo)，選取分裂矩陣M為帶參為帶參數(shù)

24、的下三角矩陣數(shù)的下三角矩陣從而得到解從而得到解Ax=b的的逐次超松弛迭代法逐次超松弛迭代法 (Successive Over Relaxation Method，簡稱，簡稱SOR方法方法).).(1LDM 其中其中 0為可選擇的為可選擇的松弛因子松弛因子. 于是，由于是，由(2.3)可構(gòu)造一個迭代法，其迭代矩陣為可構(gòu)造一個迭代法，其迭代矩陣為.)1()()(11UDLDALDIL )10. 2(), 1 , 0()()()1()0( kfxLxxkk ，初始向量初始向量 解解Ax=b的的SOR方法方法為為.其中其中.)(,)1()(11bLDfUDLDL 下面給出解下面給出解Ax=b的的SOR

25、方法方法的分量計算公式的分量計算公式. 記記,),()()()(1)(Tknkikkxxxx 由由(2.10)式可得式可得,)1()()()1(bxUDxLDkk ).()()()1()()1(kkkkkDxUxLxbDxDx 由此，得到解由此，得到解Ax=b的的SOR方法方法的計算公式的計算公式或或)11. 2(.), 2 , 1 , 0;, 2 , 1(/ )()1 (,),()(11)1()()1()0()0(1)0( 為松弛因子為松弛因子 kniaxaxabxxxxxiinijkjijijkjijikikiTn .), 2 , 1 , 0;, 2 , 1()12. 2(/ )(,),(

26、)(11)1()()1()0()0(1)0(為松弛因子為松弛因子 kniaxaxabxxxxxxxiinijkjijijkjijiiikikiTn (1) 顯然，當顯然，當 =1時即為時即為GaussSeidel 迭代法迭代法. (2) SOR方法方法每迭代一次主要運算量是計算一次每迭代一次主要運算量是計算一次矩陣與向量的乘法矩陣與向量的乘法. (3) 當當 1時，稱為時，稱為超松弛法超松弛法；當；當 1時，稱為時，稱為低低松弛法松弛法. (4) 在計算機實現(xiàn)時可用在計算機實現(xiàn)時可用 )()1(11maxmaxkikiniinixxx控制迭代終止，或用控制迭代終止，或用 )()(kkAxbr控

27、制迭代終止控制迭代終止. SOR迭代法迭代法是是GaussSeidel 迭代法迭代法的一種修正，的一種修正，可由下述思想得到可由下述思想得到. 設(shè)已知設(shè)已知x(k)及已計算及已計算x(k+1)的分量的分量xj(k+1) (j=1,2,i- -1).)14. 2().()1 ()()1()()1()()1(kikikikikikixxxxxx (1) 首先用首先用GaussSeidel 迭代法迭代法定義輔助量定義輔助量 ,)1( kix)13. 2(./ )(1)(11)1()1(iinijkjijijkjijikiaxaxabx (2) 再由再由 與與 加權(quán)平均定義加權(quán)平均定義 ，即，即)1(

28、 kix)(kix)1( kix將將(2.13)代入代入(2.14)得到解得到解Ax=b的的SOR迭代迭代(2.11)式式.例例3 用用SOR迭代法迭代法解方程組解方程組. 見書見書P195.6.3 迭代法的收斂性迭代法的收斂性6.3.1 一階定常迭代法的基本定理一階定常迭代法的基本定理其中，其中，A=(aij)Rnn為非奇異矩陣，記為非奇異矩陣，記x*為為(3.1)精確精確解，且設(shè)有等價的方程組解，且設(shè)有等價的方程組 設(shè)線性方程組設(shè)線性方程組 Ax=b， (3.1) 于是于是.fBxxbAx )2 . 3(.fBxx 設(shè)有解設(shè)有解Ax=b的一階定常迭代法的一階定常迭代法)3 . 3(.)()

29、1(fBxxkk 有意義的問題是：迭代矩陣有意義的問題是：迭代矩陣B滿足什么條件時，滿足什么條件時，由迭代法產(chǎn)生的向量序列由迭代法產(chǎn)生的向量序列x(k)收斂到收斂到x*. 引進引進誤差向量誤差向量)., 2 , 1 , 0()()( kxxkk 由由(3.3)式減式減(3.2)得到得到誤差向量的遞推公式誤差向量的遞推公式)., 2 , 1 , 0(,)0()()()1( kBBkkkk 由由6.1節(jié)可知，研究迭代法節(jié)可知，研究迭代法(3.3)收斂性問題就是要研收斂性問題就是要研究迭代矩陣究迭代矩陣B滿足什么條件時，有滿足什么條件時，有.).)(0 kBk零矩陣零矩陣 定義定義2 設(shè)有矩陣序列設(shè)

30、有矩陣序列 Ak=(aij(k)Rnn 及及A=(aij)Rnn，如果，如果n2個數(shù)列極限存在且有個數(shù)列極限存在且有)., 2 , 1,(lim)(njiaaijkijk 則則Ak稱收斂于稱收斂于A，記為，記為lim (k).例例4 設(shè)有矩陣序列設(shè)有矩陣序列Ak, 其中其中Ak=Bk,而而,0,02,011222 kkkkkBBB 且設(shè)且設(shè)|1，考查矩陣序列極限，考查矩陣序列極限.解解 顯然顯然, 當當|1時時, 則有則有.0000limlim kkkkBA矩陣序列極限概念可以用矩陣算子范數(shù)來描述矩陣序列極限概念可以用矩陣算子范數(shù)來描述. 定理定理1 其中其中|為為矩陣的任意一種算子范數(shù)矩陣的

31、任意一種算子范數(shù)., 0limlim AAAAkkkk證明證明 顯然有顯然有. 0limlim AAAAkkkk再由矩陣范數(shù)的等價性再由矩陣范數(shù)的等價性, 則定理對其它算子范數(shù)亦對則定理對其它算子范數(shù)亦對.定理定理2.limlimAxxARxAAkknkk 都有都有對對證明作為練習(xí)證明作為練習(xí). 定理定理3 設(shè)設(shè)B=(bij)Rnn，則，則limBk=0 (k)(零零矩陣矩陣)的充分必要條件是矩陣的充分必要條件是矩陣B的譜半徑的譜半徑 (B)1.證明證明 由矩陣由矩陣B的的若當標準形若當標準形,存在非奇異矩陣存在非奇異矩陣P使使,211JJJJBPPr 其中其中若當若當(Jordan)塊塊,1

32、1iinniiiiJ 且，顯然有且，顯然有nnrii 1其中其中,11 PPJBPJPBkk.21 krkkkJJJJ)., 2 , 1( , 0lim0lim0limriJJBkikkkkk 于是于是 顯然有顯然有, Et,0=I, Et,k=0(當當kt)，(Et,1)k= Et,k. 由于由于Ji=I+Et,1 ，因此，因此下面考查下面考查Jik的情況的情況. 引進記號引進記號).(000,ittktntRktIE 101 ,01 ,1 ,)()()(tjjtjkijkkjjtjkijkktikiECECEIJ )., 2 , 1(11)2(211)1(12211riCCCCCCttki

33、kiktkitkkikkitkitkkikkikki 其中其中.!)1()1()!( !jjkkkjkjkCjk 得到得到利用極限利用極限),0, 10(0lim rcckkrk. 10lim jkjkkC. 1)(), 2 , 1( 10lim BriJikik 即即所以所以 定理定理4(迭代法基本定理迭代法基本定理) 設(shè)有方程組設(shè)有方程組 x=Bx+f. (3.4) 及一階定常迭代法及一階定常迭代法 x(k+1)=Bx(k)+f. (3.5) 對任意選擇初始向量對任意選擇初始向量x(0)，迭代法，迭代法(3.5)收斂的充要條收斂的充要條件是矩陣件是矩陣B的譜半徑的譜半徑 (B)1.證明證明

34、 充分性充分性. 設(shè)設(shè) (B)1，易知，易知Ax=f(其中其中A=I- -B)有唯一解，記為有唯一解，記為x*，則，則 x*=Bx*+f.誤差向量誤差向量.,)0()0()0()()( xxBxxkkk 由設(shè)由設(shè) (B)1，應(yīng)用定理，應(yīng)用定理3，有，有 . 于是對任意于是對任意x(0)有有 ，即，即 .0lim kkB0lim kk xxkk)(lim其中其中x(k+1)=Bx(k)+f . 顯然，極限顯然，極限x*是方程組是方程組(3.4)的解，的解，且對任意且對任意x(0)有有必要性必要性. 設(shè)對任何設(shè)對任何x(0)有有0lim kkB).(0)0()()( kBxxkkk ,lim)(

35、xxkk由定理由定理2知知再由定理再由定理3，即得，即得 (B)1.定理定理4是一階定常迭代法的基本理論是一階定常迭代法的基本理論. 定理定理3和定理和定理4的結(jié)論和起來即為的結(jié)論和起來即為 (1) 迭代法迭代法x(k+1)=Bx(k)+f 收斂收斂limBk=O； (2) 迭代法迭代法x(k+1)=Bx(k)+f 收斂收斂 (B)1. 推論推論 設(shè)設(shè)Ax=b，其中，其中A=D- -L- -U為非奇異矩陣且為非奇異矩陣且D非奇異矩陣，則有非奇異矩陣，則有 (1) Jacobi迭代法迭代法收斂收斂 (J)1, 其中其中J=D- -1(L+U). . (2) G- -S迭代法迭代法收斂收斂 (G)

36、1, 其中其中G=(D- -L)- -1U. . (3) SOR迭代法迭代法收斂收斂 (L)1, 其中其中L=(D- -L)- -1(1- -)D+U. . 例例5 考察用考察用Jacobi方法解方程組方法解方程組(1.2)的收斂性的收斂性. 解解 因為方程組因為方程組(1.2)的矩陣的矩陣A及迭代矩陣及迭代矩陣J為為解得解得, 0039772727. 0034090909. 0)det(317638833 JI,3445. 01841. 0,3445. 01841. 0,3082. 0321ii . 13592. 0, 13082. 0321 即即 (J)1. ,62, 1 這說明用迭代法解

37、此方程組這說明用迭代法解此方程組不收斂不收斂. 迭代法的基本定理在理論上是重要的，根據(jù)譜迭代法的基本定理在理論上是重要的，根據(jù)譜半徑的性質(zhì)半徑的性質(zhì) (B)|B|，下面利用矩陣，下面利用矩陣B的范數(shù)建立的范數(shù)建立判別迭代法收斂的充分條件判別迭代法收斂的充分條件. 定理定理5(迭代法收斂的充分條件迭代法收斂的充分條件) 設(shè)有方程組設(shè)有方程組 x=Bx+f， B=(bij)Rnn，及一階定常迭代法及一階定常迭代法 x(k+1)=Bx(k)+f. 如果有如果有B的某種算子范數(shù)的某種算子范數(shù)|B|=q1 ，則，則 (1) 迭代法迭代法收斂，即對任取收斂，即對任取x(0)有有.,lim)(fBxxxxk

38、k 且且.)2()0()(xxqxxkk .1)3()1()()( kkkxxqqxx.1)4()0()1()(xxqqxxkk 證明證明 (1)由基本定理由基本定理4結(jié)論結(jié)論(1)是顯然的是顯然的.(2) 顯然有關(guān)系式顯然有關(guān)系式x*- -x(k+1)=B(x*- -x(k) 及及x(k+1) x(k)=B(x(k) x(k- -1).于是有于是有 (a) |x(k+1) x(k)|q|x(k) x(k- -1)|; (b) |x*- -x(k+1)|q|x*- -x(k)|.反復(fù)利用反復(fù)利用(b)即得即得(2). (3) 考查考查 |x(k+1) x(k)|=|x*x(k)(x*x(k+1

39、)| |x*x(k)| x*x(k+1)| (1q)|x*x(k)|,.111)1()()()1()( kkkkkxxqqxxqxx即得即得 (4) 利用利用(3)的結(jié)果反復(fù)利用的結(jié)果反復(fù)利用(a)，則得到，則得到(4). 即即 .11)0()1()1()()(xxqqxxqqxxkkkk 6.3.2 關(guān)于解某些特殊方程組迭代法的收斂性關(guān)于解某些特殊方程組迭代法的收斂性 在科學(xué)及工程計算中，要求解方程組在科學(xué)及工程計算中，要求解方程組Ax=b，其，其矩陣矩陣A常常具有某些特性常常具有某些特性. 例如，例如，A具有對角占優(yōu)性具有對角占優(yōu)性質(zhì)或質(zhì)或A為不可約陣，或為不可約陣，或A是對稱正定陣，下面

40、討論用是對稱正定陣，下面討論用基本迭代法解這些方程組的收斂性基本迭代法解這些方程組的收斂性. 定義定義3(對角占優(yōu)陣對角占優(yōu)陣) 設(shè)設(shè)A=(aij)nn . (1) 如果如果A的元素滿足的元素滿足)., 2 , 1(1niaanijjijii 稱稱A為為嚴格嚴格(按行按行)對角占優(yōu)陣對角占優(yōu)陣. (2) 如果如果A的元素滿足的元素滿足)., 2 , 1(1niaanijjijii 且上式至少有一個不等式成立，稱且上式至少有一個不等式成立，稱A為為弱弱(按行按行)對角對角占優(yōu)陣占優(yōu)陣. 定義定義4(可約與不可約矩陣可約與不可約矩陣) 設(shè)設(shè)A=(aij)nn (n2)，如果存在置換陣如果存在置換陣

41、P使使)6 . 3(,0221211 AAAAPPT其中其中A11為為r階方陣，階方陣，A22為為n- -r階方陣階方陣(1rn)，則稱，則稱A為為可約矩陣可約矩陣. 否則，如果不存在這樣置換陣否則，如果不存在這樣置換陣P使使(3.6)式成立，則稱式成立，則稱A為為不可約矩陣不可約矩陣. A為可約矩陣意即為可約矩陣意即A可經(jīng)過若干行列重排化為可經(jīng)過若干行列重排化為(3.6)或或Ax=b可化為兩個低階方程組求解可化為兩個低階方程組求解(如果如果A經(jīng)過兩行經(jīng)過兩行交換的同時進行相應(yīng)兩列的交換，稱對交換的同時進行相應(yīng)兩列的交換，稱對A進行一次行進行一次行列重排列重排). 事實上，由事實上，由Ax=b

42、可化為可化為PTAP(PTx)=PTb. 于是，求解于是，求解Ax=b化為求解化為求解且記且記 ,其中其中yi, di為為r維向量維向量. 2121,ddbPdyyxPyTT .,22221212111dyAdyAyA由上式第由上式第2個方程組求出個方程組求出y2,再代入第再代入第1個方程組求出個方程組求出y1. 顯然，如果顯然，如果A所有元素都非零，則所有元素都非零，則A為不可約陣為不可約陣. 例例7 設(shè)有矩陣設(shè)有矩陣),(.4110140110410114,11122211都不為零都不為零iiinnnnncbaBbacbacbacbA 則則A, B都是不可約矩陣都是不可約矩陣. 定理定理6

43、(對角占優(yōu)定理對角占優(yōu)定理) 如果如果A=(aij)nn為為嚴格對嚴格對角占優(yōu)矩陣角占優(yōu)矩陣或或A為為不可約弱對角占優(yōu)矩陣不可約弱對角占優(yōu)矩陣，則，則A為非為非奇異矩陣奇異矩陣. 證明證明 只就只就A為為嚴格對角占優(yōu)矩陣嚴格對角占優(yōu)矩陣證明此定理證明此定理. 采用反證法，如果采用反證法，如果det(A)=0，則，則Ax=b有非零解，記有非零解，記為為x=(x1, x2,xn)T，則，則 .0max1 inxkxx 由齊次方程組第由齊次方程組第k個方程個方程, 01 njjijxa則有則有,|111 nkjjkjknkjjjkjnkjjjkjkkkaxxaxaxa即即,1 nkjjkjkkaa這

44、與假設(shè)矛盾，故這與假設(shè)矛盾，故det(A)0. 定理定理7 設(shè)方程組設(shè)方程組Ax=b，如果，如果(1) A為為嚴格對角占優(yōu)陣，則解嚴格對角占優(yōu)陣，則解Ax=b的的Jacobi迭迭代法代法, Gauss- -Seidel 迭代法迭代法均收斂均收斂.(2) A為弱對角為弱對角占優(yōu)陣，且占優(yōu)陣，且A為不可約矩陣為不可約矩陣, 則則解解Ax=b的的Jacobi迭代法迭代法, Gauss- -Seidel 迭代法迭代法均收斂均收斂. 證明證明 只證只證(1)，(2)作為練習(xí)作為練習(xí).因為因為A是嚴格對角占優(yōu)陣，所以是嚴格對角占優(yōu)陣，所以aii0(i=1,n).)(1ULDJ 00021222222111

45、11112nnnnnnnnaaaaaaaaaaaa則則|J| 1，所以，所以 Jacobi 迭代法迭代法收斂收斂.Jacobi迭代陣迭代陣)(det)det(1ULDIGI . 0)(det)det(1 ULDLD )(. 0)(det ULD 下面證明下面證明GaussSeidel 迭代法迭代法收斂收斂.由由G=(D- -L)- -1U，得，得下面證明下面證明| |1. 若不然若不然, 即即| | 1, 則則. ), 2 , 1(|111 ijnijijijijijiiniaaaa 由于由于. 0)det(1 LD所以所以即矩陣即矩陣 ULD)( 是嚴格對角占優(yōu)矩陣，故可逆，這與是嚴格對角占

46、優(yōu)矩陣，故可逆，這與(*) 式矛盾，所式矛盾，所以以| |1, 從而從而 (G)0.).(),(),(),(ibayLyLyyyyLT 所以所以| |1, 從而從而 (G)1, 故故Gauss- -Seidel迭代法迭代法收斂收斂.1)(|22222 baba 令令 - -(Ly, y)=a+ib，則由復(fù)向量內(nèi)積的性質(zhì)有，則由復(fù)向量內(nèi)積的性質(zhì)有.)(),(),(),(ibaibayLyyDyyyLT 下面研究對于解方程組下面研究對于解方程組Ax=b的的SOR方法方法中松弛中松弛因子因子在什么范圍內(nèi)取值，在什么范圍內(nèi)取值，SOR方法方法才可能收斂才可能收斂.定理定理8(SOR方法收斂的必要條件方

47、法收斂的必要條件) 設(shè)解設(shè)解方程組方程組 Ax=b的的SOR迭代法迭代法收斂，則收斂，則0 2. 1)1 ()1 ()()1det()det()det(1111 nniiiniiiaaUDLDL 證證 A=D- -L- -U，L =(D- - L)- -1(1- - )D + U, 由于由于SOR迭代法迭代法收斂，則收斂，則 (L )1. 設(shè)迭代矩陣設(shè)迭代矩陣L 的特征值的特征值為為 i (i=1,n)，則有，則有det(L )| 1 2 n| (B )n1.于是于是所以所以|1- - | |1 1，即，即 0 2.定理定理8說明解說明解Ax=b的的SOR迭代法迭代法，只有在，只有在(0, 2

48、)范范圍內(nèi)取松弛因子圍內(nèi)取松弛因子 ，才可能收斂，才可能收斂.定理定理9(SOR方法收斂的充分條件方法收斂的充分條件) 設(shè)有設(shè)有方程組方程組 Ax=b，如果：，如果：(1) A為對稱為對稱正定矩陣正定矩陣，A=D- -L- -LT;(2) 0 2.則解則解方程組方程組 Ax=b的的SOR迭代法迭代法收斂收斂.證證 在上述假定下，設(shè)迭代矩陣在上述假定下，設(shè)迭代矩陣L 的任一特征值的任一特征值為為 ，只要證明，只要證明| |0. 令令 - -(Ly, y)=a+ib，則由復(fù)向量內(nèi)積的性質(zhì)有，則由復(fù)向量內(nèi)積的性質(zhì)有).(),(),(),(ibayLyLyyyyLT ,2),)(),(0ayyLLDyAyT 因為因為.)()(biabia ,),(),(),(),(),(yLyyDyyyLyDyyDyT .)()(2222222baba 當當0 2時，有時，有(分子減分母分子減分母). 0)2)(2()()(22 aaa即即L 的任一特征值滿足的任一特征值滿足| |1, 故故SOR迭代法迭代法收斂收斂.由定理由定理3證明中可知，如果證明中可知，如果 (B)1且且