3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Taking $x_0 = 0$, we have that $x_1 \in <M^{-1}b>$.

For the next iteration, we get $x_2 \in <M^{-1}b, M^{-1}AM^{-1}b>$.

For the next iteration, we get $x_3 \in <M^{-1}b, (M^{-1}A)^2M^{-1}b>$.

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – sunshine Dec 5 '19 at 9:30
  • $\begingroup$ 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. $\endgroup$ – Thijs Steel Dec 5 '19 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.