數(shù)值分析課件ch06方程組迭代法

1、1第六章線(xiàn)性方程組的數(shù)值解法-迭代法2q 直接法得到的解是理論上準(zhǔn)確的，但是計(jì)算量都是直接法得到的解是理論上準(zhǔn)確的，但是計(jì)算量都是 n3 n3數(shù)量級(jí)，存儲(chǔ)量為數(shù)量級(jí)，存儲(chǔ)量為n2n2量級(jí)，這在量級(jí)，這在n n比較小的時(shí)候比較小的時(shí)候 還比較合適（還比較合適（n400n400）q 實(shí)際問(wèn)題中，往往方程組的階數(shù)很高，而且這些矩實(shí)際問(wèn)題中，往往方程組的階數(shù)很高，而且這些矩 陣陣( (系數(shù)矩陣系數(shù)矩陣) )往往是含有大量的往往是含有大量的0 0元素（元素（稀疏矩陣稀疏矩陣 方程組方程組）。直接法運(yùn)算量將會(huì)很大并且大量占用計(jì)）。直接法運(yùn)算量將會(huì)很大并且大量占用計(jì) 算機(jī)資源。算機(jī)資源。q 因此有必要引入一

2、類(lèi)新的方法：因此有必要引入一類(lèi)新的方法：迭代法迭代法。 引言引言3q q 迭代法的基本思想迭代法的基本思想 迭代法是解線(xiàn)性方程組的一種重要的實(shí)用方迭代法是解線(xiàn)性方程組的一種重要的實(shí)用方 法，特別適用于求解在實(shí)際中大量出現(xiàn)的，系法，特別適用于求解在實(shí)際中大量出現(xiàn)的，系 數(shù)矩陣為稀疏陣的大型線(xiàn)性方程組。數(shù)矩陣為稀疏陣的大型線(xiàn)性方程組。 迭代法的基本思想是去構(gòu)成一個(gè)向量序列迭代法的基本思想是去構(gòu)成一個(gè)向量序列 x x( (k k) ) ， 使其收斂至某個(gè)極限向量使其收斂至某個(gè)極限向量x x* * ，并且，并且x x* *就是要求解就是要求解 的方程組：的方程組：Ax = b Ax = b 的準(zhǔn)確解。

