稳定双共轭梯度法

在数值线性代数中，稳定双共轭梯度法（通常简称为“BiCGSTAB”）是一种由荷兰数学家 H. A. van der Vorst 提出的用于数值求解非对称线性方程组的迭代方法。它是双共轭梯度法（BiCG）的一个变种，比双共轭梯度法本身以及诸如共轭梯度平方法（CGS）等其他变种有更快速和更平滑的收敛性。它是一种 Krylov 子空间方法。

算法步骤

无预处理稳定双共轭梯度法

要求解线性方程组 $\boldsymbol{Ax}=\boldsymbol{b}$，稳定双共轭梯度法从初始解 $\boldsymbol{x}_0$ 开始按以下步骤迭代：

1. $\boldsymbol{r}_0=\boldsymbol{b}-\boldsymbol{Ax}$
2. 任意选择向量 $\boldsymbol{\hat{r}}_0\;$ 使得 $(\boldsymbol{\hat{r}}_0,\boldsymbol{r}_0) \neq0\;$，例如，$\boldsymbol{\hat{r}}_0=\boldsymbol{r}_0\;$
3. $\rho_0=\alpha=\omega_0=1\;$
4. $\boldsymbol{v}_0=\boldsymbol{p}_0=\boldsymbol{0}$
5. 对 $i=1,2,3,\ldots$
   1. $\rho_i=(\boldsymbol{\hat{r}}_0,\boldsymbol{r}_{i-1})\;$
   2. $\beta=(\rho_i/\rho_{i-1})(\alpha/\omega_{i-1})\;$
   3. $\boldsymbol{p}_i=\boldsymbol{r}_{i-1}+\beta(\boldsymbol{p}_{i-1}-\omega_{i-1}\boldsymbol{v}_{i-1})$
   4. $\boldsymbol{v}_i=\boldsymbol{Ap}_i$
   5. $\alpha=\rho_i/(\boldsymbol{\hat{r}}_0,\boldsymbol{v}_i)\;$
   6. $\boldsymbol{s}=\boldsymbol{r}_i-\alpha\boldsymbol{v}_i$
   7. $\boldsymbol{t}=\boldsymbol{As}$
   8. $\omega_i=(\boldsymbol{t},\boldsymbol{s})/(\boldsymbol{t},\boldsymbol{t})$
   9. $\boldsymbol{x}_i=\boldsymbol{x}_{i-1}+\alpha\boldsymbol{p}_i+\omega_i\boldsymbol{s}$
   10. 若 $\boldsymbol{x}_i$ 足够精确则退出
   11. $\boldsymbol{r}_i=\boldsymbol{s}-\omega_i\boldsymbol{t}$

预处理稳定双共轭梯度法

预处理通常被用来加速迭代方法的收敛。要使用预处理子 $\boldsymbol{K}=\boldsymbol{K}_1\boldsymbol{K}_2\approx\boldsymbol{A}$ 来求解线性方程组 $\boldsymbol{Ax}=\boldsymbol{b}$，预处理稳定双共轭梯度法从初始解 $\boldsymbol{x}_0$ 开始按以下步骤迭代：

