六范數(shù)與極限PPT課件

1、.,1,第6章 范數(shù)與極限 （ norm and limit） 理解向量范數(shù)、矩陣范數(shù)的概念; 掌握幾種常用的范數(shù)； 理解范數(shù)等價(jià)的定義，了解矩陣的譜半徑及其性質(zhì)。了解矩陣序列與極限的概念。 了解矩陣的冪級(jí)數(shù)并掌握斂散性的基本判別方法。,.,2,對(duì)于n 維線(xiàn)性空間，定義了內(nèi)積以后，向量就有了長(zhǎng)度（大?。?、角度、距離等度量概念，這顯然是3維現(xiàn)實(shí)空間中相應(yīng)概念的推廣。利用公理化的方法，可以進(jìn)一步把向量長(zhǎng)度的概念推廣到范數(shù)。,.,3,1 向量范數(shù),定義1：設(shè)V 是數(shù)域P上的線(xiàn)性空間， V， 表示以為自變量的的非負(fù)實(shí)值函數(shù)，如果它具有下列性質(zhì)：,（3）三角不等式：即對(duì)任意兩個(gè)向量，V，恒有,(1) 非

2、負(fù)性：當(dāng) 0, 0，當(dāng)=0時(shí)，=0,(2) 齊次性：即對(duì)任何實(shí)數(shù)kP，V，,則稱(chēng)為向量的范數(shù)，并稱(chēng)定義了范數(shù)的空間為賦范線(xiàn)性空間,.,4,Cn中幾個(gè)常用范數(shù)：,（1）1-范數(shù),（2）2-范數(shù),（3）-范數(shù),設(shè)x = (x1, x2, xn)TCn,則在Cn上定義范數(shù),.,5,關(guān)于p-范數(shù),定理1 Holder不等式,定理3 對(duì)任意向量x，由（*）式定義的|x|p是向量范,數(shù)，且有,1-范數(shù),2-范數(shù),-范數(shù)都是p-范數(shù)的特殊情形；,定理2 Minkowski不等式,（*）,.,6,幾何意義:,對(duì)任意 ,對(duì)應(yīng)于四種范數(shù)1,2,p的閉單位圓 |x|=1 的圖形分別為,注：內(nèi)積空間定義的向量長(zhǎng)度等于

3、這里的2-范數(shù)，稱(chēng)為由內(nèi)積導(dǎo)出的范數(shù)，但范數(shù)不一定都是由內(nèi)積導(dǎo)出的。,.,7,由已知的范數(shù)構(gòu)造新范數(shù)： 定理4 設(shè)| 是Cm上的向量范數(shù)， ACmn且rank(A)=n,則由 |x| = |Ax|， xCn 所定義的非負(fù)函數(shù)|是Cn上的向量范數(shù)。,構(gòu)造新范數(shù),.,8,定理5：有限維線(xiàn)性空間V上的任意兩個(gè)向量范數(shù)等價(jià)。,稱(chēng)范數(shù)|x| ，|x| 等價(jià)。,定義2：在n維線(xiàn)性空間V上定義兩個(gè)向量范數(shù)|x| ，|x| ，若存在兩個(gè)正常數(shù) M 與 m ( Mm ) 使得對(duì)一切xV，,注 這個(gè)結(jié)論對(duì)無(wú)限維未必成立。另外，根據(jù)等價(jià)性，處理向量問(wèn)題（例如向量序列的斂散性）時(shí)，我們可以基于一種范數(shù)來(lái)建立理論，而使

