Proving an identity We define $\|x\|_A^2:= x^TAx$ and $(x,y)_M := y^TMx$ for a symmetric positive definite matrix $A$ and an invertible matrix $M$.
I want to show the following identity for the errors of Richardson's method for solving an equation system $Ax=b$:
$$\frac{\|e_k\|^2_A - \|e_{k+1}\|_A^2}{\|e_k\|_A^2} = \frac{(y_k,y_k)_M^2}{(M^{-1}Ay_k,y_k)_M(A^{-1}My_k,y_k)_M}$$
whereas $e_k=x-x_k$, $y_k=M^{-1}r_k$, $r_k=b-Ax_k$ and $e_{k+1} = (I-M^{-1}A)e_k$ with $I$ the unit matrix.
So far I established the identity:
$\|e_{k+1}\|^2_A= e_k^Tr_k - e_k^T Ay_k - r_k^T M^{-1}Ae_k + y_k^T AM^{-1}Ae_k$
and I'm tried to calculate that
$$\frac{\|e_k\|^2_A - \|e_{k+1}\|_A^2}{\|e_k\|_A^2}\cdot (M^{-1}Ay_k,y_k)_M(A^{-1}My_k,y_k)_M = (y_k,y_k)_M^2$$
but my calculations never really go anywhere.
Does anyone have an idea on how to show this? Or how to calculate that the identity holds without getting confused somewhere along the way?
 A: I guess this actually does hold. Not for the (preconditioned) Richardson method but for the (preconditioned) steepest descent method.
In the preconditioned SD method, you update your $x_k$ such that the $A$-norm of the error of $x_{k+1}$ is minimal along the direction of the preconditioned residual $y_k=M^{-1}r_k$, that is, $x_{k+1}=x_k+\alpha_k y_k$, and since $e_{k+1}=e_k-\alpha_k y_k$ and 
$$
\|e_{k+1}\|_A^2 = \|e_k\|_A^2-2\alpha_ky_k^Tr_k+\alpha_k^2y_k^TAy_k,
$$
we have $\alpha_k=y_k^Tr_k/y_k^TAy_k$.
Then
$$
\begin{split}
\|e_{k+1}\|_A^2 &= \|e_k^2\|_A^2-2\left(\frac{y_k^Tr_k}{y_k^TAy_k}\right)y_k^Tr_k+\left(\frac{y_k^Tr_k}{y_k^TAy_k}\right)^2y_k^TAy_k\\
&=\|e_k\|_A^2-\frac{2(y_k^Tr_k)^2-(y_k^Tr_k)^2}{y_k^TAy_k}
=\|e_k\|_A^2-\frac{(y_k^Tr_k)^2}{y_k^TAy_k}
\end{split}
$$
and hence
$$
\|e_k\|_A^2-\|e_{k+1}\|_A^2=\frac{(y_k^Tr_k)^2}{y_k^TAy_k}
$$
and
$$
\frac{\|e_k\|_A^2-\|e_{k+1}\|_A^2}{\|e_k\|_A^2}=\frac{(y_k^Tr_k)^2}{(y_k^TAy_k)(e_k^TAe_k)}.
$$
Since $y_k^Tr_k=y_k^TMy_k$, $e_k^TAe_k=r_k^TA^{-1}r_k=y_k^TM^TA^{-1}My_k$, we have
$$
\frac{\|e_k\|_A^2-\|e_{k+1}\|_A^2}{\|e_k\|_A^2}=\frac{(y_k^TMy_k)^2}{(y_k^TAy_k)(y_k^TM^TA^{-1}My_k)}.
$$
So far without any further assumptions on $M$.
Assuming that $M$ is symmetric and positive definite (so that it induces an inner product $(x,y)_M=y^TMy$), is equivalent to
$$
\frac{\|e_k\|_A^2-\|e_{k+1}\|_A^2}{\|e_k\|_A^2}=\frac{(y_k,y_k)_M^2}{(M^{-1}Ay_k,y_k)_M(A^{-1}My_k,y_k)_M},
$$
which looks like what you are looking for. However, it is true if:


*

*You use the steepest descent method instead of the simple Richardson,

*the preconditioner $M$ is symmetric and positive definite.


Hope this helps, feel free to ask for clarification on any point (I could make a typo somewhere too).
P.S.: Without the assumption that $M$ is SPD (or at least symmetric), the last identity is correct (if you set $(x,y)_M=y^TMx$ formally without it being an actual inner product), except the second term in the denominator on the right-hand side because $y_k^TM^TA^{-1}My_k$ would be actually $(A^{-1}My_k,y_k)_{M^T}$ instead of $(A^{-1}My_k,y_k)_{M}$.
