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}