下一节:子空间迭代法 上一级:单向量和多向量迭代 上一节:逆迭代法

瑞利商迭代法

逆迭代的自然延伸是在每一步改变移位值。事实证明,从特征向量近似值 x \not =0 中可以得出的最佳移位值是 x瑞利商,即 \rho(x)\equiv x^{\ast} \, A \, x / x^{\ast} \, x

一般来说,瑞利商迭代(RQI)比使用固定移位的逆迭代需要更少的迭代次数来找到一个特征值;它最终具有三次收敛性,而逆迭代是线性收敛的。然而,如何选择初始向量 y 以使 RQI 收敛到特定的特征值/特征向量对并不明显。例如,RQI 可能收敛到一个特征值,该特征值并不是最接近初始瑞利商 \rho(y) 的,或者收敛到一个特征向量,该特征向量并不是最接近初始向量 y 的。此外,还存在一个微小但令人讨厌的可能性,即它可能根本不收敛到任何特征值/特征向量对。RQI 比逆迭代更昂贵,因为它在每次迭代中都需要对 A - \rho_k I 进行分解,而当 \rho_k 达到某个特征值时,这个矩阵将变为奇异矩阵。因此,只有当每次迭代中都能廉价地获得这种分解时,RQI 才是实用的。更多细节请参见 Parlett [353]。

算法 4.3 HEP的瑞利商迭代
(1)  取初始猜测向量 y = z,令 v = y / \Vert y \Vert_2, \; \rho_1 = \rho(v)
(2)  for k = 1, 2, ...
(3)    y = (A - \rho_k I)^{-1}v,
(4)    若奇异,结束
(5)    \theta = \Vert y \Vert_2,
(6)    \rho_{k+1} = \rho_k + y^\ast v / \theta^2,
(7)    v = y / \theta,
(8)    若 \theta \ge \epsilon_M^{-1/2}, 结束
(9)  end for
(10) 结果: \lambda = \rho_k, \; x = v



下一节:子空间迭代法 上一级:单向量和多向量迭代 上一节:逆迭代法
Susan Blackford 2000-11-20