秦 2反迭代方法 将幂迭代作用到A-1上，从而计算A的模最小特征值，这就是反迭代。 算法2.l反迭代算法(Inverse Iteration) 1:Choose a scalar o and an initial vector (0)with (2=1 2:set=0 3:while not convergence do 4 y+)=(A-I)-1x 5: x依+1=yk+/川gk+2 6: 4k+1=(xk+1),Axk+1) 7: k=k+1 8:end while 白显然：以收敛到距离σ最近的特征值，x)收敛到对应的特征向量。 http://math.ecnu.edu.cn/~jypan 11/67
2 反迭代方法 将幂迭代作用到 A−1 上，从而计算 A 的模最小特征值, 这就是反迭代。 算法 2.1 反迭代算法 (Inverse Iteration) 1: Choose a scalar σ and an initial vector x (0) with ∥x (0)∥2 = 1 2: set k = 0 3: while not convergence do 4: y (k+1) = (A − σI) −1x (k) 5: x (k+1) = y (k+1)/∥y (k+1)∥2 6: µk+1 = (x (k+1), Ax(k+1)) 7: k = k + 1 8: end while ✍ 显然: µk 收敛到距离 σ 最近的特征值, x (k) 收敛到对应的特征向量。 http://math.ecnu.edu.cn/~jypan 11/67
秦 一理论上，反迭代+位移策略，可以计算矩阵的任意一个特征值 优点： (1)若σ与某个特征值入k非常接近，则反迭代的收敛速度非常快 (2)只要选取合适的位移σ，就可以计算A的任意一个特征值， 缺点： (1) 每步迭代需要解一个线性方程组(A-oI)yk+)=x( (2)与幂迭代一样，反迭代算法一次只能求一个特征值， (3)怎样选取位移？→Rayleigh商：动态选取，自动调整 http://math.ecnu.edu.cn/-jypan 12/67
✍ 理论上, 反迭代 + 位移策略, 可以计算矩阵的任意一个特征值 优点: (1) 若 σ 与某个特征值 λk 非常接近, 则反迭代的收敛速度非常快. (2) 只要选取合适的位移 σ, 就可以计算 A 的任意一个特征值. 缺点: (1) 每步迭代需要解一个线性方程组 (A − σI)y (k+1) = x (k) (2) 与幂迭代一样, 反迭代算法一次只能求一个特征值. (3) 怎样选取位移 σ? → Rayleigh 商: 动态选取, 自动调整 http://math.ecnu.edu.cn/~jypan 12/67
秦 Rayleigh商迭代 出发点 使得位移σ尽可能地接近所求的特征值。 期望能直接给出一个理想位移是不太现实的，比较现实的方法就是动态调 整，使得位移逐渐靠近某个特征值。 Rayleigh商迭代：以Rayleigh商为位移的反迭代，简称RQI 理由：以会逐渐收敛到某个特征值←幂迭代的收敛性 http://math.ecnu.edu.cn/~jypan 13/67
Rayleigh 商迭代 出发点 使得位移 σ 尽可能地接近所求的特征值。 ✍ 期望能直接给出一个理想位移是不太现实的，比较现实的方法就是动态调 整，使得位移逐渐靠近某个特征值。 Rayleigh 商迭代: 以 Rayleigh 商为位移的反迭代，简称 RQI 理由: µk 会逐渐收敛到某个特征值 ← 幂迭代的收敛性 http://math.ecnu.edu.cn/~jypan 13/67
秦 算法2.2 Rayleigh商迭代(Rayleigh Quotient Iteration,RQI) 1:Choose an initial vector x(0)with ll(0)2=1 2:set=0 3:compute=(z(0))*Ar(0) 4:while not converge do 5: y(k+1)=(A-aI)-1z(k) 6 xk+)=yk+1/川yk+l2 7: 4k+1=(zk+1),Axk+1) 8: 0=k+1 9: k=k+1 10:end while http://math.ecnu.edu.cn/~jypan 14/67
算法 2.2 Rayleigh 商迭代 (Rayleigh Quotient Iteration, RQI) 1: Choose an initial vector x (0) with ∥x (0)∥2 = 1 2: set k = 0 3: compute σ = (x (0)) ∗Ax(0) 4: while not converge do 5: y (k+1) = (A − σI) −1x (k) 6: x (k+1) = y (k+1)/∥y (k+1)∥2 7: µk+1 = (x (k+1), Ax(k+1)) 8: σ = µk+1 9: k = k + 1 10: end while http://math.ecnu.edu.cn/~jypan 14/67
秦 RQI算法的收敛性 般来说，如果Rayleigh商迭代收敛到A的一个单特征值，则至少是二次收敛 的，即具有局部二次收敛性.如果A是对称的，则能达到局部三次收敛，详情 见后面的对称特征值问题 缺点： 由于每次迭代的位移是不同的，因此每次迭代需要求解一个不同的线性方程 组，这使得运算量大大增加。 RQI通常应用于三对角矩阵的特征值计算. http://math.ecnu.edu.cn/~jypan 15/67
RQI 算法的收敛性 一般来说, 如果 Rayleigh 商迭代收敛到 A 的一个单特征值, 则至少是二次收敛 的, 即具有局部二次收敛性. 如果 A 是对称的, 则能达到局部三次收敛, 详情 见后面的对称特征值问题. 缺点: 由于每次迭代的位移是不同的, 因此每次迭代需要求解一个不同的线性方程 组, 这使得运算量大大增加. ✍ RQI 通常应用于 三对角矩阵 的特征值计算. http://math.ecnu.edu.cn/~jypan 15/67