GMRES算法解非对称线性方程组
字数 3052 2025-10-26 19:15:23

GMRES算法解非对称线性方程组

题目描述
给定一个大型稀疏非对称线性方程组 Ax = b，其中 A 是 n×n 的非对称矩阵，b 是 n 维向量。请使用广义最小残量（GMRES）算法求解未知向量 x。该算法特别适用于系数矩阵 A 非对称且可能非正定的情况。

解题过程

GMRES 算法的核心思想是在一个不断扩大的 Krylov 子空间中，寻找一个向量，使得其对应的残差范数最小。这个过程可以循序渐进地理解。

第一步：问题转化与核心思想

  1. 初始猜测：我们从解的一个初始猜测 \(x_0\) 开始（例如，可以设为零向量）。
  2. 初始残差：计算初始残差 \(r_0 = b - A x_0\)。我们的目标是让这个残差趋近于零。
  3. Krylov 子空间：GMRES 算法在第 m 步迭代时，在如下的 Krylov 子空间中寻找近似解：

\[ x_m \in x_0 + \mathcal{K}_m(A, r_0) = x_0 + \text{span}\{ r_0, A r_0, A^2 r_0, \dots, A^{m-1} r_0 \} \]

这意味着，近似解 $ x_m $ 等于初始猜测 $ x_0 $ 加上一个由初始残差和矩阵 A 的幂次张成的空间中的一个向量。
  1. 最小残差准则：在所有的 \(x_m\) 中，GMRES 选择那个使得 2-范数 \(\| b - A x_m \|_2\) 最小的一个。这等价于在 Krylov 子空间中最小化残差。

第二步：构建正交基（Arnoldi 过程）

直接在 Krylov 子空间中进行最小化计算上是不稳定的。因此，GMRES 使用 Arnoldi 迭代过程为该子空间构建一组标准正交基 \(\{v_1, v_2, \dots, v_m\}\)，其中 \(v_1 = r_0 / \| r_0 \|_2\)。

  1. 初始化：

    • 计算初始残差：\(r_0 = b - A x_0\)
    • 计算第一个基向量：\(v_1 = r_0 / \beta\)，其中 \(\beta = \| r_0 \|_2\)

  2. 迭代构建（对于 j = 1 到 m）：

    • 矩阵向量乘法：计算 \(w = A v_j\)。
    • 正交化：对于 i = 1 到 j，计算 \(h_{i,j} = (w, v_i)\)（即 w 与所有已有基向量 \(v_i\) 的内积），然后从 w 中减去这些分量：\(w = w - h_{i,j} v_i\)。
      • 这一步确保了新向量 w 与之前所有的 \(v_i\) 正交。
    • 归一化：计算 \(h_{j+1, j} = \| w \|_2\)。如果 \(h_{j+1, j}\) 接近于 0，则算法提前终止。否则，新的基向量为 \(v_{j+1} = w / h_{j+1, j}\)。
    • 经过 j 步后，我们得到了一个标准正交向量组 \(V_m = [v_1, v_2, \dots, v_m]\)（一个 n×m 矩阵）。

第三步：将原问题投影到小规模问题上

Arnoldi 过程产生了一个关键关系：

\[A V_m = V_{m+1} \tilde{H}_m \]

其中 \(V_{m+1} = [v_1, v_2, \dots, v_m, v_{m+1}]\) 是 n×(m+1) 矩阵，\(\tilde{H}_m\) 是一个 (m+1)×m 的上 Hessenberg 矩阵（除了主对角线和次对角线，其他下方元素均为零），其元素就是 Arnoldi 过程中计算的 \(h_{i,j}\)。

现在，我们在 Krylov 子空间中寻找近似解 \(x_m = x_0 + V_m y\)，其中 \(y\) 是一个 m 维向量。我们的最小化问题变为：

\[\min_{x_m \in x_0 + \mathcal{K}_m} \| b - A x_m \|_2 = \min_{y \in \mathbb{R}^m} \| b - A(x_0 + V_m y) \|_2 = \min_{y \in \mathbb{R}^m} \| r_0 - A V_m y \|_2 \]

利用 \(r_0 = \beta v_1 = V_{m+1} (\beta e_1)\)（其中 \(e_1 = [1, 0, ..., 0]^T\) 是 m+1 维单位向量）和 \(A V_m = V_{m+1} \tilde{H}_m\)，上式可转化为：

\[\| r_0 - A V_m y \|_2 = \| V_{m+1} (\beta e_1) - V_{m+1} \tilde{H}_m y \|_2 = \| V_{m+1} (\beta e_1 - \tilde{H}_m y) \|_2 \]

