共轭梯度法的推导

在数值线性代数中，共轭梯度法是一种求解对称正定线性方程组

的迭代方法。共轭梯度法可以从不同的角度推导而得，包括作为求解最优化问题的共轭方向法的特例，以及作为求解特征值问题的Arnoldi/Lanczos迭代的变种。

本条目记述这些推导方法中的重要步骤。

从共轭方向法推导

共轭梯度法可以看作是应用于二次函数最小化的共轭方向法的特例



 共轭方向法 
在共轭方向上求最小化：



从最初的猜测开始，以及相应的残差 , 并通过公式计算迭代和残差



其中， 为一系列相互共轭的方向，例如：

 ，对于任何

由于共轭方向法没有给出用于选择方向的公式，因此该方法具有误差 

而共轭方向法也有多种方法分支，包括共轭梯度法和高斯消元法。

从Arnoldi/Lanczos迭代推导
共轭梯度法可以看作Arnoldi/Lanczos迭代应用于求解线性方程组时的一个变种。

一般Arnoldi方法
Arnoldi迭代从一个向量开始，通过定义，其中

逐步建立Krylov子空间

的一组标准正交基。

换言之，对于，由将相对于进行Gram-Schmidt正交化然后归一化得到。

写成矩阵形式，迭代过程可以表示为

其中

当应用于求解线性方程组时，Arnoldi迭代对应于初始解的残量开始迭代，在每一步迭代之后计算和新的近似解.

直接Lanzcos方法
在余下的讨论中，我们假定是对称正定矩阵。由于的对称性, 上Hessenberg矩阵变成对阵三对角矩阵。于是它可以被更明确地表示为

这使得迭代中的有一个简短的三项递推式。Arnoldi迭代从而简化为Lanczos迭代。

由于对称正定，同样也对称正定。因此，可以通过不选主元的LU分解分解为

其中和有简单的递推式：

改写为

其中

此时需要观察到

实际上，和同样有简短的递推式：

通过这个形式，我们得到的一个简单的递推式：

以上的递推关系立即导出比共轭梯度法稍微更复杂的直接Lanczos方法。

从正交性和共轭性导出共轭梯度法
如果我们允许缩放并通过常数因子补偿缩放的系数，我们可能可以得到以下形式的更简单的递推式：

作为简化的前提，我们现在推导的正交性和的共轭性，即对于,

各个残量之间满足正交性的原因是实际上可由乘上一个系数而得。这是因为对于，，对于，

要得到的共轭性，只需证明是对角矩阵：

是对称的下三角矩阵，因而必然是对角矩阵。

现在我们可以单纯由的正交性和的共轭性推导相对于缩放后的的常数因子和。

由于的正交性，必然有。于是

类似地，由于的共轭性，必然有。于是

推导至此完成。

参考文献

Category:数值线性代数
Category:最优化算法