Conjugate Gradient
对于对称正定矩阵A和向量b,构造优化目标函数\phi(x)=\frac{1}{2}x^TAx-b^Tx.
可以用张量记号写作:\phi=\frac{1}{2}x_ia_{ij}x_j.
对x_i求导得:
\frac{\partial\phi}{\partial x_i}=\frac{1}{2}a_{ij}x_j+\frac{1}{2}x_ja_{ji}.
由于A对称,故这两项相等,即\frac{\partial\phi}{\partial x_i}=a_{ij}x_j=Ax.
Preconditioner
https://ending2015a.github.io/Ending2015a/52045/
假设有一个对称正定矩阵M\approx A,而且很好求逆。则作为一个对称正定阵,可以分解为M=EE^T,对其求逆得M^{-1}=E^{-T}E^{-1}.那么我们可以做变换:
\begin{aligned}
Ax&=b.\
M^{-1}Ax&=M^{-1}b.\
E^{-T}E^{-1}Ax&=E^{-T}E^{-1}b.\
(E^{-1}AE^{-T})E^Tx&=E^{-1}b.
\end{aligned}