Are GMRES and CG iterations the same for SPD matrix? Just curious, I know computationally, due to storage, cg would be the best when A is SPD. However I am curious if just their iterations are the same? My intuition says no, but if someone could confirm this for me that would be great.
 A: They are not. Consider the solution of the linear system $Ax=b$, starting with the initial guess $x_0 = 0$. After $k$ iterations GMRES minimizes the 2-norm of the residual $r_k = b - Ax_k$ over the Krylov subspace $K_k(A,b)$. In contrast, CG minimizes the A-norm of the error $e_k = x - x_k$ over the same space. These results can be found in Saad's book "Iterative methods for sparse linear systems".
A: Let $x_0$ be an initial guess to the solution of $Ax=b$ and $r_0=b-Ax_0$ be the corresponding residual vector. Krylov subspace methods construct approximations  $x_k\in x_0+c_k$, where $c_k\in K_k$ and $K_k:=\mathrm{span}(r_0,Ar_0,\ldots,A^{k-1}r_0)$. A particular method is determined by the way how $c_k$ is constructed.
The GMRES method chooses $c_k:=c_k^{\rm GMRES}$ such that the 2-norm of the residual is minimal:
$$
\|r_k^{\rm GMRES}\|_2=\|r_0-Ac_k^{\rm GMRES}\|_2=\min_{c\in K_k}\|r_0-Ac\|_2.
$$
Since $Ac\in AK_k$ this turns out to be equivalent to
$$
r_k^{\rm GMRES}\perp AK_k.
$$
Another method, called FOM here (full orthogonalization method), generates $c_k:=c_k^{\rm FOM}$ such that 
$$
r_k^{\rm FOM} \perp K_k.
$$
Now, this turns out to be equivalent to minimizing the $A$-norm of the error, exactly as CG does, provided that $A$ is SPD. Note that with $e_k:=x-x_0=A^{-1}r_k$, we have
$$
\|e_k\|_A = \|r_k\|_{A^{-1}} = \|A^{-1/2}(r_0-Ac_k)\|_2.
$$
If we want this to be minimal, we need $A^{-1/2}r_k\perp A^{1/2}K_k$, which is equivalent to $r_k\perp K_k$.
Consequently, CG is not equivalent to GMRES, but is mathematically equivalent to FOM. I say "mathematically" because FOM is based on the full orthogonalization by the Arnoldi method, while CG uses short recurrences and thus the latter is very sensitive to rounding errors. So while the methods are equivalent on the paper, there can generate different iterates when implemented on a computer with finite precision.
One relation between GMRES and FOM is worth mentioning (see Prop. 6.13 in the referenced book) which reveals a sort of equivalence of the two methods on a certain condition:
$$
\|r_k^{\rm FOM}\|_2=\frac{\|r_k^{\rm GMRES}\|_2}{\sqrt{1-\left(\frac{\|r_k^{\rm GMRES}\|_2}{\|r_{k-1}^{\rm GMRES}\|_2}\right)^2}}.
$$
Hence $\|r_k^{\rm FOM}\|_2\approx \|r_k^{\rm GMRES}\|_2$ provided that $\|r_k^{\rm FOM}\|_2\ll \|r_{k-1}^{\rm FOM}\|_2$. So, for example, if GMRES has fast convergence for a certain problem (e.g., with a good preconditioner), the residual norms of the generated iterates are very close for both methods (note that this does not necessarily mean that the iterates need to be close if $A$ is ill-conditioned).
