數(shù)值分析向量,矩陣范數(shù),矩陣的條件數(shù).

1、 8向量，矩陣范數(shù)，矩陣的條件數(shù)、向量、矩陣范數(shù)為了討論線性方程組近似解的誤差估計(jì)與研究解方程組迭代法的收斂 性，需要在Rn（或Rnn）中引進(jìn)向量序列（或矩陣序列）極限概念。為此， 這就需要對(duì)量空間 Rn（或Rn n矩陣空間）元素的“大小”引進(jìn)某種度量即向量范數(shù)（或矩陣范數(shù)）即距離的概念。（一）向量范數(shù) :向量范數(shù)是 R3中向量長(zhǎng)度概念的推廣。Xi定義8 （1） cn =x x= ：xi為復(fù)數(shù)稱(chēng)為n維復(fù)向量空間。Xn= a a = G ）網(wǎng)為復(fù)數(shù)稱(chēng)為n n復(fù)矩陣空間。設(shè)x Cn, A Cn n ,稱(chēng)xH = （Xi，Xn）二xT為x的共軛轉(zhuǎn)置，HTA =A稱(chēng)為A共軛轉(zhuǎn)置矩陣。在許多應(yīng)用中，對(duì)向

2、量的范數(shù) （對(duì)向量的“大小”的度量）都要求滿足正定條件，齊次條件和三角不等式，下面給出向量范數(shù)的抽象定義。定義9（向量范數(shù)）關(guān)于向量x e Rn （或xE Cn）的某個(gè)實(shí)值非負(fù)函數(shù)N（x）三|x|，如果滿足下述條件（1）正定性 |x=0u n x=0齊次性|a*其中a e R（或a e C ）三角不等式 収+ y|W|x| +|y| Wx, y乏Rn（或乏Cn），稱(chēng)N（x）三|x是Rn上（或Cn） 一個(gè)向量范數(shù)（或?yàn)槟＃?。由三角不等式可推出不等式?）x|y| x - y下面給出矩陣計(jì)算中一些常用向量范數(shù)。定義10設(shè)X =(為，Xn) E Rn(或X壬CS(1)向量的“ o”范數(shù)n/x)三惻辺

3、=max Xin向量的“ 1”范數(shù) N,(x)三I*,=送xiTn向量的“ 2”范數(shù) n2(x)三|卷=(x,x)1/2 = (瓦xi 2)1/2i=1（4）向量的能量范數(shù)設(shè)A Rn n為對(duì)稱(chēng)正定陣xRn Na（x）二xA = （Ax,x）1/2稱(chēng)為向量的能量范數(shù)。定理 19| 設(shè)Rn（或 xCn），則 N/xhNzgNjx）是 Rn 上（或 Cn）的向量范數(shù)。證明只驗(yàn)證三角不等式：對(duì)任意 x,y Rn，則| x+y 2勻x2科 心利用哥西不等式：(x, yNIJy 2，則有x y 2 =(x y,x y) =(x, x) 2(x,y)(y, y)2 2X22 y：=(x2 y2)2定理20（

4、范數(shù)的等價(jià)性）|對(duì)任何x, y w Rn則（1）x； x2 - n x|：ML引Ml蘭阿X2 X 腫 xnx：xil證只證(1)。記xXjF hL=maxxiN2于是有岡孑2Xjn 0(當(dāng) k)k .7其中II .|7為向量的任一范數(shù)。證明只對(duì)v - :, v = 2證明。顯然有l(wèi)im x(k)k_)：:=x 二= |im Xj(k) -Xj= 0(i , ,n)0(當(dāng) k；u n lim x(k) x tin的某個(gè)非負(fù)實(shí)值函數(shù)N(A)三|A|，如果滿足下述條件：(1)正定性：A 0,且A =0= 是A = 0齊次性：|ctA 叫A,a E R(3)三角不等式：|a + B蘭制+|b|則稱(chēng)N(

5、A)是Rn n上的一個(gè) 矩陣范數(shù)(或模)。由于在許多應(yīng)用問(wèn)題中，矩陣和向量是相聯(lián)系的，現(xiàn)引進(jìn)一種矩陣的算子范數(shù)。它是由向量范數(shù)誘導(dǎo)出來(lái)的并且這種矩陣范數(shù)和向量范數(shù)是相容的，即-xRn,A Rn n不等式 Ax 一 A| x 成立。定義14(矩陣的算子范數(shù))設(shè)x e Rn,Ae Rn：且設(shè)有一種向量范數(shù)| X| v相應(yīng)的定義一個(gè)矩陣的非負(fù)函數(shù)N(A)= Av二 maxx=.Ox.RnAXvXv(最大比值),稱(chēng)N(A)為矩陣A的算子范數(shù)AXvXvF面驗(yàn)證三角不等式:Bv 乞 Av B=max xRn x P(A B)Xv定理2彳設(shè)lix v是Rn上的向量范數(shù)，貝y N(A)三|A|v是R詢上一個(gè)范

6、數(shù) 且滿足相容條件：(1) Ax vXv AB J Av BvA,B Rnn)證明由N(A)三|Av定義,可知有”或 Ax J Av XvA Rnn,x Rn)由于(A B)x AXv BxjAvXv BvX(A B)x(A B)XvXv勻 a|v+|b|v，(WxE R% X)故IA + B|v 蘭|A|v+|冋v|Ax|車(chē)nA “ = max=max 瓦aii1g “1j J稱(chēng)為A的行范數(shù)）n定理23 （矩陣范數(shù)公式）設(shè)x Rn, A Rnn，則網(wǎng)max骨max叨（稱(chēng)為A的列范數(shù)）A 2 = max X-=max(ATA)(稱(chēng)為 A 的 “ 2” 范數(shù))X 2其中max （ A A）為A

