下一节:瑞利商迭代法 上一级:单向量和多向量迭代 上一节:幂法

逆迭代法

幂法的一些缺点可以通过将其应用于 (A - \sigma I)^{-1} 而不是A上来部分克服,其中\sigma被称为位移(shift)。这将使方法收敛到最接近\sigma的特征值,而不仅仅是 \lambda_{\max}。这种方法被称为逆迭代,或逆幂法

算法 4.2 HEP逆迭代法
(1) 取初始猜测向量 y = z,
(2) for k = 1, 2, ...
(3)     v = y / \Vert y \Vert_2
(4)     y = (A - \sigma I)^{-1} v
(5)     \theta = v^\ast y
(6)     若 \Vert y-\theta v\Vert_2 \le \epsilon_M \vert\theta\vert, 结束
(7) end for
(8) 结果: \lambda = \sigma+1/\thetax=y/\theta

需要注意的是,在步骤(4)中没有必要显式计算 逆 \left(A-\sigma I\right)^{-1}。我们只需要高效地解一个形如 \left(A-\sigma I\right) y = v 的系统来求 y,这从形式上给出 y = \left(A-\sigma I\right)^{-1} \, v

与幂法类似,我们应该期望由逆幂法生成的v向量序列变得越来越平行于 (A - \sigma I)^{-1} 的模最大的特征值对应的特征向量。更具体地说,假设\lambda_jx_jA的一个特征值和特征向量对,使得 \vert\lambda_j - \sigma \vert^{-1}(A - \sigma I)^{-1} 的模最大的特征值。如果z不垂直于x_j,逆幂法收敛。收敛速度为 \left\vert(\lambda_j - \sigma )/(\lambda_k- \sigma )\right\vert,其中\lambda_kA的一个特征值,使得 \vert\lambda_k - \sigma \vert^{-1}(A - \sigma I)^{-1} 的模第二大的特征值。

逆迭代相对于幂法的一个优点是能够收敛到任何期望的特征值(最接近\sigma的那个)。通过选择非常接近某个期望特征值的\sigma,逆迭代可以非常快速地收敛。当我们有一个特征值的良好近似并且只想计算这个特征值及其对应的特征向量时,这种方法特别有效。然而,逆迭代确实需要对矩阵A-\sigma I进行分解,这使得当这种分解成本较高时,逆迭代不那么有吸引力。



下一节:瑞利商迭代法 上一级:单向量和多向量迭代 上一节:幂法
Susan Blackford 2000-11-20