4、用另一種范數(shù)來(lái)進(jìn)行計(jì)算。,等價(jià)范數(shù),.,9,對(duì)常用范數(shù)，容易驗(yàn)證下列不等式：,.,10,例1 計(jì)算C4的向量x=(3i,0,-4i,-12)T 的1,2,范數(shù)。 解：|x|1=|3i|+|-4i|+|-12|=19 |x|2=(xHx)1/2=(3i)(-3i)+(-4i)(4i)+(-12)21/2=13 |x|=max(|3i|,|0|,|-4i|,|-12|)=12 注：在同一線(xiàn)性空間中,不同定義的范數(shù)大小可能不同,.,11,對(duì)任意，V，定義與之間的距離為 d(，)=|-| 稱(chēng)為由范數(shù)|決定的距離。,常用距離測(cè)度包括:,歐氏距離 Manhattan(曼哈頓)距離 Chebyshev(切比

5、雪夫)距離,距離,.,12,例（模式識(shí)別中的模式分類(lèi)問(wèn)題）,模式分類(lèi)問(wèn)題指的是根據(jù)已知類(lèi)型屬性的觀測(cè)樣本的模式向量s1 ,sm，判斷未知類(lèi)型屬性的模式向量x歸屬于哪一類(lèi)模式。其基本思想是根據(jù)x與模式樣本向量si的相似度大小作出判斷。 最簡(jiǎn)單的方法是用兩向量之間的距離來(lái)表示相似度，距離越小，相似度越大。最典型的是Euclidean距離:,.,13,定義4 設(shè)x(k)是Cn中的向量序列，其中 x(k)=(x1(k)，x2(k)，,xn(k)T,如果當(dāng)k時(shí)，x(k)的每一個(gè)分量xi(k)都有極限xi(i=1,2,n),則稱(chēng)向量序列x(k)是收斂的，并且向量x=(x1，x2，,xn)T稱(chēng)為x(k)的極

6、限，記為,注 不同的向量范數(shù)可能具有不同的大小，但在各種范數(shù)下，向量序列的收斂問(wèn)題卻表現(xiàn)出簡(jiǎn)潔性和一致性。,向量序列的極限,.,14,定理3：向量序列xk依坐標(biāo)收斂于x*的充要條件是,向量序列依范數(shù)收斂與依坐標(biāo)收斂是等價(jià)的。,注：若賦范線(xiàn)性空間中任一收斂的向量序列的極限仍屬于此賦范線(xiàn)性空間，稱(chēng)此空間為完備的賦范線(xiàn)性空間或Banach空間。,我們常根據(jù)不同的要求選擇一種方便的范數(shù)來(lái)研究向量序列的收斂性問(wèn)題。,.,15,1. （廣義）矩陣范數(shù) 定義1（廣義）矩陣范數(shù) 設(shè)ACmn，定義一個(gè)實(shí)值函數(shù)|A|，若滿(mǎn)足：,(1) 非負(fù)性：|A|0，且|A|=0當(dāng)且僅當(dāng)A=0；,(2) 齊次性：|aA|=|a

7、| |A|，aC；,(3) 三角不等式：|A+B|A|+|B|，A,B Cmn;,則稱(chēng)|A|為A的廣義矩陣范數(shù)。,2 矩陣范數(shù),.,16,例1 對(duì)于A=(aij)Cmn,都是廣義矩陣范數(shù)， 稱(chēng)為Frobenius范數(shù)，簡(jiǎn)稱(chēng)為F-范數(shù)。,.,17,定理1（等價(jià)性定理）：| 與| 是Cmn,上的矩陣范數(shù)， 則存在僅與| ，|有關(guān)的正數(shù)d1 ，d2 ， 使得ACmn ，,即| 與|等價(jià)。,.,18,2.相容矩陣范數(shù) 考慮到矩陣乘法運(yùn)算的重要性，加入相容性條件。,定義2 對(duì)任意兩個(gè)n階矩陣A、B，有,則稱(chēng)矩陣范數(shù)|是相容范數(shù)。,.,19,定義2包含了矩陣范數(shù)與向量范數(shù)的相容性定義： 例如矩陣的F-范數(shù)

8、與向量的Euclid范數(shù)相容： 即 |Ax|2|A|F |x|2,例1中的m1-范數(shù)，F(xiàn)-范數(shù)都是相容范數(shù)； 注意，m不具備相容條件；,定理4：設(shè)| 是Cmn上的相容矩陣范數(shù)，則在Cn存在與之相容的向量范數(shù)。,.,20,矩陣不僅僅是向量，它還可以看成變換或算子。 實(shí)際中，從算子或變換的角度來(lái)定義范數(shù)更加有用。 下面對(duì)給定的向量范數(shù)，定義與之相容的矩陣范數(shù),3.算子范數(shù),.,21,定義3：設(shè)| 與| 分別是Cm與Cn上的兩個(gè)向量范數(shù)， 對(duì)ACmn ，令,則|,是Cmn上的矩陣范數(shù)，且和| 與|相容， 即|AX| |A|, |x| 稱(chēng)該矩陣范數(shù)為Cmn上的算子范數(shù)或由向量范數(shù)| 與| 誘導(dǎo)出的矩陣

9、范數(shù)。,定理5 Cnn的算子范數(shù)是相容矩陣范數(shù)；,.,22,定理6：設(shè)n 階方陣A = (aij)nn，則,（）與 相容的矩陣范數(shù) 列和-范數(shù),（）與 相容的矩陣范數(shù) 譜范數(shù),（）與 相容的矩陣范數(shù) 行和范數(shù),即矩陣的1-范數(shù)，譜范數(shù)，-范數(shù)都是由相應(yīng)的向量范數(shù)導(dǎo)出的矩陣范數(shù)。,.,23,注：矩陣的m1-范數(shù)，m-范數(shù)，F(xiàn)-范數(shù)不是算子范數(shù)(可由單位矩陣驗(yàn)證),但F-范數(shù)的優(yōu)點(diǎn)是當(dāng)A左乘或右乘酉矩陣后F-范數(shù)的值不變（酉不變性），所以F-范數(shù)也是常用的范數(shù)之一.,.,24,注2：譜范數(shù)雖然不便于計(jì)算，但它有很多好性質(zhì)：,對(duì)于m階酉矩陣U和n階酉矩陣V，有 |UAV|2=|A|2 （5）,.,2

10、5,例 S=xP2 | |x|p=1 在矩陣 作用下的效果分別為,.,26,.,27,注：矩陣范數(shù)和特征值有個(gè)很重要的關(guān)系 定理7 對(duì)任意的矩陣ACnn，總有 (A)|A| 其中，(A)是A的譜半徑。 即A的譜半徑不會(huì)超過(guò)A的任何一種范數(shù)。,.,28,計(jì)算 ， ， 和 。 解,例1,因?yàn)?所以,.,29,補(bǔ)充：Hilbert空間,定義 完備的內(nèi)積空間V稱(chēng)為Hilbert空間，記作H 即內(nèi)積空間V按距離,是完備的，亦是Banach空間。,完備空間：一個(gè)度量空間中的任何Cauchy列都收斂在該空間內(nèi)，稱(chēng)該空間是完備的； 直觀上講，一個(gè)空間完備就是指“沒(méi)有孔”且“不缺皮”，兩者都是某種“不缺點(diǎn)”。沒(méi)

