代數(shù)征值問題

1、代數(shù)特征值問題代數(shù)特征值問題武漢大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院武漢大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院向向 華華xxgt1extg: google matrix, “the worlds largest matrix computation”. 4,300,000,000 x: pagerank vector “the $25,000,000,000 eigenvector”搜索引擎搜索引擎london, england: millennium (wobbly) bridge (1998-2002, norman foster and partners and arup associates) the natural mo

2、des and frequencies of a structure are the solution of an eigenvalue problem that is quadratic when damping effects are included in the model. (f. tisseur, k. meerbergen, the quadratic eigenvalue problem, sirev 43, 2000, pp.235-286)主成分分析主成分分析 ( pca ) pca的目的：尋找能夠表示采樣數(shù)據(jù)的最好的投影子的目的：尋找能夠表示采樣數(shù)據(jù)的最好的投影子空間空間

3、. pca的求解：對(duì)樣本的散布矩陣進(jìn)行特征值分解的求解：對(duì)樣本的散布矩陣進(jìn)行特征值分解, 所所求子空間為過樣本均值求子空間為過樣本均值, 以最大特征值所對(duì)應(yīng)的特征向量以最大特征值所對(duì)應(yīng)的特征向量為方向的子空間為方向的子空間.principalcomponent定義定義: :設(shè)設(shè) a a 是是 n n 階矩陣階矩陣, , 如果數(shù)如果數(shù) 和和 n n 維列向量維列向量 , ,使得使得則稱則稱 是是a a的的特征值特征值, , 非零向量非零向量x x 稱為其對(duì)應(yīng)的稱為其對(duì)應(yīng)的特征向量特征向量. .比如比如:0110a投影矩陣投影矩陣0001a. 1,1111x. 1,1122x. 1,0111x.

