共轭梯度法的推导

维基百科,自由的百科全书
跳转至: 导航搜索

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

迭代方法。共轭梯度法可以从不同的角度推导而得,包括作为求解最优化问题的共轭方向法的特例,以及作为求解特征值问题的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). 
  2. Saad, Y. Chapter 6: Krylov Subspace Methods, Part I. Iterative methods for sparse linear systems 2nd. SIAM. 2003. ISBN 978-0898715347.