1. $\boldsymbol{r}_0=\boldsymbol{b}-\boldsymbol{Ax}$
2. 任意选择向量 $\boldsymbol{\hat{r}}_0\;$ 使得 $(\boldsymbol{\hat{r}}_0,\boldsymbol{r}_0) \neq0\;$，例如，$\boldsymbol{\hat{r}}_0=\boldsymbol{r}_0\;$
3. $\rho_0=\alpha=\omega_0=1\;$
4. $\boldsymbol{v}_0=\boldsymbol{p}_0=\boldsymbol{0}$
5. 对 $i=1,2,3,\ldots$
   1. $\rho_i=(\boldsymbol{\hat{r}}_0,\boldsymbol{r}_{i-1})\;$
   2. $\beta=(\rho_i/\rho_{i-1})(\alpha/\omega_{i-1})\;$
   3. $\boldsymbol{p}_i=\boldsymbol{r}_{i-1}+\beta(\boldsymbol{p}_{i-1}-\omega_{i-1}\boldsymbol{v}_{i-1})$
   4. $\boldsymbol{y}=\boldsymbol{K}^{-1}\boldsymbol{p}_i$
   5. $\boldsymbol{v}_i=\boldsymbol{Ay}$
   6. $\alpha=\rho_i/(\boldsymbol{\hat{r}}_0,\boldsymbol{v}_i)\;$
   7. $\boldsymbol{s}=\boldsymbol{r}_i-\alpha\boldsymbol{v}_i$
   8. $\boldsymbol{z}=\boldsymbol{As}$
   9. $\boldsymbol{t}=\boldsymbol{K}^{-1}\boldsymbol{z}$
   10. $\omega_i=(\boldsymbol{K}_1^{-1}\boldsymbol{t},\boldsymbol{K}_1^{-1}\boldsymbol{s})/(\boldsymbol{K}_1^{-1}\boldsymbol{s},\boldsymbol{K}_1^{-1}\boldsymbol{s})$
   11. $\boldsymbol{x}_i=\boldsymbol{x}_{i-1}+\alpha\boldsymbol{y}+\omega_i\boldsymbol{z}$
   12. 若 $\boldsymbol{x}_i$ 足够精确则退出
   13. $\boldsymbol{r}_i=\boldsymbol{s}-\omega_i\boldsymbol{t}$

这个形式等价于将无预处理的稳定双共轭梯度法应用于显式预处理后的方程组

$\boldsymbol{\tilde{A}\tilde{x}}=\boldsymbol{\tilde{b}}$，

其中 $\boldsymbol{\tilde{A}}=\boldsymbol{K}_1^{-1}\boldsymbol{AK}_2^{-1}$，$\boldsymbol{\tilde{x}}=\boldsymbol{K}_2\boldsymbol{x}$，$\boldsymbol{\tilde{b}}=\boldsymbol{K}_1^{-1}\boldsymbol{b}$。换句话说，左预处理和右预处理都可以通过这个形式实施。

推导

双共轭梯度法的多项式形式

在双共轭梯度法中，搜索方向 $\boldsymbol{p}_i$ 和 $\boldsymbol{\hat{p}}_i$ 以及残量 $\boldsymbol{r}_i$ 和 $\boldsymbol{\hat{r}}_i$ 通过以下递推关系更新：

$\boldsymbol{p}_i=\boldsymbol{r}_i+\beta_i\boldsymbol{p}_{i-1}\text{,}$

$\boldsymbol{\hat{p}}_i=\boldsymbol{\hat{r}}_i+\beta_i\boldsymbol{p}_{i-1}\text{,}$

$\boldsymbol{r}_i=\boldsymbol{r}_{i-1}-\alpha_i\boldsymbol{Ap}_{i}\text{,}$

$\boldsymbol{\hat{r}}_i=\boldsymbol{\hat{r}}_{i-1}-\alpha\boldsymbol{A}^{\mathrm{T}}\boldsymbol{\hat{p}}_i\text{.}$

常数 $\alpha_i\;$ 和 $\beta_i\;$ 取值为

$\alpha_i=\rho_i/(\boldsymbol{\hat{p}}_i,\boldsymbol{Ap}_i)\text{,}$

$\beta_i=\rho_i/\rho_{i-1}\text{,}\;$

其中 $\rho_i=(\boldsymbol{\hat{r}}_{i-1},\boldsymbol{r}_{i-1})$，使得残量和搜索方向分别满足双正交性和双共轭性，也就是对于 $i\neq j$，

$(\boldsymbol{\hat{r}}_i,\boldsymbol{r}_j)=0\text{,}$

$(\boldsymbol{\hat{p}}_i,\boldsymbol{Ap}_j)=0\text{.}$

不难证明，

$\boldsymbol{r}_i=P_i(\boldsymbol{A})\boldsymbol{r}_0\text{,}$

