Have a Question?
共轭梯度算法 | Conjugate Gradient Method
1 定义
共轭梯度法(英语:Conjugate gradient method),是求解系数矩阵为对称正定矩阵的线性方程组的数值解的方法。共轭梯度法是一个迭代方法,它适用于系数矩阵为稀疏矩阵的线性方程组。
线性共轭梯度法是用来求解线性方程 Ax=b 的算法,它的思想如下:
我们定义一个线性方程:
f(\mathbf{x}) = \tfrac12 \mathbf{x}^\mathsf{T} \mathbf{A}\mathbf{x} - \mathbf{x}^\mathsf{T} \mathbf{b}, \qquad \mathbf{x}\in\mathbf{R}^n
对上面方程求一阶导:
\nabla f(\mathbf{x}) = \mathbf{A} \mathbf{x} - \mathbf{b}
可以看到,方程的一阶导数就是我们需要解的线性方程组,令一阶导数为 0,那么我们需要解的就是这样一个线性方程组了。也就是说可以转化为求解 f(\mathbf{x}) 的最小值的问题。
假设我们随机定义 x 的一个初始向量为 x_0,那么我们可以定义第一个共轭向量为 p_0=b−Ax_0, 后续的基向量都是和梯度共轭的,所以称为共轭梯度法。
2 过程
经过一些简化,可以得到下列求解 Ax=b 的算法,其中 A 是实对称正定矩阵。
\begin{aligned}& \mathbf{r}_0 := \mathbf{b} - \mathbf{A x}_0 \\& \mathbf{p}_0 := \mathbf{r}_0 \\& k := 0 \\& \text{repeat} \\& \qquad \alpha_k := \frac{\mathbf{r}_k^\mathsf{T} \mathbf{r}_k}{\mathbf{p}_k^\mathsf{T} \mathbf{A p}_k} \\& \qquad \mathbf{x}_{k+1} := \mathbf{x}_k + \alpha_k \mathbf{p}_k \\& \qquad \mathbf{r}_{k+1} := \mathbf{r}_k - \alpha_k \mathbf{A p}_k \\& \qquad \text{if } r_{k+1} \text{ is sufficiently small, then exit loop} \\& \qquad \beta_k := \frac{\mathbf{r}_{k+1}^\mathsf{T} \mathbf{r}_{k+1}}{\mathbf{r}_k^\mathsf{T} \mathbf{r}_k} \\& \qquad \mathbf{p}_{k+1} := \mathbf{r}_{k+1} + \beta_k \mathbf{p}_k \\& \qquad k := k + 1 \\& \text{end repeat} \\\end{aligned}
结果为 {x}_{k+1}.
参考文献
[1] https://blog.csdn.net/matrix_space/article/details/80467190
[2] https://zh.wikipedia.org/wiki/%E5%85%B1%E8%BD%AD%E6%A2%AF%E5%BA%A6%E6%B3%95
[3] Magnus R. Hestenes and Eduard Stiefel(1952),Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49, 409–436.
[4] https://zhuanlan.zhihu.com/p/98642663