代數特征值问题课件.pptVIP

* * 代数特征值问题 武汉大学数学与统计学院 向 华 G: Google Matrix, “the world’s 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的求解：对样本的散布矩阵进行特征值分解, 所求子空间为过样本均值, 以最大特征值所对应的特征向量为方向的子空间. Principal component 定义: 设 A 是 n 阶矩阵, 如果数 和 n 维列向量 ,使得 则称 是A的特征值, 非零向量x 称为其对应的特征向量. 比如: 投影矩阵 设 为方阵A的一个特征值, 则由方程 求出非零解 , 就是对应于 的特征向量. 求解特征方程 如何求解 　? 即 例: 给定 , 求其特征值和特征向量. 特征值 特征向量 乘幂法的基本思想 对应的特征向量 求按模最大的特征值和对应的特征向量． 思考：如果恰好在x1分量上a1=0？ 假设 当｜λ1 ＜１或｜λ1｜＞１，产生下溢或上溢.作规格化： 迭代格式 可视为关于特征值　的近似特征向量 当阶数很高，无法使用其他方法时，乘幂法几乎是唯一的选择． 基本思想可以导出一些更有效的算法（如反幂法，子空间迭代法），是其他方法的基础． 收敛速度取决于|λ２/λ１|的大小 定理: 设对称阵　　 , 　　　 ,X＝［x1,…,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年龄段的出生率 - 0.3 4 9-12 0.8 0.8 8 6-9 0.4 0.5 12 3-6 0.2 0 6 0-3 si mi x(0) Age interval (months) 对某一网页: 所有指向P的网页 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)： 每次求解不同的方程组． 近似μk 近似qk 一步反迭代 Rayleigh商 推广四（Subspace iteration, Orthogonal iteration, Simultaneous iteration)： (4)据