《代数特征值问题课件》由会员分享，可在线阅读，更多相关《代数特征值问题课件（21页珍藏版）》请在金锄头文库上搜索。
1、代数特征值问题课件Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望G: Google Matrix, “the worlds largest matrix computation”. 4,300,000,000x: PageRank vector “The $25,000,000,000 Eigenvector”搜索引擎搜索引擎London, England: Millennium (Wobbly) Bridge (1998-2002, Norman Foster and Partn
2、ers and Arup Associates) the natural modes 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的目的：寻找能
3、够表示采样数据的最好的投影子的目的：寻找能够表示采样数据的最好的投影子空间空间. PCA的求解：对样本的散布矩阵进行特征值分解的求解：对样本的散布矩阵进行特征值分解, 所所求子空间为过样本均值求子空间为过样本均值, 以最大特征值所对应的特征向以最大特征值所对应的特征向量为方向的子空间量为方向的子空间.Principalcomponent定义定义: :设设 A A 是是 n n 阶矩阵阶矩阵, , 如果数如果数 和和 n n 维列向量维列向量 , ,使得使得则称则称 是是A A的的特征值特征值, , 非零向量非零向量x x 称为其对应的称为其对应的特征向量特征向量. .比如比如:投影矩阵投影矩阵
4、设设 为方阵为方阵A A的一个特征值的一个特征值, , 则由方程则由方程求出非零解求出非零解 , , 就是对应于就是对应于 的特征向量的特征向量. .求解特征方程求解特征方程如何求解如何求解 ?即例例: : 给定给定 , , 求其特征值和特征向量求其特征值和特征向量. .特征值特征值特征向量特征向量乘幂法的基本思想乘幂法的基本思想对应的特征向量求按模最大的特征值和对应的特征向量思考：如果恰好在x1分量上a1=0？假设当1 或1，产生下溢或上溢.作规格化：迭代格式迭代格式可视为关于特征值的近似特征向量当阶数很高，无法使用其他方法时，乘幂法几乎是唯一的选择当阶数很高，无法使用其他方法时，乘幂法几乎
5、是唯一的选择基本思想可以导出一些更有效的算法（如反幂法，子空间迭代法），是基本思想可以导出一些更有效的算法（如反幂法，子空间迭代法），是其他方法的基础其他方法的基础收敛速度取决于收敛速度取决于|/|的大小的大小定理定理: : 设设对称阵对称阵 , , , ,Xx1,xn 是正交是正交阵且阵且 . .向量向量qk由幂法产生且定义由幂法产生且定义 , ,则则例(1)(1)比较比较=30=30和和=-30=-30时时的迭代次数，的迭代次数，注意两种情景下注意两种情景下 |2 /1|的大小的大小Hint:Note:(2)(2)取取=16,16,此时此时 研究初始向量为研究初始向量为q0=(2,-2,3
6、,-3)(2,-2,3,-3)T T时的收敛行为时的收敛行为. . 结论：不用担心初始向量结论：不用担心初始向量q0在在x1方向上分量为方向上分量为因为迭代过程舍入误差通常能保证迭代序列在此方向上有分量因为迭代过程舍入误差通常能保证迭代序列在此方向上有分量例Demography(Lotka,1920;Leslie,1940s)在时刻t处于年龄段i的个体数第i年龄段的存活率第i年龄段的出生率Age intervalAge interval (months)x(0)misi0-30-3600.23-63-6120.50.46-96-980.80.89-129-1240.3-对某一网页:所有指向P的
7、网页Q指向外的链接数对n个页面若 链接到 其他PageRank向量修正Google矩阵矩阵推广一（inverse power method)：求模最小的特征值推广二（power method with shift)：下一个迭代向量在相应的特征方向上的成分就非常多H.Wielandt,1944; J.Wilkinson,1957.坏条件的线性方程组不精确反迭代如何估计位移如何估计位移(Gershgorin circles)：例如例如, A=30,1,2,3; 4,15,-4,-2; -1,0,3,5; -3,5,0,-1 ;推广三（Rayleigh Quotient Iteration)：每次求
8、解不同的方程组近似近似k近似近似qk一步反迭代Rayleigh商推广四（Subspace iteration, Orthogonal iteration, Simultaneous iteration)：(4)据 , 知 收缩技巧(deflation):已知 1和 x1: A x1= 1 x1,记A1=A1.1.Hotelling(1933):(1933):2.2.用相似变换用相似变换: :(2)求B2对应的2和y2(3)求A2对应的特征向量 z2 (, y2T)T(1)求H1, s.t. H1x1=t e1eigshttp:/www.caam.rice.edu/software/ARPACK/eighttp:/lib.org/lapack/QR算法的C程序(见附件)参考 Numerical Recipes 或 C+数值算法数值算法,（美）普雷斯 等著，胡健伟 等译,电子工业出版社 进一步的内容进一步的内容: :1.QR算法2.分而治之(divide-and-conquer)3.The Lanczos Method4.Arnoldis Method5.Jacobi-Davidson Methods6.LOBPCG(Locally Optimal Block Preconditioned Conjugate Gradient)