$\boldsymbol{\hat{r}}_i=P_i(\boldsymbol{A}^{\mathrm{T}})\boldsymbol{\hat{r}}_0\text{,}$

$\boldsymbol{p}_{i+1}=T_i(\boldsymbol{A})\boldsymbol{r}_0\text{,}$

$\boldsymbol{\hat{p}}_{i+1}=T_i(\boldsymbol{A}^{\mathrm{T}})\boldsymbol{\hat{r}}_0\text{,}$

其中 $P_i(\boldsymbol{A})$ 和 $T_i(\boldsymbol{A})$ 是关于 $\boldsymbol{A}$ 的 $i\;$ 次多项式。这些多项式满足以下递推关系：

$P_i(\boldsymbol{A})=P_{i-1}(\boldsymbol{A})-\alpha_i\boldsymbol{A}T_{i-1}(\boldsymbol{A})\text{,}$

$T_i(\boldsymbol{A})=P_i(\boldsymbol{A})-\beta_{i+1}T_{i-1}(\boldsymbol{A})\text{.}$

从双共轭梯度法导出稳定双共轭梯度 法

双共轭梯度法的残量和搜索方向不是必须显式跟踪的。换句话说，双共轭梯度法的迭代是可以隐式进行的。稳定双共轭梯度法中希望得到

$\boldsymbol{\tilde{r}}_i=Q_i(\boldsymbol{A})P_i(\boldsymbol{A})\boldsymbol{r}_0$

的递推关系，其中 $Q_i(\boldsymbol{A})=(\boldsymbol{I}-\omega_1\boldsymbol{A})(\boldsymbol{I}-\omega_1\boldsymbol{A})\cdots(\boldsymbol{I}-\omega_i\boldsymbol{A})$，$\omega_j\;$ 为适当选取的常数。以此代替 $\boldsymbol{r}_i=P_i(\boldsymbol{A})$ 的目的是希望 $Q_i(\boldsymbol{A})$ 可以使 $\boldsymbol{\tilde{r}}_i$ 有比 $\boldsymbol{r}_i$ 更快速和更平滑的收敛性。

根据 $P_i(\boldsymbol{A})$ 和 $T_i(\boldsymbol{A})$ 的递推关系以及 $Q_i(\boldsymbol{A})$ 的定义，

$Q_i(\boldsymbol{A})P_i(\boldsymbol{A})\boldsymbol{r}_0=(\boldsymbol{I}-\omega_i\boldsymbol{A})\bigl(Q_{i-1}(\boldsymbol{A})P_{i-1}(\boldsymbol{A})\boldsymbol{r}_0-\alpha_i\boldsymbol{A}Q_{i-1}(\boldsymbol{A})P_{i-1}(\boldsymbol{A})\boldsymbol{r}_0\bigr)\text{.}$

于是还需要一条关于 $Q_i(\boldsymbol{A})T_i(\boldsymbol{A})\boldsymbol{r}_0$ 的递推关系。这同样可以从双共轭梯度法的递推关系中导出：

$Q_i(\boldsymbol{A})T_i(\boldsymbol{A})\boldsymbol{r}_0=Q_i(\boldsymbol{A})P_i(\boldsymbol{A})\boldsymbol{r}_0-\beta_{i+1}(\boldsymbol{I}-\omega_i\boldsymbol{A})Q_{i-1}(\boldsymbol{A})T_{i-1}(\boldsymbol{A})\boldsymbol{r}_0\text{.}$

类似于 $\boldsymbol{\tilde{r}}_i$，稳定双共轭梯度法定义

$\boldsymbol{\tilde{p}}_{i+1}=Q_i(\boldsymbol{A})T_i(\boldsymbol{A})\boldsymbol{r}_0\text{.}$

写成向量形式，$\boldsymbol{\tilde{p}}_i$ 和 $\boldsymbol{\tilde{r}}_i$ 的递推关系就是

$\boldsymbol{\tilde{p}}_i=\boldsymbol{\tilde{r}}_{i-1}+\beta_i(\boldsymbol{I}-\omega_{i-1}\boldsymbol{A})\boldsymbol{\tilde{p}}_{i-1}\text{,}$

