I'm trying to understand the proof for convergence of an algorithm.
Here is the proof. Assuming:
A is a Symmetric positive definite matrix
$x_{k+1} = x_k + αr_k + \beta Ar_k$
$ r_{k+1} =r_k −A(\alpha r_k + \beta Ar_k) \quad \quad r_{k+1}\perp Ar_k \text{ and } r_{k+1} \perp r_k$
$ \quad \quad \text{where } r_i\in \mathbb{R^n} , A \in \mathbb{R}^{n\times n}, \text{ and } \alpha , \beta \in \mathbb{R} $
Thus, we have:
$\begin{cases} (r_k −\alpha Ar_k −βA^2r_k,r_k)=0 \\ (r_k −\alpha Ar_k −\beta A^2r_k,Ar_k)=0 \end{cases}$
$\begin{cases}(r_k, r_k) = \alpha(Ar_k, r_k) + \beta(A^2r_k, r_k) \\ (r_k, Ar_k) = \alpha(Ar_k, Ar_k) + \beta(A^2r_k, Ar_k)\end{cases}$
$\begin{cases}(r_k, r_k) = \alpha(Ar_k, r_k) + β(A^2r_k, r_k) \\ (Ar_k, r_k) = \alpha (A^2r_k, r_k) + \beta(A^3r_k, r_k) \end{cases}$
We also know $r_{k} = Ad_{k}$ and $r_{k+1} = Ad_{k+1}$
$\|d_{k+1}\|_{A}^{2}= (Ad_{k+1}, d_{k+1})$
$= (r_{k+1}, d_{k+1})$
$=(r_{k+1}, d_k − \alpha r_k − \beta Ar_k)$
$=(r_{k+1},d_k)$
$=(r_k −\alpha Ar_k −\beta A^{2}r_k,d_k)$
$= (r_k, d_k) − \alpha(r_k, Ad_k) − \beta(A^2r_k, d_k)$
$= (Ad_k, d_k) − \alpha(r_k, r_k) − \beta(Ar_k, r_k)$
$ = \|d_{k}\|_{A}^{2} − \alpha \|r_k\| − \beta \|r_k\|_A$
$\rightarrow \|d_{k+1}\|_{A}^{2} ≤ \|d_{k}\|_{A}^{2}$
I don't understand how the last line ($ \|d_{k+1}\|_{A}^{2} = \|d_{k}\|_{A}^{2} − \alpha \|r_k\| − \beta \|r_k\|_A \rightarrow \|d_{k+1}\|_{A}^{2} ≤ \|d_{k}\|_{A}^{2}$) was concluded?
I would appreciate any help to understand this. Thank you.
PS: I don't know if value of $\alpha$ and $\beta$ needed since it was not mentioned in the proof. But It can be obtain as follows:
$\begin{bmatrix} r_k& Ar_k \end{bmatrix} \begin{bmatrix} \alpha \\ \beta \end{bmatrix}= \begin{bmatrix} r_k&Ar_k \end{bmatrix}(\begin{bmatrix} r_k&Ar_k \end{bmatrix}^TA\begin{bmatrix} r_k&Ar_k\end{bmatrix})^{-1} \begin{bmatrix} r_k&Ar_k\end{bmatrix}^{T}r_k$
$ \quad \quad \text{where } r_k\in \mathbb{R^n} , A \in \mathbb{R}^{n\times n}, \text{ and } \alpha , \beta \in \mathbb{R} $
There is a mistake in the last line (it should be $\|d_{k}\|_{A}^{2}$ not $\|d_{k+1}\|_{A}^{2}$):
\begin{equation} \|d_{k+1}\|_{A}^{2}= (Ad_{k+1}, d_{k+1}) = (Ad_k, d_k) − \alpha(r_k, r_k) − \beta(Ar_k, r_k)\\ \|d_{k+1}\|_{A}^{2} = \|d_{k}\|_{A}^{2} − \alpha \|r_k\| − \beta \|r_k\|_A \rightarrow \|d_{k+1}\|_{A}^{2} ≤ \|d_{k}\|_{A}^{2} \end{equation}
If $\alpha,\beta\ge 0$ we have a positive quantity ($\|d_{k}\|_{A}^{2}$) less two negative numbers ($− \alpha \|r_k\| − \beta \|r_k\|_A$) so you get $\|d_{k+1}\|_{A}^{2}$ subtracting $− \alpha \|r_k\| − \beta \|r_k\|_A$ by $\|d_{k}\|_{A}^{2}$...hence $\|d_{k+1}\|_{A}^{2} ≤ \|d_{k}\|_{A}^{2}$.