第6章上ch6方程組的解法

1、第第6 6章章 線性代數(shù)方程組的解法線性代數(shù)方程組的解法考慮線性方程組也就是 AX=b. nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 低階稠密的線性方程組用低階稠密的線性方程組用直接法直接法( (如如高斯消去法高斯消去法和和三三角分解法角分解法( (LULU分解法分解法）) )。線性方程組的解法可分為線性方程組的解法可分為直接法直接法和和迭代法迭代法兩大類。兩大類。大型稀疏非帶狀的線性方程組(n很大,且零元素很多.如偏微方程數(shù)值解產(chǎn)生的線性方程組,n104)的求解問題？零元素多，適合用迭代法迭代法。迭代法簡單好用，而直接法計算代價太高

2、。 我們主要介紹迭代法的一般理論及雅可比迭代法、高斯塞德爾迭代法、超松弛迭代法，研究它們的收斂性。下面先介紹向量和矩陣的范數(shù)向量和矩陣的范數(shù)滿足的某個非負(fù)實值函數(shù)或如果向量范數(shù) |,x|)x(N)C(Rx nn) )定義6.1(定義6.1(1) 正定性正定性：,|0 x等號當(dāng)且僅當(dāng)0 x時成立；(2) 齊次性齊次性：; | , xxR(3) 三角不等式三角不等式：., , |nRyxyxyx則稱| x為向量x的范數(shù)范數(shù)或模模。由(3)可推出不等式(4)., , |nRyxyxyx 6.1 6.1 向量和矩陣的范數(shù)向量和矩陣的范數(shù) 為了研究線性方程組的近似解的為了研究線性方程組的近似解的誤差估計

3、誤差估計和和迭代法的迭代法的收斂性收斂性, 我們需要對我們需要對Rn中的向量中的向量(或或Rnn中的矩陣中的矩陣)的的大小引進(jìn)某種度量大小引進(jìn)某種度量向量向量(或矩陣或矩陣)的范數(shù)的范數(shù).幾種常用范數(shù)幾種常用范數(shù) |,|max|1inixx(無窮范數(shù)無窮范數(shù)) |,|nxxx11(1-范數(shù)范數(shù)) ,|2212nxxx(2-范數(shù)范數(shù))., 1 ,1)|(|/1pnixxppip(p-范數(shù)范數(shù))可以驗證它們都是范數(shù). 易見前三種范數(shù)是p-范數(shù)的特殊情況).|lim|(|ppxxinix1maxppnppxxx121)(ppinixn11)max(inipxn11max)(max1pxini),(時

4、pxxp12xxx且5例1.求下列向量的各種常用范數(shù)Tx)1,3 ,4 , 1(解:1x421xxx92x21242221)(xxx3327 xiix41max4即即本本例例中中顯顯然然, 211 xcxxc,1 1* *4 499/499/4* *4=94=9.x,x,xx)x(NR|x|)x(N)xN(n21n的連續(xù)函數(shù)的分量是范數(shù)，則是上任一向量為設(shè)的連續(xù)性 ) )定定理理6 6. .1 1( (. *xxlim. *xx),n, 2 , 1i (*xxlim .*)x,*,x*,x(*x,)x,x,x(x,Rx )k(k)k(i)k(ikTn21T)k(n)k(2)k(1)k(n)k(

5、記為收斂到則稱若記中一個向量序列為設(shè)定義6.2定義6.2.|x|c|x|x|c Rx, 0c,c,R|x| ,|x|s2ts1n21nts有使得對一切則存在常數(shù)任意兩種范數(shù)是上向量為設(shè)向量范數(shù)的等價性 ) )定定理理6 6. .2 2( (.|, 0|*xx|lim*xxlim)k(k)k(k的任一種范數(shù)為向量其中 定定理理6 6. .3 3中矩陣的一種范數(shù)范數(shù)得到上的向量，則由中中矩陣為視廣到矩陣上下面把向量范數(shù)概念推nnnnnnRRRR2 .22)( 11|2FrobeniusFninjijaAF范數(shù)，.般定義下面給出矩陣范數(shù)的一定義定義6.36.3(矩陣的范數(shù)矩陣的范數(shù)) 滿足的某個非負(fù)

6、實值函數(shù)如果 |,|)( AANRAnn(1) 正定性：,|0A等號當(dāng)且僅當(dāng)0A時成立；(2) 齊次性：; | , AAR(3) 三角不等式：., , |nnRBABABA則稱| A為 矩陣矩陣A的范數(shù)范數(shù)或模模。., , | )(nnRBABAAB4.|上的一個矩陣范數(shù)就是nnFRA .Rx,RA |,x|A|Ax| nnn性，即滿足和向量范數(shù)的相容我們希望一種矩陣范數(shù).)|A|( .|x| |Ax| max|A| ,|x| .RA,Rx vvv0 xvvnnn稱為矩陣的算子范數(shù)是矩陣的一種范數(shù)下面驗證相應(yīng)地定義向量范數(shù)對于給定一種設(shè)矩陣的算子范數(shù)) )定義6.5(定義6.5( .Rx,RA

7、 |,x|A|Ax| ,R|A| ,R|x|nnnnnvnv且滿足相容條件一種矩陣范數(shù)上是則上一種向量范數(shù)是設(shè) 定定理理誘導(dǎo)出的常用矩陣范數(shù)矩陣范數(shù)有： ,RA6nn則設(shè) .4.4定理定理列范數(shù) , |max|niijaAnj111行范數(shù) , |max|njijaAni11范數(shù)的最大特征值矩陣22 ,|AAAT它們滿足如下相容關(guān)系：. | , | | , | |11222221xAAxxAAxxAAxxAAxF，,大值的每行絕對值之和的最A(yù),大值的每列絕對值之和的最A(yù)大值的特征值的絕對值的最為AAAATT)(max)(maxAAT2A11例2.求矩陣A的各種常用范數(shù)110121021A解:1A

8、niijnja11max25234252 ,5 ,2max1njAnjijnia11max42 ,4 ,3max1ni2A)(maxAAT由于12的特征值因此先求AATAAT110121021110122011211190102特征方程為)det(AAIT2010911120的特征值為可得AAT9361. 0,9211. 2,1428. 9321131428. 9)(maxAAT2A)(maxAAT0237. 3FA)(AAtrT2926056. 31AA2AFA容易計算計算較復(fù)雜對矩陣元素的變化比較敏感不是從屬范數(shù)較少使用使用最廣泛性質(zhì)較好9361. 0,9211. 2,1428. 9321

9、AAT21119010214定義6.6.稱的特征值為設(shè),21nnnRA,max)(21nA的譜半徑為矩陣A顯然2A)(maxAAT)(AAT).(|A|)A( ,RAnn任一范數(shù)則設(shè)特征值上界 ) )定理6.5(定理6.5(任何一種算子范數(shù)的譜半徑不超過矩陣的即矩陣A.|A|)A( ,RA2nn則為對稱矩陣若 定理6.6定理6.6.|B|11|BI| ,BI , 1|B|B1且為非奇異陣則滿足若方陣 定理6.7定理6.7的最大特征值矩陣AAAT2|6.6 6.6 線性代數(shù)方程組的基本迭代法線性代數(shù)方程組的基本迭代法考慮線性方程組也就是也就是 Ax=b. nnnnnnnnnnbxaxaxabxa

10、xaxabxaxaxa22112222212111212111 進(jìn)行矩陣分解進(jìn)行矩陣分解 A=M-N, 其中其中M M為可選擇的非奇異矩陣為可選擇的非奇異矩陣, ,且使且使Mx=dMx=d容易求解。容易求解。于是, Ax=bx=M-1Nx+M-1b. fBxx . bMf ,NMB 11其中, 1 , 0k, fBxx Rx )k()1k(n)0(，得迭代方程取初始向量. fBxxbAx 變形得到等價的一般地，由1 f*Bx*x *,x則設(shè)有解2 fBxx ,x)k()1k()0(則可構(gòu)造迭代序列又設(shè)任取初值.2fBxx(1) ) )迭代法(迭代法(定義1定義1一階定常迭代法近似解的方法稱為逐

11、步代入求，用公式對于方程組.,*,*)(lim)2()(否則迭代法發(fā)散是解顯然，則稱此記為存在若xxx迭代法收斂迭代法收斂kk .BB 21*,xx)0(k)k()1k()k()k(得則由引進(jìn)誤差向量 .lim0lim )(0 0kkkkB收斂： . ) )0 0( (kkBB滿足什么條件下要研究問題：（問題：（1）如何建立迭代公式）如何建立迭代公式？（2）向量序列收斂的條件是什么？）向量序列收斂的條件是什么？（3）收斂速度、誤差估計是多少？）收斂速度、誤差估計是多少？1.1.雅可比（雅可比（JacobiJacobi迭代迭代例例1 1 求解線性方程組 (1) .36x12x3x6,33xx11

12、x4,20 x2x3x83213213216.6.1 6.6.1 迭代公式的建立迭代公式的建立記為Ax=b,即 .36332012361114238321 xxx 精確解x*=(3,2,1)T.改寫(1)為(2) ).36x3x6(x ),33xx4(x ),20 x2x3(x21121331111232811或?qū)憺閤=B0 x+f,即 .000123611338203211231261111148283321 xxx xxx (1) .36x12x3x6,33xx11x4,20 x2x3x8321321321任取初值,如x(0)=(0,0,0)T,代入(2)得到x(1)=(2.5,3,3)T

13、.反復(fù)迭代(3) .12/)36x3x6(x,11/)33xx4(x ,8/)20 x2x3(x)k(2)k(1)1k(3)k(3)k(1)1k(2)k(3)k(2)1k(1即 x(k+1)=B0 x(k)+f， (k=0,1,2,).*,000187.0 ,)9998813.0 ,999838.1 ,000032.3()10()10()10()10(xxx其中T,xi),n, 2 , 1i (0aiii個方程中解出從方程組的第設(shè)1 1、雅可比迭代法、雅可比迭代法)(1 )111(1 )(111,1112121111nnnnnnnniiiinnxaxabaxnijjxijaijjxijabax

14、xaxabax可以得到計算公式(雅可比迭代法雅可比迭代法) ：對k=0,1,), 1( ,/ )( ,),(1)()1()0()0(1)0(niaxijabxxxxiinijjkjikiTn雅可比迭代分量形式雅可比迭代分量形式其中采用矩陣分裂記號, ULDA ,0001121nnnaaaL ,nnaaaD2211.,0001112nnnaaaU xxkkkbULxD)()()1( 就有fxBbDxULDx)(1)(1) 1()( kJkk 示形式為雅可比迭代法的矩陣表A的下三角部分的負(fù)矩陣A的上三角部分的負(fù)矩陣bDf),UL(DB11J其中迭代矩陣。稱為 JacobiBJ23例1.用Jacob

15、i迭代法求解方程組,誤差不超過1e-41233204121114238321xxx解:4121114238A4000110008D000100230U012004000L24)(1ULDBJ04121111011441830bDf1335 .2迭代法使用取初值JacobixT,000)0(fxBxkJk)()1(),2 , 1 ,0(nk 2504121111011441830fxBxJ)0()1(335 .2000T3,3,5 .2924.4)0()1( xx04121111011441830fxBxJ)1()2(335 .2335 .2T1 ,3636.2,875.21320.2)1()2