$\boldsymbol{\tilde{r}}_i=(\boldsymbol{I}-\omega_i\boldsymbol{A})(\boldsymbol{\tilde{r}}_{i-1}-\alpha_i\boldsymbol{A\tilde{p}}_i)\text{.}$

为了导出 $\boldsymbol{x}_i$ 的递推关系，定义

$\boldsymbol{s}_i=\boldsymbol{\tilde{r}}_{i-1}-\alpha_i\boldsymbol{A\tilde{p}}_i\text{.}$

于是 $\boldsymbol{\tilde{r}}_i$ 的递推关系就可以写成

$\boldsymbol{\tilde{r}}_i=\boldsymbol{\tilde{r}}_{i-1}-\alpha_i\boldsymbol{A\tilde{p}}_i-\omega_i\boldsymbol{As}_i\text{,}$

这对应于

$\boldsymbol{x}_i=\boldsymbol{x}_{i-1}+\alpha_i\boldsymbol{\tilde{p}}_i+\omega_i\boldsymbol{s}_i\text{.}$

确定稳定双共轭梯度法的常数

现在只需确定双共轭梯度法的常数 $\alpha_i\;$ 和 $\beta_i\;$ 以及选择一个合适的 $\omega_i\;$。

在双共轭梯度法中，$\beta_i=\rho_i/\rho_{i-1}\;$， 其中

$\rho_i=(\boldsymbol{\hat{r}}_{i-1},\boldsymbol{r}_{i-1})=\bigl(P_{i-1}(\boldsymbol{A}^{\mathrm{T}})\boldsymbol{\hat{r}}_0,P_{i-1}(\boldsymbol{A})\boldsymbol{r}_0\bigr)\text{.}$

由于稳定双共轭梯度法不显式跟踪 $\boldsymbol{\hat{r}}_i$ 或 $\boldsymbol{r}_i$，$\rho_i\;$ 不能立即用这条公式计算出来。但是，它可以和标量

$\tilde{\rho}_i=\bigl(Q_{i-1}(\boldsymbol{A}^{\mathrm{T}})\boldsymbol{\hat{r}}_0,P_{i-1}(\boldsymbol{A})\boldsymbol{r}_0\bigr)=\bigl(\boldsymbol{\hat{r}}_0,Q_{i-1}(\boldsymbol{A})P_{i-1}(\boldsymbol{A})\boldsymbol{r}_0\bigr)=(\boldsymbol{\hat{r}}_0,\boldsymbol{r}_{i-1})$

关联起来。由于双正交性，$\boldsymbol{r}_{i-1}=P_{i-1}(\boldsymbol{A})\boldsymbol{r}_0$ 正交于 $U_{i-2}(\boldsymbol{A}^{\mathrm{T}})\boldsymbol{\hat{r}}_0$，其中 $U_{i-2}(\boldsymbol{A}^{\mathrm{T}})$ 是关于 $\boldsymbol{A}^{\mathrm{T}}$ 的任意 $i-2\;$ 次多项式。因此在点积 $\bigl(P_{i-1}(\boldsymbol{A}^{\mathrm{T}})\boldsymbol{\hat{r}}_0,P_{i-1}(\boldsymbol{A})\boldsymbol{r}_0\bigr)$ 和 $\bigl(Q_{i-1}(\boldsymbol{A}^{\mathrm{T}})\boldsymbol{\hat{r}}_0,P_{i-1}(\boldsymbol{A})\boldsymbol{r}_0\bigr)$ 中只需考虑 $P_{i-1}(\boldsymbol{A}^{\mathrm{T}})$ 和 $Q_{i-1}(\boldsymbol{A}^{\mathrm{T}})$ 的最高次项。$P_{i-1}(\boldsymbol{A}^{\mathrm{T}})$ 和 $Q_{i-1}(\boldsymbol{A}^{\mathrm{T}})$ 的最高次项系数分别是 $(-1)^{i-1}\alpha_1\alpha_2\cdots\alpha_{i-1}$ 和 $(-1)^{i-1}\omega_1\omega_2\cdots\omega_{i-1}$。因此

