$A$ is square and positive definite, and let $r_k = Ax_k - b$. Also let $M = \frac{1}{2}(A+A^T)$. I want to show that $$\frac{||r_{k+1}||_2}{||r_k||_2} \le \left(1-\frac{\lambda_\min(M)^2}{\lambda_\max(A^TA)} \right)^{1/2}$$

We define $x_{k+1} = x_k + \alpha_k r_k$, where $\alpha_k$ is chosen to minimize $||r_{k+1}||_2$.

I think I found $\alpha_k$, to be specific I think that $$\alpha_k = -\frac{r_k^TA^TAx_k}{r_k^TA^T Ar_k}$$

An earlier part of the problem has us prove that $$\frac{v^TAv}{v^Tv}\ge \lambda_\min(M) > 0$$

I am having trouble using those two facts to get the desired result. I tried expanding $||r_{k+1}||_2^2 = r_{k+1}^Tr_{k+1}$ by using its definition and the definition of $\alpha$, but I didn't get really anywhere. Any ideas? Thanks!

  • $\begingroup$ With your optimal choice of alpha, what is $x_{k+1}$ in terms of values from iteration $k$? $\endgroup$ Aug 20, 2016 at 1:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.