基于Krylov子空间的GMRES-DR算法（隐式重新启动的广义最小残差法结合谱变换）在求解大规模稀疏非对称线性方程组中的加速收敛策略
字数 2767 2025-12-18 14:01:26

基于Krylov子空间的GMRES-DR算法（隐式重新启动的广义最小残差法结合谱变换）在求解大规模稀疏非对称线性方程组中的加速收敛策略

算法描述
GMRES-DR（Generalized Minimal RESidual with Deflated Restarting）是求解大型稀疏非对称线性方程组 \(Ax = b\) 的一种Krylov子空间方法。它结合了标准GMRES算法和隐式重新启动技术，通过保留近似特征向量的信息来加速收敛。当矩阵 \(A\) 具有接近零或小模特征值时，标准GMRES在重启时可能丢失关键信息，导致收敛缓慢。GMRES-DR 在每次重启时保留一组近似特征向量（称为“调和Ritz向量”），用于构建子空间，从而改善重启后的收敛性。该方法特别适用于特征值分布不利的问题（如具有小特征值或病态矩阵）。

解题过程循序渐进讲解
我们将从问题背景、Krylov子空间构建、调和Ritz向量提取、隐式重新启动机制，到完整算法步骤，逐步展开。

步骤1：问题形式化与标准GMRES的局限性

  • 求解线性方程组 \(Ax = b\)，其中 \(A \in \mathbb{R}^{n \times n}\) 非对称稀疏，\(b \in \mathbb{R}^n\)。
  • 标准GMRES在 \(m\) 步迭代后构建Krylov子空间 \(\mathcal{K}_m(A, r_0) = \text{span}\{r_0, A r_0, \dots, A^{m-1} r_0\}\)，其中 \(r_0 = b - A x_0\) 为初始残差。
  • 解近似为 \(x_m = x_0 + V_m y_m\)，其中 \(V_m\) 是子空间正交基，\(y_m\) 通过最小化残差范数 \(\|b - A x_m\|\) 得到。
  • 当 \(m\) 较大时，存储和计算成本高，需重启（重置子空间）。但重启会丢弃特征信息，可能使收敛停滞。

步骤2：GMRES-DR的核心思想

  • 在重启时，不丢弃全部信息，而是保留 \(k\) 个近似特征向量（调和Ritz向量），这些向量近似对应于 \(A\) 的极端特征值（尤其是小模特征值，因其影响收敛）。
  • 新子空间由这些特征向量和当前残差向量张成，形式为：
    \(\mathcal{K}_{m}(A, [v_1, \dots, v_k, r_{m}])\)，其中 \(v_i\) 是保留的调和Ritz向量，\(r_m\) 是当前残差。
  • 这相当于隐式地应用了谱变换，将不利特征值“压缩”，加速后续迭代。

步骤3：调和Ritz向量的计算

  • 在GMRES的Arnoldi过程中，得到关系：
    \(A V_m = V_{m+1} \bar{H}_m\)，其中 \(\bar{H}_m \in \mathbb{R}^{(m+1) \times m}\) 是上Hessenberg矩阵。
  • 调和Ritz对 \((\theta, u)\) 满足：
    \((A - \theta I)^* (A u - \theta u) \perp A \mathcal{K}_m(A, r_0)\)，可简化为求解广义特征值问题：
    \(H_m^* H_m y = \theta H_m^* e_1 \|r_0\|\)，其中 \(H_m\) 是 \(\bar{H}_m\) 的前 \(m\) 行，\(u = V_m y\)。
  • 实际计算中，通过求解小型矩阵 \((H_m^T H_m + h_{m+1,m}^2 e_m e_m^T) y = \theta H_m^T e_1 \|r_0\|\) 得到近似特征对，选取 \(k\) 个对应 \(|\theta|\) 最小的特征向量 \(u_i = V_m y_i\)。

步骤4：隐式重新启动与子空间构建

  • 重启时，构造新子空间的初始正交基 \(V_{\text{new}} = [u_1, \dots, u_k, r_m / \|r_m\|]\)，但需保证基的正交性（例如用Modified Gram-Schmidt处理）。
  • 随后对新基执行Arnoldi过程，扩展子空间到维度 \(m\)。这相当于隐式重启的Arnoldi方法，但目标是最小化残差而非计算特征值。
  • 关键技巧：通过正交变换将调和Ritz向量嵌入新基的前 \(k\) 列，并更新Hessenberg矩阵，避免显式重建。

