预处理位移幂法

带位移的预处理幂法是最简单的预处理迭代方法。它只能找到最小的（或最大的，对于不同的位移）特征值及其对应的特征向量。

我们针对矩阵束B - \mu A提出了该方法的单向量版本，如算法11.5所示。输出时，\mu^{(k)}和x^{(k)}近似于最大特征值\mu_{1}及其对应的特征向量。

需要注意的是，位移\tau需要知道\mu_{\min}或其从下的估计值。如果B是非负定矩阵，那么\mu_{\min}可以简单地替换为0。

算法 11.5：预处理幂方法用于广义特征值问题

(1) 选择一个初始向量 x^{(0)}。
(2) 对于 i=0,\ldots，直到收敛执行：
(3) \mu^{(i)}:=\left(x^{(i)}, B x^{(i)}\right)/\left(x^{(i)}, A x^{(i)}\right)
(4) r:= B x^{(i)}-\mu^{(i)} A x^{(i)}
(5) w:=\operatorname{Tr}
(6) x:=w+\tau x，其中平移 \tau=\delta_{1}\left(\mu^{(i)}-\mu_{\min}\right)
(7) x^{(i+1)}=x/\|x\|_{A}

基于A^{-1}B的特征分解的标准论证，对于矩阵束B - \mu A，并不能证明幂法收敛，因为特征分解中的特征向量不一定是迭代算子的特征向量。这使得收敛理论相当复杂。D'yakonov及其同事[150,146,147]利用假设(11.9)，对迭代算法11.5得到了线性收敛的显式估计。简而言之（参见[264,265,268]），算法11.5的收敛速率估计可以写为

\frac{\mu_1 - \mu^{(n)}}{\mu^{(n)} - \mu_2} \leq (1 - \xi )^n \frac{\mu_1-\mu^{(0)}}{\mu^{(0)}-\mu_2}, \quad \xi = \frac{\delta_0}{\delta_1}\frac{\mu_1 - \mu_2}{\mu_1 - \mu_{\min}}, \tag{11.13}

在假设\mu^{(0)} > \mu_2下。

该估计表明收敛至少是线性的。注意，A和B的条件数并未出现在估计中。

类似的结果可以在某些p>1满足\mu_p \geq \mu^{(0)} > \mu_{p+1}的情况下获得[147]。

在数值实验中，算法11.5通常对随机初始猜测收敛到\mu_1。当\mu_p \geq \mu^{(0)} > \mu_{p+1}时，序列x^{(k)}需要通过p个特征向量，这些特征向量是瑞利商的鞍点，才能达到u_1。原则上，在每个鞍点附近，收敛可能会减慢。对于一般的预处理器T，很难预测对于给定的初始猜测x^{(0)}是否会发生这种情况。

我们在以下两个表格中分别收集了算法11.5每次迭代的存储和浮点运算的主要成本。

项目	存储
残差	1 n-向量
近似特征向量	1 n-向量
临时向量	1-2 n-向量

操作	主要成本
瑞利商\mu^{(i)}	2 点积
残差r	2 矩阵-向量乘积
预处理残差w	取决于预处理器T
近似特征向量	1 更新

预处理位移幂法的主要优点当然是其算法的简单性和每次迭代成本的低廉。使用事先选择的位移提供了对迭代方法的全面控制。该方法非常稳定和健壮，并且存在坚实的收敛理论。

需要对\delta_1和\lambda_{\min}的界限来计算位移是一个明显的缺点。此外，我们下面考虑的其他预处理特征求解器也通常以线性方式收敛，但通常具有更好的速率。