广义极小残差法（GMRES）解非对称线性方程组

字数 2342 2025-10-31 08:19:17

广义极小残差法（GMRES）解非对称线性方程组

题目描述
广义极小残差法（GMRES）是一种迭代算法，用于求解大型稀疏非对称线性方程组 \(A\mathbf{x} = \mathbf{b}\)，其中 \(A\) 是 \(n \times n\) 的非对称矩阵。该算法通过构建Krylov子空间，并在该子空间中寻找使残差 \(\|\mathbf{b} - A\mathbf{x}_k\|_2\) 最小的近似解 \(\mathbf{x}_k\)。GMRES特别适用于非对称矩阵，因为它不依赖矩阵的对称性或正定性。

解题过程

问题转化与初始设置
- 目标：求 \(\mathbf{x} \in \mathbb{R}^n\) 使得 \(A\mathbf{x} = \mathbf{b}\)。
- 初始猜测解 \(\mathbf{x}_0\)（常取零向量），计算初始残差 \(\mathbf{r}_0 = \mathbf{b} - A\mathbf{x}_0\) 和残差范数 \(\beta = \|\mathbf{r}_0\|_2\)。
- 定义Krylov子空间：

\[ \mathcal{K}_k(A, \mathbf{r}_0) = \text{span}\{\mathbf{r}_0, A\mathbf{r}_0, A^2\mathbf{r}_0, \dots, A^{k-1}\mathbf{r}_0\}. \]

 GMRES在第 $ k $ 步寻找解 $ \mathbf{x}_k \in \mathbf{x}_0 + \mathcal{K}_k(A, \mathbf{r}_0) $，使得残差最小化。

Arnoldi过程构建正交基
- 使用Arnoldi迭代将 \(A\) 投影到Krylov子空间上，生成一组标准正交基 \(\{\mathbf{v}_1, \dots, \mathbf{v}_k\}\)（通过Gram-Schmidt正交化）：
  1. 初始化：\(\mathbf{v}_1 = \mathbf{r}_0 / \beta\)。
  2. 对于 \(j = 1, 2, \dots, k\)：
    - 计算 \(\mathbf{w}_j = A\mathbf{v}_j\)。
    - 对 \(i = 1\) 到 \(j\)，计算投影系数 \(h_{ij} = \mathbf{v}_i^\top \mathbf{w}_j\)，并正交化：\(\mathbf{w}_j \leftarrow \mathbf{w}_j - h_{ij}\mathbf{v}_i\)。
    - 计算 \(h_{j+1,j} = \|\mathbf{w}_j\|_2\)，若 \(h_{j+1,j} = 0\) 则提前终止，否则归一化 \(\mathbf{v}_{j+1} = \mathbf{w}_j / h_{j+1,j}\)。
- 得到关系式：

\[ A V_k = V_{k+1} \tilde{H}_k, \]

 其中 $ V_k = [\mathbf{v}_1, \dots, \mathbf{v}_k] $ 是正交基矩阵，$ \tilde{H}_k $ 是 $ (k+1) \times k $ 的上Hessenberg矩阵。

最小二乘问题求解
- 设近似解 \(\mathbf{x}_k = \mathbf{x}_0 + V_k \mathbf{y}_k\)（\(\mathbf{y}_k \in \mathbb{R}^k\)），则残差：

\[ \mathbf{r}_k = \mathbf{b} - A\mathbf{x}_k = \mathbf{r}_0 - A V_k \mathbf{y}_k = \beta \mathbf{v}_1 - V_{k+1} \tilde{H}_k \mathbf{y}_k. \]

由于 \(V_{k+1}\) 列正交，最小化 \(\|\mathbf{r}_k\|_2\) 等价于最小化：

\[ \|\beta \mathbf{e}_1 - \tilde{H}_k \mathbf{y}_k\|_2, \quad \mathbf{e}_1 = [1, 0, \dots, 0]^\top \in \mathbb{R}^{k+1}. \]

通过Givens旋转将 \(\tilde{H}_k\) 转换为上三角矩阵 \(R_k\)，并同步更新右端项 \(\beta \mathbf{e}_1\) 为 \(\mathbf{g}_k\)，最终解 \(\mathbf{y}_k = R_k^{-1} \mathbf{g}_k\)。

迭代终止与重启策略
- 当残差范数 \(\|\mathbf{r}_k\|_2\) 小于预设容忍度时，输出 \(\mathbf{x}_k\)。
- 若迭代步数 \(k\) 过大（避免存储成本过高），采用重启GMRES：用当前解 \(\mathbf{x}_k\) 作为新的 \(\mathbf{x}_0\)，重新开始迭代。

关键点总结

GMRES通过Arnoldi过程保证数值稳定性，避免直接计算幂次导致的病态问题。
每步迭代需存储所有基向量 \(\mathbf{v}_j\)，因此重启策略对大规模问题至关重要。
对于对称矩阵，GMRES退化为MINRES算法，可节省计算量。