3、的準(zhǔn)確解。4迭代法的主要步驟迭代法的主要步驟The process of iterative methodThe process of iterative methodq 解線(xiàn)性方程組迭代法的主要步驟是解線(xiàn)性方程組迭代法的主要步驟是: :l 把線(xiàn)性方程組把線(xiàn)性方程組Ax=bAx=b化成如下形式的同解方程組化成如下形式的同解方程組l x=Bx+f 給出初始向量給出初始向量 , ,按按迭迭 代公式代公式 x(k+1)=Bx(k)+f (k=0,1,2,) 進(jìn)行計(jì)算進(jìn)行計(jì)算, ,其中其中k k 表迭代次數(shù)表迭代次數(shù)。 nTnRxxxX002)0(10,5 如果按上述迭代公式所得到的向量序列如果按上述

4、迭代公式所得到的向量序列 x x( (k k) ) 收收斂于某個(gè)向量斂于某個(gè)向量x x* * , ,則則x x* * 就是方程組就是方程組 Ax =b Ax =b 的解，并稱(chēng)的解，并稱(chēng)此迭代法此迭代法收斂收斂。否則，就叫不收斂或發(fā)散。否則，就叫不收斂或發(fā)散。 迭代公式中的矩陣迭代公式中的矩陣B B ，稱(chēng)為，稱(chēng)為迭代矩陣迭代矩陣。 q 問(wèn)題問(wèn)題 l 迭代公式的建立迭代公式的建立l 迭代公式的收斂性迭代公式的收斂性l 收斂速度收斂速度l 誤差估計(jì)誤差估計(jì)6基本迭代公式基本迭代公式,0,AMNM把矩陣把矩陣 A A 分裂為分裂為()AxbMN xb則則11xMNxM b.xBxf記記 B = M-

5、-1N， f = M- -1b， 則則注注：選取選取M M陣，就得到解陣，就得到解 Ax=b Ax=b 的各種迭代法的各種迭代法. .7 本章重點(diǎn)介紹三個(gè)迭代法，即：本章重點(diǎn)介紹三個(gè)迭代法，即： l JacobiJacobi迭代法迭代法l Gauss-SeidelGauss-Seidel 迭代法迭代法l 超松弛迭代法（超松弛迭代法（SORSOR法）法）8Jacobi迭代法迭代法112213 31111221 123 322221 122,1111()1()1()nnnnnnnn nnnnxa xa xa xbaxa xa xa xbaxa xa xaxba由方程組由方程組AXAX= =b b的

6、第的第i i個(gè)方程解出個(gè)方程解出ix(1,2, )in得到一個(gè)同解方程組得到一個(gè)同解方程組q 9獲得相應(yīng)的迭代公式獲得相應(yīng)的迭代公式(1)( )( )( )11221331111(1)( )( )( )221 12332222(1)( )( )( )1 122,111()1()1()kkkknnkkkknnkkkknnnn nnnnnxa xa xa xbaxa xa xa xbaxa xa xaxbaJacobi迭代法迭代法取初始向量取初始向量(0)(0)(0)(0)12(,)TnXxxx稱(chēng)上式為雅可比迭稱(chēng)上式為雅可比迭JacobiJacobi迭代公式。迭代公式。10Jacobi迭代法的矩陣

7、形式迭代法的矩陣形式若記若記q 000000211221212211nnnnnnaaaUaaaLaaaD則有則有 A=D-L-U A=D-L-U 成立，矩陣形式為成立，矩陣形式為 Dx =（L+U)x +b 等式兩邊乘以等式兩邊乘以D D- -1 1，得，得 x= D-1（L+U）x+ D-1b 由此得到迭代公式由此得到迭代公式( The iterative scheme is :) x（k+1）= D-1（L+U）x（k）+ D-1b 11q 迭代矩陣迭代矩陣 Jacobi迭代法的特點(diǎn)迭代法的特點(diǎn)1()JBDLU1()JBDLUq 每迭代一次主要是計(jì)算一次矩陣乘向量每迭代一次主要是計(jì)算一次矩

8、陣乘向量 所以計(jì)算量為所以計(jì)算量為n n平方數(shù)量級(jí)。平方數(shù)量級(jí)。 )(kJxBq 計(jì)算過(guò)程中涉及到的中間變量計(jì)算過(guò)程中涉及到的中間變量 及及 , ,需要需要 兩組工作單元兩組工作單元x(n),y(n)x(n),y(n)來(lái)存儲(chǔ)來(lái)存儲(chǔ). .q 計(jì)算過(guò)程中計(jì)算過(guò)程中, ,初始數(shù)據(jù)初始數(shù)據(jù)A A始終不變始終不變; ; )(kx)1( kx12問(wèn)題：如何判斷迭代終止？q 定理定理若迭代矩陣若迭代矩陣B B滿(mǎn)足滿(mǎn)足|B|B|1 1 則則)1()()(*1kkkXXBBXXq 此定理此定理給出了一個(gè)停止迭代的判別準(zhǔn)則。給出了一個(gè)停止迭代的判別準(zhǔn)則。)1()(kkXX13q 輸入最大迭代次數(shù)輸入最大迭代次數(shù)N

9、 N，控制誤差，控制誤差以及迭代初值以及迭代初值 x=（x1，x2 ，xn）輸出近似值輸出近似值y=（y1，y2， ，yn）Jacobi迭代法的計(jì)算步驟迭代法的計(jì)算步驟l k=1；l l 如果如果|y-x| N N，算法失敗。如果，算法失敗。如果 k=1.0e6 x0= y; y=B*x0+f; n = n +1;end17高斯高斯塞德?tīng)柸聽(tīng)? (Gauss-Seidel) )迭代法迭代法 q q 研究雅可比迭代法，我們發(fā)現(xiàn)在逐個(gè)求 的分量時(shí)， 當(dāng)計(jì)算到 的分量時(shí)，當(dāng)計(jì)算到 都已 經(jīng)求得.設(shè)想一旦新分量代替舊分量，可能會(huì)加速收斂。 例如例如 (1)kX(1)kix(1)(1)11,kkixx

