如何更好的理解共軛梯度方法？

01-21

如題

國內的教材和論文中對此深度講解的較少，建議參看《An Introduction to the Conjugate Gradient Method Without the Agonizing Pain》，直觀講解此CG演算法。

找到n個basis，然後找到如何對寫basis vector進行線性組合的參數，方程就解出來了，只是這樣的n個basis vector在和矩陣有conjugate gradient關係的時候非常容易找到，不要額外存儲舉著或向量等特點。買本numerical optimization吧

令 $X=X_{0} + e_{0}=X_{0}+JC$ , $X_{0}$ 為初始值， $J$ 為 $X$ 空間內一個完備的坐標基組，可以通過其他完備的基組構建， $C$ 是初始error在這組基下的坐標。

方程映射到b的空間是 $b=AX=AX_{0}+AJC$ ，即 $r_{0}=AJC$ 。

假如 $J$ 滿足 $J^{T}AJ=Lambda$ ， $Lambda$ 為對角化的矩陣，相比普通的正交矩陣 $M^{T}M=Lambda$ ，可以稱 $J$ 為 $A$ -正交或者 $A$ -共軛。

於是有 $J^{T}r_{0}=J^{T}AJC=Lambda C$ ， $C$ 可以很簡單地得到。 $J$ 的維度和 $A$ 相同，所以理論上 $e_{0}$ 可在n步內求出。

下個問題是如何構建 $J$ ，從一般的基組出發計算量太大。而如果從 $r_{0}$ 出發，取 $j_{0}=r_{0}$ ，再取 $r_{i}$ 中與 $span(r_{0},r_{1}, ... ,r_{i-1})$ 即 $span(j_{0},j_{1},...,j_{i-1})$ 即 $Krylov subspace$ $span(b, Ab, A^{2}b, ..., A^{i-1} b)$ }中 $A$ -正交的部分作為 $j_{i}$ ，可以巧妙地發現 $j_{i+1}$ 的構建只需要 $j_{i}$ 的信息，簡化了計算，以及計算的儲存量要求。

參考文獻推薦：

An Introduction to the Conjugate Gradient Method Without the Agonizing Pain by Jonathan Richard Shewchuk.

https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf