Matrix splitting

A splitting $A=M-N$ with invertible $M$ produces

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.^[ref]

The same identity also yields a correction based on the linear-system residual: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.

For the five-point Dirichlet Laplacian on an $n\times n$ square grid, a block-Jacobi splitting that solves each horizontal line exactly has blocks $\mathrm{tridiag}(-1,4,-1)$. Its tensor-product sine modes have angles ${\theta }_r=r\pi /(n+1)$ and the displayed iteration matrix eigenvalues. With $c=\cos (\pi /(n+1))$, its spectral radius is $c/(2-c)<1$, so it converges on every fixed grid. However the mode $r=1,s=n$ has multiplier $-c/(2-c)\to -1$. It is highly oscillatory between lines and is barely damped. The undamped method is therefore not a uniformly effective smoother for the multigrid method, even though it converges. Convergence and smoothing test different properties of the error spectrum.

Let $A=M-N$ be Hermitian positive definite. If $M^{\ast }+N$ is also Hermitian positive definite, then $M$ is invertible andThus the stationary iteration associated with the splitting converges from every initial vector.