预处理的一般框架

预处理方法旨在应对这样的情况：我们仅能对矩阵束中的矩阵 A 和 B 执行向量乘法操作。为了加速收敛，我们引入一个预处理器 T。通常也将其逆 T^{-1} = M 称为预处理器；例如，参见前一节。将预处理器 Tx 应用于向量 x 通常涉及求解线性系统 Mu=f。

在许多工程应用中，线性系统 Ax=b 的预处理迭代求解器已经可用，并且构建了高效的预处理器 T \approx A^{-1}。我们将展示，同样的预处理器 T 可以用于求解特征值问题 Ax = \lambda x 和 Bx = \mu Ax。此外，现有的 Ax=b 系统代码通常只需稍作修改，即可用于求解带 A 的部分特征值问题。

我们将假设预处理器 T 是对称正定的。由于 A 也是对称正定的，因此存在正的常数 \delta_1 \geq \delta_0 > 0 使得

\delta_0 (M x,x) \leq (Ax,x) \leq \delta_1 (M x,x), \ M = T^{-1} . \tag{11.9}

比值 \delta_1 / \delta_0 可以视为预处理矩阵 TA 的谱条件数 \kappa(TA)，并衡量 M 在缩放范围内对原矩阵 A 的近似程度。较小的比值 \delta_1 / \delta_0 确保更快的收敛。

对于对称特征值问题，也可能使用不定预处理器，但不推荐。当预处理器不定的情况下，通常应使用基于残差最小化的非对称问题迭代方法，这可能会显著增加计算成本。

我们不假设预处理器 T 与 A 或 A^{-1}B 可交换，尽管这种假设会极大地简化预处理方法的理论。

我们首先定义，参照 [268]，对于矩阵束 B - \mu A，一个预处理的单向量迭代求解器，作为一种广义多项式方法：

x^{(k)}=P_{m_k}(TA,TB) x^{(0)}, \tag{11.10}

其中 P_{m_k} 是两个独立变量的 m_k 次多项式， x^{(0)} 是初始猜测，T 是固定的预处理器。

我们只需选择一个多项式，无论是先验的还是迭代过程中的，并使用递归公式来引导迭代方案。对于给定的特征向量近似 x^{(i)}，对于矩阵束 B - \mu A 的特征值近似 \mu^{(i)}，通常使用瑞利商 \mu (x) (11.8)：

\mu(x^{(i)}) = \frac {(x^{(i)},Bx^{(i)})}{(x^{(i)},A x^{(i)})}.

因此，我们有了一个完整的预处理特征求解器，用于矩阵束 B - \mu A 的描述，如下所示：

预处理特征求解器

1. 开始：选择 x^{(0)}。
2. 迭代 m_k 步，计算 x^{(k)}=P_{m_k}(TA,TB) x^{(0)}。
3. 计算 \mu^{(k)} = {(x^{(k)},Bx^{(k)})}/{(x^{(k)},A x^{(k)})}。

当 B=I 且 \lambda = 1 / \mu 时，我们可以得到一个类似的算法用于 A - \lambda I。多项式可以选择特殊方式，以迫使 x^{(k)} 收敛到非极端特征值对应的特征向量。

类似地，我们定义一般的预处理块迭代方法，其中一组向量 x^{(k)}_j, \ j=1, \ldots, m，同时计算：

x^{(k)}_j=P_{m_k}(TA,TB) x^{(0)}_j, \qquad j=1, \ldots, m, \tag{11.11}

其中 P_{m_k} 是两个独立变量的 m_k 次多项式， x^{(0)}_j 是初始猜测。多项式 P_{m_k} 不必（实际上通常不是）对不同的 j 值相同。如果相同，则 (11.11) 可以重写为子空间迭代：

S^{(k)}=P_{m_k}(TA,TB) S^{(0)}, \tag{11.12}

其中 S^{(0)} 和 S^{(k)} 是 m 维子空间。这种方法在理论上更容易分析；参见基于移位幂方法的预处理子空间迭代的例子 [148,149]，但在实践中可能收敛较慢。

在 (11.11) 中，迭代子空间 S^{(k)} 定义为单个向量 x^{(k)}_j 的跨度：

S^{(k)} = {\rm span}\{ x^{(k)}_1, \ldots, x^{(k)}_m \}

通常通过将其与选择 S^{(k)} 中单个向量作为下一递归步骤初始向量的过程结合，来递归使用 (11.11)。瑞利-里兹方法是这种过程的常见选择。递归的一步如下所示：

块预处理特征求解器

1. 开始：选择 x^{(0)}_j, \ j=1, \ldots, m。
2. 迭代 m_k 步，计算 \hat{x}^{(k)}_j=P_{m_k}(TA,TB) x^{(0)}_j, \ j=1, \ldots, m。
3. 在子空间 {\rm span} \{ \hat{x}^{(k)}_1, \ldots, \hat{x}^{(k)}_m \} 中使用瑞利-里兹方法，计算矩阵束 B - \mu A 的里兹值 \mu^{(k)}_j 和相应的里兹向量 x^{(k)}_j。

在以下章节中，我们将考虑预处理特征求解器的具体例子。