第2章 線性方程組的迭代法

1、科大研究生學(xué)位課程1第第2 2章章 解線性方程組的迭代法解線性方程組的迭代法n元線性方程組nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111 （2.1） 或 Ax=b思思路路與解與解 f (x)=0 的不動(dòng)點(diǎn)迭代相似的不動(dòng)點(diǎn)迭代相似 ,將將Ax=b等價(jià)改寫為等價(jià)改寫為x=Mx+f,建立迭代建立迭代x(k+1)=Mx(k)+f,從從初值初值x(0)出發(fā)，得到序列出發(fā)，得到序列x(k).研究研究 內(nèi)容：內(nèi)容： 如何建立迭代格式？如何建立迭代格式？ 收斂速度？收斂速度？ 向量序列的收斂條件？向量序列的收斂條件？ 誤差估計(jì)？誤差估計(jì)？ （2.2）

2、科大研究生學(xué)位課程22.1 迭代法的一般理論 為了研究線性方程組近似解的誤差估計(jì)和迭代法的收斂性，我們需要對(duì)Rn(n維向量空間)中的向量或Rnxn中矩陣的“大小”引入一種度量，向量和矩陣的范數(shù)。 在一維數(shù)軸上，實(shí)軸上任意一點(diǎn)x到原點(diǎn)的距離用|x|表示。而任意兩點(diǎn)x1，x2之間距離用| x1-x2 |表示。科大研究生學(xué)位課程3向量和矩陣的范數(shù) 而在二維平面上，平面上任意一點(diǎn)P(x,y)到原點(diǎn)的距離用 表示。而平面上任意兩點(diǎn)P1(x1,y1),P2(x2,y2)的距離用 表示。 推廣到n維空間，則稱為向量范數(shù)。|22OPyx22122121)()(|yyxxPP科大研究生學(xué)位課程42.1.1 2.

3、1.1 向量和矩陣的范數(shù)向量和矩陣的范數(shù)向量的范數(shù)向量的范數(shù) 定義定義2.2 2.2 設(shè)是向量空間Rn上的實(shí)值函數(shù), 且滿足條件: (1)非負(fù)性非負(fù)性: : 對(duì)任何向量xRn ,x0 ,且x=0當(dāng) 且僅當(dāng)x=0 0 (2)齊次性齊次性: : 對(duì)任何向量x Rn 和實(shí)數(shù) , x=| |x (3)三角不等式三角不等式: : 對(duì)任何向量x ,yRn x+yx+y則稱為空間Rn上的范數(shù),x為向量x的范數(shù). 科大研究生學(xué)位課程5 記x=(x1,x2,xn)T, 常用的向量范數(shù)有: 向量的向量的1-1-范數(shù)范數(shù):x1=|x1|+|x2|+|xn| 向量的向量的2-2-范數(shù)范數(shù):x2= 22221nxxx

4、向量的向量的 - -范數(shù)范數(shù):x= |max1inix 例例 設(shè)向量x=(2,-4,3,1)T, 求向量范數(shù)xp ,p=1,2, . . 解解 由定義x1=10 , x2= 30,x=4 . 雖然不同范數(shù)的值可能不同，但它們間存在等價(jià)關(guān)系. 定理定理 (范數(shù)的等價(jià)性范數(shù)的等價(jià)性) 對(duì)于 Rn 上的任何兩種范數(shù)和 ,存在正常數(shù)m,M,使得 m x x M x , xRn科大研究生學(xué)位課程6 常用的三種向量范數(shù)滿足如下等價(jià)關(guān)系 x x1 nx , xRnnRnxxxx,2nRnxxxx,212 定義定義 設(shè)向量序列,),()()(2)(1)(Tknkkkxxxx k=1,2,向量,),(*2*1*

5、Tnxxxx如果 0lim*)(xxkk則稱向量序列x(k)收斂于向量x*, 記作 )(,lim*)(*)(kkkkxxxx或易見, nixxikik, 2 , 1,*)(*)( xx科大研究生學(xué)位課程72.2.矩陣的范數(shù)矩陣的范數(shù) 定義定義2.3 2.3 設(shè)是以n階方陣為變量的實(shí)值函數(shù),且滿足條件: (1)非負(fù)性非負(fù)性: : A0 ,且A=0當(dāng)且僅當(dāng)A=0 0 (2)齊次性齊次性: : A=| |A, R (3)三角不等式三角不等式: :A+BA+B (4)相容性相容性: :ABAB則稱A為矩陣A的范數(shù). 記A=(aij) , 常用的矩陣范數(shù)有: 矩陣的矩陣的1-1-范數(shù)范數(shù):A1 niij

6、nja11max,也稱矩陣的列范數(shù)列范數(shù). . 矩陣的矩陣的2-2-范數(shù)范數(shù):A2 )(maxAAT,也稱為譜范數(shù)譜范數(shù). .科大研究生學(xué)位課程8 矩陣的矩陣的 - -范數(shù)范數(shù):A njijnia11max,也稱為行范數(shù)行范數(shù). . 矩陣的矩陣的F F- -范數(shù)范數(shù):AF njiija1,2例例 設(shè)矩陣3211A求矩陣A的范數(shù)Ap ,p=1,2, ,F. . 解解 A1=4 , A=5 , AF 151055532113121AAT010555令25515 ,25515,21得255152A所以科大研究生學(xué)位課程9 設(shè)是一種向量范數(shù), 則定義AxxAxAx0 x1maxmax 稱之為由向量范數(shù)

7、派生的矩陣算子范數(shù)矩陣算子范數(shù). 矩陣的算子范數(shù)滿足 AxAx, xRn把滿足上式的矩陣范數(shù)稱為與向量范數(shù)與向量范數(shù)相容相容的矩陣范數(shù)的矩陣范數(shù). . 對(duì)于p=1,2,矩陣范數(shù)Ap是由向量范數(shù)xp派生的矩陣算子范數(shù),所以Ap是與xp相容的矩陣范數(shù).但AF不是一種算子范數(shù),卻與x2是相容的. 設(shè)是一種算子范數(shù), 則1max xxII0 xnIF，但科大研究生學(xué)位課程10 矩陣的范數(shù)與矩陣的特征值之間也有密切的聯(lián)系. 設(shè)是矩陣A的特征值,x是對(duì)應(yīng)的特征向量,則有 Ax= x利用向量和矩陣范數(shù)的相容性, 則得 |x=x=AxAx 于是 |A 設(shè)n階矩陣A的n個(gè)特征值為1, 2, , n, 則稱 in

8、i1max)(A為矩陣A的譜半徑譜半徑. 對(duì)矩陣的任何一種相容范數(shù)都有 (A)A 另外, 0, 一種相容范數(shù), 使 A (A)+ 科大研究生學(xué)位課程11 任何兩種矩陣范數(shù)也具有等價(jià)性 m A A M A , ARnn 矩陣序列的收斂性也定義為矩陣序列的收斂性也定義為0limlim*)(*)(AAAAkkkk njiaaijkij,1 ,*)(。的充分必要條件是則設(shè)定理1)(0lim,AkAkRAnn科大研究生學(xué)位課程1212.3 :| 1,1 | ()|1|AIAIAA定理如果則為非奇異，且000det( -)0( -)00IAIA xxAxx證明：（反證法）若有非零解，即，使得0000|1|

9、 | |AxAxAxx而 | 1,A從而與假設(shè)矛盾-1( -)( -) IA IAI又11()()I IAA IAI11()()IAIA IA11|() | | |() |IAIAIA11| ()|1|IAA科大研究生學(xué)位課程13把n元線性方程組nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111 （2.1） 或 Ax=b改寫成等價(jià)的方程組 nnnnnnnnnnnfxmxmxmxfxmxmxmxfxmxmxmx2211222221212112121111 或 x=Mx+f2.1.2 迭代格式的構(gòu)造 （2.2） 科大研究生學(xué)位課程14由此建立方

10、程組的迭代格式 x(k+1)=Mx(k)+f , k=0,1,2, (2.5)其中M稱為迭代矩陣迭代矩陣。 對(duì)任意取定的初始向量x(0),由(2.5)式可逐次算出迭代向量x(k),k=1,2, 如果向量序列x(k) 收斂于x*,由(2.5)式可得 x*=Mx*+f 從而x*是方程組x=Mx+f 的解,也就是方程組Ax=b的解.對(duì)迭代格式(2.5),定義誤差向量 e(k)=x(k)-x*,則迭代法收斂就是e(k)0 0.由于 x(k+1)=Mx(k)+f k=0,1,2, x*=Mx*+f k=0,1,2,科大研究生學(xué)位課程15 x(k+1)=Mx(k)+f k=0,1,2, x*=Mx*+f

11、k=0,1,2,所以 e(k+1)=Me(k) , k=0,1,2,遞推可得 e(k)=Mke(0) , k=0,1,2,可見,當(dāng)k時(shí), e e(k)0 0 Mk O O. 對(duì)任意初始向量x(0),迭代法收斂(M)1.定理定理2.4證證: (必要性） 若(M)0,使得(M)+1.則由定理2.2MkMk (M)+)k 0.若Mk0,k(M)=(Mk)Mk0,所以(M)1.科大研究生學(xué)位課程16 若若M1,則對(duì)任意x(0),迭代法收斂,而且 定理定理2.5-6)9 . 2(1)0()1(xxMMxxk*(k)10. 2(1)1()(*)(kkkxxMMxx 證證 由于 x(k+1)=Mx(k)+f

12、 , x(k)=Mx(k-1)+f x*=Mx*+f所以 x(k+1) -x(k)=M(x (k) -x(k-1) ) , x(k+1) x*=M(x (k) x* )于是有 x(k+1) -x(k) Mx (k) -x(k-1) x(k+1) x*Mx (k) x* x(k+1) -x(k) =(x (k+1) x* )-(x(k) x* ) x (k) x*-x(k+1) x* (1-M)x(k) x*科大研究生學(xué)位課程17所以)()1(*)(11kkkxxMxx)1()(1kkxxMM)0()1(1xxMMk 上述定理只是收斂的充分條件,并不必要,如7 . 005 . 08 . 0M則M

13、1=1.2,M=1.3,M2=1.09,MF=1.17但(M)=0.81,所以迭代法是收斂的.由由(2.10)(2.10)式可見式可見,M越小收斂越快越小收斂越快, ,且當(dāng)且當(dāng)x (k) -x(k-1) 很小很小時(shí)時(shí),x(k) x*就很小就很小, ,實(shí)際上用實(shí)際上用x (k) -x(k-1) 作為作為迭代終止迭代終止的條件的條件.科大研究生學(xué)位課程18 , 即若使x(k) x* ,只需)0()1(1xxMMkM)xx)M(1ln/ )ln()0()1(k可以事先估計(jì)達(dá)到某一精度需要迭代多少步可以事先估計(jì)達(dá)到某一精度需要迭代多少步. . 線性方程組的迭代法主要有線性方程組的迭代法主要有Jocob

14、i迭代法、迭代法、Gauss-Seidel迭代法和超松弛迭代法和超松弛(Sor)迭代法迭代法.科大研究生學(xué)位課程19nnnnnnnnnnbxaxaxabxaxaxabxaxaxa221122222121112121112.2雅克比（雅克比（Jacobi）迭代法）迭代法若系數(shù)矩陣非奇異，且若系數(shù)矩陣非奇異，且 (i = 1, 2, n)，將方程組將方程組0iia改成改成11,221112323121222213132121111111nnnnnnnnnnnnnxaxaxabaxxaxaxabaxxaxaxabax科大研究生學(xué)位課程20然后寫成迭代格式然后寫成迭代格式)(11,)(22)(11)1

