收敛性质

在本节中，我们将详细讨论收敛性质。首先回顾了Lanczos算法背景下的SI方法。接着概述了针对非对称特征值问题的双侧算法的收敛理论，并参考了本文其他部分的内容。最后，回顾了应对无法获得归一化残差的技术。

Ritz值倾向于首先收敛到谱的凸包边界上的特征值。为了计算内部特征值，通常值得对A应用谱变换。策略是通过将复平面中期望的特征值映射到变换谱的外部来加速收敛速率。标准方法是将对Lanczos算法应用于移位和逆矩阵

C=(A-\sigma I)^{-1} \tag{7.44}

复平面中离移位\sigma最近的特征值首先收敛。注意，LU分解，

A-\sigma I = LU, \tag{7.46}

可以用于计算Lanczos算法中所需的C q_j = U^{-1}(L^{-1}q)和C^{\ast} p_j =L^{-\ast}(U^{-\ast}p)。参见第§10.3节。

非对称特征值问题(NHEP)的一个内在困难是，已知的\theta_i^{(j)}到A的特征值的距离界限不实用[425,256]。另一个复杂之处是，为了有用，双侧算法的收敛理论必须考虑到左右Krylov子空间同时近似A的特征值这一事实。这两个问题通过界定距离\Vert F\Vert到具有特征三元组(\theta_i^{(j)},x_i^{(j)},y_i^{(j)})的最近矩阵A-F来解决。特征值敏感度（条件数）也可用。回想残差向量r_i^{(j)}和s_i^{(j)}，如式(7.40)和(7.41)所定义。接下来观察到双正交条件(7.37)意味着(s_i^{(j)})^{\ast} x_i^{(j)} = (y_i^{(j)})^{\ast} r_i^{(j)} = 0。这些关系一起意味着

F = \frac{ r_i^{(j)} (x_i^{(j)})^{\ast} }{ \Vert x_i^{(j)}\Vert^2_2 } + \frac{ y_i^{(j)} (s_i^{(j)})^{\ast}}{ \Vert y_i^{(j)}\Vert^2_2 } \tag{7.46}

是所需的扰动，使得

(A-F) x_i^{(j)} = x_i^{(j)} \theta_i^{(j)}, \tag{7.47}

(y_i^{(j)})^{\ast} (A-F) = \theta_i^{(j)} (y_i^{(j)})^{\ast}, \tag{7.48}

并且\Vert F\Vert^2_{\rm F} = \Vert r_i^{(j)}\Vert^2_2/ \Vert x_i^{(j)}\Vert^2_2 +\Vert s_i^{(j)}\Vert^2_2 / \Vert y_i^{(j)}\Vert^2_2。参见第§7.13节，进一步讨论如何推导近似特征值和特征向量的精度误差界限。

关于测试Ritz向量收敛性存在一个微妙但关键的复杂问题。原始矩阵A的近似特征向量仅在步骤(16)的测试表明Ritz值\theta^{(j)}_i收敛到A的期望特征值后才计算。如果存储了Lanczos向量，则使用基Q_j和P_j来获取近似特征向量。如果未存储Lanczos向量，则有两种可能性[93]：要么重新运行三项递归来生成请求的特征向量，要么应用逆迭代（参见第§7.4节）。复杂之处在于，决定是否接受Ritz向量作为近似特征向量不能基于这些未归一化的残差。在计算了x_i^{(j)}=Q_jz_i^{(j)}和y_i^{(j)}=P_j w_i^{(j)}之后，需要比较归一化残差

\frac{ \Vert r_i^{(j)}\Vert _2 }{ \Vert x_i^{(j)} \Vert _2 } \quad\text{和}\quad \frac{ \Vert s_i^{(j)}\Vert _2 }{ \Vert y_i^{(j)} \Vert _2 }

到用户指定的容差。归一化残差的范数可能大于未归一化残差的范数。可能需要拒绝计算的Ritz向量，继续Lanczos算法，然后重新计算Ritz向量。如果\Vert Q_j z_i^{(j)}\Vert _2显著小于\Vert z_i^{(j)}\Vert _2，则拒绝Ritz向量x_i^{(j)}。这种缩小的两个常见原因是由于双正交性的损失，\theta_i^{(j)}是一个虚假特征值[93]。这种情况可以通过重新双正交化[105]或不计算对应于虚假模式的Ritz向量[93]来解决。

缩小的第二个常见原因是最好在Lanczos算法的实现中解释，其中q_j和p_j被缩放到具有单位欧几里得长度[179,354,105]。内积

\omega_i = \frac{p_j^* q_j}{ \Vert p_j\Vert _2 \Vert q_j\Vert _2}

界定了Lanczos向量矩阵的条件数[354]。在[29]中表明

\mathrm{cond}(Q_j) = \Vert Q_j\Vert _2 \Vert Q^{\dagger}_j\Vert _2\leq \sum^j_{i=1} \vert \omega_i \vert ^{-1},

其中Q^{\dagger}_j表示Q_j的广义逆，该界限也适用于\mathrm{cond}(P_j)。右Krylov子空间近似不变，如果\Vert r_j\Vert _2相对于三对角矩阵范数（容易估计）与\Vert Q_j\Vert _2的乘积非常小。在这种尺度下，界限\Vert Q_j\Vert _2 \leq \sqrt{j}简化了不变子空间的检测。

通常，\{ \vert \omega_i \vert \}在数百次Lanczos步骤中几乎单调且大幅下降[179,105]。在这种情况下，未归一化的残差对于那些直到\vert\omega_i\vert下降了几个数量级后才出现的Ritz值的估计效果不佳。更准确地说，对于具有特殊性质的特征向量z_i^{(j)}，即z_i^{(j)}(1:k)可忽略不计，下界

\Vert Q_jz_i^{(j)} \Vert _2 \geq \max_{i >k} \vert \omega_i \vert \Vert z_i^{(j)}\Vert _2/\sqrt{j-(k+1)}

很可能是近似相等的，如果\max_{i >k} \vert \omega_i \vert极其小，则不建议形成Q_jz_i^{(j)}。