共轭梯度算法的直观解释

共轭梯度法是科学计算中最重要的思想之一，它适用于求解大型稀疏线性方程组，如偏微分方程的数值求解。 它也是一种强有力的优化方法。

本文试图对共轭梯度法作一个直观的介绍。从现在开始，通常缩写为"；CG"；

CG方法基于一个美丽的几何概念，但这个概念在大多数论述文本中几乎没有解释，乔纳森·休丘克(Jonathan Shewchuk)那篇夸张的论文“没有痛苦的共轭梯度法简介”(An Introduction To The Conjugate Gradient Method)对此表示遗憾(并得到缓解)。本文试图将休丘克的精彩解释转化为一种更具互动性的媒介。

请注意，本文是为在大小适中的显示器上阅读而设计的。虽然电话屏幕将显示必要的信息，但有些功能和可视化效果可能不能令人满意。

如果您发现错误，对数学和/或教学说明有意见，请给我发电子邮件到[email protected]。

我假设您在以下用例之一需要此算法： 求解矩阵\(A\in\mathbb R^{n\x n}\)的线性方程组\[Ax=b\] 对称正定和向量(x，b\in\mathbb R^n\)。此设置通常在需要数值求解偏微分方程时出现。

用矩阵最小化二次函数\[f(X)=\frac{1}{2}x^Tax-b^Tx+c\] (a\in\mathbb R^{n\×n})对称正定的向量\(x，b\in\mathbb R^n\) 和标量\(c\in\mathbb R\)。

虽然CG是为最小化二次函数而开发的，但它是 也适用于非二次极小化问题。

显然，\(Ax=b\)的解是\(x=A^{-1}b\)，但是我们假设问题的维数\(n\) 是如此之高以至于我们不能反转矩阵。从现在开始，我们将不允许将矩阵求逆作为一种可行的操作。我们甚至禁止 显式求解形式为\(Ax=b\)的线性方程。这与\(A\)倒数和\(A^{-1}b\)相乘不同，而且很大 比这更快，但我们假设问题是如此之大，即使这样也不会奏效。 另一方面，我们允许向量和矩阵之间的所有类型的(有效)乘法，并假设这些可以是 做得很有效率。

因为CG方法是在优化上下文中最直观地理解的，所以我们现在将省略\(Ax=b\)方面 我们将主要研究最小化形式为\[f(X)=\frac{1}{2}x^Tax-b^Tx+c]的二次函数的问题。 我们还假设A是平方的、对称的和正定的。

因为我们假设最小化问题的精确解(或者等价地，求解相应的线性方程)不能有效地进行， 我们将研究迭代方法，即我们将构造一个迭代\(x_{i}\mapstto x_{i+1}\)，使得序列 [x_0，x_1，x_2，\ldots\]收敛到最小值。

在本文中，我假设您熟悉基本的线性代数，特别是以下主题： 格拉姆-施密特正交化(尽管您不需要明确了解它，只是对它的作用有一个短暂的了解)