共轭梯度法的推导

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

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

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

从共轭方向法推导

编辑

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

 

共轭方向法

编辑

在共轭方向上求最小化:

 

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

 

其中,  为一系列相互共轭的方向,例如:

 ,对于任何 

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

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

从Arnoldi/Lanczos迭代推导

编辑

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

一般Arnoldi方法

编辑

Arnoldi迭代从一个向量 开始,通过定义 ,其中

 

逐步建立Krylov子空间

 

的一组标准正交基 

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

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

 

其中

 

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

直接Lanzcos方法

编辑

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

 

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

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

 

其中  有简单的递推式:

 

改写 

 

其中

 

此时需要观察到

 

实际上,  同样有简短的递推式:

 

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

 

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

从正交性和共轭性导出共轭梯度法

编辑

如果我们允许缩放 并通过常数因子补偿缩放的系数,我们可能可以得到以下形式的更简单的递推式:

 

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

 

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

 

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

 

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

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

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

 

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

 

推导至此完成。

参考文献

编辑
  1. Hestenes, M. R.; Stiefel, E. Methods of conjugate gradients for solving linear systems (PDF). Journal of Research of the National Bureau of Standards. 1952年12月, 49 (6) [2010-06-20]. (原始内容 (PDF)存档于2010-05-05). 
  2. Saad, Y. Chapter 6: Krylov Subspace Methods, Part I. Iterative methods for sparse linear systems 2nd. SIAM. 2003. ISBN 978-0898715347.