双共轭梯度法（BiCG）解非对称线性方程组

字数 2097 2025-10-29 11:31:55

双共轭梯度法（BiCG）解非对称线性方程组

题目描述
考虑一个非对称线性方程组 \(A\mathbf{x} = \mathbf{b}\)，其中 \(A\) 是一个 \(n \times n\) 的非对称矩阵（即 \(A \neq A^\top\)），\(\mathbf{b}\) 是已知向量。双共轭梯度法（BiCG）是一种迭代算法，用于求解此类方程组。其核心思想是通过构建两个相互正交的Krylov子空间（分别由 \(A\) 和 \(A^\top\) 生成），并利用双正交性（即两个向量序列相互正交）来逼近解。BiCG不需要矩阵对称或正定，但可能遇到数值不稳定问题。

解题过程

初始化
选择初始解猜测 \(\mathbf{x}_0\)（通常设为零向量），计算初始残差 \(\mathbf{r}_0 = \mathbf{b} - A\mathbf{x}_0\)。同时，选择一个辅助残差向量 \(\tilde{\mathbf{r}}_0\)，要求满足 \(\langle \mathbf{r}_0, \tilde{\mathbf{r}}_0 \rangle \neq 0\)（通常直接设 \(\tilde{\mathbf{r}}_0 = \mathbf{r}_0\)）。初始化搜索方向 \(\mathbf{p}_0 = \mathbf{r}_0\)，\(\tilde{\mathbf{p}}_0 = \tilde{\mathbf{r}}_0\)。
迭代步骤（第 \(k\) 步）
- 步长计算：
  计算步长 \(\alpha_k = \frac{ \langle \mathbf{r}_k, \tilde{\mathbf{r}}_k \rangle }{ \langle A\mathbf{p}_k, \tilde{\mathbf{p}}_k \rangle }\)。分母中的内积确保方向 \(A\mathbf{p}_k\) 和 \(\tilde{\mathbf{p}}_k\) 双正交。
- 更新解和残差：

\[ \mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{p}_k, \quad \mathbf{r}_{k+1} = \mathbf{r}_k - \alpha_k A\mathbf{p}_k, \quad \tilde{\mathbf{r}}_{k+1} = \tilde{\mathbf{r}}_k - \alpha_k A^\top \tilde{\mathbf{p}}_k. \]

 注意：$ \tilde{\mathbf{r}}_{k+1} $ 是 $ A^\top $ 的残差，用于维持双正交性。

收敛检查：
若 \(\|\mathbf{r}_{k+1}\|\) 小于预设容忍误差，则终止迭代，输出 \(\mathbf{x}_{k+1}\) 作为近似解。
方向更新：
计算系数 \(\beta_k = \frac{ \langle \mathbf{r}_{k+1}, \tilde{\mathbf{r}}_{k+1} \rangle }{ \langle \mathbf{r}_k, \tilde{\mathbf{r}}_k \rangle }\)，并更新搜索方向：

\[ \mathbf{p}_{k+1} = \mathbf{r}_{k+1} + \beta_k \mathbf{p}_k, \quad \tilde{\mathbf{p}}_{k+1} = \tilde{\mathbf{r}}_{k+1} + \beta_k \tilde{\mathbf{p}}_k. \]

 这一步确保新方向 $ \mathbf{p}_{k+1} $ 和 $ \tilde{\mathbf{p}}_{k+1} $ 满足双共轭条件。

算法特性
- 每步迭代需两次矩阵向量乘（计算 \(A\mathbf{p}_k\) 和 \(A^\top \tilde{\mathbf{p}}_k\)）。
- 残差满足双正交性：\(\langle \mathbf{r}_i, \tilde{\mathbf{r}}_j \rangle = 0\)（当 \(i \neq j\)）。
- 若 \(A\) 对称且 \(\tilde{\mathbf{r}}_0 = \mathbf{r}_0\)，BiCG退化为标准共轭梯度法（CG）。

总结
BiCG通过交替在原始空间和对偶空间进行迭代，有效处理非对称问题。虽然可能因内积消失（即 \(\langle \mathbf{r}_k, \tilde{\mathbf{r}}_k \rangle = 0\)）而失败，但其计算效率使其在科学计算中广泛应用。后续改进算法（如BiCGSTAB）通过引入稳定化策略进一步优化数值稳定性。

