向量和矩陣的范數(shù)_病態(tài)方程組_解線性方程組的迭代法

1、3.4 向量和矩陣的范數(shù)n為了研究線性方程組近似解的誤差估計(jì)和迭代法的收斂性，我們需要對(duì)Rn(n維向量空間)中的向量或Rnxn中矩陣的“大小”引入一種度量，向量和矩陣的范數(shù)。向量和矩陣的范數(shù)n在一維數(shù)軸上，實(shí)軸上任意一點(diǎn)x到原點(diǎn)的距離用|x|表示。而任意兩點(diǎn)x1，x2之間距離用| x1-x2 |表示。向量和矩陣的范數(shù)n而在二維平面上，平面上任意一點(diǎn)P(x,y)到原點(diǎn)的距離用 表示。而平面上任意兩點(diǎn)P1(x1,y1),P2(x2,y2)的距離用 表示。 推廣到n維空間，則稱為向量范數(shù)。|22OPyx22122121)()(|yyxxPP向量范數(shù)的范數(shù)。為向量則稱，都有三角不等式：對(duì)任意奇次性：時(shí)

2、，當(dāng)且僅當(dāng)非負(fù)性：且滿足法則對(duì)應(yīng)于一非負(fù)實(shí)數(shù)按某一確定的設(shè)任一向量xxRRkkkRyxyxyxxxxxxxxnn|,)3;|,|)2;0|00|)1:|,|,3.4.1定義常見(jiàn)的向量范數(shù)|max|)(),()|(|),.,(12121211221121iniTniiniiTnxxxxxxxxxxxxxx設(shè)向量向量范數(shù)性質(zhì)nnnnnRMmMmxxxRRxxxxxxyxyxyx|,| ,|R3,.,|,2121使得則必存在兩正數(shù)中定義的任意兩種范數(shù)對(duì)性質(zhì)的一致連續(xù)函數(shù)。是分量則向量范數(shù)設(shè)性質(zhì)。有對(duì)任意性質(zhì)，向量范數(shù)性質(zhì)等價(jià)性質(zhì)：niiininiixxxnnnnnxxxxxxxxxxx1111211

3、1|max|1|1:|)3|)2|1) 1例如向量的收斂性*)(*)(*2*1*)()(2)(1)()(|0|limlim,),.,2 , 1(lim),.,(,.,.),2 , 1(3.4.2xxxxxxxxxxxkkkkkkikiknTnTknkkkknnixxRxxxxxxkR收斂到依范數(shù)則稱向量序列如果有記作依次收斂到則稱向量序列滿足如果存在其中中一向量序列設(shè)定義),.2 , 1(lim0maxlim0|lim|,.)2 , 1(1 . 4 . 3*)()(1*)(*)(nixxxxkikikikinikkkkkxxxxxx）（事實(shí)上由。收斂到數(shù)依范的充分必要條件是坐標(biāo)收斂到依向量序列

4、定理3.4.2 矩陣范數(shù)的一種范數(shù)。為則稱，相容性：三角不等式：，奇次性：時(shí)，當(dāng)且僅當(dāng)非負(fù)性且滿足應(yīng)于一非負(fù)實(shí)數(shù)若按某一確定的法則對(duì)設(shè)任意定義nnnnnnnnRARBABAABRBABABARkAkkAAAAARA|,)4;,|,|)3;|)2; 0|00|:|) 1:|,|,3 . 4 . 3相容范數(shù)是相容的。與此向量范數(shù)則稱該矩陣范數(shù)如果的一種范數(shù)和分別為設(shè)定義|,|,|4 . 4 . 3xAxAAxRRAxnnn算子范數(shù)且稱其為算子范數(shù)。上的矩陣范數(shù)為則定義向量范數(shù)上并在設(shè)定理,|max|max|,|,2 . 4 . 31|0nnxxnnnnRAxxAxAxRRARx算子范數(shù)。只有可能，

