第3章 線性方程組的解法—迭代法

1、上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 3.4 線性代數(shù)方程組的解法線性代數(shù)方程組的解法(二二) 迭代方法迭代方法 引言引言 基本迭代法基本迭代法 迭代法的收斂性迭代法的收斂性上頁(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)柕?，超松弛迭代法超松弛迭代法?下面舉簡(jiǎn)例，以便了解迭代法的思想下面舉簡(jiǎn)例，以便了解迭代法的思想. 對(duì)線性方程組對(duì)線性方程組 Ax=b， (1.1) 引言引言上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例例1 求解方程組求解方程組)2 . 1(.361236,33114,20238321321321 xxxxxxxxx記為記為Ax=b，其中，其中.363330,12361114238321 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

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)稳〕跏贾担缛(0)=(0, 0, 0)T. 將這些值將這些值代入代入(1.3)式右邊式右邊(若若(1.3)式為等式即求得方程組的解，式為等式即求得方程組的解，但一般不滿足但一般不滿足)，得到新的值，得到新的值x(1)=(x1(1), x2(1), x3(1)T=(3.5, 3, 3)T ，再將，再將x

4、(1)分量代入分量代入(1.3)式右邊得到式右邊得到 x(2)，反復(fù)利用這個(gè)計(jì)算程序，得到一向量序列和一般的計(jì)反復(fù)利用這個(gè)計(jì)算程序，得到一向量序列和一般的計(jì)算公式算公式(迭代公式迭代公式),)(3)(2)(1)()1(3)1(2)1(1)1()0(3)0(2)0(1)0( kkkkxxxxxxxxxxxx上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè))4 . 1(.12/ )3636(,11/ )334(, 8/ )2023()(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表示迭代次

5、數(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ì)于任何一個(gè)方程組x=Bx+f(由由Ax=b變形得到的變形得到的等價(jià)方程組等價(jià)方程組)，由迭代法產(chǎn)生的向量序列，由迭代法產(chǎn)生的向量序列x(k)是否一定是否一定逐步逼近方程組的

6、解逐步逼近方程組的解x*呢？回答呢？回答是不一定是不一定. 考慮用迭考慮用迭代法解下述方程組代法解下述方程組 . 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)造向量序列 x(k+1)=Bx(k)+f , k=0,1,2,.(1.6)其中其中k表示迭代次數(shù)表示迭代次數(shù). 定義定義1 (1)對(duì)于給定的方程組對(duì)于給定的方程組x=Bx+f , 用公

7、式用公式(1.6)逐步代入求近似解的方法稱為逐步代入求近似解的方法稱為迭代法迭代法(或稱為或稱為一階定一階定常迭代法常迭代法，這里，這里B與與k無(wú)關(guān)無(wú)關(guān)). B稱為稱為迭代矩陣迭代矩陣. (2) 如果如果limx(k) (k)存在存在(記為記為x*), 稱此稱此迭代法迭代法收斂收斂, 顯然顯然x*就是方程組的解就是方程組的解, 否則稱此否則稱此迭代法發(fā)散迭代法發(fā)散.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)基本迭代法基本迭代法其中，其中，A=(aij)Rnn為非奇異矩陣，下面研究任何建為非奇異矩陣，下面研究任何建立立Ax=b的各種迭代法的各種迭代法. 設(shè)線性方程組設(shè)線性方程組 Ax=b，

8、 (2.1) 其中，其中，M為可選擇的非奇異矩陣，稱為可選擇的非奇異矩陣，稱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)造一階定常迭代法可構(gòu)造一階定常迭代法)3 . 2(), 1 , 0()()()1()0( kfBxxxkk，初初始始向向量量其中其中 B=M- -1N=M- -1(M- -A)=I- -M- -1A ， f=M- -1b. 稱稱 B=I- -M- -1A為迭代法的為迭代法的迭代矩

9、陣迭代矩陣，選取，選取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è).00000000, 121, 211, 1121,212, 11 , 1212211ULDaaaaaaaaaaaaaaaAnnnnnnnnnnnnnn 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)111212122212nnnnnnaaaaaaAaaa 1122nnaaDa 2112000nnaLaa1212000nnaaaU即即A=D- -L- -U上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)

