广义极小残差法（GMRES）解非对称线性方程组
字数 2075 2025-10-27 17:41:11

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

题目描述
广义极小残差法（GMRES）是一种迭代算法，用于求解大型稀疏非对称线性方程组 \(A\mathbf{x} = \mathbf{b}\)，其中 \(A \in \mathbb{R}^{n \times n}\) 是非奇异矩阵（但非对称或不定），\(\mathbf{b} \in \mathbb{R}^{n}\) 是已知向量。GMRES 通过最小化残差 \(\|\mathbf{b} - A\mathbf{x}\|_2\) 在 Krylov 子空间中的投影来逼近解，尤其适用于迭代求解病态或非对称问题。

解题过程

  1. 问题转化
    设初始猜测解为 \(\mathbf{x}_0\)，初始残差为 \(\mathbf{r}_0 = \mathbf{b} - A\mathbf{x}_0\)。GMRES 在第 \(m\) 步迭代时，在 Krylov 子空间 \(\mathcal{K}_m(A, \mathbf{r}_0) = \text{span}\{\mathbf{r}_0, A\mathbf{r}_0, \dots, A^{m-1}\mathbf{r}_0\}\) 中寻找解 \(\mathbf{x}_m = \mathbf{x}_0 + \mathbf{z}_m\)，其中 \(\mathbf{z}_m \in \mathcal{K}_m\)，使得残差 \(\|\mathbf{r}_m\|_2 = \|\mathbf{b} - A\mathbf{x}_m\|_2\) 最小。

  2. Arnoldi 过程构建正交基
    使用 Arnoldi 迭代将 Krylov 子空间正交化，生成一组标准正交基向量 \(\{\mathbf{v}_1, \dots, \mathbf{v}_m\}\) 和一个上 Hessenberg 矩阵 \(H_m \in \mathbb{R}^{(m+1) \times m}\)：

    • 初始化：\(\mathbf{v}_1 = \mathbf{r}_0 / \|\mathbf{r}_0\|_2\)。
    • 对 \(j = 1, 2, \dots, m\)：
      • 计算 \(\mathbf{w} = A\mathbf{v}_j\)。
      • 对 \(i = 1\) 到 \(j\)：正交化 \(h_{i,j} = \langle \mathbf{w}, \mathbf{v}_i \rangle\)，并更新 \(\mathbf{w} = \mathbf{w} - h_{i,j}\mathbf{v}_i\)。
      • 计算 \(h_{j+1,j} = \|\mathbf{w}\|_2\)，若 \(h_{j+1,j} = 0\) 则提前终止。
      • 标准化 \(\mathbf{v}_{j+1} = \mathbf{w} / h_{j+1,j}\)。
        最终得到关系式 \(A V_m = V_{m+1} H_m\)，其中 \(V_m = [\mathbf{v}_1, \dots, \mathbf{v}_m]\) 的列向量构成正交基。

  3. 最小二乘问题求解
    将解表示为 \(\mathbf{x}_m = \mathbf{x}_0 + V_m \mathbf{y}_m\)（\(\mathbf{y}_m \in \mathbb{R}^m\)），残差可写为：

\[ \mathbf{r}_m = \mathbf{b} - A\mathbf{x}_m = \mathbf{r}_0 - A V_m \mathbf{y}_m = V_{m+1} (\|\mathbf{r}_0\|_2 \mathbf{e}_1 - H_m \mathbf{y}_m), \]

其中 \(\mathbf{e}_1 = [1, 0, \dots, 0]^T \in \mathbb{R}^{m+1}\)。由于 \(V_{m+1}\) 列正交，最小化 \(\|\mathbf{r}_m\|_2\) 等价于求解：

\[ \min_{\mathbf{y}_m} \| \|\mathbf{r}_0\|_2 \mathbf{e}_1 - H_m \mathbf{y}_m \|_2. \]

此问题可通过 QR 分解（如 Givens 旋转）将 \(H_m\) 化为上三角矩阵后回代求解。

  1. 迭代终止与重启策略
    • 当残差范数小于容忍误差时终止迭代。
    • 若 \(m\) 较大时内存不足，采用重启策略：用当前解 \(\mathbf{x}_m\) 作为新的初始猜测，重新开始 Arnoldi 过程。

关键点

  • GMRES 保证残差单调递减，但重启可能破坏收敛性。
  • 适用于非对称矩阵，但需注意重启次数对效率的影响。
