Splitting methods

Assume, for example, that we can quickly solve $Mx=b$ and $M\approx A$. Then:

$$\begin{array}{c}Ax=b\\ (A-M)x+Mx=b\\ Mx=b-(A-M)x\end{array}$$

This suggests a simple iterative strategy based on the idea of fixed-point iteration.

$$\begin{array}{c}A=M-N\\ M{x}^{(k+1)}=b+N{x}^{(k)}\end{array}$$

If $x^{(k)}$ converges, it must converge to the solution of $Ax=b$.

This method, when it converges, requires solving with $M$ instead of $A$. In many cases, this allows solving $Ax=b$ approximately very fast.