共轭梯度法

阐述

是求解线性方程的一种 Krylov 子空间法，要求 $A=A^*$ 是正定 Hermite 矩阵。将线性方程转化为了优化问题。定义

$$\|x\|_A=\sqrt{x^*Ax}$$

最小化 $x$ 和真解之间的误差，

$$\min_{x\in\mathbb R^m}\|x-x_*\|_A^2=\min_{x\in\mathbb R^m}f(x)$$

其中 $f(x)=x^*Ax-x^*b-b^*x$。它的梯度是（使用 Cauchy-Riemann calculus）：

$$f(x+\delta)-f(x)=\delta^*\nabla_{\bar x}f+(\nabla_xf)^T\delta+O(\delta^2)$$

因此梯度为 0 就表明达到了极值点。

在共轭梯度法中，每次下降的方向 $d_n$ 并不等于 $r_n=b-Ax_n$，而是让各个方向关于 $A$ 正交，也就是 $d_n^*Ad_k=0$. 虽然可以通过 Gram-Schmidt 正交化来计算出这些方向，但是实际上只有最后一个方向是有用的，即

$$d_n=r_n+d_{n-1}\frac{r_n^*r_n}{r_{n-1}^*r_{n-1}}$$

预条件

由于 $MA$ 一般不是 Hermitian 的，需要采取

$$M^{1/2}AM^{1/2}M^{-1/2}x=M^{1/2}b$$

令 $A'=M^{1/2}AM^{1/2}$，则这个矩阵也是 Hermitian 的，而且正定。

双共轭梯度法

求解

$$\begin{pmatrix}0&A\\A^*&0\end{pmatrix}\begin{pmatrix}\hat x\\x\end{pmatrix}=\begin{pmatrix}b\\\hat b\end{pmatrix}$$

这个矩阵是 Hermitian 的，但不是正定的，求解可能不会收敛，或者收敛到鞍点上。

非线性问题

采用 $r_n=-\nabla_xf_0$，其余和线性共轭梯度方法是一样的。但是，在远离最低点处，共轭梯度的附加项可能还不如不加。

实例

性质

复杂度

• 每步一个矩阵向量乘法
• $\Theta(mn)$ 计算
• $\Theta(m)$ 存储

收敛性

最差情况 $O(\sqrt{\kappa(A)})$ 次迭代，但是经常会更好

相关内容

参考文献