# Does the k-th approximate solution of a stationary iteration belong to the k-th Krylov subspace?

For an stationary iteration method solving $$Ax=b$$ as follows: $$Mx_k = Nx_{k-1}+b,$$ I have known that when $$M = I$$, i.e., the Richardson iteration, the k-th solution $$x_k = x_{k-1}+r_{k-1}$$ is in the k-th Krylov subspace $$K_k(A,b)$$ with $$x_0=0$$. So, if we use a Krylov subspace method e.g., GMRES, the k-th solution $$x_k$$ not only belongs to the k-th Krylov subspace $$K_k(A,b)$$, but also minimize the k-th residual over this subspace. From this, we know that GMRES automatically chooses the best solution from the k-th Krylov subspace. So, it will perform "better" in some sense, than the stationary Richardson iteration method (because Richardson iteration just produces a solution lying in the same subspace, not minimizes some function), right?

My question is when the matrix $$M$$ in the stationary iterative method $$Mx_k =Nx_{k-1}+b$$ is not taken as the identity matrix, e.g., Jacobi iteration, $$M = diag(A)$$, then the k-th solution are as follows: $$x_k = x_{k-1}+M^{-1}r_{k-1}.$$ Does in this case, the $$x_k$$ still belong to the k-th subspace $$K_k(A,b)$$? If so, then Jacobi like Richardson iteration just produces a solution lying in the k-th Krylov subspace and not minimizes some function in this subspace, either. So, it still performs worse than gmres. If not, which subspace does the k-th solution $$x_k$$ obtained (from Jacobi iteration) lie in? Is the preconditioned subspace $$K_k(M^{-1}A,b)$$? any suggestions are welcome.

Taking $$x_0 = 0$$, we have that $$x_1 \in $$.
For the next iteration, we get $$x_2 \in $$.
For the next iteration, we get $$x_3 \in $$.
Continuing this argument, you will eventually find that $$x_k \in \mathcal{K}_k(M^{-1}A,M^{-1}b)$$.
This space can also be described as $$Mx_k \in \mathcal{K}_k(AM^{-1},b)$$. This is the space a Krylov method like GMRES will search in when using right preconditioning.
• Thanks for your reply, so the solution $x_k$ obtained by a stationary iteration and by a Krylov subspace method lies in different Krylov subspace, right? then How to compare which one is better? Because unlike Richardson iteration, it produces a solution lying in the same subspace with gmres. why Krylov subspace method performs "better" than a stationary iteration method except Richardson? thanks Dec 5 '19 at 9:30
• I think you misunderstood. There are multiple ways to apply a preconditioner in a Krylov subspace method. The subspace $\mathcal{K}_k(M^{-1}A,b)$ is a result of applying a left preconditioner. But you can equally well apply a right preconditioner as in my answer. The relation between the two is kind of difficult. Dec 5 '19 at 12:40