5、因?yàn)閯t若顯然成立，定義的四個(gè)條件。所以下面只要驗(yàn)證范數(shù)的一個(gè)對(duì)應(yīng)法則。到定義了所以上一定能達(dá)到最大值在有界閉集的連續(xù)性知，證明：由向量范數(shù)0, 00|, 0|0|max|) 1|1|0AAAAARRAAAAxxxxxxxxxnn|)|(|)(|max|) 3|max|max|)2000 xxxxxxxxxxxxxxxBABABABARAAAAAkAkkAkAnxxx于是，則由算子范數(shù)1|max|,|)(|max|)(|010 xxIxIIRBAABBAxxBABABAxxBAnnx則為單位矩陣中任何矩陣算子范數(shù)對(duì)推論。同理可證即有所以對(duì)常見(jiàn)的矩陣范數(shù)njijniTniijnjpnnnnnija

6、AAAAaApRRaAxx11max2111|max|)(|2|1), 2 , 1(,)(3 . 4 . 3max范數(shù)：范數(shù)：范數(shù)：相容的矩陣范數(shù)是則于向量范數(shù)，設(shè)矩陣定理常見(jiàn)的矩陣范數(shù)。則非奇異又若則為對(duì)稱矩陣設(shè)推論里德范數(shù)。為矩陣的譜范數(shù)或歐幾為矩陣的行范數(shù)，為矩陣的列范數(shù)，一般稱范數(shù)：|)(|,|,)(|,)(1min21max22121112AAAAAAAAAaAFnjniijF對(duì)稱矩陣范數(shù)|)(|)(|)()(0,)(| )(| )(|)()(|1min1max211 -1max22max2maxmax22AAAAAAAAAAAAAAAATT得由非奇異，則又因?yàn)樗杂兄C明：由例題5

7、4)2() 1(2|844. 4466.23|534. 1,466.2301710108|17101084212412264|2| |,1|2max|54| 1| |,2|2max|:|), 2 , 1(|,42121 . 4 . 32122222211FTTFpAAAAIAAAAApAA。，故解得由因?yàn)榻饧扒笤O(shè)矩陣?yán)?.4.3 矩陣的譜半徑和矩陣序列收斂性關(guān)系。的任何一種范數(shù)有某種但可能與的一種范數(shù)不是的譜半徑矩陣的譜半徑。為矩陣則稱征值的特為矩陣設(shè)定義AAAAAAA,.,n),(iinii,)(|max)(,215 . 4 . 31例題33)(33,3304212|421221AAIA所以

8、。特征值得：解：由的譜半徑。求矩陣譜半徑和矩陣序列的收斂性。的任意性，有由，故有由于則的任一特征對(duì)，即為矩陣）設(shè)（證明。則若的任意一種算子范數(shù)為這里則設(shè)定理AAAAAAAAAAAAAAARAxxxxxxxxTnnmax)(0,1|)(,)2(;|,|)() 1 (,4 . 4 . 32)(,5 . 3 . 3|)(5| ,844. 4|, 6| , 5| , 33)(,4212)(| )(|)2(*22max2AARAAAAAAAAAAAAAAnnpFT，滿足則必存在算子范數(shù)為任意指定的小正數(shù)，設(shè)定理。，所以顯然。，故因?yàn)榫仃囆蛄械氖諗啃浴Ｊ諗坑谝婪稊?shù)則稱矩陣序列如果記作收斂到矩陣則稱矩陣序列

