Conjugate Gradient Method

Conjugate Gradient Method

這邊我們一樣考慮解

$A\overrightarrow{x}=\overrightarrow{b}$，前面講的是 Gradient Method，那這節要講的是 Conjugate Gradient Method，效率一般來說會更好，而且好很多

$\alpha$ 要選來 minimize

$\mathrm{\Phi }({\overrightarrow{x}}^{(k)})$，因為我們希望它越小越好，前面的 Gradient Method 裡面

${\overrightarrow{p}}^{(k-1)}$ 是用 gradient 來做的，但這邊我們不用這個方法。

我們先看

$\alpha$，先不管

${\overrightarrow{p}}^{(k-1)}$，所以假設

${\overrightarrow{p}}^{(k-1)}$ 已知：

基本上推導過程差不多，所以重點就是

${\overrightarrow{p}}^{(k-1)}$ 要怎麼找

A-orthogonal

在開始找之前我們先給個定義，假設 A 是個

${\mathbb{R}}^{n\times n}$ 的矩陣，我們說有一個 nonzero vector 的 set

$\{{\overrightarrow{v}}^{(1)},{\overrightarrow{v}}^{(2)},...,{\overrightarrow{v}}^{(n)}\}$，如果這個集合滿足

$<{\overrightarrow{v}}^{(i)},A{\overrightarrow{v}}^{(j)}>=0ifi\ne j$ 的話，我們就說這個集合是一個 A-orthogonal 的 set。

那我們說這個集合如果是 A-orthogonal 而且 A 矩陣是對稱正定的話，那麼這個集合必定會線性獨立，證明：

代表這個集合是

${\mathbb{R}}^n$ 的一組基底

Thm 7.32

給定一個集合 A-orthogonal 的集合

$\{{\overrightarrow{v}}^{(1)},{\overrightarrow{v}}^{(2)},...,{\overrightarrow{v}}^{(n)}\}$，

$A$ 是對稱正定矩陣。

那當我們要解

$A\overrightarrow{x}=\overrightarrow{b}$ 時我們要用這個式子：

那妳可以看見

$\overrightarrow{v}$ 只有 n 項，也就代表最多只會迭代 n 次，也就是說

${\overrightarrow{x}}^{(n)}$ 就是我們要的

$\overrightarrow{x}$。

證明：

所以現在問題就變成

$\overrightarrow{v}$ 要怎麼找了

Thm 7.33

residual vector

${\overrightarrow{r}}^{(k)}$, k = 1, 2, …, n，滿足 <

${\overrightarrow{r}}^{(k)},{\overrightarrow{v}}^{(j)}$>

$=0$, j = 1, 2, …, k

也就是說

${\overrightarrow{r}}^{(1)}$ 和

${\overrightarrow{v}}^{(1)}$ 垂直，

${\overrightarrow{r}}^{(2)}$ 和

${\overrightarrow{v}}^{(1)}$ 還有

${\overrightarrow{v}}^{(2)}$ 垂直，

${\overrightarrow{r}}^{(n)}$ 和全部的

${\overrightarrow{v}}^{(j)}$ 垂直。

那證明我們就用數學歸納法：

找 A-orthogonal 的集合

假設執行到第 k 步的時候

${\overrightarrow{x}}^{(1)},{\overrightarrow{x}}^{(2)},...,{\overrightarrow{x}}^{(k-1)}$ 且

${\overrightarrow{v}}^{(1)},{\overrightarrow{v}}^{(2)},...,{\overrightarrow{v}}^{(k-1)}$ 都已經知道了，那下一次的

${\overrightarrow{v}}^{(k)}={\overrightarrow{r}}^{(k)}={\overrightarrow{r}}^{(k-1)}+{\beta }_{k-1}{\overrightarrow{v}}^{(k-1)}$

因為我們要造的是 A-orthogonal 的集合，所以我們希望找到的

${\beta }_{k-1}$ 能讓

${\overrightarrow{v}}^k$ 和上一次的

${\overrightarrow{v}}^{(k-1)}$ 垂直，那就把寫下來整理一下：

然後把前面算出來的

$\alpha$ 抄下來推一下：

算 Conjugate gradient