下一节:预处理共轭梯度法 上一级:预条件特征值求解器 上一节:Davidson方法

带预处理内迭代的算法

我们注意到,在我们的预处理特征求解器类别中,并不存在逆幂法的类似算法,因为它需要精确求解与矩阵B - \alpha A相关的线性系统。然而,如果使用预处理迭代方法作为内迭代来求解这些系统,那么内外迭代的方法就属于预处理特征求解器的范畴。作为一个例子,我们在这里考虑最直接的RQI版本,应用于矩阵束B - \mu A;参见第4.3节。

算法 11.9:用于广义特征值问题的RQI与预处理内迭代求解器

(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) 使用 l_{i} 步多项式,相对于矩阵 T\left(B-\mu^{(i)} A\right) 求解器,以向量 x^{(i)} 作为初始猜测,找到预处理线性系统 T\left(B-\mu^{(i)} A\right) x=T A x^{(i)} 的近似解
(5) x^{(i+1)}:= 内迭代的最后一个迭代向量。

通常选择MINRES作为内迭代求解器,因为系统矩阵T(B - \mu^{(i)}A)是不定的。当仅使用固定数量的内迭代时,我们不能假设方程(B - \mu^{(i)}A) x = A x^{(i)}能被准确求解,因此,像RQI的三次收敛性这样的已知收敛特性,不能直接用来确立实际内外迭代方法的收敛性。同样,标准的扰动理论也不容易应用,除非假设内步数足够大。

方程中的矩阵B - \mu^{(i)}A是病态的,不仅因为A是病态的,还因为\mu^{(i)}越来越接近矩阵束B - \mu A的特征值。通常尝试通过投影出子空间{\rm span}\{ x^{(i)} \},使用正则化或/和选择不定预处理器 T 来改善矩阵的条件数。然而,内迭代收敛性的改善是否有利于只有少数内步的实际内外迭代方法的收敛,这一点并不明显。

还有几种具有类似特性的类似方法,例如,寻找特征向量的不同版本的牛顿法作为瑞利商的平稳向量(例如,[461,468])或截断的有理Krylov方法(例如,[378,291])或不完全同伦方法(例如,[309,235,469,310]);参见前一节。

Jacobi-Davidson方法[411],在第5.6节中描述了用于广义对称特征问题的求解,是这一类别中最著名的方法之一。带有预处理系统求解器作为内迭代的不精确Jacobi-Davidson方法确实符合我们对预处理特征求解器的定义。

这类方法在少量内迭代情况下的收敛行为尚未被充分理解。



下一节:预处理共轭梯度法 上一级:预条件特征值求解器 上一节:Davidson方法
Susan Blackford 2000-11-20