Numerical Methods - Gradient method

73 Views Asked by At

Consider the (unpreconditioned) gradient method for the solution of a linear system $A\underline{x} = \underline{b}$.

(a) Show that the acceleration parameter $\alpha_{k}$ in the gradient method is the unique solution to the minimisation problem: $\alpha_{k} = arg min \Phi(\underline{x}^k +\alpha\underline{r}^k)$, where $\Phi(\underline{y})=\frac{1}{2}\underline{y}^TA\underline{y}-\underline{y}^T\underline{b}$ denotes the energy of the system $A\underline{x}=\underline{b}$.

(b) Show that the residuals in the gradient method satisfy $(\underline{r}^{k+1},\underline{r}^k)=0$ for each $k$.

(c) Give a geometric interpretation of the gradient method.

I attempted the first part of this question as follows:

$\Phi(\underline{x}^k + \alpha\underline{r}^k) = \frac{1}{2}(\underline{x}^k+\alpha\underline{r}^k)^TA(\underline{x}^k + \alpha\underline{r}^k)-(\underline{x}^k + \alpha\underline{r}^k)^T\underline{b}$.

And using the fact that $\alpha_k = \frac{||\underline{r}^k||^2_{2}}{||\underline{r}^k||^2_{A}}$, I said:

$argmin(\frac{1}{2}(\underline{x}^k+\alpha\underline{r}^k)^TA(\underline{x}^k + \alpha\underline{r}^k)-(\underline{x}^k + \alpha\underline{r}^k)^T\underline{b})=\frac{||\underline{r}^k||^2_{2}}{||\underline{r}^k||^2_{A}}$.

I'm not sure whether this is even the right approach. As for the other parts, I'm completely clueless. Any help would be appreciated.