Matrix splitting
= Matrix splitting
{wiki}
A splitting $A=M-N$ with invertible $M$ produces
$$
x^{(k+1)}=M^{-1}Nx^{(k)}+M^{-1}b.
$$
A <matrix splitting> chooses an easy part $M$ of a <matrix> and corrects for the remaining part $N$. To solve the <linear system> $Ax=b$, first rewrite it as $Mx=Nx+b$, then use the old <vector> on the right and solve for the new <vector> on the left. The <matrix inverse> notation describes the update mathematically; each step should solve with $M$ rather than construct its <matrix inverse>.<Math 221, Matrix Computations, Fall 2009/Notes for Ma221 Lecture 21, Nov 10 2009>[Math 221, Matrix Computations, Fall 2009; Basic iterative methods: definition A = M − K and recurrence (\*), with the two conditions for a useful splitting]{ref}
The same identity also yields a correction based on the <linear-system residual>:
$$
x^{(k+1)}=x^{(k)}+M^{-1}(b-Ax^{(k)}),\qquad H=I-M^{-1}A.
$$
This connects a <matrix splitting> to <matrix preconditioning>: $M^{-1}$ rescales the imbalance before adding a correction. Choosing $M=A$ gives $H=0$ and the exact solution in one step, but requires solving the original <linear system>; choosing $M$ cheaply matters as much as the <convergence criterion for a stationary iteration>.
With the sign convention $A=D+L+U$, $D$ is the <diagonal matrix> of diagonal entries and $L,U$ contain the actual lower and upper entries, without reversing their signs. The <Jacobi method> uses $M=D$, $N=-(L+U)$; the <Gauss-Seidel method> uses $M=D+L$, $N=-U$. The first requires only division by diagonal entries; the second uses a <lower triangular matrix> and <forward substitution>. These choices explain their different information flows.