因为 \(V_{m+1}\) 的列是标准正交的，乘以它不改变向量的 2-范数。所以最小化问题最终简化为一个非常小规模的问题：

\[\min_{y \in \mathbb{R}^m} \| \beta e_1 - \tilde{H}_m y \|_2 \]

第四步：求解最小二乘问题与得到近似解

  1. 问题规模缩减：我们现在只需要求解一个 (m+1)×m 维的最小二乘问题 \(\tilde{H}_m y \approx \beta e_1\)，其中 m 远小于原始问题的维度 n。这通常通过 QR 分解（例如 Givens 旋转）高效完成。
  2. 求解 y：对矩阵 \(\tilde{H}_m\) 进行 QR 分解：\(\tilde{H}_m = Q_m R_m\)，其中 \(Q_m\) 是 (m+1)×(m+1) 正交矩阵，\(R_m\) 是 (m+1)×m 的上三角矩阵（最后一行全为零）。最小二乘解 \(y_m\) 可以通过求解 \(R_m y = Q_m^T (\beta e_1)\) 的前 m 行得到。
  3. 计算近似解：得到 \(y_m\) 后，我们就可以计算出第 m 步的近似解：\(x_m = x_0 + V_m y_m\)。
  4. 检查收敛：计算当前残差范数 \(\| r_m \|_2 = \| b - A x_m \|_2\)。这个值在求解最小二乘问题的过程中很容易得到，它等于 \(| \rho_{m+1} |\)，即化简后问题中残差向量的最后一个分量的绝对值。如果 \(\| r_m \|_2\) 小于预设的容忍度，则算法终止，输出 \(x_m\) 作为解。否则，m 增加 1，继续 Arnoldi 过程，扩展 Krylov 子空间。

总结
GMRES 算法通过 Arnoldi 过程将大规模非对称问题巧妙地投影到一个不断扩大的低维 Krylov 子空间上，并在该子空间中解决一个最小残差问题。其优势在于无需存储庞大的矩阵 A（只需矩阵向量乘法），并且能有效处理非对称问题。其主要开销在于基向量的存储和正交化过程，当迭代步数很大时，可以通过重启策略（GMRES(m)）来管理内存。