4、0,1022xxxa0 x 設(shè)設(shè) 為方陣為方陣a a的一個(gè)特征值的一個(gè)特征值, , 則由方程則由方程求出非零解求出非零解 , , 就是對(duì)應(yīng)于就是對(duì)應(yīng)于 的特征向量的特征向量. .求解特征方程求解特征方程如何求解如何求解 ?)(0 xxax0 xia)(0)(xiai0)(fiixi0)(212222111211defnnnnnnaaaaaaaaaf0)det( ia即例例: : 給定給定 , , 求其特征值和特征向量求其特征值和特征向量. .3113a, 0863113)det(2ia. 2, 4210 xxia21211111111)(xx0 xxia21111111111)(xx00212

5、1xxxx21xx 111x112x特征值特征值特征向量特征向量乘冪法的基本思想乘冪法的基本思想對(duì)應(yīng)的特征向量n321nxxx,21nnaaaxxxq22110 1112111222111011xxxxxxqaknjjkaaknknnkkkaaaaajj求按模最大的特征值和對(duì)應(yīng)的特征向量思考：如果恰好在x1分量上a1=0？假設(shè)當(dāng)1 或1，產(chǎn)生下溢或上溢.作規(guī)格化：khkkkkkkkaqqzzqaqz|/1迭代格式迭代格式, 2 , 1,1kkkaqq)(111kakkxq可視為關(guān)于特征值的近似特征向量1當(dāng)階數(shù)很高，無法使用其他方法時(shí)，乘冪法幾乎是唯一的選擇當(dāng)階數(shù)很高，無法使用其他方法時(shí)，乘冪法

6、幾乎是唯一的選擇基本思想可以導(dǎo)出一些更有效的算法（如反冪法，子空間迭代法），基本思想可以導(dǎo)出一些更有效的算法（如反冪法，子空間迭代法），是其他方法的基礎(chǔ)是其他方法的基礎(chǔ)收斂速度取決于收斂速度取決于|/|的大小的大小定理定理: : 設(shè)設(shè)對(duì)稱陣對(duì)稱陣 , , , ,xx1,xn 是正交陣是正交陣且且 . .向量向量qk由冪法產(chǎn)生且定義由冪法產(chǎn)生且定義 , ,則則例(1)(1)比較比較=30=30和和=-30=-30時(shí)時(shí)的迭代次數(shù)，的迭代次數(shù)，注意兩種情景下注意兩種情景下 |2 /1|的大小的大小115144126798101151332)(a,span0qaqkkkkko12span,spandi

7、stsin1xqnnra),(diag1ntaxxn21|cos1ktkqx.,sin211212kkkkoonjkjjkkktktkaa12221212200121211)(1sinqaqaxqx,12211220200120njkjjnjkjjktktkktkkaaqaqqaqqaqhint:note:,)(12221221njkjjnjjkjjkaa(2)(2)取取=16,16,此時(shí)此時(shí) 研究初始向量為研究初始向量為q0=(2,-2,3,-3)(2,-2,3,-3)t t時(shí)的收斂行為時(shí)的收斂行為. . t)2/1, 2/1, 2/1, 2/1 (,3411x結(jié)論：不用擔(dān)心初始向量結(jié)論：不

8、用擔(dān)心初始向量q0在在x1方向上分量為方向上分量為因?yàn)榈^程舍入誤差通常能保證迭代序列在此方向上有分量因?yàn)榈^程舍入誤差通常能保證迭代序列在此方向上有分量例demography(lotka,1920;leslie,1940s)., 1, 0,0)()1(0)()1(1niititititimxxnisxx)(tix在時(shí)刻t處于年齡段i的個(gè)體數(shù)第i年齡段的存活率第i年齡段的出生率isim)()1(ttaxx)()(2)(1)(0)(tnttttxxxxx000000011010nnsssmmmaage intervalage interval (months)x(0)misi0-30-360

9、0.23-63-6120.50.46-96-980.80.89-129-1240.3-08 . 000004 . 000002 . 03 . 08 . 05 . 00at,0.3537)167,0.23670.8477,0.3(5353. 011x111xax對(duì)某一網(wǎng)頁:pbqqqrpr|)()(所有指向p的網(wǎng)頁q指向外的鏈接數(shù)pb|q對(duì)n個(gè)頁面nppp,21, 2 , 1,|)()(1)(10jqqrprnpripbqjiji. 0|,| /1,)(,),(11iijtjtjnjjtjpppprpr若 鏈接到 其他ipjppagerank向量修正tjjt limteveepp,)1 (goo

10、gle矩陣矩陣推廣一（inverse power method)：求模最小的特征值1111|/,khkkkkkkkqaqzzqqaznkk/1lim推廣二（power method with shift)：niiiiiiiiniiaa10110)(xqiaxaxxq下一個(gè)迭代向量在相應(yīng)的特征方向上的成分就非常多h.wielandt,1944; j.wilkinson,1957.壞條件的線性方程組不精確反迭代1111)(|/,)(khkkkkkkkqiaqzzqqiaz如何估計(jì)位移如何估計(jì)位移(gershgorin circles)：例如例如, a=30,1,2,3; 4,15,-4,-2; -

11、1,0,3,5; -3,5,0,-1 ;推廣三（rayleigh quotient iteration)：每次求解不同的方程組近似近似k近似近似qk一步反迭代rayleigh商khkkkkkkkkaqqzzqqiaz|/)(111推廣四（subspace iteration, orthogonal iteration, simultaneous iteration)：kkkkkrqzaqz1spanspanspanspanspan0101qxxqaaqzqkkkkk(4)據(jù) , 知 收縮技巧(deflation):已知 1和 x1: a x1= 1 x1,記a1=a1.1.hotelling(

12、1933):(1933):2.2.用相似變換用相似變換: :tt1111211, 1xxaaxx,111111111xhxhhah,i.e.1111111eehah2111112b0hahat(2)求b2對(duì)應(yīng)的2和y2(3)求a2對(duì)應(yīng)的特征向量 z2 (, y2t)t22221yyb0t222111122zzhahza2112zhx(1)求h1, s.t. h1x1=t e1eigs/software/arpack/eig/lapack/qr算法的c程序(見附件)參考 numerical recipes 或 c+數(shù)值算法數(shù)值算法,（美）普雷斯 等著