代数特征值问题.ppt
代数特征值问题,武汉大学数学与统计学院,向 华,G: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 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的目的：寻找能够表示采样数据的最好的投影子空间.PCA的求解：对样本的散布矩阵进行特征值分解,所求子空间为过样本均值,以最大特征值所对应的特征向量为方向的子空间.,定义:设 A 是 n 阶矩阵,如果数 和 n 维列向量,使得则称 是A的特征值,非零向量x 称为其对应的特征向量.,比如:,投影矩阵,设 为方阵A的一个特征值,则由方程求出非零解,就是对应于 的特征向量.,求解特征方程,如何求解?,即,例:给定,求其特征值和特征向量.,特征值,特征向量,乘幂法的基本思想,对应的特征向量,求按模最大的特征值和对应的特征向量,思考：如果恰好在x1分量上a1=0？,假设,当1 或1，产生下溢或上溢.作规格化：,迭代格式,可视为关于特征值的近似特征向量,当阶数很高，无法使用其他方法时，乘幂法几乎是唯一的选择基本思想可以导出一些更有效的算法（如反幂法，子空间迭代法），是其他方法的基础收敛速度取决于|/|的大小,定理:设对称阵,Xx1,xn是正交阵且.向量qk由幂法产生且定义,则,例,(1)比较=30和=-30时的迭代次数，注意两种情景下|2/1|的大小,Hint:,Note:,(2)取=16,此时 研究初始向量为q0=(2,-2,3,-3)T时的收敛行为.,结论：不用担心初始向量q0在x1方向上分量为因为迭代过程舍入误差通常能保证迭代序列在此方向上有分量,例Demography(Lotka,1920;Leslie,1940s),在时刻t处于年龄段i的个体数第i年龄段的存活率第i年龄段的出生率,对某一网页:,对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)：每次求解不同的方程组,推广四（Subspace iteration,Orthogonal iteration,Simultaneous iteration)：,(4)据,知,收缩技巧(deflation):已知 1和 x1:A x1=1 x1,记A1=A,1.Hotelling(1933):2.用相似变换:,(2)求B2对应的2和y2,(3)求A2对应的特征向量 z2(,y2T)T,(1)求H1,s.t.H1x1=t e1,eigshttp:/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),