11、有孔是指內(nèi)部不缺點(diǎn)，不缺皮是指邊界上不缺點(diǎn)。,設(shè)xn是度量空間中的向量序列，如果對(duì)于任意的0，存在自然數(shù)N，當(dāng)m,nN時(shí)，d(xm,xn)，稱(chēng)xn是一個(gè)Cauchy列。,.,30,補(bǔ)充：Hilbert空間,Hilbert空間是有限維歐幾里得空間向無(wú)窮維的推廣；完備性使得微積分中的大部分概念都可以無(wú)障礙地推廣到希爾伯特空間中。希爾伯特空間為基于任意正交系上的多項(xiàng)式表示的傅立葉級(jí)數(shù)和傅立葉變換提供了一種有效的表述方式。,.,31,舉例,例1 在n維（實(shí)或復(fù)數(shù)）向量空間Rn中，,范數(shù),按范數(shù)是完備的內(nèi)積空間，即Hilbert空間。,定義內(nèi)積,.,32,在,中，,定義內(nèi)積,（滿(mǎn)足三條公理）,，則,按范

12、數(shù)是完備的內(nèi)積空間Hilbert空間,例2,范數(shù),L2a,b指的是平方可積函數(shù)的集合，按照函數(shù)的加法和數(shù)乘構(gòu)成線(xiàn)性空間：其一組基最常用的是三角函數(shù)系,.,33,例3 在,定義內(nèi)積,（滿(mǎn)足三條公理）,l 2是Hilbert空間。稱(chēng)為平方可和空間,范數(shù),.,34,是內(nèi)積空間U中的標(biāo)準(zhǔn)正交基,則對(duì)于xU,，x在M上的投影,并且,標(biāo)準(zhǔn)正交基的性質(zhì),1.設(shè),通常稱(chēng),x0的長(zhǎng)度,為Bessel不等式。 即x在M上的投影,.,35,2.推廣到無(wú)窮維：,是U中的標(biāo)準(zhǔn)正交基，則對(duì)xU有,設(shè),.,36,3.最佳逼近定理 設(shè) 是U中的標(biāo)準(zhǔn)正交基， xU， 則對(duì)于任意 一組數(shù)， 恒有 （*）,.,37,該定理說(shuō)明：U