10、(1)( )( )( )13112121311111111(1)(1)( )( )23221213222222222kkkknnkkkknnaaabxxxxaaaaaaabxxxxaaaa 18)(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk )(13)(3)(434)1(232)1(13133)1(3bxaxaxaxaaxknnkkkk )(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax Gauss-

11、Seidel迭代法分量形式迭代法分量形式 19Gauss-Seidel迭代的矩陣形式迭代的矩陣形式bLDUxLDxbLDUxLDxbUxxLDbxULDbAxkk1)(1)1(11)()()()()()(作作 A 的另一個(gè)分裂：的另一個(gè)分裂：()ADLUq 迭代矩陣迭代矩陣 1GBDLU20例子例子1231231231023210152510 xxxxxxxxx(1)( )( )123(1)(1)( )213(1)(1)(1)3121(23)101(215)101(210)5kkkkkkkkkxxxxxxxxx解：解：相應(yīng)的高斯相應(yīng)的高斯- -賽德?tīng)柕綖橘惖聽(tīng)柕綖?1取迭代初值取迭

12、代初值(0)(0)(0)(0)123(,)(0,0,0)TTXxxx按此迭代公式進(jìn)行迭代，計(jì)算結(jié)果為按此迭代公式進(jìn)行迭代，計(jì)算結(jié)果為k( )1kx( )2kx( )3kx01234500.30.88040.98430.99780.999701.561.94451.99231.99891.999902.6842.95392.99382.99912.999922迭代法的收斂性迭代法的收斂性 迭代法的收斂性迭代法的收斂性，是指方程組是指方程組bAx q 從任意初始向量從任意初始向量X X(0)(0)出發(fā)，由迭代算法出發(fā)，由迭代算法fBxxkk)()1(算出向量序列算出向量序列,)1()()2()1(

13、kkxxxx隨著隨著k k的增加而趨向于解向量的增加而趨向于解向量X X * *。q 記各次記各次誤差向量誤差向量)()1(1)0(0kkXXXXXX 23迭代法的收斂性迭代法的收斂性 q 迭代法的收斂性等價(jià)于誤差向量序列迭代法的收斂性等價(jià)于誤差向量序列,10k 隨著隨著k k的增加而的增加而趨向于零趨向于零。q 由由 x(k+1)=Bx(k)+f 及及 x*=Bx*+fk+1 =X(k+1)-X*=B（X(k)-X*） = = B k+1（X(0)-X)=B k+1 0 可推知可推知q x x( (k k) ) 的收斂性的收斂性 B Bk k 0 0 ( (k k ) ) 24迭代法的收斂性