10、下頁(yè)下頁(yè)下頁(yè)3.4.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)迭代法迭代法. 又稱又稱簡(jiǎn)單迭代法簡(jiǎn)單迭代法.其中其中BJ=I- -D- -1A=D- -1(L+U), f=D- -1b. 稱稱BJ為解為解Ax=b的的雅可比迭代法的迭代矩陣雅可比迭代法的迭代矩陣.kkJxxB xfk(0)(1)( )()(2.5)(0,1,),初初始始向向量量，上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下

11、頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)于是雅可比迭代法可寫(xiě)為于是雅可比迭代法可寫(xiě)為矩陣形式矩陣形式bDxULDxkk1)(1)1()( 其其Jacobi迭代矩陣迭代矩陣為為 )(1ULDBJ 0002122222211111112nnnnnnnnaaaaaaaaaaaa上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下面給出雅可比迭代法下面給出雅可比迭代法(2.5)的分量計(jì)算公式的分量計(jì)算公式, 記記,),()()()(1)(Tknkikkxxxx 由雅可比迭代法由雅可比迭代法(2.5)有有,)()()1(bxULDxkk 每一個(gè)分量寫(xiě)出來(lái)為每一個(gè)分量寫(xiě)出來(lái)為)., 2 , 1(1)(11)()1(nibxaxa

12、xainijkjijijkjijkiii 即當(dāng)即當(dāng)aii 0時(shí)，有時(shí)，有)., 2 , 1()(11)(11)()1(nibxaxaaxinijkjijijkjijiiki 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)等等價(jià)價(jià)方方程程組組其中其中 aii(i) 0 (i=1,2,n)11221111221122221122111nnnnnnnnnnxa xa xbaxa xa xbaxa xa xba 即由方程組即由方程組Ax=b得到的得到的上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)建立的雅可比迭代格式為建立的雅可比迭代格式為 )(1)(1)(1)(11)(11) 1(2)(2)(3

13、23)(12122) 1(21)(1)(313)(21211) 1(1nknnnknnnknknnkkkknnkkkbxaxaaxbxaxaxaaxbxaxaxaax上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)于是，解于是，解Ax=b的雅可比迭代法的計(jì)算公式為的雅可比迭代法的計(jì)算公式為)6 . 2()., 1 , 0(), 2 , 1(,/ )(,),(1)()1()0()0(1)0( 表表示示迭迭代代次次數(shù)數(shù)kniaxabxxxxiinijjkjijikiTn 由由(2.6)式可知，雅可比迭代法計(jì)算公式簡(jiǎn)單，式可知，雅可比迭代法計(jì)算公式簡(jiǎn)單，每迭代一次只需計(jì)算一次矩陣和向量的乘法且計(jì)算每

14、迭代一次只需計(jì)算一次矩陣和向量的乘法且計(jì)算過(guò)程中原始矩陣過(guò)程中原始矩陣A始終不變始終不變. 上頁(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)

15、x3(k)10.720.830.8420.9711.071.1511 1.099993 1.199993 1.29999112 1.099998 1.199998 1.299997取取 x(0)=(0,0,0)T 計(jì)算計(jì)算結(jié)果結(jié)果如下：如下：上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)3.4.2 高斯賽德?tīng)柕ǜ咚官惖聽(tīng)柕ㄔ谠?Jacobi 迭代中，計(jì)算迭代中，計(jì)算 xi(k+1)(2 i n)時(shí)時(shí)，使用使用xj(k+1)代替代替xj(k) (1 j i- -1)，即有即有 )(1)(1)(1) 1(11) 1(11) 1(2)(2)(323) 1(12122) 1(21)(1)(3

16、13)(21211) 1(1nknnnknnnknknnkkkknnkkkbxaxaaxbxaxaxaaxbxaxaxaax建建立立迭迭代代格格式式上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)或縮寫(xiě)為或縮寫(xiě)為稱為稱為高斯高斯塞德?tīng)柸聽(tīng)?Gauss Seidel)迭代法迭代法.bLDxULDxkk1)(1)1()()( 其其Gauss Seidel迭代矩陣迭代矩陣為為BG = (D- -L)- -1U于是高斯于是高斯塞德?tīng)柕蓪?xiě)為塞德?tīng)柕蓪?xiě)為矩陣形式矩陣形式)., 2 , 1()(11)(11)1()1(nibxaxaaxinijkjijijkjijiiki 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)