15、()(2)(323)(121122)1(2)(1)(313)(212111)1(1111knnnknknnnnknknnkkkknnkkkxaxaxabaxxaxaxabaxxaxaxabax（2.11）（2.11）式也可以簡(jiǎn)單地寫為式也可以簡(jiǎn)單地寫為), 2, 1(1)(1)1(nixabaxkjnijjijiiiki（2.11）科大研究生學(xué)位課程21寫成寫成矩陣形式矩陣形式：A =LUDBfJacobi 迭代迭代陣陣bDxULDxkk1)(1) 1()( (2.12)bxULDxbxULDbAx )()(bDxULDx11)( 科大研究生學(xué)位課程22算法算法2.1（Jacobi迭代法）：迭

16、代法）：(0)(0)(0)(0)112(0)1(0)(0)1.(),( ,),(,),.2.1.3.1,2, ()/4.,55.,1,(1,2, ),3 ijnnniiijjiijj iiiAabbbn xxxxNkinxba xaxxxkNkk xxin 輸入維數(shù)最大容許迭代次數(shù)置對(duì)若輸出 停機(jī)；否則轉(zhuǎn) 。若置轉(zhuǎn) ；否則，輸出失敗信息，停機(jī)。( )(1,kkMxx ）評(píng)價(jià)：公式簡(jiǎn)單，每迭代一次只需計(jì)算一次矩陣和向量的乘法，不改變的稀疏性，需兩組工作單元，存。程序見P19?？拼笱芯可鷮W(xué)位課程232.2.2 Jacobi迭代法的收斂條件迭代法的收斂條件 迭代格式收斂(B)1 。若B1迭代法收斂.

17、定理：若系數(shù)矩陣A滿足下列條件之一，則Jacobi迭代收斂。A為行對(duì)角占優(yōu)陣A為列對(duì)角占優(yōu)陣 A滿足nijjijiiaa, 1jiijjjaa1,1nijjiijiaa對(duì)于Jacobi迭代，我們有一些保證收斂的充分條件. 引理引理 若A是嚴(yán)格對(duì)角占優(yōu)矩陣, 則det(A)0. 證證 A=D-L-U=D(I-D-1(L+U)= 因?yàn)锳是嚴(yán)格對(duì)角占優(yōu)矩陣, 所以det(D)0, 而且1max11nijjiiijniaaB因此, (B)B1,故=1不是B的特征值,det(I-B)0.所以, det(A)0.D(I-B)科大研究生學(xué)位課程24證明：)(1ULDB iiijijijiiijiaaaaB

18、1max1max1 jiiiijiaaB 由條件知，A為列對(duì)角占優(yōu)陣，則AT為行對(duì)角占優(yōu)陣，有)()(1TADIB證畢A為行對(duì)角占優(yōu)陣A為列對(duì)角占優(yōu)陣)(1TTADI11)(DAIDAITT1max11nijjiijiniaa科大研究生學(xué)位課程25 為了加快收斂速度，同時(shí)為了節(jié)省計(jì)算機(jī)的內(nèi)存，我們作如下的改進(jìn)：每算出一個(gè)分量的近似值，立即用到下一個(gè)分量的計(jì)算中去，即用迭代格式： iinijkjijijkjijikiaxaxabx1)1(11)()(2.3 .3 高斯高斯賽得爾賽得爾(Gauss-Seidel)迭代法迭代法逐一寫出來即為科大研究生學(xué)位課程26)(1)(1)(414)(313)(2

19、12111) 1(1knnkkkkxaxaxaxabax)(1)(2)(424)(323) 1(121222) 1(2knnkkkkxaxaxaxabax)(1)(3)(434) 1(232) 1(131333) 1(3knnkkkkxaxaxaxabax)(1) 1(11) 1(33) 1(22) 1(11) 1(knnnknknknnnnknxaxaxaxabax 只存一組向量即可。只存一組向量即可。寫成寫成矩陣形式矩陣形式：bDUxLxDxkkk1)()1(1)1()( bUxxLDkk )()1()(bLDUxLDxkk1)(1)1()()( B fGauss-Seidel 迭代陣迭代

20、陣2.3 .3 高斯高斯賽得爾賽得爾(Gauss-Seidel)迭代法迭代法(2.14)(2.16)科大研究生學(xué)位課程27(0)(0)(0)(0)112(0)1111121(0)111.(),(,),(,),.2.1.3. () / () /(2,1) (ijnnnjjjiniiijjijjiijjinnAabbbn xxxxNkxba xaxba xa xainxba 輸入維數(shù)最大容許迭代次數(shù)置計(jì)算11(0)(0) /4.,55.,1,(1,2,),3nnjjnnjiixaxxxkNkk xxin若輸出停機(jī)；否則轉(zhuǎn) 。若置轉(zhuǎn) ；否則，輸出失敗信息，停機(jī)。程序見P23。算法算法2.2（Gaus

21、s-Seidel迭代法）：迭代法）：科大研究生學(xué)位課程28 例例 用雅可比迭代法解方程組用雅可比迭代法解方程組 2 . 453 . 82102 . 7210321321321xxxxxxxxx 3 . 12 . 11 . 1x )2 . 4(51)3 . 82(101)2 . 72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx解：雅解：雅 可可 比比 迭迭 代代 格式為格式為科大研究生學(xué)位課程29kx1(k) x2(k)x3(k)10.720.830.8420.9711.071.15 11 1.099993 1.199993 1.299

22、99112 1.099998 1.199998 1.299997 取取計(jì)算如下計(jì)算如下 Tx)0 , 0 , 0()0( )2 . 4(51)3 . 82(101)2 . 72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx科大研究生學(xué)位課程30 解：解： 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 例例 用用GaussSeidel 迭代法解上題。迭代法解上題。 2 .

23、453 . 82102 . 7210321321321xxxxxxxxx科大研究生學(xué)位課程31取取 x(0)=(0,0,0)T 計(jì)算如下：計(jì)算如下：kx1(k) x2(k)x3(k)10.720.9021.1644 81.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科大研究生學(xué)位課程322.3.2 收斂條件收斂條件我們看一下Gauss-Seidel迭代法收斂的充分條件定理：若A滿足下列條件之一，則Seidel i迭代收斂。A為行或列對(duì)角占優(yōu)

24、陣A對(duì)稱正定陣（證略書上定理2.9） 迭代格式收斂(B)1 。若B1迭代法收斂. det(I-B)= det(I-(D-L)-1U)證明：= det(D-L)-1)det(D-L)-U)=0所以有 det(D-L)-U)=0nnnnnnaaaaaaaaa212222111211UL)(D科大研究生學(xué)位課程33nnnnnnaaaaaaaaa212222111211UL)(D 若|1, 則矩陣(D-L)-U 是嚴(yán)格對(duì)角占優(yōu)矩陣, 這與 det(D-L)-U)=0矛盾, 所以|1,于是(B)1. 二種方法都存在二種方法都存在收斂性問題收斂性問題。 有例子表明：有例子表明：Gauss-Seidel法收

