共轭梯度法的推导

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

$𝑨𝒙=𝒃$

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

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

从共轭方向法推导

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

$f(𝒙)={𝒙}^{\mathrm{T}}𝑨𝒙-2{𝒃}^{\mathrm{T}}𝒙\text{.}$

共轭方向法

在共轭方向上求最小化：

$f(𝒙)={𝒙}^{\mathrm{T}}𝑨𝒙-2{𝒃}^{\mathrm{T}}𝒙\text{.}$

从最初的猜测${𝒙}_0$开始，以及相应的残差 ${𝒓}_0=𝒃-{𝑨𝒙}_0$, 并通过公式计算迭代和残差

$\begin{array}{cc}{\alpha }_i& =\frac{{𝒑}_i^{\mathrm{T}}{𝒓}_i}{{𝒑}_i^{\mathrm{T}}{𝑨𝒑}_i}\text{,}\\ {𝒙}_{i+1}& ={𝒙}_i+{\alpha }_i{𝒑}_i\text{,}\\ {𝒓}_{i+1}& ={𝒓}_i-{\alpha }_i{𝑨𝒑}_i\end{array}$

其中，${𝒑}_0,{𝒑}_1,{𝒑}_2,\dots$ 为一系列相互共轭的方向，例如：

${𝒑}_i^{\mathrm{T}}{𝑨𝒑}_j=0$，对于任何$i\ne j$

由于共轭方向法没有给出用于选择方向的公式，因此该方法具有误差 ${𝒑}_0,{𝒑}_1,{𝒑}_2,\dots$

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

从Arnoldi/Lanczos迭代推导

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

一般Arnoldi方法

Arnoldi迭代从一个向量${𝒓}_0$开始，通过定义${𝒗}_i={𝒘}_i/\Vert {𝒘}_i{\Vert }_2$，其中