17、上頁(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)迭代法迭代法.其中其中BG=I- -(D- -L)- -1A= (D- -L)- -1U, f=(D- -L)- -1b. 稱矩陣稱矩陣BG=(D- -L)- -1U為解為解Ax=b的的高斯高斯塞德?tīng)柸聽(tīng)柕ǖ牡仃嚪ǖ牡仃?kkGxxB xfk(0)(1)( )()(2.7)(0,1,),初初始始向向量量，上頁(yè)上頁(yè)上

18、頁(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)為)., 2 , 1(1)(11)1()1(nixaxabxanijkjijijkjijikiii 即當(dāng)即當(dāng)aii 0時(shí)，有時(shí)，有(與前面一樣的式子與前面一樣的式子)., 2 , 1()(11)(11)1()1(nixaxabaxnijkjijijkjijiiiki 或或,)()1()1(bUxLxDxkkk 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)于是，解于是，解Ax=b的的高斯高斯塞德?tīng)柸聽(tīng)柕ǖ挠?jì)算公式為迭代法的計(jì)算公式為

19、)8 . 2()., 1 , 0(), 2 , 1(,/ )(),(),(1)(11)1()1()0()0(1)0( 表表示示迭迭代代次次數(shù)數(shù)初初始始向向量量kniaxaxabxxxxiinijkjijijkjijikiTn上頁(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). 可看作可

20、看作雅可比迭代法雅可比迭代法的一種改的一種改進(jìn)進(jìn). 由由(2.8)可知，可知，高斯高斯塞德?tīng)柕饺聽(tīng)柕矫康淮蚊康淮沃恍栌?jì)算一次矩陣與向量的乘法只需計(jì)算一次矩陣與向量的乘法.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例例2 用用高斯高斯塞德?tīng)柕ㄈ聽(tīng)柕ń饫饫?的方程組的方程組(1.2).)., 2 , 1 , 0(.12/ )3636(,11/ )433(, 8/ )2320()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1 kxxxxxxxxxkkkkkkkkk 解解 用用高斯高斯塞德?tīng)柕剑喝聽(tīng)柕剑喝∪(0)=(0, 0,

21、 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è) 由此例可知，用由此例可知，用高斯高斯塞德?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ì)的滿足一定條件