25、斂時(shí)，法收斂時(shí)，Jacobi法可能法可能不收斂；而不收斂；而Jacobi法收斂時(shí)，法收斂時(shí)， Gauss-Seidel法也可能法也可能不收斂。不收斂?？拼笱芯可鷮W(xué)位課程342.4 逐次超松弛迭代法逐次超松弛迭代法記)()1()(kkkxxx則)()()1(kkkxxx可以看作在前一步上加一個(gè)修正量。若在修正量前乘以一個(gè)因子，有)()()1(kkkxxx)()()1(1)1(bUxLxDxkkk對(duì)GaussSeidel迭代格式)1()()()1()()1()1 ()(kkkkkkxxxxxx)()(1)(1)1(1)()1(kkkkkxbDUxDLxDxx)()1 (1)(1)1(1)()1(b

26、DUxDLxDxxkkkk(2.22)bDxUDIxLDIkk1)(1)1(1)1()(科大研究生學(xué)位課程35故故SOR的迭代格式的迭代格式bDxUDIxLDIkk1)(1)1(1)1()(bDLDIxUDILDIxkk111)(111) 1()()1()(bLDfUDLDB11)( )1()( bLDxUDLDxkk1)(1)1()()1()(（2.23）SOR的迭代矩陣的迭代矩陣科大研究生學(xué)位課程36)(1)1(11)1(1kjnijijkjijijiiikixaxabax), 2, 1()1 ()1()()1(nixxxkikiki)(1)1(11)()1()1 (kjnijijkjij

27、ijiiikikixaxabaxx用分量形式討論，設(shè)用分量形式討論，設(shè)加速加速（迭代公式）（迭代公式）是松馳因子是松馳因子(02), 當(dāng)01時(shí)叫超松弛， =1時(shí)，就是Gauss-Seidel迭代法。科大研究生學(xué)位課程37(0 )(0 )(0 )(0 )112(0 )(0 )11111121(0 )(0 )111.(),(,),(,),.2.1.3. (1)() / (1)() / ijnnnjjjiniiiijjijjiijjiAabbbn xxxxNkxxbaxaxxba xa xa 輸 入維 數(shù)最 大 容 許 迭 代 次 數(shù)， 參 數(shù)置計(jì) 算1(0 )1(0 )(0 ) (2,1) (1)

28、() /4.,55.,1,(1, 2,),3nnnnnjjnnjiiinxxbaxaxxxkNkk xxin若輸 出停 機(jī) ； 否 則 轉(zhuǎn)。若置轉(zhuǎn)；否 則 ， 輸 出 失 敗 信 息 ， 停 機(jī) 。程序見P28。算法算法2.3（SOR迭代法）：迭代法）：科大研究生學(xué)位課程38 例 用SORSOR方法解線性方程組7910431017210424321321321xxxxxxxxx解解 SORSOR方法迭代公式為方程組的精確解是x*=(2,1,-1)T.)91047(9)101723(17)42410(4)(3)1(2)1(1)(3)1(3)(3)(2)1(1)(2)1(2)(3)(2)(1)(1)1(1kkkkkkkkkkkkkkkxxxxxxxxxxxxxxx取x(0)=(0,0,0)T,=1.46,計(jì)算結(jié)果如下:科大研究生學(xué)位課程39kx1(k)x2(k)x3(k)01232003.652.321669102.56