第五章特征值与特征向量 幂法 Power method 计算矩阵的主特征根及对应的特征向量 >原始幂法/ the original method 条件:4有特征根>2…≥20,对应n个线性无 关的特征向晶 ntyou have to 思路:从任意v≠出脚要啦(△x)≤0 (1.A< spectra ∑ax2以1着h∈v)=Av Av()≈1a1Ax i=1 p=Ap0=∑a1x1=∑叫(这是关于的近以 P=Ap=∑当充大时,有 (k) v≈x4a1x1,v≈x-a1x1(v4) 1
第五章 特征值与特征向量 —— 幂法 /* 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个线性无 关的特征向量 x xn , ... , 1 思路：从任意 (0) 0 出发，要求 ( , 1 ) 0 (0) x , 1 0 1 (0) = = n i i xi = = (1) (0) A = n i i i xi 1 = = (2) (1) A = n i i i xi 1 2 … … … = = − = = = n i i k i i k n i i k i i k k x A x 1 1 1 1 ( ) ( 1) | i / 1 | < 1 当k 充分大时，有 1 1 1 1 ( 1) 1 1 1 ( ) x , x k k k k − − 这是A关于1的近似 特征向量 ( ) 1 1 1 1 ( ) k k k A Ax ( 1) 1 ( ) ( ) ( ) − i k i k
Ch5 Power Method- The Original Method 定理|设相R为非摄矩阵e其主特 征根/ dominant eigen知e为实根,且>风22…21 则从任意非零向量满足a1=(m",)≠0出发,选代v=v 收敛到主特征向+)v)收敛到x 注:一结论对重根41=42=…=4成立。 HW: v=41∑ax+∑ i=r+1 (4//≈n4 ait p98#1 若有A1=-2则此法不收敛 任取初始向量时,因为不知道x1,所以不能保 证a1≠0,故所求得之v不一定是x1,而是使 得,xn)≠0的第一个x,同时得到的特征根 是λm
Ch.5 Power Method – The Original Method 定理 设 ARnn为非亏损矩阵 /* non-derogatory */，其主特 征根 /* dominant eigenvalue */ 1为实根，且|1 | > |2 | … | n | 。 则从任意非零向量 (满足 )出发, 迭代 收敛到主特征向量 ， 收敛到1。 (0) ( , 1 ) 0 (0) 1 = v x ( ) (0) k k = A 1 x i k i k ( ) /( ) ( 1) ( ) + 每个不同的特征根 只对应一个Jordan 块 注： 结论对重根 1 = 2 = … = r 成立。 = + = = + = r i i i k r i n i r i k i i i i k k x x x 1 1 1 1 1 1 ( ) 若有 1 = −2 ，则此法不收敛。 任取初始向量时，因为不知道 ，所以不能保 证 1 0，故所求得之 不一定是 ，而是使 得 的第一个 ，同时得到的特征根 是 m 。 1 x (k ) 1 x ( , ) 0 (0) xm m x HW: p.98 #1
Ch5 Power Method - Normalization >规范化/ normalization 为避免大数出现,需将迭代向量规范化,即每一步先保 证‖‖=1,再代入下一步迭代。一般用‖ν=max|v。 记:‖v6)|=|v则有: (k-1) k-13(0) Av(o) L (k-1) p(k)=Ar(k-1)= (k-1) (k) D4)1 k-1 Algorithm: Power Method To approximate the dominant eigenvalue and an associated eigenvector of the nxn matrix a given a nonzero initialvector. Input: dimension n; matrix a[[ initial vector vo[ tolerance Tol; maximum number ofiterations mar Output: approximate eigenvalue n and approximate eigenvector (normalized)or a message of failure
Ch.5 Power Method – Normalization ➢ 规范化 /* normalization */ 为避免大数出现，需将迭代向量规范化，即每一步先保 证 || || = 1 ，再代入下一步迭代。一般用 。 || || max | | 1 i i n v = 记： || || | | ( ) (k) i k k = 则有： − = − − − − = = − 1 0 ( ) 1 (0) ( 1) ( 1) ( 1) | | | | 1 k s s i k k i k k s k v A v v v u − = − = = 1 0 ( ) (0) ( ) ( 1) | | k s s i k k k s v A v v Au | | ( ) ( ) ( ) k i k k k v v u = 1 x ( ) ( 1) ( ) 1 1 k k i i k i k v u v − = − Algorithm: Power Method To approximate the dominant eigenvalue and an associated eigenvector of the nn 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
Ch 5 Power Method- Normalization Algorithm: Power Method (continued) Step 1 set k=1; Step 2 Find index such that vo[ index=l vo oo Step 3 Set vo[=vo/vol index l; / normalize vo*/ Step 4 While(ksnmnary do steps 5-11 Step 5 V[=A vO; /*compute V from UR-I*/ step6λ= M index; Step 7 find index such that M index=vlloo; Step 8 If F index ==0 the Output(“ a has the eigenvalue0”;oIl);STOP. / the matrix is singular and user should try a new vo */ Step 9 err=l v-V/M index 1; Vol]=MJ/M index ]; / compute Uk Step 10 If (err< ToL) then Output(n; VOI D; STOP. /successful * Step 1l Set k++; Step 12 Output(Maximum number of iterations exceeded) STOP. / unsuccessful
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 singular and user should try a new V0 */ Step 9 err = || V0 − V / V[ index ] || ; V0[ ] = V[ ] / V[ index ]; /* compute Uk */ Step 10 If (err < TOL) then Output ( ; V0[ ] ) ; STOP. /* successful */ Step 11 Set k ++; Step 12 Output (Maximum number of iterations exceeded); STOP. /* unsuccessful */ Ch.5 Power Method – Normalization