22、時(shí)才是對(duì)的. 上頁(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(1kkkkkkkkkxxxxxxxxx 例例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.1

23、64481.0999981.1999991.3上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)3.4.3 松弛迭代法松弛迭代法(SOR方法方法) 我們?nèi)∥覀內(nèi)?0為為松弛因子松弛因子，建立迭代格式如下，建立迭代格式如下).,2,1(),()1 (,/ )()()1()()1()()1(1)(11)1()1(nixxxxxxaxaxabxkikikikikikiiinijkjijijkjijiki 即即./ )()(11)1()()1(iinijkjijijkjijikikiaxaxabxx 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)或改寫(xiě)為或改寫(xiě)為.)()1()(1)(1)1(bLDxU

24、DLDxkk 其其逐次超逐次超松弛迭代矩陣松弛迭代矩陣為為11L( DL) ()DU . 逐次超松弛法逐次超松弛法可寫(xiě)為可寫(xiě)為矩陣形式矩陣形式./ )()(11)1()()1(iinijkjijijkjijikikiaxaxabxx , 2 , 1 , 0), 2 , 1(./ )()1 ()(11)1()()1( kniaxaxabxxiinijkjijijkjijikiki 稱為稱為逐次超逐次超松弛迭代法松弛迭代法，簡(jiǎn)稱，簡(jiǎn)稱SOR方法方法. 顯然，顯然， =1就是就是GaussSeidel 迭代法迭代法.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 下面用矩陣方法推導(dǎo)，選取分裂矩陣下

25、面用矩陣方法推導(dǎo)，選取分裂矩陣M為帶參為帶參數(shù)的下三角矩陣數(shù)的下三角矩陣從而得到解從而得到解Ax=b的的逐次超松弛迭代法逐次超松弛迭代法 (Successive Over Relaxation Method，簡(jiǎn)稱，簡(jiǎn)稱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方法方法

26、為為.其中其中.)(,)1()(11bLDfUDLDL 下面給出解下面給出解Ax=b的的SOR方法方法的分量計(jì)算公式的分量計(jì)算公式. 記記,),()()()(1)(Tknkikkxxxx 由由(2.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( 為為松松弛弛因因子子 kniax

27、axabxxxxxiinijkjijijkjijikikiTn上頁(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í)，稱為時(shí)，稱為超松弛法超松弛法；當(dāng)；當(dāng) 1時(shí)，稱為時(shí)，稱為低低松弛法松弛法.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)3.4.4 迭代法的收斂性迭代法的收斂性一階定常迭代法的基本定理一階定常迭代法的基本定理其中，其中，A=(aij)Rnn為非奇異矩陣，記為非奇異矩

28、陣，記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)生的向量序列x(k)收斂到收斂到x*. 引進(jìn)引進(jìn)誤差向量誤差向量)., 2 , 1 , 0()()( kxxkk 由由(3.3)式減式減(3.2)得到得到誤差向量的遞

29、推公式誤差向量的遞推公式)., 2 , 1 , 0(,)0()()()1( kBBkkkk 由由6.1節(jié)可知，研究迭代法節(jié)可知，研究迭代法(3.3)收斂性問(wèn)題就是要研收斂性問(wèn)題就是要研究迭代矩陣究迭代矩陣B滿足什么條件時(shí)，有滿足什么條件時(shí)，有.).)(0 kBk零零矩矩陣陣上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定理定理3 設(shè)設(shè)B=(bij)Rnn，則，則limBk=0 (k)(零零矩陣矩陣)的充分必要條件是矩陣的充分必要條件是矩陣B的譜半徑的譜半徑 (B)1.證明證明 由矩陣由矩陣B的的若當(dāng)標(biāo)準(zhǔn)形若當(dāng)標(biāo)準(zhǔn)形,存在非奇異矩陣存在非奇異矩陣P使使,211JJJJBPPr 其中其中若當(dāng)若

30、當(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的情況的情況. 引進(jìn)記號(hào)引進(jìn)記號(hào)).(000,ittktntRktIE 101 ,01 ,1 ,)()()(tjjtjkij

31、kkjjtjkijkktikiECECEIJ 上頁(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è)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定理定理4(迭代法基本定理迭代法基本定理) 設(shè)有方程組設(shè)有方程組 x=Bx+f. (3.4) 及一階定

32、常迭代法及一階定常迭代法 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)有唯一解，記為有唯一解，記為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

33、 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知知再由定理再由定理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) 迭代法迭代

34、法x(k+1)=Bx(k)+f 收斂收斂 (B)1. 推論推論 設(shè)設(shè)Ax=b，其中，其中A=D- -L- -U為非奇異矩陣且為非奇異矩陣且D非奇異矩陣，則有非奇異矩陣，則有 (1) Jacobi迭代法迭代法收斂收斂 (BJ)1, 其中其中BJ =D- -1(L+U). . (2) G- -S迭代法迭代法收斂收斂 (BG)1, 其中其中BG =(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)

