I am studying a proof for convergence of iterative algorithm (page 145 of this link )and I don't understand how it is simplified at some point. Here is the proof:
Assuming A is symmetric positive definite matrix, and $d_{k+1} = d_k - \alpha_kr_k$, Where $d_k \in \mathbb{R}^n$ and $A \in \mathbb{R}^{n\times n}$. We also know:
$r_i =Ad_i\quad $ or $\quad d_i =A^{-1}r_i$ $\quad\quad\quad\forall i$
By expanding the square of $A-\text{norm}$ of $d_{k+1}$ we have:
$\| d_{k+1}\|_A^{2}=(d_k-\alpha_k r_k,r_k) = (A^{-1}r_k,r_k)-\alpha_k(r_k,r_k)$
$\quad\quad\quad = \|d_k\|_A^{2}(1-\frac{(r_k,r_k)}{(r_k,A^{-1}r_k)} \times \frac{(r_k,r_k)}{(r_k,A^{-1}r_k)})$
My question :
I am not sure if if this helps but I can simplify $\| d_{k+1}\|_A^{2}$ as follows :
$\| d_{k+1}\|_A^{2}= \| d_{k}\|_A^{2}(1-\frac{\alpha_k}{\|d_k\|^2}(r_k,r_k))= \| d_{k}\|_A^{2}(1 + \frac{(A^{-1}r_{k+1},r_k)}{(r_{k},A^{-1}r_k)} -\frac{(A^{-1}r_{k},r_k)}{(r_{k},A^{-1}r_k)} )$
I cannot simplify it further to obtain:
$$ \|d_k\|_A^{2}(1-\frac{(r_k,r_k)}{(r_k,Ar_k)} \times \frac{(r_k,r_k)}{(r_k,A^{-1}r_k)})$$
Could anyone help please?
Thanks in advance.
From the link you've provided, you've correctly transcribed this part of the proof:
$\| d_{k+1}\|_A^{2}=(d_k-\alpha_k r_k,r_k) = (A^{-1}r_k,r_k)-\alpha_k(r_k,r_k).$
I'm going to assume that you're okay up to here and that this is your starting point. Since $(A^{-1}r_k,r_k)= (d_k,r_k) = (d_k,Ad_k)= \|d_k\|_A^{2}$, we then have that
$$(A^{-1}r_k,r_k) -\alpha_k(r_k,r_k)=(A^{-1}r_k,r_k)(1-\frac{\alpha_k(r_k,r_k)}{(r_k,A^{-1}r_k)})=\|d_k\|_A^{2}(1-\frac{\alpha_k(r_k,r_k)}{(r_k,A^{-1}r_k)}).$$
Your desired expression then follows from the fact that $\alpha_k=\frac{(r_k,r_k)}{(r_k,Ar_k)}$ for the steepest descent algorithm.