Gradient Method

Thm 7.31

給定一個 ${\mathbb{R}}^{n\times n}$ 裡的 symmetric postive matrix $A$，當我們想解 $A\overrightarrow{x}=\overrightarrow{b}$ 的 $\overrightarrow{x}$ 時，等價於找到能 minimizes $\mathrm{\Phi }(\overrightarrow{y})=\frac{1}{2}<A\overrightarrow{y},\overrightarrow{y}>-<\overrightarrow{b},\overrightarrow{y}>$ 的 $\overrightarrow{x}$

而怎麼去找 $\mathrm{\Phi }$ 的最小值的方法就叫 Gradient Method

證明：

而我們利用這個方法去找到每次的 $x^{(k)}$：

也就是用上一步的 $x^{(k-1)}$，加上某一個純量(scalar) ${\alpha }_{k-1}$ 乘上更新的方向 ${\overrightarrow{p}}^{(k-1)}$

所以我們需要知道 ${\overrightarrow{p}}^{(k-1)}$ 長怎樣，另外一個就是要知道每一步要跨多大，所以要知道 ${\alpha }_{k-1}$ 的值是多少，要注意 ${\alpha }_{k-1}$ 需要大於 0，這樣才會是我們要的方向

為什叫 Gradient Method

因為之前有說過如果一個函數可微的話，那麼這個函數的負的 gradient 方向就會指出它最大的遞減方向

所以 ${\overrightarrow{p}}^{(k-1)}=-\mathrm{\nabla }\mathrm{\Phi }({\overrightarrow{x}}^{(k-1)})$ 就會是 ${\overrightarrow{x}}^{(k-1)}$ 那點的最大遞減方向，那麼 ${\overrightarrow{x}}^{(k-1)}$ 加上 $-{\alpha }_{k-1}\mathrm{\nabla }\mathrm{\Phi }({\overrightarrow{x}}^{(k-1)})$ 就可以保證越來越小

這個 ${\overrightarrow{r}}^{(k-1)}$ 是之前說的那個 residual vector，通常定義是 ${\overrightarrow{r}}^{(k-1)}=\overrightarrow{b}-A{\overrightarrow{x}}^{(k-1)}$

所以這樣我們就可以推出我們下一步的解要沿著 residual vector 的方向來做變化

找 alpha

接下來要來決定 ${\alpha }_{k-1}$，推導：

那我們可以做個簡單的操作來得到 residual vector 的 equation：

Pseudo Code