步骤5：GMRES-DR算法步骤

  1. 输入：矩阵 \(A\)，右端项 \(b\)，初始猜测 \(x_0\)，重启维度 \(m\)，保留特征向量数 \(k\)（\(k < m\)），容差 \(\epsilon\)。
  2. 计算初始残差 \(r_0 = b - A x_0\)，令 \(V_1 = r_0 / \|r_0\|\)。
  3. 主循环：
    a. 执行 \(m\) 步Arnoldi过程，构建 \(V_m\) 和上Hessenberg矩阵 \(\bar{H}_m\)。
    b. 求解最小二乘问题 \(\min \| \|r_0\| e_1 - \bar{H}_m y \|\) 得 \(y_m\)，更新近似解 \(x = x_0 + V_m y_m\)，计算残差范数。
    c. 若残差小于 \(\epsilon\)，终止。
    d. 从当前子空间计算 \(k\) 个调和Ritz向量（对应 \(|\theta|\) 最小的特征对）。
    e. 隐式重启：
    • 对 \(k+1\) 维子空间 \([u_1, \dots, u_k, r_m]\) 正交化，得到新基 \(V_{k+1}\)。
    • 更新Hessenberg矩阵：通过正交变换将 \(A V_{k+1}\) 表示为新基的线性组合，得到 \(\bar{H}_{k+1}\)。
    • 继续执行Arnoldi过程，将子空间从 \(k+1\) 维扩展到 \(m\) 维。
      f. 重复步骤a-e直到收敛。

步骤6：收敛性与实际考虑

  • 保留调和Ritz向量相当于在重启后子空间中引入了近似不变子空间，降低了小特征值对残差的负面影响。
  • 参数选择：通常 \(m\) 取20–50，\(k\) 取5–15，取决于问题规模和特征值分布。
  • 复杂度：每次迭代需矩阵-向量乘、正交化和小型稠密矩阵运算（\(O(m^2)\)），但比标准GMRES收敛更快，减少总迭代数。

总结
GMRES-DR通过隐式重启和调和Ritz向量保留，有效缓解了GMRES重启时的信息丢失问题，特别适用于具有不利特征值分布的非对称问题。其核心在于将特征值信息融入Krylov子空间，实现加速收敛。