35、的收斂性的收斂性. 解解 因?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. 0321 即即 (J)1. ,62, 1 這說(shuō)明用迭代法解此方程組這說(shuō)明用迭代法解此方程組不收斂不收斂. 迭代法的基本定理在理論上是重要的，根據(jù)譜迭代法的基本定理在理論上是重要的，根據(jù)譜半徑的性質(zhì)半徑的性質(zhì) (B)|B|，下面利用矩陣，下面利用矩陣B的范數(shù)建立的范數(shù)建立判別迭代法收

36、斂的充分條件判別迭代法收斂的充分條件.上頁(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|=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è)下

37、頁(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*- -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)|,上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè).111)

38、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è)6.3.2 關(guān)于解某些特殊方程組迭代法的收斂性關(guān)于解某些特殊方程組迭代法的收斂性 在科學(xué)及工程計(jì)算中，要求解方程組在科學(xué)及工程計(jì)算中，要求解方程組Ax=b，其，其矩陣矩陣A常常具有某些特性常常具有某些特性. 例如，例如，A具有對(duì)角占優(yōu)性具有對(duì)角占優(yōu)性質(zhì)或質(zhì)或A為不可約陣，或?yàn)椴豢杉s陣，或A是對(duì)稱正定陣，下面討論用是對(duì)稱正定陣，下面討論用基