16、( xx2604121111011441830fxBxJ)2()3(335 .213636.2875.2T9716.0,0455.2,1364.34127.0)2()3( xx依此類推,得方程組滿足精度的解為x12迭代次數(shù)為12次 x4 = 3.0241 1.9478 0.9205 d = 0.1573 x5 = 3.0003 1.9840 1.0010 d = 0.0914 x6 = 2.9938 2.0000 1.0038 d = 0.0175 x7 = 2.9990 2.0026 1.0031 d = 0.0059 x8 = 3.0002 2.0006 0.9998 d = 0.0040

17、 x9 = 3.0003 1.9999 0.9997 d = 7.3612e-004x10 = 3.0000 1.9999 0.9999 d = 2.8918e-004x11 = 3.0000 2.0000 1.0000 d = 1.7669e-004x12 = 3.0000 2.0000 1.0000 d = 3.0647e-0050000.10000.20000.3321xxx27分析Jacobi迭代法的迭代過程,將(5)式細(xì)化)(11)(1111)(1)1(1njkjjkkxabaxx)(11)(2222)(2)1(2njkjjkkxabaxx已經(jīng)求出之前發(fā)現(xiàn)在)1(1)1(2)1(1)

18、1(,kikkkixxxx進(jìn)行迭代仍用時但當(dāng)求)(1)(2)(1)1(,kikkkixxxx?,)1(1)1(2)1(1)1(進(jìn)行迭代呢利用時能否求kikkkixxxx11)( )( )( )11111()() ijjjninkkkkiijiijijjjj jiiiij ixba x ba xa x aa ( 2 2、高斯、高斯塞德爾迭代法塞德爾迭代法28考慮迭代式(7)fxBxkJk)()1(),2 , 1 ,0(kbDxULDxkk1)(1)1()(即bUxLxDxkkk)()()1(),(不含對角線下三角的形式注意到 LbUxLxDxkkk)()1()1(-(8)11)( )( )( )