9、如果及矩陣設(shè)矩陣序列定義AAAAAAAAnjiaaaAkaAkkkkkkijkijknnijnnkijk|0|limlim,),.,2 , 1,(lim,)(),.,2 , 1()(6 . 4 . 3)()(。的充分必要條件是則設(shè)定理。收斂于矩陣依范數(shù)的充分必要條件是收斂到矩陣，矩陣序列與向量序列收斂性類似1)(0lim,6 .3.4),.,2 , 1(AkAkRAAAAnkAnnkk3.5 病態(tài)方程組與矩陣的條件數(shù)。該方程組的精確解為解什么樣的變化解將產(chǎn)生項(xiàng)有微小擾動(dòng)試分析系數(shù)矩陣和右端設(shè)線性方程組例Txxx) 1 , 1 (?,97. 199. 198. 099. 099. 011 . 5

10、 . 3213.5.1 病態(tài)方程組與擾動(dòng)方程組的誤差分析TxxxxxxxA)5 .48,50(97. 198. 099. 099. 199. 00001. 197. 199. 198. 099. 099. 00001. 10000001. 0)1(212121，解得所以即動(dòng)設(shè)系數(shù)矩陣有微小的擾病態(tài)方程組與擾動(dòng)方程組的誤差分析Txbxx)99. 0,97. 2(9701. 19899. 198. 099. 099. 010001. 00001. 0)2(21解得則若右端有微小變動(dòng)病態(tài)方程組與擾動(dòng)方程組的誤差分析T)3(21)005.148, 5 .148(0197. 19989 . 198. 0

11、99. 099. 00001. 1,xbxxAbA解得則擾動(dòng)若同時(shí)對(duì)病態(tài)方程組與擾動(dòng)方程組的誤差分析。）（，）（；）（現(xiàn)計(jì)算相對(duì)誤差：，005.149|3;99. 1|105|25 .49|105|1321)3()2(5)1(5xxxxbxxxxxAAA,i(i)(i)病態(tài)方程組與擾動(dòng)方程組的誤差分析樣的方程為病態(tài)方程。稱這解發(fā)生很大的變化有微小變化時(shí)陣和右端項(xiàng)顯然上述方程在系數(shù)矩,病態(tài)方程組n擾動(dòng)方程 由于計(jì)算機(jī)字長(zhǎng)限制，在解AX=b時(shí)，舍入誤差是不可避免的。因此我們只能得出方程的近似解 。 是方程組（A+A）x=b+ b (1) xx 在沒(méi)有舍入誤差的解。稱方程（1）為方程Ax=b的擾動(dòng)方

12、程。其中A， b為由舍入誤差所產(chǎn)生的擾動(dòng)矩陣和擾動(dòng)向量。當(dāng)A， b的微小擾動(dòng)，解得（1）的解與Ax=b的解x的相對(duì)誤差不大稱為良態(tài)方程，否則為病態(tài)方程。擾動(dòng)方程組的誤差界。所以得又因?yàn)閺亩杏杉扔幸粋€(gè)擾動(dòng)產(chǎn)生則解有一個(gè)小的擾動(dòng)中設(shè)，bbxxxbbxbxbxbbxxxxbbbxAAAAAAAA111|)() 1 (,。所以得從而有由既有一個(gè)擾動(dòng)產(chǎn)生則解有一個(gè)小的擾動(dòng)中設(shè)，AAAAAAAAAAAAAAxxxxxxxxbxbxxxxbx111|)()()2(,。時(shí)得當(dāng)從而即有由既有一個(gè)擾動(dòng)產(chǎn)生則解都有一個(gè)小擾動(dòng)時(shí)和中設(shè)，)(1|1|)()()3(11111111,AAAAAAAAAAAAAAAAAA

13、AAAAAAAAbAAbbxxxbxxxbxxxbxbxbbxxxxbx|)(1)(|0|)(|0|)|(|)(1)(|,|)(, 1|,)(1 . 5 . 311AAAAAcondAcondxxbbbAcondxxAbbAAAAAcondAcondxxAAAcondAAAAxxxbAxxRAbbxnn時(shí)當(dāng)時(shí)當(dāng)則如果的解是擾動(dòng)方程組精確解。的是方程組且非奇異。設(shè)定理3.5.2 矩陣的條件數(shù).)(;AAAACond(A)RA1 . 5 . 32121 -bx的譜條件數(shù)關(guān)于方程組為矩陣稱的條件數(shù)關(guān)于線性方程組為矩陣為非奇異矩陣，稱設(shè)定義bAxAAAAKnn為病態(tài)方程組。稱解的相對(duì)誤差也大，則大時(shí)如

14、果謂良態(tài)方程組；的相對(duì)誤差也小，則稱解相對(duì)較小時(shí)如果與條件數(shù)相關(guān)解的相對(duì)誤差直接線性方程組bAxAbAxAbAx,)cond(,)(cond,矩陣的條件數(shù)的性質(zhì)。且為正交矩陣性質(zhì)。其中則性質(zhì)為非零常數(shù)。性質(zhì)。性質(zhì))()()(, 1)(,4| )(|,)(|,|)(3)(cond)(cond21)(cond1minmax11AKAPKPAKPKPAAAkAAcAcAAnnT相對(duì)誤差的事后估計(jì)n定理3.6.3 誤差越小。越小誤差越大；則。則殘余向量的解，記是擾動(dòng)方程組精確解，的是方程組且非奇異設(shè),)(|, 1)(|)(|)(|)(|)(1)()1 (,AcondxxAcondbxrAcondxxb

15、xrAcondxAbxrxxxbAxxRAnn例題是病態(tài)方程。所以方程由于因?yàn)橄禂?shù)矩陣?yán)齜AxAkAAn1396010005. 098025. 1|)()(cond98. 099. 099. 011 . 5 . 3123.6 解線性方程組的迭代法fGxx。RRRAbAxxbbxnnnn寫成等價(jià)方程組將類似非線性方程迭代法有唯一解由線性方程組理論知式且且非奇異其中設(shè)線性方程組) 1 . 6 . 3(。) 1 . 6 . 3(0,) 1 . 6 . 3(*3.6.1 解線性方程組迭代法概述），（作任取初始向量.2 , 1 , 0.)()1()1()2()0()1()0(kGGGfxxfxxfxxx

16、kk解線性方程組迭代法概述的解。也是的解，同時(shí)為方程組即則或即是收斂的若向量序列bAxGGfxxxfxxxxxxxkkkkk*)(*)()(0|limlim解線性方程組迭代法概述。其中，所以即改寫為則方程非奇異其中令唯一解設(shè)方程組綜上所述bMfNMfGxxNMNMMNMAxxxbxxbxxn11T*2*1*,G)2 . 6 . 3()() 1 . 6 . 3(,),.,() 1 . 6 . 3(:解線性方程組迭代法概述的解。組為方程是收斂的，且則稱迭代格式若的右端得代入方程任取初始向量) 1 . 6 . 3() 3 . 6 . 3(lim) 3 . 6 . 3(,.)2 , 1 , 0()2