39、本迭代法解這些方程組的收斂性基本迭代法解這些方程組的收斂性.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定義定義3(對(duì)角占優(yōu)陣對(duì)角占優(yōu)陣) 設(shè)設(shè)A=(aij)nn . (1) 如果如果A的元素滿足的元素滿足)., 2 , 1(1niaanijjijii 稱稱A為為嚴(yán)格嚴(yán)格(按行按行)對(duì)角占優(yōu)陣對(duì)角占優(yōu)陣. (2) 如果如果A的元素滿足的元素滿足)., 2 , 1(1niaanijjijii 且上式至少有一個(gè)不等式成立，稱且上式至少有一個(gè)不等式成立，稱A為為弱弱(按行按行)對(duì)角對(duì)角占優(yōu)陣占優(yōu)陣.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定義定義4(可約與不可約矩陣可約與不可約矩陣)

40、 設(shè)設(shè)A=(aij)nn (n2)，如果存在置換陣如果存在置換陣P使使)6 . 3(,0221211 AAAAPPT其中其中A11為為r階方陣，階方陣，A22為為n- -r階方陣階方陣(1rn)，則稱，則稱A為為可約矩陣可約矩陣. 否則，如果不存在這樣置換陣否則，如果不存在這樣置換陣P使使(3.6)式成立，則稱式成立，則稱A為為不可約矩陣不可約矩陣. A為可約矩陣意即為可約矩陣意即A可經(jīng)過(guò)若干行列重排化為可經(jīng)過(guò)若干行列重排化為(3.6)或或Ax=b可化為兩個(gè)低階方程組求解可化為兩個(gè)低階方程組求解(如果如果A經(jīng)過(guò)兩行經(jīng)過(guò)兩行交換的同時(shí)進(jìn)行相應(yīng)兩列的交換，稱對(duì)交換的同時(shí)進(jìn)行相應(yīng)兩列的交換，稱對(duì)A進(jìn)

41、行一次行進(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所有元素都非零，則所有元素都非零，則A為不可約陣為不可約陣.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例例7 設(shè)有矩陣設(shè)有矩陣),(.4110

42、140110410114,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)矩陣證明此定理證明此定理. 采用反證法，如果采用反證法，如果det(A)=0，則，則Ax=b有非零解，記有非零解，記為為x=(x1, x2,xn)T，則，則 .

43、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 迭代法迭代法均收斂均收斂.(2) A為弱對(duì)角為弱對(duì)角占優(yōu)陣，且占優(yōu)陣，且A為不可約矩陣為不可約矩陣, 則則解解Ax=b的的J

44、acobi迭代法迭代法, Gauss- -Seidel 迭代法迭代法均收斂均收斂. 證明證明 只證只證(1)，(2)作為練習(xí)作為練習(xí).因?yàn)橐驗(yàn)锳是嚴(yán)格對(duì)角占優(yōu)陣，所以是嚴(yán)格對(duì)角占優(yōu)陣，所以aii0(i=1,n).)(1ULDJ 0002122222211111112nnnnnnnnaaaaaaaaaaaa則則|J| 1，所以，所以 Jacobi 迭代法迭代法收斂收斂.Jacobi迭代陣迭代陣上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè))(det)det(1ULDIGI . 0)(det)det(1 ULDLD )(. 0)(det ULD 下面證明下面證明GaussSeidel 迭代法迭代

45、法收斂收斂.由由G=(D- -L)- -1U，得，得下面證明下面證明| |1. 若不然若不然, 即即| | 1, 則則. ), 2 , 1(|111 ijnijijijijijiiniaaaa 由于由于. 0)det(1 LD所以所以上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)即矩陣即矩陣 ULD)( 是嚴(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è)).(),(),(),(ibayLyLyyyyLT 所以所以| |1, 從而從而 (G)1, 故故Gauss- -S

46、eidel迭代法迭代法收斂收斂.1)(|22222 baba 令令 - -(Ly, y)=a+ib，則由復(fù)向量?jī)?nèi)積的性質(zhì)有，則由復(fù)向量?jī)?nèi)積的性質(zhì)有.)(),(),(),(ibaibayLyyDyyyLT 下面研究對(duì)于解方程組下面研究對(duì)于解方程組Ax=b的的SOR方法方法中松弛中松弛因子因子在什么范圍內(nèi)取值，在什么范圍內(nèi)取值，SOR方法方法才可能收斂才可能收斂.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)定理定理8(SOR方法收斂的必要條件方法收斂的必要條件) 設(shè)解設(shè)解方程組方程組 Ax=b的的SOR迭代法迭代法收斂，則收斂，則0 2. 1)1 ()1 ()()1det()det()det(

47、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.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)定理定理8說(shuō)明解說(shuō)明解Ax=b的的SOR迭代法迭代法，只有在，只有在(0, 2)范范圍內(nèi)取松弛因子圍內(nèi)取松弛因子 ，才可能收斂，才可能收斂.定理定理9(SOR方法收斂的充分條件方法收

48、斂的充分條件) 設(shè)有設(shè)有方程組方程組 Ax=b，如果：，如果：(1) A為對(duì)稱為對(duì)稱正定矩陣正定矩陣，A=D- -L- -LT;(2) 0 2.則解則解方程組方程組 Ax=b的的SOR迭代法迭代法收斂收斂.證證 在上述假定下，設(shè)迭代矩陣在上述假定下，設(shè)迭代矩陣L 的任一特征值的任一特征值為為 ，只要證明，只要證明| |0. 令令 - -(Ly, y)=a+ib，則由復(fù)向量?jī)?nèi)積的性質(zhì)有，則由復(fù)向量?jī)?nèi)積的性質(zhì)有).(),(),(),(ibayLyLyyyyLT 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè),2),)(),(0ayyLLDyAyT 因?yàn)橐驗(yàn)?)()(biabia ,),(),()

49、,(),(),(yLyyDyyyLyDyyDyT .)()(2222222baba 當(dāng)當(dāng)0 2時(shí)，有時(shí)，有(分子減分母分子減分母). 0) 2)(2()()(22 aaa即即L 的任一特征值滿足的任一特征值滿足| |1, 故故SOR迭代法迭代法收斂收斂.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)由定理由定理3證明中可知，如果證明中可知，如果 (B)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)，上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)故故.)0()( kkB 現(xiàn)設(shè)現(xiàn)設(shè)B為對(duì)稱矩陣，則有為對(duì)稱矩陣，則有.)(2)0(2)0(22)( kkkBB 下面確定使初始誤差縮小下面確定使初始誤差縮小10-s所需的迭代次數(shù)所需的迭代次數(shù), 即使即使.10)(skB 取對(duì)數(shù)，得到所需最少迭代次數(shù)為取對(duì)數(shù)，得到所需最少迭代次數(shù)為.)(ln10lnBsk