共轭梯度法原理（共轭梯度法（Conjugate Gradients）（1））
最近在看ATOM ，作者在线训练了一个分类器 ，用的方法是高斯牛顿法和共轭梯度法 。看不懂 ，于是恶补了一波 。学习这些东西并不难 ，只是难找到学习资料 。简单地搜索了一下 ，许多文章都是一堆公式 ，这谁看得懂啊 。
后来找到一篇《An Introduction to the Conjugate Gradient Method Without the Agonizing Pain》 ，解惑了 。
为什么中文没有这么良心的资料呢？英文看着费劲 ，于是翻译过来搬到自己的博客 ，以便回顾 。由于原文比较长 ，一共
66
66
66 页的PDF ，所以这里分成几个部分来写 。目录
共轭梯度法（Conjugate Gradients）（1）
共轭梯度法（Conjugate Gradients）（2）
共轭梯度法（Conjugate Gradients）（3）
共轭梯度法（Conjugate Gradients）（4）
共轭梯度法（Conjugate Gradients）（5）Abstract （摘要）
共轭梯度法（Conjugate Gradient Method）是求解稀疏线性方程组最棒的迭代方法 。然鹅 ，许多教科书上面既没有插图 ，也没有解说 ，学生无法得到直观的理解 。时至今日（今日指1993年 ，因为这份教材是1993年发表的） ，仍然能看到这些教材的受害者们在图书馆的角落里毫无意义地琢磨 。只有少数的大佬破译了这些正常人看不懂的教材 ，有深刻地几何上的理解 。然而 ，共轭梯度法只是一些简单的 、优雅的思路的组合 ，像你一样的读者都可以毫不费力气学会 。
本文介绍了二次型（quadratic forms） ，用于推导最速下降（Steepest Descent） ，共轭方向（Conjugate Directions）和共轭梯度（Conjugate Gradients） 。
解释了特征向量（Eigenvectors） ，用于检验雅可比方法（Jacobi Method） 、最速下降 、共轭梯度的收敛性 。
还有其它的主题 ，包括预处理（preconditioning）和非线性共轭梯度法（nonlinear Conjugate Gradient Method）
本文的结构：
1. Introduction（简介）
当我决定准备学共轭梯度法（Conjugate Gradient Method ， 简称 CG）的时候 ，读了
4
4
4 种不同的版本 ，恕我直言 ，一个都看不懂 。很多都是简单地给出公式 ，证明了一下它的性质 。没有任何直观解释 ，没有告诉你 CG 是怎么来的 ，怎么发明的 。我感到沮丧 ，于是写下了这篇文章 ，希望你能从中学到丰富和优雅的算法 ，而不是被大量的公式困惑 。CG 是一种最常用的迭代方法 ，用于求解大型线性方程组 ，对于这种形式的问题非常有效：
A
x
=
b
(1)
Ax=b\tag{1}
Ax=b(1)其中：
x
x
x 是未知向量 ，b
b
b是已知向量 。
A
A
A 是已知的 方形的（square） 、对称的（symmetric） 、正定的（positive-definite）矩阵 。
（如果你忘了什么是“正定 ” ，不用担心 ，我会先给你回顾一下 。）这样的系统会出现在许多重要场景中 ，如求解偏微分方程（partial differential equations）的有限差分（finite difference）和有限元（finite element）法 、结构分析 、电路分析和你的数学作业 。
像 CG 这样的迭代方法适合用稀疏（sparse）矩阵 。如果
A
A
A 是稠密（dense）矩阵 ，最好的方法可能是对A
A
A 进行因式分解（factor） ，通过反代入来求解方程 。对稠密矩阵A
A
A 做因式分解的耗时和迭代求解的耗时大致相同 。一旦对A
A
A 进行因式分解后 ，就可以通过多个b
b
b 的值快速求解 。稠密矩阵和大一点的稀疏矩阵相比 ，占的内存差不多 。稀疏的A
A
A 的三角因子通常比A
A
A 本身有更多的非零元素 。由于内存限制 ，因式分解不太行 ，时间开销也很大 ，即使是反求解步骤也可能比迭代解法要慢 。另外一方面 ，绝大多数迭代法用稀疏矩阵都不占内存且速度快 。下面开始 ，我就当作你已经学过线性代数（linear algebra） ，对矩阵乘法（matrix multiplication）和线性无关（linear independence）等概念都很熟悉 ，尽管那些特征值特征向量什么的可能已经不太记得了 。我会尽量清楚地讲解 CG 的概念 。
2. Notation（标记）
∙
\bullet
∙ 除了一些特例 ，这里一般用大写字母表示矩阵（matrix） ，小写字母表示向量（vector） ，希腊字母表示标量（scalar） 。所以
A
A
A 是一个n
×
n
n\times n
n×n 的矩阵 ，x
x
x 和b
b
b 是向量（同时也是n
×
1
n \times 1
n×1矩阵） 。公式(1) 的完整写法：
[
A
11
A
12
…
A
1
n
A
21
A
22
…
A
2
n
⋮
⋱
⋮
A
n
1
A
n
2
…
A
n
n
]
[
x
1
x
2
⋮
x
n
]
=
[
b
1
b
2
⋮
b
n
]
\begin{bmatrix} A_{11} & A_{12} & \dots & A_{1n} \\[0.5em] A_{21} & A_{22} & \dots & A_{2n} \\[0.5em] \vdots & & \ddots & \vdots \\[0.5em] A_{n1} & A_{n2} & \dots & A_{nn} \\ \end{bmatrix} \begin{bmatrix} x_1 \\[0.5em] x_2 \\[0.5em] \vdots \\[0.5em] x_n \end{bmatrix} = \begin{bmatrix} b_1 \\[0.5em] b_2 \\[0.5em] \vdots \\[0.5em] b_n \end{bmatrix}
⎣⎢⎢⎢⎢⎢⎡A11A21⋮An1A12A22An2……⋱…A1nA2n⋮Ann⎦⎥⎥⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎡x1x2⋮xn⎦⎥⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎢⎡b1b2⋮bn⎦⎥⎥⎥⎥⎥⎤∙
\bullet
∙ 两个向量的内积（inner product）写成x
T
y
x^{T}y
xTy ，可以用标量的和∑
i
=
1
n
x
i
y
i
\sum^{n}_{i=1} x_i y_i
∑i=1nxiyi 来表示 。注意这里
x
T
y
=
y
T
x
x^T y = y^T x
xTy=yTx 。 如果x
x
x 和y
y
y 是正交（orthogonal）的 ，则x
T
y
=
x^T y = 0
xTy=0 。x
T
y
=
y
T
x
=
∑
i
=
1
n
x
i
y
i
x
T
y
=
（
正
交
）
x^{T}y = y^T x = \sum^{n}_{i=1} x_i y_i \\[0.5em]x^T y = 0 （正交）
xTy=yTx=i=1∑nxiyixTy=0（正交）一般来说 ，这些运算会得到
1
×
1
1 \times 1
1×1 的矩阵 。像x
T
y
x^T y
xTy 和x
T
A
x
x^T A x
xTAx 这种 ，运算结果是一个标量值 。∙
\bullet
∙ 对于任意非零向量x
x
x ，如果下面的 公式(2) 成立 ，则矩阵A
A
A 是正定（positive-definite）的：
x
T
A
x
>
(2)
x^T A x > 0 \tag{2}
xTAx>0(2)这可能对你来说没什么意义 ，但是不要感到难过 。
因为它不是一种很直观的概念 ，很难去想像一个正定和非正定的矩阵看起来有什么不同 。
当我们看到它怎么对二次型的造成影响时 ，你就会对“正定 ”产生感觉了 。∙
\bullet
∙最后 ，还有一些基本的定义：
(
A
B
)
T
=
B
T
A
T
(
A
B
)
−
1
=
B
−
1
A
−
1
(AB)^T = B^T A^T \\[0.5em] (AB)^{-1} = B^{-1} A^{-1}
(AB)T=BTAT(AB)−1=B−1A−13. The Quadratic Form（二次型）
二次型
（quadratic form）简单来说是一个标量 。
一个向量的二次型方程具有以下形式：
f
(
x
)
=
1
2
x
T
A
x
−
b
T
x
+
c
(3)
f(x) = \frac{1}{2} x^T A x - b^T x + c \tag{3}
f(x)=21xTAx−bTx+c(3)其中
A
A
A 是一个矩阵 ，b
b
b 是一个向量 ，c
c
c 是一个标量常数 。如果
A
A
A 是对称（symmetric） 且正定（positive-definite） ，则f
(
x
)
f(x)
f(x) 的最小化问题等同于求解A
x
=
b
Ax=b
Ax=b 。本文的所有例子都基于下面的值来讲解：
A
=
[
3
2
2
6
]
，
b
=
[
2
−
8
]
，
c
=
(4)
A = \begin{bmatrix} 3 & 2 \\ 2 & 6 \end{bmatrix} ， \quad b = \begin{bmatrix} 2 \\ -8 \end{bmatrix} ， \quad c=0 \tag{4}
A=[3226] ，b=[2−8] ，c=0(4)可以把 (4) 代入 (3) 得到：
f
(
x
)
=
1
2
⋅
[
x
1
x
2
]
[
3
2
2
6
]
[
x
1
x
2
]
−
[
2
−
8
]
⋅
[
x
1
x
2
]
+
=
1
2
⋅
[
x
1
x
2
]
[
3
x
1
+
2
x
2
2
x
1
+
6
x
2
]
−
(
2
x
1
−
8
x
2
)
=
1
2
⋅
(
x
1
(
3
x
1
+
2
x
2
)
+
x
2
(
2
x
1
+
6
x
2
)
)
−
2
x
1
+
8
x
2
=
3
2
x
1
2
+
3
x
2
2
+
2
x
1
x
2
−
2
x
1
+
8
x
2
\begin{aligned} f(x) &= \dfrac{1}{2} \cdot \begin{bmatrix} x_1 & x_2 \end{bmatrix} \begin{bmatrix} 3 & 2 \\[0.5em] 2 & 6 \end{bmatrix} \begin{bmatrix} x_1 \\[0.5em] x_2 \end{bmatrix} - \begin{bmatrix} 2 & -8 \end{bmatrix} \cdot \begin{bmatrix} x_1 \\[0.5em] x_2 \end{bmatrix} + 0 \\[1.5em] &= \dfrac{1}{2} \cdot \begin{bmatrix} x_1 & x_2 \end{bmatrix} \begin{bmatrix} 3x_1 + 2x_2 \\[0.5em] 2x_1 + 6x_2 \end{bmatrix} - (2x_1 - 8x_2) \\[1.5em] &= \dfrac{1}{2} \cdot {\Large(} x_1\left( 3x_1+ 2x_2 \right) + x_2 \left( 2x_1 + 6x_2\right) {\Large)} - 2x_1 + 8x_2 \\[1.5em] &= \frac{3}{2}x_1^2 + 3x_2^2 + 2x_1 x_2 -2x_1 + 8x_2 \end{aligned}
f(x)=21⋅[x1x2][3226][x1x2]−[2−8]⋅[x1x2]+0=21⋅[创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！