浙江大学《数值分析》课件-第5章.pptVIP

第五章 特征值与特征向量 —— 幂法 /* Power Method */ 计算矩阵的主特征根及对应的特征向量 Wait a second, what does that dominant eigenvalue mean? That is the eigenvalue with the largest magnitude. Why in the earth do I want to know that? Don’t you have to compute the spectral radius from time to time? ? 原始幂法 /* the original method */ 条件：A 有特征根 |?1| |?2| ? … ? |?n| ? 0，对应n个线性无关的特征向量 思路：从任意 出发，要求 … … … | ?i / ?1 | 1 当k 充分大时，有 这是A关于?1的近似 特征向量 Ch.5 Power Method – The Original Method 定理 设 A?Rn?n为非亏损矩阵 /* non-derogatory */，其主特征根 /* dominant eigenvalue */ ?1为实根，且|?1| |?2| ? … ? |?n| 。则从任意非零向量 (满足 )出发, 迭代 收敛到主特征向量 ， 收敛到?1。 每个不同的特征根只对应一个Jordan块 注：? 结论对重根 ?1 = ?2 = … = ?r 成立。 ? 若有 ?1 = ??2 ，则此法不收敛。 ? 任取初始向量时，因为不知道 ，所以不能保证 ?1 ? 0，故所求得之　 不一定是　 ，而是使得 的第一个　 ，同时得到的特征根是?m 。 HW: p.98 #1 Ch.5 Power Method – Normalization ? 规范化 /* normalization */ 为避免大数出现，需将迭代向量规范化，即每一步先保证 ，再代入下一步迭代。一般用 。 记： 则有： Algorithm: Power Method To approximate the dominant eigenvalue and an associated eigenvector of the n?n matrix A given a nonzero initial vector. Input: dimension n; matrix a[ ][ ]; initial vector V0[ ]; tolerance TOL; maximum number of iterations Nmax. Output: approximate eigenvalue ? and approximate eigenvector (normalized) or a message of failure. Algorithm: Power Method (continued) Step 1 Set k = 1; Step 2 Find index such that | V0[ index ] | = || V0 ||? ; Step 3 Set V0[ ] = V0[ ] / V0[ index ]; /* normalize V0 */ Step 4 While ( k ? Nmax) do steps 5-11 Step 5 V [ ] = A V0[ ]; /* compute Vk from Uk?1 */ Step 6 ? = V[ index ]; Step 7 Find index such that | V[ index ] | = || V ||? ; Step 8 If V[ index ] == 0 then Output ( “A has the eigenvalue 0”; V0[ ] ) ; STOP. /* the matrix is singula