19、11111()() ijjjninkkkkiijiijijjjj jiiiij ixba x ba xa x aa ( 1(k)ix若把已經(jīng)計算出來的值立即代入迭代計算,則得到:1(1)(1)( )11 () jjinkkkiiiijijjjja xba xa x 29bUxxLDkk)()1()(可逆時當(dāng)LD 部分包括對角線的下三角即為)(ALD bLDUxLDxkk1)(1)1()()(得設(shè),)(,)(11bLDfULDBGGGkGkfxBx)()1(-(9)上式稱為Gauss-Seidel迭代法,簡稱G-S法利用(8)式展開Gauss-Seidel迭代法也可表示成),2 , 1 ,0(k

20、迭代矩陣。稱為SGBG301112)(111)1(111baxaaxnjkjjk2223)(22211)1(222)1(2111baxaaxaaxnjkjjjkjjk3334)(33321)1(333)1(3111baxaaxaaxnjkjjjkjjkiiinijkjijiiijkjijiikibaxaaxaax1111)(11)1()1(nnnnjkjnjnnknbaxaax1111)1()1(31例2.用Gauss-Seidel迭代法求解例1.解:迭代法使用取初值SeidelGaussxT,0 , 0 , 0)0(11132)(111)1(111baxaaxjkjjk5 .2)23(81)