13、中的任意元x，當(dāng)用,作有限維線(xiàn)性組合去逼近時(shí)，以,為最好逼近元，其中線(xiàn)性組合系數(shù)(x,ei ),可見(jiàn)在有限維線(xiàn)性子空間M中求U中x的最佳逼近元等同于求投影。,稱(chēng)為Fourier系數(shù)。,.,38,標(biāo)準(zhǔn)正交基的完全性及完備性,是內(nèi)積空間U中的標(biāo)準(zhǔn)正交基, 當(dāng)且僅當(dāng),時(shí)，,則稱(chēng)L=ei是完全的。,1.定義 設(shè),（1）若對(duì)于xU,此式稱(chēng)為巴塞弗（Parseval）等式，也稱(chēng)為廣義“商高定理”,（2）若對(duì)于xU，都有,則稱(chēng)L=ei是完備的。,.,39,.,40,定理2 H空間中任意兩個(gè)完全標(biāo)準(zhǔn)正交基,和,具有相同的基,之間存在一一對(duì)應(yīng)的關(guān)系）。,（即,.,41,定理3 無(wú)窮維H空間可分的,H中存在完全標(biāo)

14、準(zhǔn)正交基。,注：H可分：在H中存在可數(shù)子集D，使得H中的每個(gè)元素都是D中元素序列的極限。,.,42,定理4 無(wú)窮維可分的H空間必與l 2空間線(xiàn)性及內(nèi)積同構(gòu)。 即：存在H到l 2的一一映射 ，使其保持線(xiàn)性運(yùn)算及 內(nèi)積相等，即,例如：可取,則是由H到l 2的一一映射，并且H與l 2線(xiàn)性及內(nèi)積同構(gòu)。,.,43,特別的，當(dāng)H中的完全標(biāo)準(zhǔn)正交基為有限集,時(shí)，則H與R n同構(gòu)，可取映射,由此可知，歐氏空間R n可看作有限維H空間的模型，平方可和空間l 2可以看作無(wú)限維H空間的模型。從而把對(duì)可分的H空間的研究轉(zhuǎn)化為對(duì)Rn或l 2的研究。 例如： 是可分的H空間，要研究 中的函數(shù)，只要研究該函數(shù)的傅立葉系數(shù)就