GMRES算法解非对称线性方程组 题目描述 给定一个大型稀疏非对称线性方程组 Ax = b，其中 A 是 n×n 的非对称矩阵，b 是 n 维向量。请使用广义最小残量（GMRES）算法求解未知向量 x。该算法特别适用于系数矩阵 A 非对称且可能非正定的情况。 解题过程 GMRES 算法的核心思想是在一个不断扩大的 Krylov 子空间中，寻找一个向量，使得其对应的残差范数最小。这个过程可以循序渐进地理解。 第一步：问题转化与核心思想 初始猜测 ：我们从解的一个初始猜测 \( x_ 0 \) 开始（例如，可以设为零向量）。 初始残差 ：计算初始残差 \( r_ 0 = b - A x_ 0 \)。我们的目标是让这个残差趋近于零。 Krylov 子空间 ：GMRES 算法在第 m 步迭代时，在如下的 Krylov 子空间中寻找近似解： \[ x_ m \in x_ 0 + \mathcal{K}_ m(A, r_ 0) = x_ 0 + \text{span}\{ r_ 0, A r_ 0, A^2 r_ 0, \dots, A^{m-1} r_ 0 \} \] 这意味着，近似解 \( x_ m \) 等于初始猜测 \( x_ 0 \) 加上一个由初始残差和矩阵 A 的幂次张成的空间中的一个向量。 最小残差准则 ：在所有的 \( x_ m \) 中，GMRES 选择那个使得 2-范数 \( \| b - A x_ m \|_ 2 \) 最小的一个。这等价于在 Krylov 子空间中最小化残差。 第二步：构建正交基（Arnoldi 过程） 直接在 Krylov 子空间中进行最小化计算上是不稳定的。因此，GMRES 使用 Arnoldi 迭代过程为该子空间构建一组标准正交基 \( \{v_ 1, v_ 2, \dots, v_ m\} \)，其中 \( v_ 1 = r_ 0 / \| r_ 0 \|_ 2 \)。 初始化 ： 计算初始残差：\( r_ 0 = b - A x_ 0 \) 计算第一个基向量：\( v_ 1 = r_ 0 / \beta \)，其中 \( \beta = \| r_ 0 \|_ 2 \) 迭代构建（对于 j = 1 到 m） ： 矩阵向量乘法 ：计算 \( w = A v_ j \)。 正交化 ：对于 i = 1 到 j，计算 \( h_ {i,j} = (w, v_ i) \)（即 w 与所有已有基向量 \( v_ i \) 的内积），然后从 w 中减去这些分量：\( w = w - h_ {i,j} v_ i \)。 这一步确保了新向量 w 与之前所有的 \( v_ i \) 正交。 归一化 ：计算 \( h_ {j+1, j} = \| w \| 2 \)。如果 \( h {j+1, j} \) 接近于 0，则算法提前终止。否则，新的基向量为 \( v_ {j+1} = w / h_ {j+1, j} \)。 经过 j 步后，我们得到了一个标准正交向量组 \( V_ m = [ v_ 1, v_ 2, \dots, v_ m ] \)（一个 n×m 矩阵）。 第三步：将原问题投影到小规模问题上 Arnoldi 过程产生了一个关键关系： \[ A V_ m = V_ {m+1} \tilde{H} m \] 其中 \( V {m+1} = [ v_ 1, v_ 2, \dots, v_ m, v_ {m+1}] \) 是 n×(m+1) 矩阵，\( \tilde{H} m \) 是一个 (m+1)×m 的上 Hessenberg 矩阵（除了主对角线和次对角线，其他下方元素均为零），其元素就是 Arnoldi 过程中计算的 \( h {i,j} \)。 现在，我们在 Krylov 子空间中寻找近似解 \( x_ m = x_ 0 + V_ m y \)，其中 \( y \) 是一个 m 维向量。我们的最小化问题变为： \[ \min_ {x_ m \in x_ 0 + \mathcal{K} m} \| b - A x_ m \| 2 = \min {y \in \mathbb{R}^m} \| b - A(x_ 0 + V_ m y) \| 2 = \min {y \in \mathbb{R}^m} \| r_ 0 - A V_ m y \| 2 \] 利用 \( r_ 0 = \beta v_ 1 = V {m+1} (\beta e_ 1) \)（其中 \( e_ 1 = [ 1, 0, ..., 0]^T \) 是 m+1 维单位向量）和 \( A V_ m = V {m+1} \tilde{H} m \)，上式可转化为： \[ \| r_ 0 - A V_ m y \| 2 = \| V {m+1} (\beta e_ 1) - V {m+1} \tilde{H}_ m y \| 2 = \| V {m+1} (\beta e_ 1 - \tilde{H} m y) \| 2 \] 因为 \( V {m+1} \) 的列是标准正交的，乘以它不改变向量的 2-范数。所以最小化问题最终简化为一个非常小规模的问题： \[ \min {y \in \mathbb{R}^m} \| \beta e_ 1 - \tilde{H}_ m y \|_ 2 \] 第四步：求解最小二乘问题与得到近似解 问题规模缩减 ：我们现在只需要求解一个 (m+1)×m 维的最小二乘问题 \( \tilde{H}_ m y \approx \beta e_ 1 \)，其中 m 远小于原始问题的维度 n。这通常通过 QR 分解（例如 Givens 旋转）高效完成。 求解 y ：对矩阵 \( \tilde{H}_ m \) 进行 QR 分解：\( \tilde{H}_ m = Q_ m R_ m \)，其中 \( Q_ m \) 是 (m+1)×(m+1) 正交矩阵，\( R_ m \) 是 (m+1)×m 的上三角矩阵（最后一行全为零）。最小二乘解 \( y_ m \) 可以通过求解 \( R_ m y = Q_ m^T (\beta e_ 1) \) 的前 m 行得到。 计算近似解 ：得到 \( y_ m \) 后，我们就可以计算出第 m 步的近似解：\( x_ m = x_ 0 + V_ m y_ m \)。 检查收敛 ：计算当前残差范数 \( \| r_ m \|_ 2 = \| b - A x_ m \| 2 \)。这个值在求解最小二乘问题的过程中很容易得到，它等于 \( | \rho {m+1} | \)，即化简后问题中残差向量的最后一个分量的绝对值。如果 \( \| r_ m \|_ 2 \) 小于预设的容忍度，则算法终止，输出 \( x_ m \) 作为解。否则，m 增加 1，继续 Arnoldi 过程，扩展 Krylov 子空间。 总结 GMRES 算法通过 Arnoldi 过程将大规模非对称问题巧妙地投影到一个不断扩大的低维 Krylov 子空间上，并在该子空间中解决一个最小残差问题。其优势在于无需存储庞大的矩阵 A（只需矩阵向量乘法），并且能有效处理非对称问题。其主要开销在于基向量的存储和正交化过程，当迭代步数很大时，可以通过重启策略（GMRES(m)）来管理内存。