21、(3)(2kkxx22233)(22211)1(222)1(2111baxaaxaaxjkjjjkjjk3111114)(3)1(1kkxx3321)1(333)1(311baxaaxjkjjk3)12(41)1(2)1(1kkxx32x1 =2.5000 2.0909 1.2273 d =3.4825x2=2.9773 2.0289 1.0041 d =0.5305x3 =3.0098 1.9968 0.9959 d =0.0465x4 =2.9998 1.9997 1.0002 d =0.0112x5 =2.9998 2.0001 1.0001 d =3.9735e-004x6 =3.00

22、00 2.0000 1.0000 d =1.9555e-004x7 =3.0000 2.0000 1.0000 d =1.1576e-005通過迭代,至第7步得到滿足精度的解x7從例1和例2可以看出,Gauss-Seidel迭代法的收斂速度比Jacobi迭代法要高。Jacobi迭代法和Gauss-Seidel迭代法統(tǒng)稱為簡單迭代法簡單迭代法。6.6.2 6.6.2 迭代法的收斂性分析迭代法的收斂性分析. fBxx bAx *,x,RA(1) bAx nn并有有精確解非奇異其中設(shè)(2) . f*Bx*x 則(3) fBxx )k()1k(并有迭代法公式 . *,)0()()1()()(BBxxk

23、kkkk則引進(jìn)誤差向量 . *,)0()()1()()(BBxxkkkkk則引進(jìn)誤差向量. ) )0 0( (kkBB滿足什么條件有要研究何時收斂，即.lim), 2 , 1,( lim )(,)( )()(AAAAAAkkkijkijknnijnnkijknjiaaRaRa，記為收斂于則稱，若設(shè)矩陣序列定定義義2 2.1|0,02,01 1222，考查其極限且，設(shè)矩陣序列kkkkkAAA例例4 4. 01limlimlim1kkkkkkkkk.|0limlim 的任一算子范數(shù)為矩陣，其中AAAAkkkk定定理理1 1.lim,lim AxxAxAAkknkkR定定理理2 2. 1)( )3(

24、; 0lim )2(; 0lim , ) 1 (: ,)( )(BBBxBxB的譜半徑則下列三個條件等價設(shè)矩陣kkkknnnkijRRb定理3定理3. 0) 1() 1(!lim limlimlim11nknkknkknkknknkknknkkk. 1)(), 1( 10lim0limBriJBikkkk. 1)B()5(x(5) fBxx (4) fBxx )0()k()1k(收斂迭代法則對任意初始向量及迭代法設(shè)有方程組定理4定理41) Jacobi: BJ=D-1(L+U)，fJ=D-1b;2) Gauss-Seidel: BG=(D-L)-1U，fG= =(D-L)-1b;迭代的統(tǒng)一格式