$\rho_i=(\alpha_1/\omega_1)(\alpha_2/\omega_2)\cdots(\alpha_{i-1}/\omega_{i-1})\tilde{\rho}_i\text{,}$

于是

$\beta_i=\rho_i/\rho_{i-1}=(\tilde{\rho}_i/\tilde{\rho}_{i-1})(\alpha_{i-1}/\omega_{i-1})\text{.}$

关于 $\alpha_i\;$ 的简单公式可以类似地导出。在双共轭梯度法中，

$\alpha_i=\rho_i/(\boldsymbol{\hat{p}},\boldsymbol{Ap}_i)=\bigl(P_{i-1}(\boldsymbol{A}^{\mathrm{T}})\boldsymbol{\hat{r}}_0,P_{i-1}(\boldsymbol{A})\boldsymbol{r}_0\bigr)\big/\bigl(T_{i-1}(\boldsymbol{A}^{\mathrm{T}})\boldsymbol{\hat{r}}_0,\boldsymbol{A}T_{i-1}(\boldsymbol{A})\boldsymbol{r}_0\bigr)\text{.}$

类似于上面的情况，由于双正交性和双共轭性，在点积中只需考虑 $P_{i-1}(\boldsymbol{A}^{\mathrm{T}})$ 和 $T_{i-1}(\boldsymbol{A}^{\mathrm{T}})$ 的最高次项。$P_{i-1}(\boldsymbol{A}^{\mathrm{T}})$ 和 $T_{i-1}(\boldsymbol{A}^{\mathrm{T}})$ 的最高次项系数恰巧是相同的。因此，它们可以在公式中被同时替换为 $Q_{i-1}(\boldsymbol{A}^{\mathrm{T}})$，于是

$\alpha_i=\bigl(Q_{i-1}(\boldsymbol{A}^{\mathrm{T}})\boldsymbol{\hat{r}}_0,P_{i-1}(\boldsymbol{A})\boldsymbol{r}_0\bigr)\big/\bigl(Q_{i-1}(\boldsymbol{A}^{\mathrm{T}})\boldsymbol{\hat{r}}_0,\boldsymbol{A}T_{i-1}(\boldsymbol{A})\boldsymbol{r}_0\bigr)=\tilde{\rho}_i\big/\bigl(\boldsymbol{\hat{r}}_0,\boldsymbol{A}Q_{i-1}(\boldsymbol{A})T_{i-1}(\boldsymbol{A})\boldsymbol{r}_0\bigr)=\tilde{\rho}_i/(\boldsymbol{\hat{r}}_0,\boldsymbol{A\tilde{p}}_i)\text{.}$

最后，稳定双共轭梯度法选择 $\omega_i\;$ 使得 $\boldsymbol{\tilde{r}}_i=(\boldsymbol{I}-\omega_i\boldsymbol{A})\boldsymbol{s}_i$ 的 2-范数作为 $\omega_i\;$ 的函数被最小化。这在

$\bigl((\boldsymbol{I}-\omega_i\boldsymbol{A})\boldsymbol{s}_i,\boldsymbol{As}_i\bigr)=0$

时达到，因此 $\omega_i\;$ 的最优值是

$\omega_i=(\boldsymbol{As}_i,\boldsymbol{s}_i)/(\boldsymbol{As}_i,\boldsymbol{As}_i)\text{.}$

相关主题

• 双共轭梯度法
• 共轭梯度法

参考文献

• Van der Vorst, H. A. Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems. SIAM Journal on Scientific and Statistical Computing. 1992, 13: 631–644. doi:10.1137/0913035. 
• Saad, Y. §7.4.2 BICGSTAB//Iterative Methods for Sparse Linear Systems 2nd. SIAM. 2003: 231–234. doi:10.2277/0898715342. ISBN 978-0-898715-34-7.