17、. 6 . 3(),.,(*)()()1(0)0(2)0(1)0(xkGxxxxxfxxxkkkkTn3.6.2 Jacobi迭代法和Gauss-Seidel迭代法nnnnnnnnnnnnnnnnniibbbxxxaaaaaaxxxaaabbbxxxaaaaaaaaaniaA.0.0.0.) 1 . 6 . 3(.),.,2 , 1(02121212211122122112121212222111211將其改寫成為非奇異矩陣且設(shè)Jacobi迭代法),.,2 , 1(/ )(,210.0.0211222111122222211111112njiijijiiJnnnnnnnnniaxabxGaba

18、babnxxxaaaaaaaaaanxxxfxx其分量形式得則Jacobi迭代法迭代法。稱其為為：而迭代序列的分量形式其迭代序列Jacbi,.,2 , 1/ )(,.2 , 1 , 01)(1)()1(nijjiikjiji)(kikJkniaxabxkfxGx例題05251101010210110201015352111021210Jacbi1 . 6 . 3321JGxxx解：因?yàn)榈仃嚍榈ń饩€性方程組試用例例題T)11(T)0()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1321321)0000. 3 ,0000. 2 ,0000. 1 (11)0 , 0 , 0(,

19、.1 , 021 . 02 . 05 . 11 . 02 . 03 . 01 . 02 . 025 . 13 . 004 . 02 . 01 . 002 . 01 . 02 . 00 xxkxxxxxxxxxxxxxxxkkkkkkkkk次有迭代到第取其迭代格式原方程改寫為Jacobi迭代法的矩陣形式bfJocbibxxbxxbxDULDGDULDULDULDULDaaaaaaaaaAJnnnnnnn1111111221212211, )()()(,)(0.0.00.00迭代矩陣為，因此所以即故有Jacobi迭代法的算法慢。算法的缺點(diǎn)：收斂速度。返回、停機(jī)；輸出、如果、計(jì)算、輸入初始向量、輸入

20、3),.,2 , 1(5),.,2 , 1(|max4);,.,2 , 1(/ )(3);,.,2 , 1(2;),.,2 , 1(),.,2 , 1,(11, 1niyxniyxyniaxabynixnibnjiaiiiiiniiinijjjijiiiiijGauss-Seidel迭代法。得，步由第依此類推；得同理由步第；代入迭代公式得由步第；由迭代公式解得步第設(shè)初值迭代法進(jìn)行修正對(duì))1()0()1(1)1(3)1(2)1(1)1(3)0()0(3)1(2)1(1)1(2)0()0(2)1(1)1(1)0()0(2)0(1,.,.,3,.,21,.,Jacobinnnnnnxxxxxxnxx

21、xxxxxxxxxxxGauss-Seidel迭代法bfbxxbxxbxxxLDULDGLDULDULDULDknixaxabaxsskkkijnijkjijkjijiiiki1111)() 1() 1(111)() 1() 1()()(SeidelGauss)()()(,.)1 , 0(),.,2 , 1()(1，迭代矩陣為因此故有所以矩陣形式：由于故將迭代法改寫成例題迭代法收斂速度快。顯然，次得，迭代到第取初值由解：法求線性方程組用例SGxxxxxxxxxxxkkkkkkkkkT)6(T)0()1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1)000. 3 ,000. 2

