下一节:预处理Lanczos方法 上一级:预条件特征值求解器 上一节:预处理位移幂法

预处理最速上升/下降法

这些方法与上一小节中的算法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每次迭代的主要成本,包括存储和浮点运算,分别列于以下两个表格中:

项目 存储
残差 1n维向量
近似特征向量 1n维向量
临时向量 3-5个n维向量

操作 主要成本
Rayleigh-Ritz方法 6次点积和2次矩阵-向量乘积
残差 r 2次矩阵-向量乘积,1次更新
预处理残差 w 取决于预处理矩阵 T
近似特征向量 1 次更新

预处理最速下降/上升法的主要优点是相对简单和每次迭代成本较低,与其他预处理特征求解器相比。使用Rayleigh-Ritz方法而不是先验选择的位移,无需任何边界知识。另一方面,每次迭代的成本可能是算法11.5的两倍左右。尽管收敛性通常优于算法11.5,但仍不如我们下面考虑的其他预处理特征求解器的线性收敛。



下一节:预处理Lanczos方法 上一级:预条件特征值求解器 上一节:预处理位移幂法
Susan Blackford 2000-11-20