基于Krylov子空间的GMRES-DR算法（隐式重新启动的广义最小残差法结合谱变换）在求解大规模稀疏非对称线性方程组中的加速收敛策略 算法描述 GMRES-DR（Generalized Minimal RESidual with Deflated Restarting）是求解大型稀疏非对称线性方程组 \(Ax = b\) 的一种Krylov子空间方法。它结合了标准GMRES算法和隐式重新启动技术，通过保留近似特征向量的信息来加速收敛。当矩阵 \(A\) 具有接近零或小模特征值时，标准GMRES在重启时可能丢失关键信息，导致收敛缓慢。GMRES-DR 在每次重启时保留一组近似特征向量（称为“调和Ritz向量”），用于构建子空间，从而改善重启后的收敛性。该方法特别适用于特征值分布不利的问题（如具有小特征值或病态矩阵）。 解题过程循序渐进讲解 我们将从问题背景、Krylov子空间构建、调和Ritz向量提取、隐式重新启动机制，到完整算法步骤，逐步展开。 步骤1：问题形式化与标准GMRES的局限性 求解线性方程组 \(Ax = b\)，其中 \(A \in \mathbb{R}^{n \times n}\) 非对称稀疏，\(b \in \mathbb{R}^n\)。 标准GMRES在 \(m\) 步迭代后构建Krylov子空间 \(\mathcal{K}_ m(A, r_ 0) = \text{span}\{r_ 0, A r_ 0, \dots, A^{m-1} r_ 0\}\)，其中 \(r_ 0 = b - A x_ 0\) 为初始残差。 解近似为 \(x_ m = x_ 0 + V_ m y_ m\)，其中 \(V_ m\) 是子空间正交基，\(y_ m\) 通过最小化残差范数 \(\|b - A x_ m\|\) 得到。 当 \(m\) 较大时，存储和计算成本高，需重启（重置子空间）。但重启会丢弃特征信息，可能使收敛停滞。 步骤2：GMRES-DR的核心思想 在重启时，不丢弃全部信息，而是保留 \(k\) 个近似特征向量（调和Ritz向量），这些向量近似对应于 \(A\) 的极端特征值（尤其是小模特征值，因其影响收敛）。 新子空间由这些特征向量和当前残差向量张成，形式为： \(\mathcal{K} {m}(A, [ v_ 1, \dots, v_ k, r {m}])\)，其中 \(v_ i\) 是保留的调和Ritz向量，\(r_ m\) 是当前残差。 这相当于隐式地应用了谱变换，将不利特征值“压缩”，加速后续迭代。 步骤3：调和Ritz向量的计算 在GMRES的Arnoldi过程中，得到关系： \(A V_ m = V_ {m+1} \bar{H}_ m\)，其中 \(\bar{H}_ m \in \mathbb{R}^{(m+1) \times m}\) 是上Hessenberg矩阵。 调和Ritz对 \((\theta, u)\) 满足： \((A - \theta I)^* (A u - \theta u) \perp A \mathcal{K}_ m(A, r_ 0)\)，可简化为求解广义特征值问题： \(H_ m^* H_ m y = \theta H_ m^* e_ 1 \|r_ 0\|\)，其中 \(H_ m\) 是 \(\bar{H}_ m\) 的前 \(m\) 行，\(u = V_ m y\)。 实际计算中，通过求解小型矩阵 \((H_ m^T H_ m + h_ {m+1,m}^2 e_ m e_ m^T) y = \theta H_ m^T e_ 1 \|r_ 0\|\) 得到近似特征对，选取 \(k\) 个对应 \(|\theta|\) 最小的特征向量 \(u_ i = V_ m y_ i\)。 步骤4：隐式重新启动与子空间构建 重启时，构造新子空间的初始正交基 \(V_ {\text{new}} = [ u_ 1, \dots, u_ k, r_ m / \|r_ m\| ]\)，但需保证基的正交性（例如用Modified Gram-Schmidt处理）。 随后对新基执行Arnoldi过程，扩展子空间到维度 \(m\)。这相当于隐式重启的Arnoldi方法，但目标是最小化残差而非计算特征值。 关键技巧：通过正交变换将调和Ritz向量嵌入新基的前 \(k\) 列，并更新Hessenberg矩阵，避免显式重建。 步骤5：GMRES-DR算法步骤 输入 ：矩阵 \(A\)，右端项 \(b\)，初始猜测 \(x_ 0\)，重启维度 \(m\)，保留特征向量数 \(k\)（\(k < m\)），容差 \(\epsilon\)。 计算初始残差 \(r_ 0 = b - A x_ 0\)，令 \(V_ 1 = r_ 0 / \|r_ 0\|\)。 主循环 ： a. 执行 \(m\) 步Arnoldi过程，构建 \(V_ m\) 和上Hessenberg矩阵 \(\bar{H}_ m\)。 b. 求解最小二乘问题 \(\min \| \|r_ 0\| e_ 1 - \bar{H}_ m y \|\) 得 \(y_ m\)，更新近似解 \(x = x_ 0 + V_ m y_ m\)，计算残差范数。 c. 若残差小于 \(\epsilon\)，终止。 d. 从当前子空间计算 \(k\) 个调和Ritz向量（对应 \(|\theta|\) 最小的特征对）。 e. 隐式重启： 对 \(k+1\) 维子空间 \([ u_ 1, \dots, u_ k, r_ m]\) 正交化，得到新基 \(V_ {k+1}\)。 更新Hessenberg矩阵：通过正交变换将 \(A V_ {k+1}\) 表示为新基的线性组合，得到 \(\bar{H}_ {k+1}\)。 继续执行Arnoldi过程，将子空间从 \(k+1\) 维扩展到 \(m\) 维。 f. 重复步骤a-e直到收敛。 步骤6：收敛性与实际考虑 保留调和Ritz向量相当于在重启后子空间中引入了近似不变子空间，降低了小特征值对残差的负面影响。 参数选择：通常 \(m\) 取20–50，\(k\) 取5–15，取决于问题规模和特征值分布。 复杂度：每次迭代需矩阵-向量乘、正交化和小型稠密矩阵运算（\(O(m^2)\)），但比标准GMRES收敛更快，减少总迭代数。 总结 GMRES-DR通过隐式重启和调和Ritz向量保留，有效缓解了GMRES重启时的信息丢失问题，特别适用于具有不利特征值分布的非对称问题。其核心在于将特征值信息融入Krylov子空间，实现加速收敛。