广义极小残差法（GMRES）解非对称线性方程组 题目描述 广义极小残差法（GMRES）是一种迭代算法，用于求解大型稀疏非对称线性方程组 \( A\mathbf{x} = \mathbf{b} \)，其中 \( A \in \mathbb{R}^{n \times n} \) 是非奇异矩阵（但非对称或不定），\( \mathbf{b} \in \mathbb{R}^{n} \) 是已知向量。GMRES 通过最小化残差 \( \|\mathbf{b} - A\mathbf{x}\|_ 2 \) 在 Krylov 子空间中的投影来逼近解，尤其适用于迭代求解病态或非对称问题。 解题过程 问题转化 设初始猜测解为 \( \mathbf{x}_ 0 \)，初始残差为 \( \mathbf{r}_ 0 = \mathbf{b} - A\mathbf{x}_ 0 \)。GMRES 在第 \( m \) 步迭代时，在 Krylov 子空间 \( \mathcal{K}_ m(A, \mathbf{r}_ 0) = \text{span}\{\mathbf{r}_ 0, A\mathbf{r}_ 0, \dots, A^{m-1}\mathbf{r}_ 0\} \) 中寻找解 \( \mathbf{x}_ m = \mathbf{x}_ 0 + \mathbf{z}_ m \)，其中 \( \mathbf{z}_ m \in \mathcal{K}_ m \)，使得残差 \( \|\mathbf{r}_ m\|_ 2 = \|\mathbf{b} - A\mathbf{x}_ m\|_ 2 \) 最小。 Arnoldi 过程构建正交基 使用 Arnoldi 迭代将 Krylov 子空间正交化，生成一组标准正交基向量 \( \{\mathbf{v}_ 1, \dots, \mathbf{v}_ m\} \) 和一个上 Hessenberg 矩阵 \( H_ m \in \mathbb{R}^{(m+1) \times m} \)： 初始化：\( \mathbf{v}_ 1 = \mathbf{r}_ 0 / \|\mathbf{r}_ 0\|_ 2 \)。 对 \( j = 1, 2, \dots, m \)： 计算 \( \mathbf{w} = A\mathbf{v}_ j \)。 对 \( i = 1 \) 到 \( j \)：正交化 \( h_ {i,j} = \langle \mathbf{w}, \mathbf{v} i \rangle \)，并更新 \( \mathbf{w} = \mathbf{w} - h {i,j}\mathbf{v}_ i \)。 计算 \( h_ {j+1,j} = \|\mathbf{w}\| 2 \)，若 \( h {j+1,j} = 0 \) 则提前终止。 标准化 \( \mathbf{v} {j+1} = \mathbf{w} / h {j+1,j} \)。 最终得到关系式 \( A V_ m = V_ {m+1} H_ m \)，其中 \( V_ m = [ \mathbf{v}_ 1, \dots, \mathbf{v}_ m ] \) 的列向量构成正交基。 最小二乘问题求解 将解表示为 \( \mathbf{x}_ m = \mathbf{x}_ 0 + V_ m \mathbf{y}_ m \)（\( \mathbf{y}_ m \in \mathbb{R}^m \)），残差可写为： \[ \mathbf{r}_ m = \mathbf{b} - A\mathbf{x}_ m = \mathbf{r}_ 0 - A V_ m \mathbf{y} m = V {m+1} (\|\mathbf{r}_ 0\|_ 2 \mathbf{e}_ 1 - H_ m \mathbf{y}_ m), \] 其中 \( \mathbf{e} 1 = [ 1, 0, \dots, 0]^T \in \mathbb{R}^{m+1} \)。由于 \( V {m+1} \) 列正交，最小化 \( \|\mathbf{r}_ m\| 2 \) 等价于求解： \[ \min {\mathbf{y}_ m} \| \|\mathbf{r}_ 0\|_ 2 \mathbf{e}_ 1 - H_ m \mathbf{y}_ m \|_ 2. \] 此问题可通过 QR 分解（如 Givens 旋转）将 \( H_ m \) 化为上三角矩阵后回代求解。 迭代终止与重启策略 当残差范数小于容忍误差时终止迭代。 若 \( m \) 较大时内存不足，采用重启策略：用当前解 \( \mathbf{x}_ m \) 作为新的初始猜测，重新开始 Arnoldi 过程。 关键点 GMRES 保证残差单调递减，但重启可能破坏收敛性。 适用于非对称矩阵，但需注意重启次数对效率的影响。