双共轭梯度法（BiCG）解非对称线性方程组题目描述考虑一个非对称线性方程组 \( A\mathbf{x} = \mathbf{b} \)，其中 \( A \) 是一个 \( n \times n \) 的非对称矩阵（即 \( A \neq A^\top \)），\( \mathbf{b} \) 是已知向量。双共轭梯度法（BiCG）是一种迭代算法，用于求解此类方程组。其核心思想是通过构建两个相互正交的Krylov子空间（分别由 \( A \) 和 \( A^\top \) 生成），并利用双正交性（即两个向量序列相互正交）来逼近解。BiCG不需要矩阵对称或正定，但可能遇到数值不稳定问题。解题过程初始化选择初始解猜测 \( \mathbf{x}_ 0 \)（通常设为零向量），计算初始残差 \( \mathbf{r}_ 0 = \mathbf{b} - A\mathbf{x}_ 0 \)。同时，选择一个辅助残差向量 \( \tilde{\mathbf{r}}_ 0 \)，要求满足 \( \langle \mathbf{r}_ 0, \tilde{\mathbf{r}}_ 0 \rangle \neq 0 \)（通常直接设 \( \tilde{\mathbf{r}}_ 0 = \mathbf{r}_ 0 \)）。初始化搜索方向 \( \mathbf{p}_ 0 = \mathbf{r}_ 0 \)，\( \tilde{\mathbf{p}}_ 0 = \tilde{\mathbf{r}}_ 0 \)。迭代步骤（第 \( k \) 步）步长计算：计算步长 \( \alpha_ k = \frac{ \langle \mathbf{r}_ k, \tilde{\mathbf{r}}_ k \rangle }{ \langle A\mathbf{p}_ k, \tilde{\mathbf{p}}_ k \rangle } \)。分母中的内积确保方向 \( A\mathbf{p}_ k \) 和 \( \tilde{\mathbf{p}}_ k \) 双正交。更新解和残差： \[ \mathbf{x}_ {k+1} = \mathbf{x}_ k + \alpha_ k \mathbf{p} k, \quad \mathbf{r} {k+1} = \mathbf{r}_ k - \alpha_ k A\mathbf{p} k, \quad \tilde{\mathbf{r}} {k+1} = \tilde{\mathbf{r}}_ k - \alpha_ k A^\top \tilde{\mathbf{p}} k. \] 注意：\( \tilde{\mathbf{r}} {k+1} \) 是 \( A^\top \) 的残差，用于维持双正交性。收敛检查：若 \( \|\mathbf{r} {k+1}\| \) 小于预设容忍误差，则终止迭代，输出 \( \mathbf{x} {k+1} \) 作为近似解。方向更新：计算系数 \( \beta_ k = \frac{ \langle \mathbf{r} {k+1}, \tilde{\mathbf{r}} {k+1} \rangle }{ \langle \mathbf{r} k, \tilde{\mathbf{r}} k \rangle } \)，并更新搜索方向： \[ \mathbf{p} {k+1} = \mathbf{r} {k+1} + \beta_ k \mathbf{p} k, \quad \tilde{\mathbf{p}} {k+1} = \tilde{\mathbf{r}} {k+1} + \beta_ k \tilde{\mathbf{p}} k. \] 这一步确保新方向 \( \mathbf{p} {k+1} \) 和 \( \tilde{\mathbf{p}} {k+1} \) 满足双共轭条件。算法特性每步迭代需两次矩阵向量乘（计算 \( A\mathbf{p}_ k \) 和 \( A^\top \tilde{\mathbf{p}}_ k \)）。残差满足双正交性：\( \langle \mathbf{r}_ i, \tilde{\mathbf{r}}_ j \rangle = 0 \)（当 \( i \neq j \)）。若 \( A \) 对称且 \( \tilde{\mathbf{r}}_ 0 = \mathbf{r}_ 0 \)，BiCG退化为标准共轭梯度法（CG）。总结 BiCG通过交替在原始空间和对偶空间进行迭代，有效处理非对称问题。虽然可能因内积消失（即 \( \langle \mathbf{r}_ k, \tilde{\mathbf{r}}_ k \rangle = 0 \)）而失败，但其计算效率使其在科学计算中广泛应用。后续改进算法（如BiCGSTAB）通过引入稳定化策略进一步优化数值稳定性。