7、A最大特征值。證明證(1):記 X=(Xi,Xn)T ,|x=max Xi| =tnn4 =max送同| =送|aij (其中1蘭io蘭n)-jj =inn送 ajXj max送 代唏_ jmaijXjj#于是 IIACmsxEtmaxZ aij =ti j#說(shuō)明，對(duì)任何向量 x=O，則有AxL：X :如果能找到一向量x0且x0 :廠1使那末，定理得證。F面來(lái)尋求Xo使比值等于 豈，記Xo =（Xi,X2，,Xn）T且使| Xo| = 1nnn曰是，AxoaXj,aiojXj,anjXj)Tjjj且由(a)式有 Ax。：1,當(dāng) aij 色0 由此，應(yīng)選取X0為：Xj =.-1，當(dāng) aij :i

8、 ii d特征值為，i(i =1,1,，n)，則有r 一匕一一厶- 0 且有Ui： 滿足 ATA5MV =1,2,n ),4,5)=“考查比值：nX R 且 x0，于是 xaiuii=1nnM2T(/ iui，/ 衛(wèi) iUi )_2 (Ax,Ax) (ATAx,x)(x,x)(x,x)n 2 :-ii An 2 :-ii =1說(shuō)明，對(duì)任何非零向量 X Rn，則有Ax1IWL另一方面，取x1則有上心一衛(wèi)皿U1(U1,U1)故 A 2 = max(A A)定理24 (矩陣范數(shù)等價(jià)性)設(shè)A Rn馮，則設(shè)I -B為奇異陣，則曰是,2)由(I -B)(I -B)，-I1 _ 1比勻IA2 蘭 JnllA

9、Q.nn定義25（矩陣的譜半徑）設(shè)Aw R網(wǎng)的特征值為 扎（i =1,，n），稱(chēng)P（A）三max入為A的譜半徑。定理25 （特征值界）（1）設(shè)A ，則P（A）勻A，其中IA為滿足矩陣，向量相容性條件 的矩陣范數(shù)。設(shè)A Rn n為對(duì)稱(chēng)矩陣，則| A 2 =（A）。證明只證（1）。設(shè)為A的任一特征值，于是，存在x = 0使Ax二，x且內(nèi) MFIM = Ax 蘭|A|x|即園 |xi或 p（a）|A定理26 設(shè)卄為矩陣的算子范數(shù)，且|B| 1,則I B為非奇異矩陣，且有估計(jì)（I _B）證明1）反證法。（I - B）x = 0有非零解記為x0，即Bx0二x0B -1，這與假設(shè)矛盾。即得(I B)v =

10、1 B(l B)斗從而IN -B）|印1+剛（I訂（I -B）*詁可矩陣的條件數(shù)、病態(tài)方程組直接法的誤差原因：1 算法及舍入原因2 方程組本身固有的問(wèn)題要分析方程組的狀態(tài)并估計(jì)算法的誤差（原始數(shù)據(jù)擾動(dòng)對(duì)解的影響）- 量度：矩陣的條件數(shù)【引例】設(shè)方程組1 1卜=精確解為x = 2. 占 1.0001 一x2 一 X。a=1 1;1 1.0001;b=2,2;ab對(duì)右端項(xiàng)作微小變化（小擾動(dòng)）：J1irxj ?甘出弘卩1=其中6b =1 1.0001 上2 一2.0001 一0.0001 一a=1 1;1 1.0001;b=2,2.0001;ab顯然有，X * x-20150.0011312102二

