这些方法与上一小节中的算法11.5类似,但在迭代过程中选择位移,无需任何边界知识。历史上,预处理最速下降/上升法用于特征问题比上一小节中先验选择位移的幂法更早提出(参见[225,393,365])。
在此,我们介绍针对矩阵束B - \mu A的单向量预处理最速上升法,见算法11.6。对于B=I,\lambda = 1 / \mu,该方法变为A - \lambda I的最速下降法。
算法 11.6:预处理最陡上升法用于广义特征值问题 (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^{(i)},选择 \tau 以最大化 \mu(x) (7) x^{(i+1)}=x/\|x\|_{A}
我们注意到,可以通过对矩阵束B - \mu A在试验子空间{\rm span}\{ x^{(i)}, w \}上应用Rayleigh-Ritz方法来确定位移。由于试验空间是二维的,投影问题可以作为二次方程求解,从而可以推导出\tau作为二次多项式根的显式公式。
通过构造,最速上升(下降)方法在每次迭代中提供Rayleigh商的最大化(最小化),与相应的迭代算法11.5相比。因此,前一节的收敛结果可以不加改变地应用,并可做出类似的观察。
我们已收集了算法11.6每次迭代的主要成本,包括存储和浮点运算,分别列于以下两个表格中:
项目 | 存储 |
残差 | 1个n维向量 |
近似特征向量 | 1个n维向量 |
临时向量 | 3-5个n维向量 |
操作 | 主要成本 |
Rayleigh-Ritz方法 | 6次点积和2次矩阵-向量乘积 |
残差 r | 2次矩阵-向量乘积,1次更新 |
预处理残差 w | 取决于预处理矩阵 T |
近似特征向量 | 1 次更新 |
预处理最速下降/上升法的主要优点是相对简单和每次迭代成本较低,与其他预处理特征求解器相比。使用Rayleigh-Ritz方法而不是先验选择的位移,无需任何边界知识。另一方面,每次迭代的成本可能是算法11.5的两倍左右。尽管收敛性通常优于算法11.5,但仍不如我们下面考虑的其他预处理特征求解器的线性收敛。