14、定理迭代法的收斂性定理 q 定理定理 (充要條件判別法充要條件判別法)給定方程組給定方程組 X=BX+f則迭代公式則迭代公式(1)( )kkXBXf對(duì)任意初始向量對(duì)任意初始向量 ，都收斂的充要條件為，都收斂的充要條件為(0)nXR( )1B性質(zhì)有關(guān)。性質(zhì)有關(guān)。的的代矩陣代矩陣的取值無(wú)關(guān)，而只與迭的取值無(wú)關(guān)，而只與迭和和與與法收斂與否法收斂與否表明，線(xiàn)性方程組迭代表明，線(xiàn)性方程組迭代定理定理 1 . 3 )0(BfXq 25q 迭代法的收斂性定理迭代法的收斂性定理 定理定理 ( (充分條件判別法充分條件判別法) )給定方程組給定方程組 X=BX+f如果如果 ，則迭代公式，則迭代公式1B 1. 對(duì)

15、任意初始向量對(duì)任意初始向量 收斂。收斂。(0)nXR(1)( )kkXBXf2. 有如下估計(jì)有如下估計(jì)( )*( )(1)1,2,3,1kkkBXXXXkB26證明證明 111*( *)( *)kkkkkxxB xxB xxxx111| *| | |(| *| |)kkkkx xBx xxx11| *|1 |kkkBxxxxB27注注 q 由于此估計(jì)式，在實(shí)際計(jì)算中，用 | | X X (k+1) - (k+1) - X X (k) | (k) | 作為迭代終止條件是合理的。 q ( )(1)(0)*1kkBXXXXB進(jìn)一步可以推知：由于( (B B) ) B B11，B越小，說(shuō)明(B) 越小

16、，序列 X (k)收斂越快。28收斂速度收斂速度下面我們給出收斂速度的概念下面我們給出收斂速度的概念： 定義定義 R R( (B B)= -)= -lnln( (B B) )，稱(chēng)為迭代法的漸進(jìn)，稱(chēng)為迭代法的漸進(jìn) 收斂速度。收斂速度。q 由于由于Gauss-Seidel迭代法逐次用計(jì)算出來(lái)的新迭代法逐次用計(jì)算出來(lái)的新值代替舊值，所以在收斂的條件下，它要比值代替舊值，所以在收斂的條件下，它要比Jacobi迭代法收斂速度快。迭代法收斂速度快。29Jacobi Jacobi 和和Gauss-SeidelGauss-Seidel的收斂性的收斂性1.() 1 ()1 ;JGAXbJacobi Seidel

17、BB解解線(xiàn)線(xiàn)性性方方程程組組的的迭迭代代法法收收斂斂的的充充要要條條件件是是2. 1 1 JGAXbJacobi SeidelBB解解線(xiàn)線(xiàn)性性方方程程組組的的迭迭代代法法收收斂斂的的充充分分條條件件是是。 ULDBULDBGJ11, 其中其中301311211111123221222222313233333331230000nnJnnnnnnnnnnaaaaaaaaaaaaBaaaaaaaaaaaa注注 31525110101021011020JB對(duì)于前面的例子由迭代矩陣的特征方程由迭代矩陣的特征方程05211102121012311717,51010 因而雅可比迭代公式是收斂的。因而雅可比迭

18、代公式是收斂的。32注注 的特征值。因而可由此式求解等價(jià)于因此由于因?yàn)椋嚎杀荛_(kāi)求逆矩陣的特征值法迭代陣求BULDBILDULDLDULDLDLDBILDULDB0)(det(0)det(0)det()(det()det()()()det()det()()( S-G 11111133直接用矩陣直接用矩陣A A判定斂散性判定斂散性q q 定義定義 如果矩陣如果矩陣A A滿(mǎn)足條件滿(mǎn)足條件(1,2, )(2)iiijj iaain則稱(chēng)則稱(chēng)A A是是嚴(yán)格對(duì)角占優(yōu)陣嚴(yán)格對(duì)角占優(yōu)陣(strictly diagonally dominant (strictly diagonally dominant matr

19、ix)matrix)；342100110114100141001410014BAA為按行按列為按行按列嚴(yán)格嚴(yán)格對(duì)角占優(yōu)陣；對(duì)角占優(yōu)陣；B為按行對(duì)角為按行對(duì)角占優(yōu)陣。占優(yōu)陣。實(shí)例實(shí)例(Example)(Example)35定理定理1 1 若若A A為為嚴(yán)格對(duì)角占優(yōu)陣嚴(yán)格對(duì)角占優(yōu)陣，則，則J Jacobiacobi 迭代法迭代法和和 G-SG-S迭代法迭代法收斂。收斂。 定理定理2 2 若若A A為為對(duì)稱(chēng)正定陣對(duì)稱(chēng)正定陣，則，則G-SG-S迭代法收斂迭代法收斂。 相關(guān)定理相關(guān)定理q q 36定理1的證明證 首先證明首先證明JacobiJacobi 迭代的收斂性。由迭代的收斂性。由nnnJnnnnn

20、nnnJabababfaaaaaaaaaaaaULDB22211121222222111111121,000)(易求ijnjiiijniJaaB,11max 由嚴(yán)格對(duì)角占優(yōu)定義，得由嚴(yán)格對(duì)角占優(yōu)定義，得 B BJ J 1, = detdet( ( ( (D-LD-L)-)-U U)=0 )=0 38 我們通過(guò)我們通過(guò)A A的嚴(yán)格對(duì)角占優(yōu)性質(zhì)去證明的嚴(yán)格對(duì)角占優(yōu)性質(zhì)去證明detdet( ( ( (D-D-L L)-)-U U)=0)=0的根的根 有性質(zhì)有性質(zhì) | | |1 |1。用。用反證法反證法：假設(shè)：假設(shè)| | |1 |1，且由于，且由于A A的嚴(yán)格對(duì)角占優(yōu)性質(zhì)，有的嚴(yán)格對(duì)角占優(yōu)性質(zhì)，有 n

21、iaaaanijijijijnijjijii, 2 , 1,111, 1nnnnaaaaaaaaaULD21112221111111)(39是嚴(yán)格對(duì)角占優(yōu)陣，所以它是非奇異的，即det(D-L)-U) 0與特征值滿(mǎn)足det(D-L)-U) =0 矛盾。故 | |1即(BG) 11 時(shí)，稱(chēng)為時(shí)，稱(chēng)為超松弛算法超松弛算法，當(dāng)，當(dāng)11 時(shí)，時(shí)，稱(chēng)為稱(chēng)為亞松弛算法亞松弛算法。 目前，還沒(méi)有自動(dòng)選擇因子的一般方法，實(shí)目前，還沒(méi)有自動(dòng)選擇因子的一般方法，實(shí)際計(jì)算中，通常?。H計(jì)算中，通常?。? 0，2 2）區(qū)間內(nèi)幾個(gè)不同的）區(qū)間內(nèi)幾個(gè)不同的值進(jìn)行試算，通過(guò)比較后，確定比較理想的松弛值進(jìn)行試算，通過(guò)比較后，

22、確定比較理想的松弛因子因子。 46例例 用用SORSOR法求解線(xiàn)性方程組法求解線(xiàn)性方程組 243024410143034321xxx 取=1 ，即Gauss-Seidel迭代： 625. 05 . 725. 075. 0675. 0)1(2)1(3)(3)1(1)1(2)(2)1(1kkkkkkkxxxxxxx 取=1.25 ，即SOR迭代法： 5 . 725. 03125. 075. 93125. 025. 09375. 05 . 79375. 025. 0)(3)1(2)1(3)(3)(2)1(1)1(2)(2)(1)1(1kkkkkkkkkkxxxxxxxxxx47例例 迭代結(jié)果見(jiàn)表3.

23、3。 表3.3 Gauss-Seidel迭代法與SOR迭代法比較 Gauss-Seidel迭代法SOR迭代法(=1.25)kx1x2x3x1x2x301.00000001.00000001.00000001.00000001.00000001.000000015.25000003.1825000-5.04687506.31250003.9195313-6.650146523.14062503.8828125-5.02929692.62231453.9585266-4.600423833.08789063.9267587-5.01831053.13330274.0402646-5.0966863

24、43.05493163.9542236-5.01144102.95705124.0074838-4.973489753.03433233.9713898-5.00715263.00372114.0029250-5.005713563.02145773.9821186-5.00447032.99632764.0009262-4.998282273.01341103.9888241-5.00279403.00004984.0002586-5.000348648 迭代法若要精確到七位小數(shù)，迭代法若要精確到七位小數(shù)，u Gauss-SeidelGauss-Seidel迭代法需要迭代法需要3434次迭代

25、；次迭代；u 而用而用SORSOR迭代法迭代法( (=1.25)=1.25)，只需要，只需要1414次迭代。次迭代。 可見(jiàn)，若選好參數(shù)可見(jiàn)，若選好參數(shù)，SORSOR迭代法收斂速度會(huì)迭代法收斂速度會(huì)很快。很快。q 49SOR迭代的矩陣形式：迭代的矩陣形式：inijkjijijkjijiikikibxaxaaxx)(11)1()()1(X(k+1) =(1-)X(k)+D-1(b+LX(k+1)+UX(k)DX(k+1) =(1-)DX(k)+(b+LX(k+1)+UX(k)）(D-L)X（k+1） =(1-)D+U X(k)+b解得解得 X(k+1)=(D-L)-1(1-)D+UX(k)+(D-L)-1b 記記 B=(D-L)-1 (1-)D+U 稱(chēng)為稱(chēng)為SORSOR法迭代矩陣法迭代矩陣。 50SOR迭代法的收斂性迭代法的收斂性q (1)SOR法收斂的充要條件是法收斂的充要條件是(B)1。(2)