11、 0.0186【說(shuō)明】 右端常數(shù)項(xiàng)的相對(duì)誤差 弊蘭IlbL0.00012= 0.5 10*12二 0.5常數(shù)項(xiàng)的微小誤差引起解的相對(duì)誤差較大，擴(kuò)大了 10*倍，也就是說(shuō)，此方程組解對(duì)方程組的數(shù)據(jù) A,b非常敏感,這樣的方程組就是 病態(tài)方程組.設(shè)線性方程組為Ax=b (1)其中A Rxn,x,b 哎且A非奇異。x* :準(zhǔn)確解，S x :解的誤差，即、X = X - X (2)S A-A的誤差，S b-b的誤差。討論S x與S A, S b的關(guān)系(一)b有誤差而A無(wú)誤差情形將帶有誤差的右端項(xiàng)和帶誤差的解向量代入方程組，則A(x丄說(shuō)=b b ( 3)由于Ax*三b，而得到6x = A6b,從而x|另

12、一方面，由,(b = 0)(1)式取范數(shù)，有|制蘭|A | x或pfnllbll可得【定理27】設(shè)A是非奇異矩陣, 差估計(jì)式Ax=bz 0,且 A (x + S x) =b+ S b 則有誤乞 cond (A)其中cond (A) A | A稱(chēng)為方陣A的條件數(shù)。說(shuō)明：1、解的相對(duì)誤差是右端項(xiàng) b的相對(duì)誤差的cond(A)倍2、如果條件數(shù)很大，則解的誤差將成倍增長(zhǎng)?！径x】 稱(chēng)條件數(shù)很大的矩陣為“病態(tài)”矩陣；稱(chēng)病態(tài)矩陣對(duì)應(yīng)的方程組為病態(tài)方程組。反之，則稱(chēng)A為良態(tài)矩陣。(二)A及b都有誤差的情形【定理28】設(shè)在方程組Ax=b中，A及b都有誤差，且|A | |pA 1，則有 IIcon d（A）網(wǎng)陽(yáng)

13、】II All證：帶有誤差的方程組為（A、A）（x 、x）=b 、b （5）由于Ax三b，因而（A 、A）、x 、Ax* 二、b （ 6）為從（6）式中解出3 x，必須限定（A+ S A） -1存在。從而x = （A、A）（b- x*） （ 7）利用A ；A二A（E A J A），得到(A A) =(E AJ A) JAJ又由定理26知，當(dāng)“A 1時(shí)(E A4 A)4|1(9) 1,-1cond(A)=cond(A ),cond(cA)=cond(A)(c 豐 0,c R)4. 若U為正交矩陣，即 UTU=I，貝U cond(U) 2=1 對(duì)非奇異矩陣 A,cond(A) 2=cond(UA)

14、 2=cond(AU) 2（四）病態(tài)方程組病態(tài)方程組的判可設(shè)Ax=b, A Rnxn,且A非奇異當(dāng)cond（A）1,則Ax=b是病態(tài)方程組（壞條件的，A是病態(tài)的）當(dāng)cond（A）相對(duì)較小時(shí)，則Ax=b是良態(tài)方程組（好條件的，A是良態(tài)的）【例】在引例方程組中，b有擾動(dòng)、巾=(0, 0.0001) T，試計(jì)算cond(A) g,并說(shuō)明對(duì)解向量x的影響。a=1 1;1 1.0001;b=2;2;no rm_b=no rm(b,i nf);detb=0;0.0001 ;n orm_detb=norm(detb,i nf);err_b=n orm_detb/norm_bcon d_a=c on d(a,

15、i nf)err_x=err_b*c ond_a；廣叫A) 4.0004 104 牆 2 200%【例】希爾伯特矩陣的條件數(shù)：con d(hilb(2),co nd(hilb(3),co nd(hilb(5),co nd(hilb(8)a=hilb(3),b=o nes(3,1);ab a =1.0000 0.5000 0.3333;0.5000 0.33330.2500;0.3333 0.25000.2000+0.000001;b=o nes(3,1);ab【注】(1)由矩陣條件數(shù)性質(zhì)可知，正交矩陣的線性方程組Ax二b是好條件的；(2) 條件數(shù)性質(zhì)4指出，正交變換保持條件數(shù)Cond (A)不

16、變，這說(shuō)明在很多方法中使用正交矩陣約化矩陣的合理性。設(shè)有方程組Ax=b，其中A Rnn為非奇異，x為精確解，又設(shè)X為計(jì)算解。一般，計(jì)算剩余向量r二b - Ax，用r大小來(lái)檢驗(yàn)計(jì)算解的精度，是否r很小，x就是Ax二b 個(gè)較好的近似解呢?【定理29】|(事后誤差估計(jì))(1)設(shè)A為非奇異矩陣,x是精確解，即 Ax二b = 0。設(shè)x是方程組一個(gè)近似解，r二bAx，則近似解x的相對(duì)誤差有估 計(jì)式|r|xnd(A)b證明 由 x-x = Ab-x = A，(b - Ax)二 Ar所以|x _x| W| A| |r| (12)另一方面，由Ax =b，有x即AA(13)由(12)及(13)式，則X -X|x|

17、說(shuō)明近似解x精度(誤差界)不僅依賴(lài)于剩余 的條件數(shù)，當(dāng)A是病態(tài)時(shí)，即使有很小的剩余, 的近似解。r “大小”，而且依賴(lài)于 A 也不能保證 x是高精度三、關(guān)于病態(tài)方程組的解法Ax =b , A- Rn n非奇異矩(一)判斷Ax=b是病態(tài)方程組(1) 當(dāng)A的行列式相對(duì)來(lái)說(shuō)很小，或A某些行(或列)近似線性相關(guān)，方程組Ax=b可能病態(tài)(2) 如果用選主元消去法求解Ax二b,在A約化中出現(xiàn)小主元，方程組Ax=b可能病態(tài)(3) 當(dāng)系數(shù)矩陣A元素?cái)?shù)量級(jí)相差很大，并且無(wú)一定規(guī)則時(shí)，方程組Ax=b可能病態(tài) 估計(jì)條件數(shù)由于Co nd (A)二二A ：一，所以發(fā)現(xiàn)Ax =b病態(tài)的可靠方法是計(jì)算 A的條件數(shù)，若直接計(jì)

18、算AJ再計(jì)算| A，滬,那末求A，大約需要n3 2n2次乘法運(yùn)算,為求解(用直接法)Ax = b計(jì)算量的3倍，代價(jià)太高一個(gè)矩陣條件數(shù)的估計(jì)方法：由于max匚 J y 770:二 max w：:(令 A=y 二 w ,由解 Aw = y 求 y-0 y：w)因此 |AL-l/lyl選擇向量y Rn且求解Aw =y使產(chǎn)生大的解w.于是Con d（AQ|A*A|AW/yb【注】方法成功的關(guān)鍵在于怎樣使比值 |wj/|yb接近它的極大值|a|瀘（二）病態(tài)方程組的解法對(duì)于病態(tài)方程組 Ax二b,當(dāng)我們用一般方法求解時(shí)，僅由舍入而產(chǎn)生的誤差也會(huì)使我們算不出比較滿意的解，此時(shí)可采用下述方法求解1采用高精度的算

19、術(shù)運(yùn)算例如,采用雙倍字長(zhǎng)進(jìn)行運(yùn)算，或用雙字長(zhǎng)求內(nèi)積等，以此改善和減輕 矩陣病態(tài)的影響，其缺點(diǎn)是計(jì)算時(shí)間將大為增加 2采用預(yù)處理方法求解Ax二b =求解：尋求非異矩陣P，Q使1PAQ（Q x） = Pb或Ax = b其中A = PAQ，X = Qx，b = Pb且改善A的條件數(shù)，Con d（PAQ） :Co nd （A）于是，可用數(shù)值穩(wěn)定方法求解 Ax = b，再求x = Qx，當(dāng)A為對(duì)稱(chēng)正定陣時(shí)一般選擇P，Q為對(duì)角陣或三角矩陣3平衡方法當(dāng)系數(shù)矩陣A元素?cái)?shù)量級(jí)差別很大，威爾金森提出采用行均衡方法，這 時(shí)矩陣A條件數(shù)可能得到改善行（或列）均衡：就是解方程組Ax = b之前首先將a的行（或列）大體 均衡一下，即對(duì)Ax = b每一行（或每一列）乘以適當(dāng)?shù)臄?shù)，使所有行（列）按 照某種范數(shù)大體上有相同的長(zhǎng)度 設(shè)Ax = b，其中A Rn n為非奇異陣.計(jì)算令 D4 二diag（1/3,1/S2，1/&）1 1 于是求解Ax = b =求解D Ax=D b或Ax = b.這時(shí)A = DJA條件數(shù)可能得到改善，再用列主元消去法或部分選主元三角分解法求解 Ax二b .設(shè)有