版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)解線性方程組的迭代方法解線性方程組的迭代方法 1 引言引言 2 基本迭代法基本迭代法 3 迭代法的收斂性迭代法的收斂性上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)其中其中A為非奇異矩陣為非奇異矩陣, 當(dāng)當(dāng)A為為低階稠密矩陣低階稠密矩陣時(shí)時(shí), 用前面討用前面討論的選主元消去法是有效的論的選主元消去法是有效的. 但對(duì)于但對(duì)于大型稀疏矩陣方大型稀疏矩陣方程組程組(A的階數(shù)的階數(shù)n很大,但很大,但零元素較多零元素較多), 利用迭代法求解利用迭代法求解是合適的是合適的. 迭代法的基本思想就是用逐次逼近的方法去求線迭代法的基本思想就是用逐次逼近的方法去求
2、線性方程組的解。性方程組的解。 本章將介紹迭代法的一些基本理論及本章將介紹迭代法的一些基本理論及雅可比迭代雅可比迭代法法,高斯高斯-賽德?tīng)柕ㄙ惖聽(tīng)柕ǎ沙诘ǔ沙诘?,而超松弛迭,而超松弛迭代法?yīng)用很廣泛。代法應(yīng)用很廣泛。 下面舉簡(jiǎn)例,以便了解迭代法的思想下面舉簡(jiǎn)例,以便了解迭代法的思想. 對(duì)線性方程組對(duì)線性方程組 Ax=b, (1.1) 1 引言引言上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例例1 求解方程組求解方程組)2 . 1(.361236,33114,20238321321321 xxxxxxxxx記為記為Ax=b,其中,其中.363330,123611142
3、38321 bxxxxA方程組的精確解是方程組的精確解是x*=(3,2,1)T. 現(xiàn)將改寫(xiě)為現(xiàn)將改寫(xiě)為上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè))3 . 1().3636(121),334(111),2023(81213312321 xxxxxxxxx或?qū)憺榛驅(qū)憺閤=B0 x+f,其中,其中.,0001236113382012312611111482830 fB上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 我們?nèi)稳〕跏贾?,例如取我們?nèi)稳〕跏贾?,例如取x(0)=(0, 0, 0)T. 將這些值將這些值代入代入(1.3)式右邊式右邊(若若(1.3)式為等式即求得方程組的解,式為等式即求得
4、方程組的解,但一般不滿足但一般不滿足),得到新的值,得到新的值x(1)=(x1(1), x2(1), x3(1)T=(3.5, 3, 3)T ,再將,再將x(1)分量代入分量代入(1.3)式右邊得到式右邊得到 x(2),反復(fù)利用這個(gè)計(jì)算程序,得到一向量序列和一般的計(jì)反復(fù)利用這個(gè)計(jì)算程序,得到一向量序列和一般的計(jì)算公式算公式(迭代公式迭代公式)(0)(1)( )111(0)(0)(1)(1)( )( )222(0)(1)( )333,kkkkxxxxxxxxxxxxLL上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè))4 . 1(.12/ )3636(,11/ )334(, 8/ )2023()
5、(2)(1)1(3)(3)(1)1(2)(3)(2)1(1 kkkkkkkkkxxxxxxxxx簡(jiǎn)寫(xiě)為簡(jiǎn)寫(xiě)為 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 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)從此例看出,由迭代法產(chǎn)生的向量序列從此例看出,由迭代法產(chǎn)生的向量序列x(k)逐步逐步逼近方程組的精確解是逼近方程組的精確解是x*=(3,2,1)T. 即有即有 對(duì)于任何一個(gè)方程組對(duì)于任何
6、一個(gè)方程組x=Bx+f(由由Ax=b變形得到的變形得到的等價(jià)方程組等價(jià)方程組),由迭代法產(chǎn)生的向量序列,由迭代法產(chǎn)生的向量序列x(k)是否一定是否一定逐步逼近方程組的解逐步逼近方程組的解x*呢?回答呢?回答是不一定是不一定. 請(qǐng)同學(xué)們請(qǐng)同學(xué)們考慮用迭代法解下述方程組考慮用迭代法解下述方程組 . 53, 521221xxxxx(k)x* xxkk)(lim上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)對(duì)于給定方程組對(duì)于給定方程組x=Bx+f,設(shè)有唯一解,設(shè)有唯一解x*,則,則 x*=Bx*+f .(1.5)又設(shè)又設(shè)x(0)為任取的初始向量為任取的初始向量, 按下述公式構(gòu)造向量序列按下述公式構(gòu)造
7、向量序列 x(k+1)=Bx(k)+f , k=0,1,2,.(1.6)其中其中k表示迭代次數(shù)表示迭代次數(shù). 定義定義1 (1)對(duì)于給定的方程組對(duì)于給定的方程組x=Bx+f , 用公式用公式(1.6)逐步代入求近似解的方法稱(chēng)為逐步代入求近似解的方法稱(chēng)為迭代法迭代法(或稱(chēng)為或稱(chēng)為一階定一階定常迭代法常迭代法,這里,這里B與與k無(wú)關(guān)無(wú)關(guān)). B稱(chēng)為稱(chēng)為迭代矩陣迭代矩陣. (2) 如果如果limx(k) (k)存在存在(記為記為x*), 稱(chēng)此稱(chēng)此迭代法迭代法收斂收斂, 顯然顯然x*就是方程組的解就是方程組的解, 否則稱(chēng)此否則稱(chēng)此迭代法發(fā)散迭代法發(fā)散.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)
8、由上述討論,需要研究由上述討論,需要研究x(k)的收斂性的收斂性. 引進(jìn)誤引進(jìn)誤差向量差向量,)1()1( xxkk (1.6)減去減去(1.5)式得:式得:(k+1)=B(k) (k=0,1,2, ) 遞推得遞推得( )(1)(0).kkkBBL 要考察要考察x(k)的收斂性,就要研究的收斂性,就要研究B在什么條件下在什么條件下有有l(wèi)im(k)=0 (k),亦即要研究,亦即要研究B滿足什么條件時(shí)有滿足什么條件時(shí)有Bk0 0(零向量零向量) (k) . x*=Bx*+f .(1.5) x(k+1)=Bx(k)+f , k=0,1,2,.(1.6)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)
9、2 基本迭代法基本迭代法其中,其中,A=(aij)Rnn為非奇異矩陣,下面研究任何建為非奇異矩陣,下面研究任何建立立Ax=b的各種迭代法的各種迭代法. 設(shè)線性方程組設(shè)線性方程組 Ax=b, (2.1) 其中,其中,M為可選擇的非奇異矩陣,且使為可選擇的非奇異矩陣,且使Mx=d容易求容易求解,一般選擇解,一般選擇A的某種近似,稱(chēng)的某種近似,稱(chēng)M為為分裂矩陣分裂矩陣. 將將A分裂為分裂為 A=M- -N. (2.2) 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 于是,求解于是,求解Ax=b轉(zhuǎn)化為求解轉(zhuǎn)化為求解Mx=Nx+b ,即求解,即求解.11bMNxMxbAx 求求解解可構(gòu)造一階定常迭代
10、法可構(gòu)造一階定常迭代法(0)(1)( )()(2.3)(0,1,),kkxxBxfkL初始向量 ,其中其中 B=M- -1N=M- -1(M- -A)=I- -M- -1A , f=M- -1b. 稱(chēng)稱(chēng) B=I- -M- -1A為迭代法的為迭代法的迭代矩陣迭代矩陣,選取,選取M矩陣,就得矩陣,就得到解到解Ax=b的各種迭代法的各種迭代法. 設(shè)設(shè)aii 0 (i=1,2,n),并將,并將A寫(xiě)成三部分寫(xiě)成三部分上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)1121221,11,212,1121,112,121,00000000.nnnnnnn nnnnnnnaaaAaaaaaaaaaaaaDL
11、UMMOOLLLLOMM上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)111212122212LLMMMLnnnnnnaaaaaaAaaa 1122OnnaaDa 2112000MMLnnaLaa1212000LLOMnnaaaU即即A=D- -L- -U上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)2.1 雅可比雅可比(Jacobi)迭代法迭代法 設(shè)設(shè)aii 0 (i=1,2,n),選取,選取M為為A的對(duì)角元素部分的對(duì)角元素部分,即選取即選取M=D(對(duì)角陣對(duì)角陣),A=D- -N,由,由(2.3)式得到解方式得到解方程組程組Ax=b的的雅可比雅可比(Jacobi)迭代法迭代法. 又稱(chēng)又稱(chēng)
12、簡(jiǎn)單迭代法簡(jiǎn)單迭代法.其中其中B=I- -D- -1A=D- -1(L+U)=J, f=D- -1b. 稱(chēng)稱(chēng)J為解為解Ax=b的的雅可比迭代法的迭代矩陣雅可比迭代法的迭代矩陣.(0)(1)( )()(2.5)(0,1,),L初始向量 ,kkxxBxfk上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)于是雅可比迭代法可寫(xiě)為于是雅可比迭代法可寫(xiě)為矩陣形式矩陣形式bDxULDxkk1)(1)1()( 其其Jacobi迭代矩陣迭代矩陣為為 )(1ULDBJ1121111221222212000nnnnnnnnaaaaaaaaaaaaL LL LMMMMMML L上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)
13、下頁(yè)下頁(yè)下面給出雅可比迭代法下面給出雅可比迭代法(2.5)的分量計(jì)算公式的分量計(jì)算公式, 記記( )( )( )( )1(,) ,LLkkkkTinxxxx由雅可比迭代法由雅可比迭代法(2.5)有有,)()()1(bxULDxkk 每一個(gè)分量寫(xiě)出來(lái)為每一個(gè)分量寫(xiě)出來(lái)為1(1)( )( )11(1,2, ). Linkkkiiiijjijjijjia xa xa xbin即當(dāng)即當(dāng)aii 0時(shí),有時(shí),有1(1)( )( )111() (1,2, ). Linkkkiijjijjijjiiixa xa xbina上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)等等價(jià)價(jià)方方程程組組其中其中 aii(i
14、) 0 (i=1,2,n)11221111221122221122111nnnnnnnnnnxa xa xbaxa xa xbaxa xa xba LLML即由方程組即由方程組Ax=b得到的得到的上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)建立的雅可比迭代格式為建立的雅可比迭代格式為(1)( )( )( )11221331111(1)( )( )( )221 12332222(1)( )( )1 1111()1()1()LLMLkkkknnkkkknnkkknnnnnnnnxa xa xa xbaxa xa xa xbaxa xaxba上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)于是,
15、解于是,解Ax=b的雅可比迭代法的計(jì)算公式為的雅可比迭代法的計(jì)算公式為(0)(0)(0)1(1)( )1(,) ,()/,(2.6)(1,2, ) (0,1,).LLL 表示迭代次數(shù)Tnnkkiiijjiijj ixxxxba xaink 由由(2.6)式可知,雅可比迭代法計(jì)算公式簡(jiǎn)單,式可知,雅可比迭代法計(jì)算公式簡(jiǎn)單,每迭代一次只需計(jì)算一次矩陣和向量的乘法且計(jì)算每迭代一次只需計(jì)算一次矩陣和向量的乘法且計(jì)算過(guò)程中原始矩陣過(guò)程中原始矩陣A始終不變始終不變. 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 從Jacobi迭代法的計(jì)算過(guò)程可知,若向量序列x(k)收斂于方程組的精確解,則顯然有x(k
16、+1)比 x(k)更靠近精確解。 事實(shí)上Jacobi方法迭代過(guò)程的每一步計(jì)算是用x(k)的全部分量來(lái)計(jì)算x(k+1)的所有分量,很顯然,在計(jì)算x(k+1)的第i個(gè)分量 ) 1()1(ixki時(shí),對(duì)已計(jì)算出的最新的分量 (1)(1)(1)121,Lkkkixxx可能沒(méi)有利用,而這些最新計(jì)算出來(lái)的(1)(1,2,1)Lkjxji可能比舊的分量 ( )(1,2,1)Lkjxji更接近于精確解,因此對(duì)這(1)(1,2,1)Lkjxji些新分量 加以利用是合理的。就得到了所謂求解方程組AX=b的的高斯賽德?tīng)柛咚官惖聽(tīng)枺℅auss-Seidel)迭代法.2.2 高斯賽德?tīng)柕ǜ咚官惖聽(tīng)柕ㄉ享?yè)上頁(yè)上頁(yè)
17、上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)在在 Jacobi 迭代中,計(jì)算迭代中,計(jì)算 xi(k+1)(2 i n)時(shí)時(shí),使用使用xj(k+1)代替代替xj(k) (1 j i- -1),即有即有(1)( )( )( )11221331111(1)(1)( )( )22112332222(1)(1)(1)11111()1()1()LLMLkkkknnkkkknnkkknnnnnnnnxa xa xa xbaxa xa xaxbaxa xaxba建建立立迭迭代代格格式式上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)或縮寫(xiě)為或縮寫(xiě)為稱(chēng)為稱(chēng)為高斯高斯塞德?tīng)柸聽(tīng)?Gauss Seidel)迭代法迭代法.
18、bLDxULDxkk1)(1)1()()( 其其Gauss Seidel迭代矩陣迭代矩陣為為BG = (D- -L)- -1U于是高斯于是高斯塞德?tīng)柕蓪?xiě)為塞德?tīng)柕蓪?xiě)為矩陣形式矩陣形式1(1)(1)( )111() (1,2, ). Linkkkiijjijjijjiiixa xa xbina上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 這就是說(shuō),選取分裂矩陣這就是說(shuō),選取分裂矩陣M為為A的下三角部分的下三角部分,即選取即選取M= D- -L(下三角陣下三角陣),A=M- -N,由,由(2.3)式得到式得到解解Ax=b的的高斯高斯塞德?tīng)柸聽(tīng)?Gauss Seidel)迭代法迭代
19、法.其中其中B=I- -(D- -L)- -1A= (D- -L)- -1U=G, f=(D- -L)- -1b. 稱(chēng)矩稱(chēng)矩陣陣G=(D- -L)- -1U為解為解Ax=b的的高斯高斯塞德?tīng)柸聽(tīng)柕ǖ牡ǖ牡仃嚧仃?)7 . 2(), 1 , 0()()()1()0( kfBxxxkk,初初始始向向量量上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)由由高斯高斯塞德?tīng)柕ㄈ聽(tīng)柕?2.7)有有,)()()1(bUxxLDkk 每一個(gè)分量寫(xiě)出來(lái)為每一個(gè)分量寫(xiě)出來(lái)為1(1)(1)( )11(1,2, ). Linkkkiiiiijjijjjjia xba xa xin即當(dāng)即當(dāng)a
20、ii 0時(shí),有時(shí),有(與前面一樣的式子與前面一樣的式子)1(1)(1)( )111() (1,2, ). Linkkkiiijjijjjjiiixba xa xina或或,)()1()1(bUxLxDxkkk 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)于是,解于是,解Ax=b的的高斯高斯塞德?tīng)柸聽(tīng)柕ǖ挠?jì)算公式為迭代法的計(jì)算公式為(0)(0)(0)11(1)(1)( )11(,)(),()/,(2.8)(1,2, ) (0,1,). LLL初始向量表示迭代次數(shù)Tninkkkiiijjijjiijj ixxxxba xa xaink或或(0)(0)(0)1(1)( )1(1)( )1(
21、,) ,(2.9)()/,(1,2, ) (0,1,).LLLTnkkiiiinkkiiijjijjiijj ixxxxxxxba xa xaink上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 雅可比迭代法雅可比迭代法不使用變量的最新信息計(jì)算不使用變量的最新信息計(jì)算xi(k+1),而,而由由高斯高斯塞德?tīng)柕饺聽(tīng)柕?2.8)可知,計(jì)算可知,計(jì)算x(k+1)的第的第 i個(gè)個(gè)分量分量xi(k+1)時(shí),利用了已經(jīng)計(jì)算出的最新分量時(shí),利用了已經(jīng)計(jì)算出的最新分量xj(k+1) (j=1,2,i- -1). 可看作可看作雅可比迭代法雅可比迭代法的一種改進(jìn)的一種改進(jìn). 由由(2.8)可知,可
22、知,高斯高斯塞德?tīng)柕饺聽(tīng)柕矫康淮沃恍栌?jì)算一次每迭代一次只需計(jì)算一次矩陣與向量的乘法矩陣與向量的乘法.Jacobi iterationGauss-Seidel iteration計(jì)算計(jì)算x(k+1)時(shí)需要時(shí)需要x(k)的所有分量,因此的所有分量,因此需開(kāi)兩組存儲(chǔ)單元需開(kāi)兩組存儲(chǔ)單元分別存放分別存放x(k)和和x(k+1)計(jì)算計(jì)算xi(k+1)時(shí)只需要時(shí)只需要x(k)的的i+1n個(gè)分量,因此個(gè)分量,因此x(k+1)的的前前i個(gè)分量可存貯在個(gè)分量可存貯在x(k)的的前前i個(gè)分量所占的存儲(chǔ)單元,個(gè)分量所占的存儲(chǔ)單元,無(wú)需開(kāi)兩組存儲(chǔ)單元無(wú)需開(kāi)兩組存儲(chǔ)單元上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)
23、下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例例2 用用高斯高斯塞德?tīng)柕ㄈ聽(tīng)柕ń饫饫?的方程組的方程組(1.2).(1)( )( )123(1)(1)( )213(1)(1)(1)312(2032)/8,(334)/11,(3663)/12.(0,1,2,).Lkkkkkkkkkxxxxxxxxxk 解解 用用高斯高斯塞德?tīng)柕剑喝聽(tīng)柕剑喝∪(0)=(0, 0, 0)T.迭代到第迭代到第7次有次有;)9999930. 0,9999987. 1,000002. 3()7(Tx .1002. 24)7()7( xx 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 由此例可知,用由此例可知,用高斯
24、高斯塞德?tīng)柕ㄈ聽(tīng)柕?,雅可比雅可比迭代法迭代法解線性方程組解線性方程組(1.2)(且取且取x(0)=0)均收斂,而均收斂,而高高斯斯塞德?tīng)柕ㄈ聽(tīng)柕ū缺妊趴杀鹊ㄑ趴杀鹊ㄊ諗枯^快收斂較快(即取相即取相同的同的x(0),達(dá)到同樣精度所需迭代次數(shù)較少,達(dá)到同樣精度所需迭代次數(shù)較少),但這結(jié),但這結(jié)論只當(dāng)論只當(dāng)A滿足一定條件時(shí)才是對(duì)的滿足一定條件時(shí)才是對(duì)的. 說(shuō)明:說(shuō)明:Jacobi迭代法的收斂性和迭代法的收斂性和G-S方法的收斂方法的收斂性沒(méi)有必然的聯(lián)系,存在前者收斂后者不收斂的方性沒(méi)有必然的聯(lián)系,存在前者收斂后者不收斂的方程組,也存在后者收斂二前者不收斂的方程組。程組,也存
25、在后者收斂二前者不收斂的方程組。上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例例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 迭代格式為迭代格式為上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.
26、1511 1.099993 1.199993 1.29999112 1.099998 1.199998 1.299997 )2 . 4(51)3 . 82(101)2 . 72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx取取 x(0)=(0,0,0)T 計(jì)算計(jì)算結(jié)果結(jié)果如下:如下:上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 解:解: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(1kkkkkkkkkxxx
27、xxxxxx 例例2 用用GaussSeidel 迭代法解上題迭代法解上題. 2 . 453 . 82102 . 7210321321321xxxxxxxxx上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)取取 x(0)=(0,0,0)T 計(jì)算計(jì)算結(jié)果結(jié)果如下:如下:kx1(k) x2(k)x3(k)10.720.9021.164481.0999981.1999991.3 )2 . 4(51)3 . 82(101)2 . 72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定義定義2
28、 設(shè)有矩陣序列設(shè)有矩陣序列 Ak=(aij(k)Rnn 及及A=(aij)Rnn,如果,如果n2個(gè)數(shù)列極限存在且有個(gè)數(shù)列極限存在且有)., 2 , 1,(lim)(njiaaijkijk 則則Ak稱(chēng)收斂于稱(chēng)收斂于A,記為,記為lim (k).例例4 設(shè)有矩陣序列設(shè)有矩陣序列Ak, 其中其中Ak=Bk,而而,0,02,011222 kkkkkBBB 且設(shè)且設(shè)|1,考查矩陣序列極限,考查矩陣序列極限.解解 顯然顯然, 當(dāng)當(dāng)|1時(shí)時(shí), 則有則有.0000limlim kkkkBA矩陣收斂有關(guān)結(jié)論矩陣收斂有關(guān)結(jié)論上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)矩陣序列極限概念可以用矩陣算子范數(shù)來(lái)描述矩
29、陣序列極限概念可以用矩陣算子范數(shù)來(lái)描述. 定理定理1 其中其中|為為矩陣的任意一種算子范數(shù)矩陣的任意一種算子范數(shù)., 0limlim AAAAkkkk證明證明 顯然有顯然有. 0limlim AAAAkkkk再由矩陣范數(shù)的等價(jià)性再由矩陣范數(shù)的等價(jià)性, 則定理對(duì)其它算子范數(shù)亦對(duì)則定理對(duì)其它算子范數(shù)亦對(duì).定理定理2.limlimAxxARxAAkknkk 都都有有對(duì)對(duì)證明作為練習(xí)證明作為練習(xí).上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定理定理3 設(shè)設(shè)B=(bij)Rnn,則,則limBk=0 (k)(零零矩陣矩陣)的充分必要條件是矩陣的充分必要條件是矩陣B的譜半徑的譜半徑 (B)1.證明證
30、明 由矩陣由矩陣B的的若當(dāng)標(biāo)準(zhǔn)形若當(dāng)標(biāo)準(zhǔn)形,存在非奇異矩陣存在非奇異矩陣P使使,211JJJJBPPr 其中其中若當(dāng)若當(dāng)(Jordan)塊塊,11iinniiiiJ 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)且,顯然有且,顯然有nnrii 1其中其中,11 PPJBPJPBkk.21 krkkkJJJJ)., 2 , 1( , 0lim0lim0limriJJBkikkkkk 于于是是上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 顯然有顯然有, Et,0=I, Et,k=0(當(dāng)當(dāng)kt),(Et,1)k= Et,k. 由于由于Ji=I+Et,1 ,因此,因此下面考查下面考查Jik的情況
31、的情況. 引進(jìn)記號(hào)引進(jìn)記號(hào)).(000,ittktntRktIE 101 ,01 ,1 ,)()()(tjjtjkijkkjjtjkijkktikiECECEIJ 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè))., 2 , 1(11)2(211)1(12211riCCCCCCttkikiktkitkkikkitkitkkikkikki 其中其中.!)1()1()!( !jjkkkjkjkCjk 得得到到利利用用極極限限),0, 10(0lim rcckkrk. 10lim jkjkkC. 1)(), 2 , 1( 10lim BriJikik 即即所所以以上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下
32、頁(yè)下頁(yè)下頁(yè)下頁(yè)3 迭代法的收斂性迭代法的收斂性3.1 一階定常迭代法的基本定理一階定常迭代法的基本定理其中,其中,A=(aij)Rnn為非奇異矩陣,記為非奇異矩陣,記x*為為(3.1)精確精確解,且設(shè)有等價(jià)的方程組解,且設(shè)有等價(jià)的方程組 設(shè)線性方程組設(shè)線性方程組 Ax=b, (3.1) 于是于是.fBxxbAx )2 . 3(.fBxx 設(shè)有解設(shè)有解Ax=b的一階定常迭代法的一階定常迭代法)3 . 3(.)()1(fBxxkk 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)有意義的問(wèn)題是:迭代矩陣有意義的問(wèn)題是:迭代矩陣B滿足什么條件時(shí),滿足什么條件時(shí),由迭代法產(chǎn)生的向量序列由迭代法產(chǎn)生的向
33、量序列x(k)收斂到收斂到x*. 引進(jìn)引進(jìn)誤差向量誤差向量)., 2 , 1 , 0()()( kxxkk 由由(3.3)式減式減(3.2)得到得到誤差向量的遞推公式誤差向量的遞推公式)., 2 , 1 , 0(,)0()()()1( kBBkkkk 由由1節(jié)可知,研究迭代法節(jié)可知,研究迭代法(3.3)收斂性問(wèn)題就是要研究收斂性問(wèn)題就是要研究迭代矩陣迭代矩陣B滿足什么條件時(shí),有滿足什么條件時(shí),有:).)(0 kBk零零矩矩陣陣當(dāng)?shù)ㄊ諗繒r(shí),如何衡量收斂速度?當(dāng)?shù)ㄊ諗繒r(shí),如何衡量收斂速度?上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)由定理由定理3證明中可知,如果證明中可知,如果 (B)
34、1且且 (B)越小時(shí),越小時(shí),迭代法收斂越快迭代法收斂越快. 現(xiàn)設(shè)有方程組現(xiàn)設(shè)有方程組下面討論迭代法的收斂速度下面討論迭代法的收斂速度. x=Bx+f, B=(bij)Rnn,及一階定常迭代法及一階定常迭代法 x(k+1)=Bx(k)+f (k=0,1,), 由基本定理有由基本定理有0 (B)1,且誤差向量,且誤差向量(k)=x(k)- -x*滿足滿足且設(shè)且設(shè)迭代法迭代法收斂,即對(duì)任取收斂,即對(duì)任取x(0),記,記.,lim)(fBxxxxkk 則則(k)=Bk(0),故故.)0()( kkB 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)現(xiàn)設(shè)現(xiàn)設(shè)B為對(duì)稱(chēng)矩陣,則有為對(duì)稱(chēng)矩陣,則有.)(2)
35、0(2)0(22)( kkkBB 下面確定使初始誤差縮小下面確定使初始誤差縮小10-s所需的迭代次數(shù)所需的迭代次數(shù), 即使即使.10)(skB 取對(duì)數(shù),得到所需最少迭代次數(shù)為取對(duì)數(shù),得到所需最少迭代次數(shù)為.)(ln10lnBsk 此式說(shuō)明,滿足精度此式說(shuō)明,滿足精度所需迭代次數(shù)與所需迭代次數(shù)與R=- -ln (B)成反成反比,當(dāng)比,當(dāng) (B)1越小,越小,R=- -ln (B)越大,則滿足越大,則滿足所需迭所需迭代次數(shù)越少,即迭代法收斂越快代次數(shù)越少,即迭代法收斂越快. 當(dāng)?shù)仃嚠?dāng)?shù)仃嘊為一為一般矩陣時(shí)的討論可參考相關(guān)文獻(xiàn)。般矩陣時(shí)的討論可參考相關(guān)文獻(xiàn)。定義定義5 稱(chēng)稱(chēng)R(B)=- -l
36、n (B)為迭代法為迭代法 x(k+1)=Bx(k)+f (k=0,1,)的的漸近收斂速度漸近收斂速度,簡(jiǎn)稱(chēng),簡(jiǎn)稱(chēng)迭代法收斂速度迭代法收斂速度.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定理定理4(迭代法基本定理迭代法基本定理) 設(shè)有方程組設(shè)有方程組 x=Bx+f. (3.4) 及一階定常迭代法及一階定常迭代法 x(k+1)=Bx(k)+f. (3.5) 對(duì)任意選擇初始向量對(duì)任意選擇初始向量x(0),迭代法,迭代法(3.5)收斂的充要條收斂的充要條件是矩陣件是矩陣B的譜半徑的譜半徑 (B)1.證明證明 充分性充分性. 設(shè)設(shè) (B)1,易知,易知Ax=f(其中其中A=I- -B)有唯一解
37、,記為有唯一解,記為x*,則,則 x*=Bx*+f.誤差向量誤差向量.,)0()0()0()()( xxBxxkkk 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)由設(shè)由設(shè) (B)1,應(yīng)用定理,應(yīng)用定理3,有,有 . 于是對(duì)任意于是對(duì)任意x(0)有有 ,即,即 .0lim kkB0lim kk xxkk)(lim其中其中x(k+1)=Bx(k)+f . 顯然,極限顯然,極限x*是方程組是方程組(3.4)的解,的解,且對(duì)任意且對(duì)任意x(0)有有必要性必要性. 設(shè)對(duì)任何設(shè)對(duì)任何x(0)有有0lim kkB).(0)0()()( kBxxkkk ,lim)( xxkk由定理由定理2知知再由定理再由
38、定理3,即得,即得 (B)1.定理定理4是一階定常迭代法的基本理論是一階定常迭代法的基本理論.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定理定理3和定理和定理4的結(jié)論和起來(lái)即為的結(jié)論和起來(lái)即為 (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迭代法迭代法收斂收
39、斂 (G)1, 其中其中G=(D- -L)- -1U. . (3) SOR迭代法迭代法收斂收斂 (L)1, 其中其中L=(D- -L)- -1(1- -)D+U. . 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例例5 考察用考察用Jacobi方法解方程組方法解方程組(1.2)的收斂性的收斂性. 解解 因?yàn)榉匠探M因?yàn)榉匠探M(1.2)的矩陣的矩陣A及迭代矩陣及迭代矩陣J為為解得解得, 0039772727. 0034090909. 0)det(317638833 JI,3445. 01841. 0,3445. 01841. 0,3082. 0321ii . 13592. 0, 13082.
40、 0321 即即 (J)1. ,62, 1 這說(shuō)明用迭代法解此方程組這說(shuō)明用迭代法解此方程組不收斂不收斂. 迭代法的基本定理在理論上是重要的,根據(jù)譜迭代法的基本定理在理論上是重要的,根據(jù)譜半徑的性質(zhì)半徑的性質(zhì) (B)|B|,下面利用矩陣,下面利用矩陣B的范數(shù)建立的范數(shù)建立判別迭代法收斂的充分條件判別迭代法收斂的充分條件.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定理定理5(迭代法收斂的充分條件迭代法收斂的充分條件) 設(shè)有方程組設(shè)有方程組 x=Bx+f, B=(bij)Rnn,及一階定常迭代法及一階定常迭代法 x(k+1)=Bx(k)+f. 如果有如果有B的某種算子范數(shù)的某種算子范數(shù)|B
41、|=q1 ,則,則 (1) 迭代法迭代法收斂,即對(duì)任取收斂,即對(duì)任取x(0)有有.,lim)(fBxxxxkk 且且.)2()0()(xxqxxkk .1)3()1()()( kkkxxqqxx.1)4()0()1()(xxqqxxkk 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)證明證明 (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*- -
42、x(k+1)|q|x*- -x(k)|.反復(fù)利用反復(fù)利用(b)即得即得(2)(3) 考查考查 |x(k+1) x(k)|=|x*x(k)(x*x(k+1)| |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 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)3.2 關(guān)于解某些特殊方程組迭代法的收斂性關(guān)于解某些特殊方程組迭代法的收斂性 在科學(xué)及工程計(jì)算中,要求解方程組
43、在科學(xué)及工程計(jì)算中,要求解方程組Ax=b,其,其矩陣矩陣A常常具有某些特性常常具有某些特性. 例如,例如,A具有對(duì)角占優(yōu)性具有對(duì)角占優(yōu)性質(zhì)或質(zhì)或A為不可約陣,或?yàn)椴豢杉s陣,或A是對(duì)稱(chēng)正定陣,下面討論用是對(duì)稱(chēng)正定陣,下面討論用基本迭代法解這些方程組的收斂性基本迭代法解這些方程組的收斂性.定義定義3(對(duì)角占優(yōu)陣對(duì)角占優(yōu)陣) 設(shè)設(shè)A=(aij)nn ,如果如果A的元素滿足的元素滿足 (1)., 2 , 1(1niaanijjijii稱(chēng)稱(chēng)A為為嚴(yán)格嚴(yán)格(按行按行)對(duì)角占優(yōu)陣對(duì)角占優(yōu)陣. (2)., 2 , 1(1niaanijjijii 且至少有一個(gè)不等號(hào)嚴(yán)格成立,稱(chēng)且至少有一個(gè)不等號(hào)嚴(yán)格成立,稱(chēng)A為
44、為弱弱(按行按行)對(duì)角占對(duì)角占優(yōu)陣優(yōu)陣.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定義定義4(可約與不可約矩陣可約與不可約矩陣) 設(shè)設(shè)A=(aij)nn (n2),如果存在置換陣如果存在置換陣P使使)6 . 3(,0221211 AAAAPPT其中其中A11為為r階方陣,階方陣,A22為為n- -r階方陣階方陣(1rn),則稱(chēng),則稱(chēng)A為為可約矩陣可約矩陣. 否則,如果不存在這樣置換陣否則,如果不存在這樣置換陣P使使(3.6)式成立,則稱(chēng)式成立,則稱(chēng)A為為不可約矩陣不可約矩陣. A為可約矩陣意即為可約矩陣意即A可經(jīng)過(guò)若干行列重排化為可經(jīng)過(guò)若干行列重排化為(3.6)或或Ax=b可化為兩個(gè)低
45、階方程組求解可化為兩個(gè)低階方程組求解(如果如果A經(jīng)過(guò)兩行經(jīng)過(guò)兩行交換的同時(shí)進(jìn)行相應(yīng)兩列的交換,稱(chēng)對(duì)交換的同時(shí)進(jìn)行相應(yīng)兩列的交換,稱(chēng)對(duì)A進(jìn)行一次行進(jìn)行一次行列重排列重排).上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 事實(shí)上,由事實(shí)上,由Ax=b可化為可化為PTAP(PTx)=PTb. 于是,求解于是,求解Ax=b化為求解化為求解且記且記 ,其中其中yi, di為為r維向量維向量. 2121,ddbPdyyxPyTT .,22221212111dyAdyAyA由上式第由上式第2個(gè)方程組求出個(gè)方程組求出y2,再代入第再代入第1個(gè)方程組求出個(gè)方程組求出y1. 顯然,如果顯然,如果A所有元素都非零
46、,則所有元素都非零,則A為不可約陣為不可約陣.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例例7 設(shè)有矩陣設(shè)有矩陣),(.4110140110410114,11122211都都不不為為零零iiinnnnncbaBbacbacbacbA 則則A, B都是不可約矩陣都是不可約矩陣.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定理定理6(對(duì)角占優(yōu)定理對(duì)角占優(yōu)定理) 如果如果A=(aij)nn為為嚴(yán)格對(duì)角嚴(yán)格對(duì)角占優(yōu)矩陣占優(yōu)矩陣或或A為為不可約弱對(duì)角占優(yōu)矩陣不可約弱對(duì)角占優(yōu)矩陣,則,則A非奇異。非奇異。 證明證明 只就只就A為為嚴(yán)格對(duì)角占優(yōu)矩陣嚴(yán)格對(duì)角占優(yōu)矩陣證明此定理證明此定理. 采用反
47、證法,如果采用反證法,如果det(A)=0,則,則Ax=b有非零解,記有非零解,記為為x=(x1, x2,xn)T,則,則 .0max1 inxkxx 由齊次方程組第由齊次方程組第k個(gè)方程個(gè)方程, 01 njjijxa則有則有,|111 nkjjkjknkjjjkjnkjjjkjkkkaxxaxaxa即即,1 nkjjkjkkaa這與假設(shè)矛盾,故這與假設(shè)矛盾,故det(A)0.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定理定理7 設(shè)方程組設(shè)方程組Ax=b,如果,如果(1) A為為嚴(yán)格對(duì)角占優(yōu)陣,則解嚴(yán)格對(duì)角占優(yōu)陣,則解Ax=b的的Jacobi迭迭代法代法, Gauss- -Seidel
48、 迭代法迭代法均收斂均收斂.(2) A為弱對(duì)角為弱對(duì)角占優(yōu)陣占優(yōu)陣,且,且A為不可約矩陣為不可約矩陣, 則則解解Ax=b的的Jacobi迭代法迭代法, Gauss- -Seidel 迭代法迭代法均收斂均收斂. 證明證明 只證只證(1),(2)作為練習(xí)作為練習(xí).因?yàn)橐驗(yàn)锳是嚴(yán)格對(duì)角占優(yōu)陣,所以是嚴(yán)格對(duì)角占優(yōu)陣,所以aii0(i=1,n).1121111221122221200()0nnnnnnnnaaaaaaaaJDLUaaaaLLMMOML則則|J| 1,所以所以 Jacobi 迭代法迭代法收斂收斂.Jacobi迭代陣迭代陣上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè))(det)det(1
49、ULDIGI . 0)(det)det(1 ULDLD det ()0( )DLU 下面證明下面證明GS迭代法迭代法收斂收斂.由由G=(D- -L)- -1U,得,得下面證明下面證明| |1. 若不然若不然, 即即| | 1, 則則. ), 2 , 1(|111 ijnijijijijijiiniaaaa 由于由于1det() 0DL即矩陣即矩陣 ULD)( .212222111211 nnnnnnaaaaaaaaa 是嚴(yán)格對(duì)角占優(yōu)矩陣,故可逆,這與是嚴(yán)格對(duì)角占優(yōu)矩陣,故可逆,這與(*) 式矛盾,所以式矛盾,所以| |1, 從而從而 (G)0.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè))
50、.(),(),(),(ibayLyLyyyyLT 所以所以| |1, 從而從而 (G)0為為松弛因子松弛因子,建立迭代格式如下,建立迭代格式如下1(1)(1)( )11(1)( )(1)( )(1)( )()/,(1)(),(1,2,). %Linkkkiiijjijjiijj ikkkkkkiiiiiixba xa xaxxxxxxin 即即./ )()(11)1()()1(iinijkjijijkjijikikiaxaxabxx 逐次超松弛法逐次超松弛法(SOR方法方法)或改寫(xiě)為或改寫(xiě)為, 2 , 1 , 0), 2 , 1(./ )()1 ()(11)1()()1( kniaxaxabx
51、xiinijkjijijkjijikiki 稱(chēng)為稱(chēng)為逐次超逐次超松松弛迭代法弛迭代法,簡(jiǎn),簡(jiǎn)稱(chēng)稱(chēng)SOR方法方法. =1就是就是G-S迭代法迭代法上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè).)()1()(1)(1)1(bLDxUDLDxkk 其其逐次超逐次超松弛迭代矩陣松弛迭代矩陣為為.)1()(1UDLDB 逐次超松弛法逐次超松弛法可寫(xiě)為可寫(xiě)為矩陣形式矩陣形式 下面用矩陣方法推導(dǎo),選取分裂矩陣下面用矩陣方法推導(dǎo),選取分裂矩陣M為帶參為帶參數(shù)的下三角矩陣數(shù)的下三角矩陣從而得到解從而得到解Ax=b的的逐次超松弛迭代法逐次超松弛迭代法 (Successive Over Relaxation M
52、ethod,簡(jiǎn)稱(chēng),簡(jiǎn)稱(chēng)SOR方法方法).).(1LDM 其中其中 0為可選擇的為可選擇的松弛因子松弛因子. 于是,由于是,由(2.3)可構(gòu)造一個(gè)迭代法,其迭代矩陣為可構(gòu)造一個(gè)迭代法,其迭代矩陣為.)1()()(11UDLDALDIL 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè))10. 2(), 1 , 0()()()1()0( kfxLxxkk ,初初始始向向量量 解解Ax=b的的SOR方法方法為為.其中其中.)(,)1()(11bLDfUDLDL 下面給出解下面給出解Ax=b的的SOR方法方法的分量計(jì)算公式的分量計(jì)算公式. 記記,),()()()(1)(Tknkikkxxxx 由由(2
53、.10)式可得式可得,)1()()()1(bxUDxLDkk ).()()()1()()1(kkkkkDxUxLxbDxDx 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)由此,得到解由此,得到解Ax=b的的SOR方法方法的計(jì)算公式的計(jì)算公式或或)11. 2(.), 2 , 1 , 0;, 2 , 1(/ )()1 (,),()(11)1()()1()0()0(1)0( 為為松松弛弛因因子子 kniaxaxabxxxxxiinijkjijijkjijikikiTn .), 2 , 1 , 0;, 2 , 1()12. 2(/ )(,),()(11)1()()1()0()0(1)0(為為松松弛
54、弛因因子子 kniaxaxabxxxxxxxiinijkjijijkjijiiikikiTn上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) (1) 顯然,當(dāng)顯然,當(dāng) =1時(shí)即為時(shí)即為GaussSeidel 迭代法迭代法. (2) SOR方法方法每迭代一次主要運(yùn)算量是計(jì)算一次每迭代一次主要運(yùn)算量是計(jì)算一次矩陣與向量的乘法矩陣與向量的乘法. (3) 當(dāng)當(dāng) 1時(shí),稱(chēng)為時(shí),稱(chēng)為超松弛法超松弛法;當(dāng);當(dāng) 1時(shí),稱(chēng)為時(shí),稱(chēng)為低低松弛法松弛法. (4) 在計(jì)算機(jī)實(shí)現(xiàn)時(shí)可用在計(jì)算機(jī)實(shí)現(xiàn)時(shí)可用 )()1(11maxmaxkikiniinixxx控制迭代終止,或用控制迭代終止,或用 )()(kkAxbr控制迭代
55、終止控制迭代終止.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) SOR迭代法迭代法是是GaussSeidel 迭代法迭代法的一種修正,的一種修正,可由下述思想得到可由下述思想得到. 設(shè)已知設(shè)已知x(k)及已計(jì)算及已計(jì)算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( kix)(kix)1( kix將將(2.13)代入代入(2.14)得到解得到解Ax=b的的SOR迭代迭代(2.11)式式.例例3 用用SOR迭代法迭代法解方程組解方程組.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)定理定理8(SOR方法收斂的必要條件方法收斂的必要條件) 設(shè)解設(shè)解方程組方程組 Ax=b的的SOR迭代法迭代法收斂,則收斂,則0 2.
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 小學(xué)語(yǔ)文滬教版課件教學(xué)課件教學(xué)課件教學(xué)
- 玉溪師范學(xué)院《數(shù)學(xué)文化》2021-2022學(xué)年第一學(xué)期期末試卷
- 玉溪師范學(xué)院《區(qū)域分析與規(guī)劃》2022-2023學(xué)年第一學(xué)期期末試卷
- 文書(shū)模板-無(wú)房證明
- 家用制冷電器具生產(chǎn)企業(yè)的賬務(wù)處理-記賬實(shí)操
- “能源變革”系列研究二:儲(chǔ)能乘政策之風(fēng)啟航-海通證券
- 龍華區(qū)錦華實(shí)驗(yàn)學(xué)校 第一單元測(cè)試2024-2025學(xué)年語(yǔ)文五年級(jí)上冊(cè)(統(tǒng)編版)
- 2023年氣血循環(huán)機(jī)項(xiàng)目綜合評(píng)估報(bào)告
- 2023年核電子產(chǎn)品項(xiàng)目綜合評(píng)估報(bào)告
- 2024屆河北保定一中高考數(shù)學(xué)試題考前指導(dǎo)卷
- 2024《技術(shù)服務(wù)合同范本》
- 全國(guó)仿真職業(yè)技能競(jìng)賽考試題庫(kù)及答案
- 小學(xué)一年級(jí)上冊(cè) 綜合實(shí)踐教學(xué)課件
- 園林工程材料試題
- 成型周期公式及計(jì)算
- RVVP線徑尺寸表
- 多高層框架結(jié)構(gòu)
- 某化工廠設(shè)備安裝施工方案【完整版】
- 8委托幫教函(最新整理)
- 正確對(duì)待調(diào)整反應(yīng)
- 《喝牛奶問(wèn)題》ppt課件
評(píng)論
0/150
提交評(píng)論