广义极小残差法（GMRES）解非对称线性方程组题目描述广义极小残差法（GMRES）是一种迭代算法，用于求解大型稀疏非对称线性方程组 \( A\mathbf{x} = \mathbf{b} \)，其中 \( A \) 是 \( n \times n \) 的非对称矩阵。该算法通过构建Krylov子空间，并在该子空间中寻找使残差 \( \|\mathbf{b} - A\mathbf{x}_ k\|_ 2 \) 最小的近似解 \( \mathbf{x}_ k \)。GMRES特别适用于非对称矩阵，因为它不依赖矩阵的对称性或正定性。解题过程问题转化与初始设置目标：求 \( \mathbf{x} \in \mathbb{R}^n \) 使得 \( A\mathbf{x} = \mathbf{b} \)。初始猜测解 \( \mathbf{x}_ 0 \)（常取零向量），计算初始残差 \( \mathbf{r}_ 0 = \mathbf{b} - A\mathbf{x}_ 0 \) 和残差范数 \( \beta = \|\mathbf{r}_ 0\|_ 2 \)。定义Krylov子空间： \[ \mathcal{K}_ k(A, \mathbf{r}_ 0) = \text{span}\{\mathbf{r}_ 0, A\mathbf{r}_ 0, A^2\mathbf{r}_ 0, \dots, A^{k-1}\mathbf{r}_ 0\}. \] GMRES在第 \( k \) 步寻找解 \( \mathbf{x}_ k \in \mathbf{x}_ 0 + \mathcal{K}_ k(A, \mathbf{r}_ 0) \)，使得残差最小化。 Arnoldi过程构建正交基使用Arnoldi迭代将 \( A \) 投影到Krylov子空间上，生成一组标准正交基 \( \{\mathbf{v}_ 1, \dots, \mathbf{v}_ k\} \)（通过Gram-Schmidt正交化）：初始化：\( \mathbf{v}_ 1 = \mathbf{r}_ 0 / \beta \)。对于 \( j = 1, 2, \dots, k \)：计算 \( \mathbf{w}_ j = A\mathbf{v}_ j \)。对 \( i = 1 \) 到 \( j \)，计算投影系数 \( h_ {ij} = \mathbf{v}_ i^\top \mathbf{w}_ j \)，并正交化：\( \mathbf{w}_ j \leftarrow \mathbf{w} j - h {ij}\mathbf{v}_ i \)。计算 \( h_ {j+1,j} = \|\mathbf{w} j\| 2 \)，若 \( h {j+1,j} = 0 \) 则提前终止，否则归一化 \( \mathbf{v} {j+1} = \mathbf{w} j / h {j+1,j} \)。得到关系式： \[ A V_ k = V_ {k+1} \tilde{H}_ k, \] 其中 \( V_ k = [ \mathbf{v}_ 1, \dots, \mathbf{v}_ k] \) 是正交基矩阵，\( \tilde{H}_ k \) 是 \( (k+1) \times k \) 的上Hessenberg矩阵。最小二乘问题求解设近似解 \( \mathbf{x}_ k = \mathbf{x}_ 0 + V_ k \mathbf{y}_ k \)（\( \mathbf{y}_ k \in \mathbb{R}^k \)），则残差： \[ \mathbf{r}_ k = \mathbf{b} - A\mathbf{x}_ k = \mathbf{r}_ 0 - A V_ k \mathbf{y}_ k = \beta \mathbf{v} 1 - V {k+1} \tilde{H}_ k \mathbf{y}_ k. \] 由于 \( V_ {k+1} \) 列正交，最小化 \( \|\mathbf{r}_ k\|_ 2 \) 等价于最小化： \[ \|\beta \mathbf{e}_ 1 - \tilde{H}_ k \mathbf{y}_ k\|_ 2, \quad \mathbf{e}_ 1 = [ 1, 0, \dots, 0 ]^\top \in \mathbb{R}^{k+1}. \] 通过Givens旋转将 \( \tilde{H}_ k \) 转换为上三角矩阵 \( R_ k \)，并同步更新右端项 \( \beta \mathbf{e}_ 1 \) 为 \( \mathbf{g}_ k \)，最终解 \( \mathbf{y}_ k = R_ k^{-1} \mathbf{g}_ k \)。迭代终止与重启策略当残差范数 \( \|\mathbf{r}_ k\|_ 2 \) 小于预设容忍度时，输出 \( \mathbf{x}_ k \)。若迭代步数 \( k \) 过大（避免存储成本过高），采用重启GMRES：用当前解 \( \mathbf{x}_ k \) 作为新的 \( \mathbf{x}_ 0 \)，重新开始迭代。关键点总结 GMRES通过Arnoldi过程保证数值稳定性，避免直接计算幂次导致的病态问题。每步迭代需存储所有基向量 \( \mathbf{v}_ j \)，因此重启策略对大规模问题至关重要。对于对称矩阵，GMRES退化为MINRES算法，可节省计算量。