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