${𝒘}_i=\{\begin{array}{cc}{𝒓}_0& \text{if }i=1\text{,}\\ {𝑨𝒗}_{i-1}-\sum _{j=1}^{i-1}({𝒗}_j^{\mathrm{T}}{𝑨𝒗}_{i-1}){𝒗}_j& \text{if }i>1\text{,}\end{array}$

逐步建立Krylov子空间

$𝒦(𝑨,{𝒓}_0)=\{{𝒓}_0,{𝑨𝒓}_0,{𝑨}^2{𝒓}_0,\dots \}$

的一组标准正交基$\{{𝒗}_1,{𝒗}_2,{𝒗}_3,\dots \}$。

换言之，对于$i>1$，${𝒗}_i$由将${𝑨𝒗}_{i-1}$相对于$\{{𝒗}_1,{𝒗}_2,\dots ,{𝒗}_{i-1}\}$进行Gram-Schmidt正交化然后归一化得到。

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

${𝑨𝑽}_i={𝑽}_{i+1}{\widetilde{𝑯}}_i\text{,}$

其中

$\begin{array}{cc}{𝑽}_i& =\left[\begin{array}{cccc}{𝒗}_1& {𝒗}_2& \cdots & {𝒗}_i\end{array}\right]\text{,}\\ {\widetilde{𝑯}}_i& =\left[\begin{array}{ccccc}{h}_{11}& h_{12}& h_{13}& \cdots & h_{1,i}\\ h_{21}& h_{22}& h_{23}& \cdots & h_{2,i}\\ & h_{32}& h_{33}& \cdots & h_{3,i}\\ & & \ddots & \ddots & ⋮\\ & & & h_{i,i-1}& h_{i,i}\\ & & & & h_{i+1,i}\end{array}\right]=\left[\begin{array}{c}{𝑯}_i\\ h_{i+1,i}{𝒆}_i^{\mathrm{T}}\end{array}\right]\text{,}\\ h_{ji}& =\{\begin{array}{cc}{𝒗}_j^{\mathrm{T}}{𝑨𝒗}_i& \text{if }j\le i\text{,}\\ \Vert {𝒘}_{i+1}{\Vert }_2& \text{if }j=i+1\text{,}\\ 0& \text{if }j>i+1\text{.}\end{array}\end{array}$

当应用于求解线性方程组时，Arnoldi迭代对应于初始解${𝒙}_0$的残量${𝒓}_0=𝒃-{𝑨𝒙}_0$开始迭代，在每一步迭代之后计算${𝒚}_i={𝑯}_i^{-1}(\Vert {𝒓}_0{\Vert }_2{𝒆}_1)$和新的近似解${𝒙}_i={𝒙}_0+{𝑽}_i{𝒚}_i$.

直接Lanzcos方法

在余下的讨论中，我们假定$𝑨$是对称正定矩阵。由于$𝑨$的对称性, 上Hessenberg矩阵${𝑯}_i={𝑽}_i^{\mathrm{T}}{𝑨𝑽}_i$变成对阵三对角矩阵。于是它可以被更明确地表示为

${𝑯}_i=\left[\begin{array}{cc}{a}_1& b_2\\ b_2& a_2& b_3\\ & \ddots & \ddots & \ddots \\ & & b_{i-1}& a_{i-1}& b_i\\ & & & b_i& a_i\end{array}\right]\text{.}$

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

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

${𝑯}_i={𝑳}_i{𝑼}_i=\left[\begin{array}{c}1\\ c_2& 1\\ & \ddots & \ddots \\ & & c_{i-1}& 1\\ & & & c_i& 1\end{array}\right]\left[\begin{array}{cc}{d}_1& b_2\\ & d_2& b_3\\ & & \ddots & \ddots \\ & & & d_{i-1}& b_i\\ & & & & d_i\end{array}\right]\text{,}$

其中$c_i$和$d_i$有简单的递推式：

$\begin{array}{cc}{c}_i& =b_i/d_{i-1}\text{,}\\ d_i& =\{\begin{array}{cc}{a}_1& \text{if }i=1\text{,}\\ a_i-c_i{b}_i& \text{if }i>1\text{.}\end{array}\end{array}$

改写${𝒙}_i={𝒙}_0+{𝑽}_i{𝒚}_i$为

$\begin{array}{cc}{𝒙}_i& ={𝒙}_0+{𝑽}_i{𝑯}_i^{-1}(\Vert {𝒓}_0{\Vert }_2{𝒆}_1)\\ & ={𝒙}_0+{𝑽}_i{𝑼}_i^{-1}{𝑳}_i^{-1}(\Vert {𝒓}_0{\Vert }_2{𝒆}_1)\\ & ={𝒙}_0+{𝑷}_i{𝒛}_i\text{,}\end{array}$

其中

$\begin{array}{cc}{𝑷}_i& ={𝑽}_i{𝑼}_i^{-1}\text{,}\\ {𝒛}_i& ={𝑳}_i^{-1}(\Vert {𝒓}_0{\Vert }_2{𝒆}_1)\text{.}\end{array}$

此时需要观察到

$\begin{array}{cc}{𝑷}_i& =\left[\begin{array}{cc}{𝑷}_{i-1}& {𝒑}_i\end{array}\right]\text{,}\\ {𝒛}_i& =\left[\begin{array}{c}{𝒛}_{i-1}\\ {\zeta }_i\end{array}\right]\text{.}\end{array}$

实际上，${𝒑}_i$和${\zeta }_i$同样有简短的递推式：

$\begin{array}{cc}{𝒑}_i& =\frac{1}{d_i}({𝒗}_i-b_i{𝒑}_{i-1})\text{,}\\ {\alpha }_i& =-c_i{\zeta }_{i-1}\text{.}\end{array}$

通过这个形式，我们得到${𝒙}_i$的一个简单的递推式：

$\begin{array}{cc}{𝒙}_i& ={𝒙}_0+{𝑷}_i{𝒛}_i\\ & ={𝒙}_0+{𝑷}_{i-1}{𝒛}_{i-1}+{\zeta }_i{𝒑}_i\\ & ={𝒙}_{i-1}+{\zeta }_i{𝒑}_i\text{.}\end{array}$

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

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

如果我们允许缩放${𝒑}_i$并通过常数因子补偿缩放的系数，我们可能可以得到以下形式的更简单的递推式：

$\begin{array}{cc}{𝒙}_i& ={𝒙}_{i-1}+{\alpha }_{i-1}{𝒑}_{i-1}\text{,}\\ {𝒓}_i& ={𝒓}_{i-1}-{\alpha }_{i-1}{𝑨𝒑}_{i-1}\text{,}\\ {𝒑}_i& ={𝒓}_i+{\beta }_{i-1}{𝒑}_{i-1}\text{.}\end{array}$

作为简化的前提，我们现在推导${𝒓}_i$的正交性和${𝒑}_i$的共轭性，即对于$i\ne j$,

$\begin{array}{cc}{𝒓}_i^{\mathrm{T}}{𝒓}_j& =0\text{,}\\ {𝒑}_i^{\mathrm{T}}{𝑨𝒑}_j& =0\text{.}\end{array}$

各个残量之间满足正交性的原因是${𝒓}_i$实际上可由${𝒗}_{i+1}$乘上一个系数而得。这是因为对于$i=0$，${𝒓}_0=\Vert {𝒓}_0{\Vert }_2{𝒗}_1$，对于$i>0$，

$\begin{array}{cc}{𝒓}_i& =𝒃-{𝑨𝒙}_i\\ & =𝒃-𝑨({𝒙}_0+{𝑽}_i{𝒚}_i)\\ & ={𝒓}_0-{𝑨𝑽}_i{𝒚}_i\\ & ={𝒓}_0-{𝑽}_{i+1}{\widetilde{𝑯}}_i{𝒚}_i\\ & ={𝒓}_0-{𝑽}_i{𝑯}_i{𝒚}_i-h_{i+1,i}({𝒆}_i^{\mathrm{T}}{𝒚}_i){𝒗}_{i+1}\\ & =\Vert {𝒓}_0{\Vert }_2{𝒗}_1-{𝑽}_i(\Vert {𝒓}_0{\Vert }_2{𝒆}_1)-h_{i+1,i}({𝒆}_i^{\mathrm{T}}{𝒚}_i){𝒗}_{i+1}\\ & =-h_{i+1,i}({𝒆}_i^{\mathrm{T}}{𝒚}_i){𝒗}_{i+1}\text{.}\end{array}$

要得到${𝒑}_i$的共轭性，只需证明${𝑷}_i^{\mathrm{T}}{𝑨𝑷}_i$是对角矩阵：

$\begin{array}{cc}{𝑷}_i^{\mathrm{T}}{𝑨𝑷}_i& ={𝑼}_i^{-\mathrm{T}}{𝑽}_i^{\mathrm{T}}{𝑨𝑽}_i{𝑼}_i^{-1}\\ & ={𝑼}_i^{-\mathrm{T}}{𝑯}_i{𝑼}_i^{-1}\\ & ={𝑼}_i^{-\mathrm{T}}{𝑳}_i{𝑼}_i{𝑼}_i^{-1}\\ & ={𝑼}_i^{-\mathrm{T}}{𝑳}_i\end{array}$

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

现在我们可以单纯由${𝒓}_i$的正交性和${𝒑}_i$的共轭性推导相对于缩放后的${𝒑}_i$的常数因子${\alpha }_i$和${\beta }_i$。

由于${𝒓}_i$的正交性，必然有${𝒓}_{i+1}^{\mathrm{T}}{𝒓}_i=({𝒓}_i-{\alpha }_i{𝑨𝒑}_i{)}^{\mathrm{T}}{𝒓}_i=0$。于是

$\begin{array}{cc}{\alpha }_i& =\frac{{𝒓}_i^{\mathrm{T}}{𝒓}_i}{{𝒓}_i^{\mathrm{T}}{𝑨𝒑}_i}\\ & =\frac{{𝒓}_i^{\mathrm{T}}{𝒓}_i}{({𝒑}_i-{\beta }_{i-1}{𝒑}_{i-1}{)}^{\mathrm{T}}{𝑨𝒑}_i}\\ & =\frac{{𝒓}_i^{\mathrm{T}}{𝒓}_i}{{𝒑}_i^{\mathrm{T}}{𝑨𝒑}_i}\text{.}\end{array}$

类似地，由于${𝒑}_i$的共轭性，必然有${𝒑}_{i+1}^{\mathrm{T}}{𝑨𝒑}_i=({𝒓}_{i+1}+{\beta }_i{𝒑}_i{)}^{\mathrm{T}}{𝑨𝒑}_i=0$。于是

$\begin{array}{cc}{\beta }_i& =-\frac{{𝒓}_{i+1}^{\mathrm{T}}{𝑨𝒑}_i}{{𝒑}_i^{\mathrm{T}}{𝑨𝒑}_i}\\ & =-\frac{{𝒓}_{i+1}^{\mathrm{T}}({𝒓}_i-{𝒓}_{i+1})}{{\alpha }_i{𝒑}_i^{\mathrm{T}}{𝑨𝒑}_i}\\ & =\frac{{𝒓}_{i+1}^{\mathrm{T}}{𝒓}_{i+1}}{{𝒓}_i^{\mathrm{T}}{𝒓}_i}\text{.}\end{array}$

推导至此完成。

参考文献

1. Template:Cite journal
2. Template:Cite book