22、,000. 1 (6)0 , 0 , 0(24 . 02 . 05 . 11 . 02 . 03 . 01 . 02 . 0SeidelGauss1 . 6 . 3Gauss-Seidel迭代法的算法。停機(jī)；否則返回輸出、如果；做、對(duì)、輸入初始向量、輸入3),.,2 , 1(|max4;) 3;)2/ )() 1,.,2 , 13);,.,2 , 1(2;),.,2 , 1(),.,2 , 1,(11, 1nixeyxxyeaxbyninixnibnjiaiiniiiiiiiinijjiiiiiij3.6.3 線性方程組迭代法收斂條件1)(),.,(,(1 . 6 . 3*)(T)0()0(2

23、)0(1)0(GxxxGAxxxfxxbxkn的充要條件是收斂到方程組的解所產(chǎn)生的解向量序列向量對(duì)任意的初始的迭代格式組線性方程迭代法收斂基本定理）定理迭代法的收斂條件不收斂。不能肯定即不是必要條件收斂。但該條件所以這是因?yàn)椤Ｊ諗浚┧a(chǎn)生的序列則由式（若出一個(gè)充分條件。此我們給是一件很困難的事。因由于求1|, 1|)(3 .3.6, 1|)()()()(kkkxGxGGxGG迭代法的收斂條件迭代法收斂。；迭代法收斂迭代法收斂。；迭代法收斂由此得出SGGGSGGGSSJJ1|1)(Jacobi1|1)(Jacobi迭代法的誤差估計(jì))14. 6 . 3(|1|)13. 6 . 3(|11|1|,3

24、 .3.6, 1)0()1(*)()1()()1()(*)(*)(xxxxxxxxxxxxGGGGGGkkkkkkkk且有估計(jì)到方程組的解必收斂）產(chǎn)生的向量序列則迭代格式（有數(shù)如果對(duì)于任一種矩陣范推論迭代法的誤差估計(jì)|1|)1()(*)(*)()()1(*)()()1(*)1(*)1(*)(*)1()(kkkkkkkkkkkkkkxxGGxxxxGxxGxxxxGxxGGxGxxxGGfxxfxx所以兩式相減取范數(shù)，因?yàn)樽C明迭代法的誤差估計(jì))0()1()1()(*)()0()1(1)3()2(2)2()1()1()(|1|1|.|xxxxxxxxxxxxxxGGGGGGGkkkkkkkkkkk所以因?yàn)槭諗康呐袆e條件理。具有某些特性的判定定常給出系數(shù)矩陣很難求，因此，目前由于迭代矩陣的譜半徑估計(jì)迭代次數(shù)。）為事前估計(jì)，是預(yù)先而式（的停機(jī)標(biāo)準(zhǔn)）為事后估計(jì)，是計(jì)算式（A14.3.6;13.3.6收