15、夠了。,.,44,根據(jù)模式識(shí)別理論，低維空間線(xiàn)性不可分的模式通過(guò)非線(xiàn)性映射到高維特征空間則可能實(shí)現(xiàn)線(xiàn)性可分，但是如果直接采用這種技術(shù)在高維空間進(jìn)行分類(lèi)或回歸，則存在確定非線(xiàn)性映射函數(shù)的形式和參數(shù)、特征空間維數(shù)等問(wèn)題，而最大的障礙則是在高維特征空間運(yùn)算時(shí)存在的“維數(shù)災(zāi)難”。采用核函數(shù)技術(shù)可以有效地解決這樣問(wèn)題。,SVM,.,45,設(shè)x,zX,X屬于R（n）空間,非線(xiàn)性函數(shù)實(shí)現(xiàn)輸入空間X到特征空間F的映射,其中F屬于R（m）,n (1) 其中：為內(nèi)積,K(x,z)為核函數(shù)。從式(1)可以看出，核函數(shù)將m維高維空間的內(nèi)積運(yùn)算轉(zhuǎn)化為n維低維輸入空間的核函數(shù)計(jì)算，從而巧妙地解決了在高維特征空間中計(jì)算的“

16、維數(shù)災(zāi)難”等問(wèn)題，從而為在高維特征空間解決復(fù)雜的分類(lèi)或回歸問(wèn)題奠定了理論基礎(chǔ)。 如何定義K(x,z)？ mercer定理：充要條件K(x,z)是對(duì)稱(chēng)半正定矩陣,.,46,由于n階矩陣可以看成nn向量，所以矩陣序列的收斂問(wèn)題可以和向量序列的收斂問(wèn)題一樣考慮。,3 矩陣序列與矩陣級(jí)數(shù),定義1 設(shè)矩陣序列A (k) ，其中,如果mn個(gè)數(shù)列 都收斂，則稱(chēng)矩陣序列 A (k) 收斂。 進(jìn)一步，如果 那么我們稱(chēng)矩陣 為矩陣序列 的極限。 記為,.,47,例1,.,48,定理1 矩陣序列 收斂于A的充分必要條件是 其中 為任意一種矩陣范數(shù)。,.,49,（1）一個(gè)收斂的矩陣序列的極限是唯一的。 （2）設(shè),矩陣

17、序列的極限運(yùn)算性質(zhì),（5）設(shè) ，且 ，A均可逆，則 也收斂，且,則 （3）設(shè) 其中 則 （4）設(shè) ，其中 則,.,50,定義 設(shè),如果有,，則稱(chēng)A為收斂矩陣。,則 的充分必要條件為,定理6.3.2 設(shè),推論 設(shè),如果存在 上的相容矩陣范數(shù)使,則有,方陣的冪構(gòu)成的序列,.,51,例2 判斷矩陣是否為收斂矩陣,解：由 知A為收斂矩陣。,注意： 是矩陣A為收斂矩陣的充分條件，不是必要條件。,即：矩陣A的范數(shù)都大于1，該矩陣也有可能是收斂矩陣。,.,52,由 中的矩陣序列 構(gòu)成的無(wú)窮和 稱(chēng)為矩陣級(jí)數(shù)，記為 ，,若由矩陣級(jí)數(shù)的部分和構(gòu)成的矩陣序列 收斂，且有極限S,即 ，則稱(chēng)矩陣級(jí)數(shù) 收斂，且有和S。 記為:,為矩陣級(jí)數(shù)的部分和。,稱(chēng):,定義1,矩陣級(jí)數(shù),不收斂的矩陣的級(jí)數(shù)稱(chēng)之為發(fā)散的。,.,53,3.若矩陣級(jí)數(shù) 收斂（或絕對(duì)收斂），則 矩陣級(jí)數(shù) 也收斂（或絕對(duì)收斂）， 并且有:,2.設(shè) ， ,則,(1),(2),1. 中的矩陣級(jí)數(shù)收斂相當(dāng)于C上的 個(gè)級(jí)數(shù)都收斂,n,.,54,定理1 矩陣級(jí)數(shù) ，若對(duì)某一個(gè)矩陣