由于V的列向量组构成C”的一组基，因此xo)可表示为 秦 x(0)=aiv+a2v2+...+anvn V[a1;02....,an]. 我们假定a1≠0，即x(o不属于span{v2,3,·,n} (由于xO)是随机选取的，从概率意义上讲，这个假设通常是成立的). 于是我们可得 1 a1X57 是 Ak(0)=(VAV-1)%V a2均 =VAk =V =a1λV ... Lan anxh ) http://math.ecnu.edu.cn/~jypan 6/67
由于 V 的列向量组构成 C n 的一组基, 因此 x (0) 可表示为 x (0) = α1v1 + α2v2 + · · · + αnvn = V [α1, α2, . . . , αn] ⊺ . 我们假定 α1 ̸= 0, 即 x (0) 不属于 span{v2, v3, . . . , vn} (由于 x (0) 是随机选取的, 从概率意义上讲, 这个假设通常是成立的). 于是我们可得 A kx (0) = (V ΛV −1 ) kV α1 α2 . . . αn = V Λ k α1 α2 . . . αn = V α1λ k 1 α2λ k 2 . . . αnλ k n = α1λ k 1V 1 α2 α1 λ2 λ1 k . . . αn α1 λn λ1 k http://math.ecnu.edu.cn/~jypan 6/67
又A/入<1，i=2,3,,n,所以 秦 =0 i=2,3,..,n. 故当k趋向于无穷大时，向量 上器(=（会） k=0,1,2, 收敛到e1=[1,0,,0T. 所以向量x=AxO)/川AxO2收敛到士1，即1的特征向量 而：=(x()*Ax()则收敛到AU1=入1 幂迭代的收敛快慢取决于2/入1的大小，2/入1越小收敛越快 http://math.ecnu.edu.cn/~jypan 7167
又 |λi/λ1| < 1, i = 2, 3, . . . , n, 所以 lim k→∞ λi λ1 k = 0, i = 2, 3, . . . , n. 故当 k 趋向于无穷大时, 向量 " 1, α2 α1 λ2 λ1 k , . . . , αn α1 λn λ1 k #⊺ , k = 0, 1, 2, . . . 收敛到 e1 = [1, 0, . . . , 0]⊺ . 所以向量 x (k) = Akx (0)/∥Akx (0)∥2 收敛到 ±v1, 即 λ1 的特征向量. 而 µk = (x (k) ) ∗Ax(k) 则收敛到 v ∗ 1Av1 = λ1. ✍ 幂迭代的收敛快慢取决于 |λ2/λ1| 的大小, |λ2/λ1| 越小收敛越快. http://math.ecnu.edu.cn/~jypan 7/67
秦 幂选代的不足： ·幂迭代只能用于计算（模）最大的特征值和其相应的特征向量 ·当入2/1接近于1时，收敛速度会非常慢. ·如果模最大的特征值是一对共轭复数，则幂迭代可能会失效： http://math.ecnu.edu.cn/~jypan 8/67
幂迭代的不足： • 幂迭代只能用于计算 (模) 最大的特征值和其相应的特征向量. • 当 |λ2/λ1| 接近于 1 时, 收敛速度会非常慢. • 如果模最大的特征值是一对共轭复数, 则幂迭代可能会失效. http://math.ecnu.edu.cn/~jypan 8/67
秦 加速技巧：位移策略 出发点：加快幂迭代算法的收敛速度←→尽可能地减小2/入l 位移策略(shif):计算A-oI的特征值 我们称o为位移(shif),满足 (1)入1-σ是A-σI的模最大的特征值： 入-0 (2) max 尽可能地小 2≤n λ1- 其中第一个条件保证最后所求得的特征值是我们所需要的，第二个条件用于 加快幂迭代的收敛速度. http://math.ecnu.edu.cn/~jypan 9/67
加速技巧: 位移策略 出发点: 加快幂迭代算法的收敛速度 ⇐⇒ 尽可能地减小 |λ2/λ1| 位移策略 (shift): 计算 A − σI 的特征值 我们称 σ 为位移 (shift), 满足 (1) λ1 − σ 是 A − σI 的模最大的特征值; (2) max 2≤i≤n λi − σ λ1 − σ 尽可能地小. 其中第一个条件保证最后所求得的特征值是我们所需要的, 第二个条件用于 加快幂迭代的收敛速度. http://math.ecnu.edu.cn/~jypan 9/67
秦 缺点： (1)σ很难选取： (2)加速效果有限 改进：与反迭代相结合，能起到很好的加速效果 http://math.ecnu.edu.cn/~jypan 10/67
缺点: (1) σ 很难选取; (2) 加速效果有限. 改进: 与反迭代相结合, 能起到很好的加速效果 http://math.ecnu.edu.cn/~jypan 10/67