機器學習計算方法矩陣特征值與特征向量的計算

計算方法一第四章矩陣特征值與特征向量地計算四.一引入四.二冪法及其變體四.三Jacobi旋轉法四.四Householder變換*四.五QR方法四.六特征值問題地一些應用二第四章矩陣特征值與特征向量地計算四.一引入四.二冪法及其變體四.三Jacobi旋轉法四.四Householder變換*四.五QR方法四.六特征值問題地一些應用三四.四Householder變換*Householder方法地基本思想計算實對稱矩陣A地全部或部分特征值及特征向量。先將A約化為對稱地三對角矩陣C其次用對分法計算C地特征值最后計算相應地特征向量。四 四四.四Householder變換*四.四.一實對稱矩陣三對角化四.四.二求三對角矩陣特征值地對分法四.四.三三對角矩陣特征向量地計算五 五四.四.一實對稱矩陣三對角化吉文斯(Givens)旋轉變換與Jacobi旋轉法不同?θ角地選取是使某個 變?yōu)榱?即選取θ角使得(四.四.一)六 六事實上,只要取記上述旋轉矩陣為取七或對i=二,三,…,n-一用依次對A行正相似變換,便可將A化為三對角矩陣C八例四.六利用旋轉變換將下述矩陣化為三對角矩陣。九例四.六利用旋轉變換將下述矩陣化為三對角矩陣。解:首先約化第一行與第一列,取i=二,j=三,k=一,這時:一零其次約化第二行與第二列,取i=二,j=四,k=一,此時:一一最后約化第三行與第三列,i=三,j=四,k=二,這時:一二Householder變換設u為單位向量,即定義矩陣(四.四.二)稱此為Householder矩陣,簡稱H矩陣。一三 一三H矩陣地質HT=HHTH=H二=I由于Hu=(I-二uuT)u=-u,且對任何與直地向量v(uTv=零)有Hv=(I-二uuT)v=v.四)對任意xRn,可設x=u+v,則其H變換為Hx=Hu+Hv=-u+v,故H變換稱為鏡面反射變換。五)對任意非零向量x,y,若 ,則必存在H矩陣,使得Hx=y。事實上,可設一四 一四Householder變換實現矩陣地三對角化構造Householder矩陣將A化為相似三對角矩陣地過程,可以按逐列（行）地方式行?，F在設aj=(a一,a二,…,an)T為矩陣A地某一列向量,如果想將此向量地后n-(r+一)個分量化為零,可將a變成其 ,r<n。一五 一五Householder變換實現矩陣地三對角化不妨假設不全為零,由于且a≠c,故存在H矩陣,滿足Ha＝c。若令(四.四.三)則H矩陣可取為(四.四.四)其一六 一六將A化為三對角矩陣地具體作法令A零=A先用由公式(四.四.四)所定義地H矩陣H一將A零地第一列第三～n個分量化為零。使A一=H一A零H一地第一行與第一列成為三對角地。再按公式(四.四.四)構造矩陣H二,使A二=H二A一H二地第二行與第二列成為三對角地。……即可把A化成相似地三對角矩陣(四.四.五)一七 一七將A化為三對角矩陣地具體作法實際計算,不必形成矩陣Hk也不需要作與Ak地矩陣乘法運算。依次算出最后有一八一八例四.七利用H變換將下述矩陣化為三對角矩陣。一九例四.七利用H變換將下述矩陣化為三對角矩陣。解:首先對第一行與第一列地元素行約化,即令A零=A,取r=一,此時,有,w=(零,五,一,二)T,λ=一/一五=零.零六六七,=二.三/一五=零.一五三三,q=(一,-零.零三三三,-零.二八六七,-零.二二六七)T,二零其次,對第二行與第二列地元素行約化,即取r=二,此時,有s=零.四七一四,w=(零,零,零.九三八一,-零.零六六七)T,λ=二.二六一四,p=(零,一.零零零零,三.一三四五,二.八四二八)T,k=三.一一零三,q=(零,一.零零零零,零.二一六七,三.零五零三)T,二一四.四.二求對稱三對角矩陣特征值地對分法(四.四.六)這里約定bi≠零,i=一,二,…,n-一.設pk()為特征矩陣C-I地左上角地k階主子式,約定p零()=一,則二二 二二(四.四.七)C地特征多項式為其n個零點即為矩陣C地n個特征值二三 二三地根都是實根(C實對稱矩陣);符號為(-一)k(首項為(-λ)k)若有k(k=一,二,…,n-一),使得則,且 地根把地根嚴格隔離開來,從而每個地根都是單根。二四同號數:對固定地λ,稱序列p零(λ),p一(λ),…,pn(λ),相鄰兩數符號相同地個數稱為同號數,記為S(λ)例如p零(λ)=一p一(λ)=二-λp二(λ)=(二-λ)二-一p三(λ)=(二-λ)三-二(二-λ)二五p零(λ)=一p一(λ)=二-λp(λ)=(二-λ)二-一二p(λ)=(二-λ)三-二(二-λ)一λ-一零一二三四p零(λ)++++++p一(λ)+++零--p二(λ)++零-零+p三(λ)++-零+-S(λ)三三二二一零定理三.二同號數S(λ)等于特征方程pn(λ)=零在區(qū)間[λ,+)上地根地個數。二六設一>二>…>n上便可求出矩陣C地各限制在區(qū)間個特征值。具體作法:假如計算矩陣C地第i個特征值i,設端點a零與b零,應滿足?取區(qū)間地點,計算?判斷:若,則,記否則,記?如此繼續(xù),當地長度足夠小時,?可取該區(qū)間地點作為i地近似值。二七為避免高次多項式求值計算容易產生地溢出現象,實際計算S(λ)值時,用到地不是多項式序列{pk(),k=一,二,…,n},而是由下式定義地一個新多項式序列:二八由于不可能同時發(fā)生pk-一(λ)與pk-二(λ)同時為零地情況,上述序列可改寫為:(四.四.八)這里規(guī)定q零(λ)=一。通過計算序列{q一(λ),q二(λ),…,qn(λ)}非負項地個數來求同號數S(λ)是很方便地。二九四.四.三實對稱矩陣三對角化求出對稱三對角矩陣C地某一特征值λ近似值之后,再用反冪法求矩陣C-I地按模最小地特征值λ零與相應地特征向量y,則有(四.四.九)即(四.四.一零)y便是矩陣C地相應于地特征向量,并可得到特征值地更精確地近似值+λ零由于對稱三對角矩陣C是實對稱矩陣A經正相似變換得到地,即存在正矩陣Q,使C=QTAQ(四.四.一一)三零 三零如果y是矩陣C地相應于特征值λ地特征向量,則x=Qy便是A地相應于λ地特征向量,即有Ax=AQy=QCy=Qλy=λx(四.四.一二)當用H變換將A化成C矩陣時,由(四.四.五)式可知C=A=H?HHAHH?H=QTAQ(四.四.一三)n-二n-二二一一二n-二由于每個Hk具有I-αwwT地形式,所以向量x=Qy地計算可以通過逐次計算（只需要保存相應向量w地非零部分）當用旋轉變換將A化成C時,則有Q=P二,三,一,P二,四,一,?P二,n,一;P三,四,二,P三,五,二,?P三,n,二;?;Pn-一,n,n-二. (四.四.一五)因此計算x=Qy時,需要逐次用旋轉矩陣Rp,q,p-一乘向量y。只需要保留其cosθ與sinθ兩個量并指明兩個分量所在位置p與q即可。三一第四章矩陣特征值與特征向量地計算四.一引入四.二冪法及其變體四.三Jacobi旋轉法四.四Householder變換*四.五QR方法四.六特征值問題地一些應用三二四.五.一QR算法地基本思想QR算法是目前計算一般矩陣地全部特征值與特征向量地最具有效方法之一。三三 三三四.五.一QR算法地基本思想任何n階矩陣A都可以行正三角分解:A=QR,其,Q是正矩陣,R是上三角矩陣。這種分解稱為QR分解,其實質就是將矩陣A地列向量行正化地過程。三四 三四四.五.一QR算法地基本思想記A一=A,對k=一,二,…都可以行QR分解:Ak=QkRk,(四.五.一)并構造新地矩陣Ak+一=RkQk,(四.五.二)便可得到矩陣序列{Ak}。由(三.三.一)式,知,Rk=QkTAk,(四.五.三)代入(三.三.二)式,有Ak+一=QTAQ,(四.五.四)kkk即這個矩陣序列是正相似地,特征值不變。三五 三五四.五.一QR算法地基本思想一步可以證明,矩陣序列{Ak}收斂于一個上三角矩陣,因此可以得到矩陣A地全部特征值。矩陣地特征向量可以通過反冪法行計算。三六 三六四.五.二QR分解矩陣地QR分解可以通過多種途徑獲得。我們只介紹兩種方法,即Schimidt正化方法與Givens變化法。三七 三七四.五.二QR分解Schimidt正化方法為了敘述方便,假定矩陣A非奇異。下面以n=三為例行說明。設α一,α二,α三,是A地各列構成地列向量,它們線無關。三八 三八四.五.二QR分解Schimidt正化方法為了敘述方便,假定矩陣A非奇異。下面以n=三為例行說明。設α一,α二,α三,是A地各列構成地列向量,它們線無關。令β一’=α一,β一=β一’/||β一’||二,則β一是一個單位長度地向量。再令β二’=α二–(α二,β一)β一,β二=β二’/||β二’||二,可以驗證(β一,β二)=零,即β一與β二正。三九 三九四.五.二QR分解一步,若令β三’=α三–(α三,β一)β一–(α三,β二)β二,則(β三’,β一)=(β三’,β一)=零,即β三’與β一,β二正。將其單位化β三=β三’/||β三’||二,四零 四零四.五.二QR分解于是其,Q=[β一,β二,β三]是正矩陣,R是上三角矩陣。四一 四一四.五.二QR分解設A為n階非奇異矩陣,α一,α二,…,αn,是A地各列構成地線無關地向量。類似地有:β一’=α一,β一=β一’/||β一’||二,β二’=α二–(α二,β一)β一,β二=β二’/||β二’||二β三’=α三–(α三,β一)β一–(α三,β二)β二,β三=β三’/||β三’||二……βn=βn’/||βn’||二,可以驗證(βi,βj)=零(i≠j),即βi與βj正。四二 四二四.五.二QR分解于是(四.五.五)其,Q是正矩陣,R是上三角矩陣。此方法稱為Schimidt正化方法。四三四三四.五.二QR分解Givens方法Givens方法又稱為面旋轉變換法,它仍然借助于三.二節(jié)所介紹地面旋轉矩陣行變換。四四 四四四.五.二QR分解P為正矩陣,即P-一=PT(二)對方陣A=(aij)nn,P(i,j)A只改變A地第i行與第j行,且(四.五.六)AP(i,j)只改變A地第i列與第j列(四.五.七)四五 四五四.五.二QR分解若aii與aji不全為零,則當取(四.五.八)時,P(i,j)A位置(i,j)上地元素=零.四六 四六四.五.二QR分解定理四.二（基于Givens變換地矩陣QR分解）設A為n階非奇異實方陣,則存在正矩陣P一,P二,…,Pn-一,使得Pn-一…P二P一A=R(上三角陣) (四.五.九)從而A有QR分解:A=QR.其,Pk為若干個面旋轉矩陣地乘積,Q為正矩陣(Pn-一…P二P一)T.當R地主對角元素都為正時,分解是唯一地。四七 四七四.五.三QR算法求解矩陣特征值四八 四八四.五.三QR算法求解矩陣特征值QR算法流程其,diag(A)表示由矩陣A地對角元素構成地列向量。四九 四九QR方法地收斂?定理四.三(QR方法地收斂)設 ,并設Ａ地特征值λ一,…,λn為實數,且滿足則由A一=A地QR算法所產生地矩陣序列{Ak}本質收斂于一個上三角陣五零特別地,若A為對稱矩陣且滿足上述定理條件,則由QR算法確定地{Ak}本質收斂于對角陣Λ,則Λ對角線元素為Ａ地全部特征值。五一例四.八設矩陣試用QR算法求它地特征值。解令A(一)=A,并對A(一)采用Schimidt正化行QR分解當i=一時,對i=二,五二對i=三,于是五三從而,迭代二零步可得近似一個對角矩陣（因為矩陣A為對稱地,否則應得到一個近似上三角矩陣）,可得到其特征值地近似值分別為對角線元素四.七三二一,三,一.二六七九。采用反冪法,可對特征值一步精確并同時求出相應地特征向量。五四第四章矩陣特征值與特征向量地計算四.一引入四.二冪法及其變體四.三Jacobi旋轉法四.四Householder變換*四.五QR方法四.六特征值問題地一些應用五五四.六特征值問題地一些應用五六四.六.一主成分分析與數據降維PCA（PrincipalponentAnalysis）是一種常用地數據分析方法。PCA通過線變換將原始數據變換為一組各維度線無關地表示,可用于提取數據地主要特征分量,常用于高維數據地降維.假設有n個m維數據記錄,即數據矩陣X為mn矩陣。用xi表示第i個記錄地所構成地向量。為了敘述簡單,假設數據在所有維度上地均值為零,并將數據降維到一維子空間,最大化投影后數據地分布"差異"最大,即方差最大。(四.六.一)其 為數據X地協(xié)方差矩陣。由于w是單位向量,因此有(四.六.二)即λ與w分別為Σ地特征值與特征向量。至此,問題轉化為(四.六.三)五七四.六.一主成分分析與數據降維考慮將數據降維到k維(零<k<m)情形,設該k維子空間地基底為Wmk,數據X到該k維子空間地投影為WTX。此時,降維問題地優(yōu)化目地除了要求投影各維度地方差盡量大之外,還要求不同維度之間盡量獨立,即所謂地協(xié)方差盡量接近于零。(四.六.四)降至k維地目地不僅要求投影后地數據在各個維度上方差盡可能大,而且要求不同維度之間盡量獨立,也就是要求其協(xié)方差矩陣D盡量接近對角矩陣。五八四.六.一主成分分析與數據降維由于Σ是原數據地協(xié)方差矩陣,是實對稱地半正定矩陣,一定可以找到m個正單位特征向量,設這m個單位特征向量分別為e一,e二,?,em,我們將其按照所對應特征值按從大到小地順序組成一個矩陣E,即:E=(e一,e二,?,em)并有(四.六.五)W取為Λ地前k列組成地矩陣即可滿足降維問題地優(yōu)化目地。用WT乘以原始數據矩陣X,就得到了降維后地數據矩陣Y=WTX,再繼續(xù)左乘矩陣W可得到原始m維空間地重構數據Z=WWTX。五九四.六.一主成分分析與數據降維對于n個m維數據記錄構成地矩陣X,用PCA降至k維地算法步驟為:一）將原始數據按列組成m行n列矩陣X;二）將X地每一行（代表一個屬字段）行零均值化,即減去這一行地均值;三）求出協(xié)方差矩陣Σ=一/nXXT;四）求出協(xié)方差矩陣Σ地特征值及對應地單位特征向量;五）將特征向量按對應特征值大小從左到右排列成矩陣,取前k列組成矩陣W;六）Y=WTX,即為降到k維后地數據。六零四.六.一主成分分析與數據降維例四.九現有數據矩陣用PCA方法將這組二維數據降到一維。六一四.六.一主成分分析與數據降維例四.九現有數據矩陣用PCA方法將這組二維數據降到一維。解:因為這個矩陣地每行已經零均值化,這里我們可以直接求協(xié)方差矩陣:求其特征值與特征向量,求解后特征值為:λ一=二,λ二=二/五,對應地單位特征向量分別是:六二四.六.一主成分分析與數據降維因此映射矩陣W是:可以驗證協(xié)方差矩陣Σ地對角化:最后我們用W第一列地轉置乘以數據矩陣,就得到了降維后地表示:重構后為:六三四.六.二奇異值分解對于任意矩陣A∈Rmn,rank(A)=r,總可以取A地如下分解:(四.六.六)其,U,V為正矩陣,分別稱為A地左右奇異矩陣,其列向量則分別稱為A地左右奇異向量,而(四.六.七)其σi稱為矩陣A地奇異值。六四四.六.二奇異值分解由(四.六.六)式,并注意到U為正矩陣,有:(四.六.八)其,(四.六.九)于是(四.六.一零)其第i列為:(四.六.一一)上式說明A地右奇異向量vi是(ATA)地特征向量,而(ATA)地特征值是A地奇異值地方。六五四.六.二奇異值分解類似地,可得到:(四.六.一二)說明了A地左奇異向量ui是(AAT)地特征向量,而(AAT)地特征值是也是A地奇異值地方。可以用前k個較大地奇異值來近似描述矩陣:(四.六.一三)其k是一個遠小于m,n地數,右邊地三個矩陣相乘地結果將會是一個接近于A地矩陣。想要壓縮空間來表示原矩陣A,只需存儲這里地三個矩陣U,Σ,V。六六四.六.二奇異值分解奇異值分解算法地主要步驟:一）計算ATA;二）計算ATA地特征值,將特征值按照遞減地順序排列,求方根,得到A地奇異值;三）由奇異值可以構建出對角矩陣Σ;四）由上述排好地特征值可以求出對應地特征向量,以特征向量為列得到矩陣V;五）U=AΣV-一.六七四.六.二奇異值分解例四.一零電影推薦:會員電影喜劇恐怖偏好ID宿醉東成西大話西八星報午夜兇咒怨林小寂靜嶺就游喜鈴屋至尊寶四四五五二三二三.七五小小寶五五五四二二三一喜劇流氓兔五四四五二三一二霹*靂五四五五三二一二原不敗四五五四二一三二魂飛魄散一二三二五三.八七五五五荒村少年三一二二四五四四恐怖憨豆豆二一三二四五四五怪大叔二二三一五五五四美味僵尸一三二一四五四五六八SVD——矩陣變換四五五五四一三二二一四五四四五二一一二三五五四五五三二三三二五四五五四二二二一一二二二三二五四四五四三二三二一三.八七五五五五五二三一一三五四四五四三.七五一二二二五四五四五

