共轭梯度：一种高中解析几何的视角

本文没有任何数学推导。我们从直观上理解这个算法，然后直接介绍算法的流程。希望了解数学推导的读者可以查看 CMU 的教案及其翻译。

1. 问题

对于实对称矩阵 和向量 ，求解

或者，等价的，

其中

2. 预备知识

2.1. 从高中学的二级结论说起

高中的时候我们学过椭圆：

如果你记性好的话，你应该记得这个二级结论：

这是一个从圆里面推广而来的结论：如果 ，椭圆退化为圆，，即 两条直线垂直。

2.2. 最速下降法

首先，你应该知道梯度下降法：

最速下降法就是在梯度下降法的基础上，选择 使得 达到最小（在搜索方向上的最小值）：

3. 共轭梯度法

3.1. 记号

• ：第 次循环之后的 向量

• ：，目标函数 在 点的负梯度，或者线性方程组在 点的残差。

  • 请记住：负梯度和残差是一个东西！
• ：在 点的搜索方向。最速下降算法里 ，共轭梯度里面需要一点修正。

3.2. 最速下降

1. 最速下降的新方向：

   • 新方向与前一步下降方向 垂直

2. 最速下降的

3.3. 共轭梯度

我们直接逐项类比最速下降。

• 新方向与前一步下降方向 垂直 斜率之积为 (Section 2.1)

  • 这个方向由最速下降的方向进行一些小改动得到。

• 步长 ：由于是在一条直线上做优化，因此和最速下降的 相同。

3.4. 算法

3.4.1. 初始化

算法输入：

3.4.2. 算法过程

3.4.3. 起讫

1. 起：如果你对解 有粗略的估计，就使用那个值作为起始点 ；否则，直接使用 。
2. 讫：通常的做法是在残差向量的 2-norm 小于某个给定阈值的时候就停下来。

其中 是一个输入的参数。

3.5. 杂项

1. 由于 在每个循环中都要被计算，且 ，故可以用上式计算 ，而不必用 。
2. 上述方法有浮点误差累计的危险，因此我们应该每过几个循环就重新用 重新计算残差。