预处理Lanczos方法

假设A和B是对称的，并且我们有一个正定的预处理器M用于A - \mu B，即M \approx A - \mu B。我们可以对M^{-1} (A-\nu B)应用Arnoldi方法来计算接近\mu的特征值。（再次使用Ritz值\theta作为零。）这导致递推关系

M^{-1} (A - \nu B) V_k = V_k H_k + f_k e_k^T \ .

由于M是正定的，我们有x^{\ast} M y是一个有效的内积。当我们在Arnoldi方法中使用M内积x^{\ast} M y而不是标准内积x^{\ast}y时，我们有V_k^{\ast} M V_k = I和 V_k^{\ast} M f_k = 0， 因此H_k = V_k^{\ast} (A-\nu B) V_k是一个对称矩阵。这意味着使用M内积的Arnoldi方法简化为对非对称矩阵M^{-1} (A-\nu B)应用M内积的Lanczos方法。从前面的讨论中，我们得出结论，使用M内积的预处理Lanczos方法与应用于扰动问题的谱变换Lanczos方法具有类似的收敛行为。

设(\zeta,z)满足H_k z = \zeta z，并定义Ritz向量x = V_k z。这个向量是从Lanczos（Arnoldi）递推关系中获得的，而不是从Galerkin投影中获得的。另一方面，Ritz值可以通过Rayleigh商计算，即

\begin{aligned} \theta & = x^{\ast} A x / x^{\ast} B x \\ & = \nu + x^{\ast} (A - \nu B) x / x^{\ast} B x \\ & = \nu + z^{\ast} V^{\ast}_k (A - \nu B) V_k z / x^{\ast} B x \\ & = \nu + z^{\ast} H_k z / x^{\ast} B x \\ & = \nu + \zeta / x^{\ast} B x, \end{aligned}

这在B是对角矩阵时计算成本较低。

回想一下，对于不精确的Cayley变换 T_{\mathrm{IC}} = M^{-1} (A - \nu B)，Lanczos递推关系是

T_{\mathrm{IC}} V_k - V_k H_k = f_k e_k^T \ .

递推关系也可以写成

T_{\mathrm{C}} V_k - V_k H_k = f_k e_k^T + (T_{\mathrm{C}} - T_{\mathrm{IC}}) V_k.

我们知道对于一个Ritz对(x, \theta)，当\theta \approx \nu时，(T_{\mathrm{C}} - T_{\mathrm{IC}}) x可能很小。因此，如果x接近T_{\mathrm{IC}}的特征向量，并且\theta接近\nu，那么x接近T_{\mathrm{C}}的特征向量，因此Ritz值\theta接近Ax = \lambda Bx的特征值。

Morgan和Scott[336]证明了以下算法的收敛性，用于计算Ax = \lambda x的特征值，即B=I。

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

(1) 给定 v_{1},\left\|v_{1}\right\|=1 和 \nu_{1}=v_{1}^{*} A v_{1}/ v_{1}^{*} B v_{1}
(2) 对于 l=1,2,\ldots 执行
(3) 为 A-\mu_{l} B 选择一个预处理器 M_{l}。
(4) 在 T_{IC}^{(l)}=M_{l}^{-1}\left(A-\nu_{l} B\right) 上运行k步Lanczos方法，并应用 M_{l} 正交化。
(5) 计算Ritz向量 x_{l}=V_{k} z_{l}，其中 H_{k} z_{l}=\zeta_{l} z_{l}，且 \zeta_{l} 是 H_{k} 的最小Ritz值。
(6) 计算 \nu_{l+1}=\theta_{l}=\nu_{l}+\zeta_{l}/ x_{l}^{*} B x_{l}。
(7) 如果 \left\|A x_{l}-\theta_{l} B x_{l}\right\|\leq TOL，则停止。

注意，如果\mu=\nu，那么预处理器不能太好地近似A - \mu B；否则T_{\mathrm{IC}} \approx I。k的值可能对每个l都不同。Morgan和Scott建议停止测试 -\zeta_l > \Vert T_{\mathrm{IC}}^{(l)} x_l - \zeta_l x_l\Vert，这在Lanczos方法中计算成本较低。在[336]中显示，如果M_l和M_l^{-1}在范数上一致有界，\theta_l收敛到 A 的一个特征值。此外，渐近收敛是二次的。