Have a Question?

共轭梯度算法 | Conjugate Gradient Method

You are here:

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

Add a Comment

您的电子邮箱地址不会被公开。 必填项已用*标注

Table of Contents