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

题目描述
双共轭梯度法（BiCG）是一种迭代算法，用于求解大型稀疏非对称线性方程组 \(A\mathbf{x} = \mathbf{b}\)，其中 \(A\) 是 \(n \times n\) 的非对称矩阵。与共轭梯度法（CG）不同，BiCG 不要求矩阵对称正定，但需构造一个对偶方程组 \(A^T \mathbf{\tilde{x}} = \mathbf{\tilde{b}}\) 来辅助计算。其核心思想是通过构建两组相互正交的残差向量序列，逐步逼近解。BiCG 的收敛速度可能不稳定，但它是许多改进算法（如 BiCGSTAB）的基础。

解题过程

1. 初始化
   • 选择初始解猜测 \(\mathbf{x}_0\)（常设为零向量），计算初始残差：

\[ \mathbf{r}_0 = \mathbf{b} - A\mathbf{x}_0 \]

• 选择对偶残差 \(\mathbf{\tilde{r}}_0\)，要求满足 \(\mathbf{\tilde{r}}_0^T \mathbf{r}_0 \neq 0\)（通常直接设 \(\mathbf{\tilde{r}}_0 = \mathbf{r}_0\)）。
• 初始化搜索方向：\(\mathbf{p}_0 = \mathbf{r}_0\)，\(\mathbf{\tilde{p}}_0 = \mathbf{\tilde{r}}_0\)。

2. 迭代步骤（对于 \(k=0,1,2,\dots\)）
   • 步骤 1：计算步长 \(\alpha_k\)
     利用残差与对偶残差的内积确定步长：

\[ \alpha_k = \frac{\mathbf{\tilde{r}}_k^T \mathbf{r}_k}{\mathbf{\tilde{p}}_k^T A \mathbf{p}_k} \]

 分母中的 $ A\mathbf{p}_k $ 是矩阵-向量乘法，需确保计算精确。

• 步骤 2：更新解和残差
  更新解向量：

\[ \mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{p}_k \]

 更新残差：  

\[ \mathbf{r}_{k+1} = \mathbf{r}_k - \alpha_k A \mathbf{p}_k \]

 同时更新对偶残差（使用 $ A^T $）：  

\[ \mathbf{\tilde{r}}_{k+1} = \mathbf{\tilde{r}}_k - \alpha_k A^T \mathbf{\tilde{p}}_k \]

• 步骤 3：检查收敛
  若 \(\|\mathbf{r}_{k+1}\|\) 小于预设容差，则终止迭代，输出 \(\mathbf{x}_{k+1}\) 作为解。

• 步骤 4：计算权重 \(\beta_k\)
  利用新旧残差的内积比例：

\[ \beta_k = \frac{\mathbf{\tilde{r}}_{k+1}^T \mathbf{r}_{k+1}}{\mathbf{\tilde{r}}_k^T \mathbf{r}_k} \]

• 步骤 5：更新搜索方向
  构建新的共轭方向：

\[ \mathbf{p}_{k+1} = \mathbf{r}_{k+1} + \beta_k \mathbf{p}_k \]

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

 这一步确保搜索方向满足双正交性：$ \mathbf{\tilde{p}}_i^T A \mathbf{p}_j = 0 $（当 $ i \neq j $）。

3. 算法特性
   • 每次迭代需两次矩阵-向量乘（计算 \(A\mathbf{p}_k\) 和 \(A^T\mathbf{\tilde{p}}_k\)）。
   • 若 \(A\) 对称且 \(\mathbf{\tilde{r}}_0 = \mathbf{r}_0\)，BiCG 退化为标准共轭梯度法。
   • 可能因分母 \(\mathbf{\tilde{p}}_k^T A \mathbf{p}_k \approx 0\) 而中断，需重启策略或改用稳定变体（如 BiCGSTAB）。