Relation between iterative methods and preconditioning , your thoughts

Question

Let's suppose we have an invertible matrix P ( P from preconditioning ) : $Ax=b \Leftrightarrow Px = Px -Ax + b$ or $ Px = (P-A)x + b$ The iterative method which produced by the above is : $Px^{k+1}= (P-A)x^{k} + b$ . So the preconditioning is to choose a matrix P (which is invertible) so you can find a good solution from your iterative method fast (few iteration). My doubt is what is the difference between preconditioning and making an iterative method, i can't see the difference . Please tell me your thoughts. Thanks in advance

Answer 1

A good preconditioner $M$ for a linear system $Ax=b$ is a nonsingular linear map such that $M^{-1}$ is a good approximation of $A^{-1}$. The iterative methods known as Krylov subspace methods typically converge fast when the coefficient matrix is close to the identity matrix. This is why it is preferable to work with one of the equivalent linear systems $(M^{-1}A)x = M^{-1}b$ (left-preconditioning) or $(AM^{-1})y = b$ (right-preconditioning) rather than the original linear system $Ax=b$.

What you are describing is not regarded as preconditioning, rather you are exhibiting a splitting of the matrix $A$. Specifically, you write $A = P - (P-A)$ and then you construct the stationary iteration based on that splitting, i.e. $x^{k+1} = G x^k + f$, where $G = P^{-1}(P-A)$ and $f = P^{-1} b$.

EDIT: It is possible to use a stationary iteration such as Jacobi's method or Gauss-Seidel's method to precondition a linear system $Ax=b$. To that end we need to view the iteration as a linear map $\phi : \mathbb{R}^n \rightarrow \mathbb{R}^n$ and check that $\phi$ is at least a tolerable approximation of $A^{-1}$. Suppose we define $y \rightarrow \phi(y)$ as the result of doing $k$ steps of the stationary iteration \begin{align} x_0 &= 0 \\ x_{j+1} &= Gx_j + f, \quad G = P^{-1}(P-A), f = P^{-1}y \end{align} then $$ \phi(y) = \sum_{j=0}^{k-1} G^j f = \sum_{j=0}^{k-1} G^j P^{-1} y$$ is clearly a linear map. Moreover, if, say $\|G\| \ll 1 $, then $\phi$ is also a good approximation of $A^{-1}$. Recall $(I - G)^{-1} = \sum_{j=0}^\infty G^j$, when $\|G\|<1$. If $\|G\| > 1$, then $\phi$ it is a worthless approximation of $A^{-1}$. If $\|G\| \lesssim 1$, then the quality of $\phi$ as a preconditioner is questionable and one had better use GMRES for the outer loop so that the residual is at least minimized over the constructed vector space.