Stationary iterative method for a linear system

A stationary iteration has the formwith a fixed iteration matrix $H$. It converges for every initial vector exactly when the spectral radius satisfies $\rho (H)<1$.

With $A=D+L+U$, the Gauss-Seidel method solves $(D+L)x^{(k+1)}=b-U{x}^{(k)}$. It uses each newly computed coordinate immediately in the remaining triangular solve. It is successive over-relaxation with parameter one, and converges from every start when $A$ is symmetric positive definite.

For a splitting $A=D+L+U$, successive over-relaxation updatesIt reduces to the Gauss-Seidel method at $\omega =1$. If $A$ is symmetric positive definite, the Householder-John theorem applies to $M=D/\omega +L$, $N=(1/\omega -1)D-U$, since $M^T+N=(2/\omega -1)D$ is positive definite for $0<\omega <2$.

For a stationary iteration $x^{(k+1)}=H{x}^{(k)}+v$, the matrix $H$ propagates the error by $e^{(k+1)}=H{e}^{(k)}$. Convergence from every initial error is equivalent to $\rho (H)<1$.

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

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.

Writing $A=D+L+U$, where $D$ is diagonal and $L,U$ are strictly triangular, the Jacobi iteration is

With relaxation parameter $\omega$, weighted Jacobi updates byIts iteration matrix is $H_{\omega }=I-\omega D^{-1}A$.

For the five-point discretization of $-\Delta +c$ on the unit square, the weighted iteration eigenvalues are $1-\omega [4{\sin }^2(\pi kh/2)+4{\sin }^2(\pi lh/2)+c{h}^2]/(4+c{h}^2)$. A fixed parameter converges for every mesh when $0<\omega \le 1$, but $\omega =1$ poorly damps the highest frequencies.

For the centered second-difference matrix with diagonal $-2$ and off-diagonals $1$, the weighted-Jacobi eigenvalues areThe method converges for every grid size exactly when $0<\omega \le 1$.

For modes with $k/(n+1)\in [1/2,1]$ and large $n$, the worst attenuation factor isIt is minimized by $\omega =2/3$, for which ${\mu }_{\omega }=1/3$.

For a three-by-three matrix with diagonal entries one and every off-diagonal entry $\alpha$, the Jacobi method iteration matrix has eigenvalue $-2\alpha$ on the all-ones vector and eigenvalue $\alpha$ with multiplicity two on its orthogonal complement. Its spectral radius is $2|\alpha |$, so Jacobi iteration converges exactly when $|\alpha |<1/2$.

If $A=D+L+L^T$ is symmetric positive definite and tridiagonal, set $S=\mathrm{diag}(1,-1,1,-1,\dots )$. Thenis positive definite. Applying the Householder-John theorem to $M=D$ and $N=-(L+L^T)$ proves that the Jacobi iteration converges.