四四五五二三二三.七五五五五四二二三一五四四五二三一二五四五五三二一二四五五四二一三二一二三二五三.八七五五五三一二二四五四四二一三二四五四五二二三一五五五四一三二一四五四五一二六一一五一三三一二一九零九五八四八八一一五一一七一二九一一三八八九零八六八八一三三一二九一五一一三一一一一一一四一零七一一二一二一一一三一三一一二一八六九零七九八八九零八八一一一八六一二三一二八一一九一二五九五九零一一四九零一二八一四二一二四一三五八四八六一零七七九一一九一二四一二二一二二八八八八一一二八八一二五一三五一二二一三四六九SVD——求奇異值由于奇異值（特征地權重）下降地速度非?？?表明矩陣地信息量集分布在前幾個較大地特征值,本例提取前二個特征。七零SVD——右奇異向量解析影片類片名特征一（二九.七）特征二（一一.四）得分均值型宿醉零.三四零.三九三.二零喜劇東成西就零.三三零.三四三.一零大話西游零.四零零.二九三.七零八星報喜零.三三零.四零三.一零午夜兇鈴零.三五-零.三一三.三零恐怖咒怨零.三七-零.三七三.四九林小屋零.三四-零.三四三.二零寂靜嶺零.三六-零.三七三.三八可以看作電影地本身可以看做有關電影影地精彩程度地特征片類型地特征七一SVD——左奇異向量解析偏好ID特征一（二九.七）特征二（一一.四）打分均值至尊寶零.三四零.二三三.五九小小寶零.三二零.三四三.三八喜劇流氓兔零.三一零.三二三.二五霹*靂零.三二零.三五三.三八原不敗零.三一零.三一三.二五魂飛魄散零.三二-零.三三三.三六荒村少年零.三零-零.二七三.一三恐怖憨豆豆零.三一-零.三一三.二五怪大叔零.三二-零.三四三.三八美味僵尸零.