25、：x(k+1)=Bx(k)+f迭代法基本定理：迭代法基本定理：.)1()(1)(;)(, 1)();(1)(, 111UDLDLLULDGGULDJJDULDAAbAx，其中迭代法收斂其中塞德爾迭代法收斂高斯，其中雅可比迭代法收斂則非奇異非奇異設(shè)SORRnn推論推論例例5 5 考察用雅可比迭代法求解線性方程組(1.2) .361236,33114,20238321321321xxxxxxxxx.53,52 1221xxxx和P187例6.14 例6.15，則的某種算子范數(shù)如果有定常迭代法及一階設(shè)有方程組迭代法收斂的充分條件1qBB ).5()4( ) )定理5(定理5(；，且，意）迭代法收斂，

26、即對任（fBxxxxx*lim 1)()0(kk；）（)0()(* 2xxxxkkq；）（) 1()()(1* 3kkkqqxxxx.1* 4)0() 1 ()(xxxxqqkk）（又因為矩陣的又因為矩陣的譜半徑譜半徑不超過其不超過其任一種算子范數(shù)任一種算子范數(shù),即即BB )(x(k+1)=Bx(k)+f （5）X = B x + f （4）39例6.判別下列方程組用判別下列方程組用J法和法和G-S法求解是否收斂法求解是否收斂?111122111221321xxx解:(1) 求Jacobi法的迭代矩陣)(1ULDBJ100010001022101220022101220, 1JJBB 的幾種常

27、用算子范數(shù)顯然因此不能用因此不能用定理定理5。只能用只能用定理定理4判斷。判斷。40)det(JBI 221122det30所以0|)max(|)(JB01即Jaobi迭代法收斂(2) 求Gauss-Seidel法的迭代矩陣ULDBG1)(1122011001000100220200320220同樣用同樣用定理定理4判斷。判斷。02|)max(|)(GB1所以Gauss-Seidel迭代法發(fā)散。注意注意：在例1和例2中,G-S法收斂速度比J法要高。但例但例6卻說明卻說明G-S法發(fā)散時而法發(fā)散時而J法卻收斂法卻收斂因此因此,不能說不能說G-S法比法比J法更好法更好41P189例6.17 也是說明

28、定理6.21僅是迭代法收斂的充分條件。42對于某些特殊矩陣,從方程本身就可以判斷其收斂性.定理6.法均收斂法和則矩陣為嚴(yán)格對角占優(yōu)的系數(shù)矩陣若線性方程組SGJacobiAbAx,證:(1)對于Jacobi迭代法,其迭代矩陣為)(1ULDBJ所以嚴(yán)格對角占優(yōu)因為系數(shù)矩陣,Aniaaijijii, 3 ,2 , 1|niaaijijii, 3 ,2 , 11|1430002122222211111112nnnnnnnnJaaaaaaaaaaaaBJBijijiiiaa|1max1根據(jù)定理5Jacobi迭代法收斂(2)對于GS迭代法,其迭代矩陣為ULDBG1)(,的形式不易確定由于GB不能使用定理5

29、,而用定理444滿足的特征值GB0)det(GBI)(det1ULDI)(det)det(1ULDLD0)(detULD00ijijiiaa|nijijijijiiaaa111|nijijnijijijijaaa1111|)1|(|即從而因此由于可得45則有如果, 1|nijijijijiiaaa111|為嚴(yán)格對角占優(yōu)矩陣則)(ULD0)(detULD從而矛盾, 1|所以, 1)(GB即由定理4GS迭代法收斂46 3ii1 .521101 (1) 142 , (2) 1 2023 10123 1 a . 2 aijjj iAAAaA 判斷以下矩陣對應(yīng)的方程組是 否收斂： （）中，因為因此 矩陣

30、為嚴(yán)格對角占優(yōu)矩 陣，對應(yīng)的方程組收斂（ ）中，因為 例例4 4 解解33ii222112 a .ijjjjj ijaaA 且因此 矩陣為弱對角占優(yōu)矩 陣，對應(yīng)的方程組收斂SOR迭代法的計算公式:對k=0,1,6.6.3 6.6.3 逐次超松馳逐次超松馳(SOR)(SOR)迭代法迭代法. 0 ), 2 , 1( ,/ )( ,),()(11)1()()1()0()0(1)0(松弛因子niaxijaxijabxxxxxiinijkjijkjikikiTn kkkkk）化為的分裂記號采用矩陣)()()1()()1( ,DxUxLxbDxDxA.)()1()( 1)(1) 1( SORkkbLDxU

31、DLDx為迭代法的矩陣表示形式. ;, ),2( 11221211否則為不可約矩陣為可約矩陣則稱為方陣，使得如果存在置換陣設(shè)矩陣AAAAAAPPPA0 0定義4定義4TnnnR定義定義3 3 （1）按行嚴(yán)格對角占優(yōu)：nijiiijjniaa1), 2 , 1( |,|（2）按行弱對角占優(yōu)：nijiiijjniaa1), 2 , 1( |,|上式至少有一個不等號嚴(yán)格成立。某些特殊方程組的迭代收斂性某些特殊方程組的迭代收斂性21212212110)(ddyyAAAbPxPAPPTTT.210123321310210321301212201 ),( ,4110140110410114 , 11122

32、211DCBA，都不為零考察矩陣iiinnnnncbabacbacbacb例7例7., 0, 2 , 12)( 否則為可約的為不可約矩陣則稱且滿足都有，和兩個非空不相交子集的任意，若對集合的階設(shè)方陣AaTjSijiWTSTSnWaAijij定義定義* * *定義定義 每行每列只有一個元素是1,其余元素是零的方陣稱為置換陣(或排列陣).,00 不可約，否則可約若強(qiáng)連通則畫箭頭到畫箭頭，到ijjijiijPPaPPa圖論法圖論法* *.301212201 ,4110140110410114CB作業(yè)作業(yè): P259, 5.，則有有精確解非奇異其中仍考慮*,xAbAxnnR定理定理6(6(對角占優(yōu)定理)若矩陣A A按行(或列)嚴(yán)格對角占優(yōu)，或按行(或列)弱對角占優(yōu)且不可約；則矩陣A A非奇異。定理定理7 7 若矩陣A A按行(或列)嚴(yán)格對角占優(yōu),或按行(或列)弱對角占優(yōu)不可約；則Jacobi迭代、Gauss-Seidel迭代都收斂。證明證明 若矩陣A按行嚴(yán)格對角占優(yōu)，或按行(或列)弱對角占優(yōu)不可約，則GS迭代收斂。假若不然，(BG)1，即迭代矩陣BG的某一特