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$.

This is an iterative method whose update matrix remains fixed.

Suppose $x_{n+1}=G{x}_n+c$ has a fixed point $x_{\ast }$ and $G=SD{S}^{-1}$ with diagonal $D$. For $e_n=x_n-x_{\ast }$ and $f_n=S^{-1}{e}_n$, subtraction gives $f_n=D^n{f}_0$. In the Euclidean norm,Thus $\Vert e_n{\Vert }_2\le \Vert S{\Vert }_2\Vert S^{-1}{\Vert }_2\rho (G{)}^n\Vert e_0{\Vert }_2$. Spectral radius below one implies convergence for every start. The unit-constant bound belongs to the transformed coordinates; it does not automatically hold in the original Euclidean norm when $S$ is nonorthogonal.

The periodic second-difference circulant matrix has constant null space, so solvability requires $\sum b_j=0$. Its Jacobi method has eigenvalues $\cos (2\pi j/n)$: for odd $n$ it converges to some solution, while for even $n$ an alternating mode oscillates unless absent from the error. Lexicographic Gauss-Seidel iteration converges to some solution for every compatible right-hand side and every initial vector. For $K=-A=D+L+U$, a coordinate sweep decreases the energy $e^{T}Ke/2$ by the sum of squared coordinate changes. This excludes all nonconstant unit-modulus eigenmodes. The constant unit eigenvalue is simple, since the invariant left vector $w=(0,1,\dots ,1,2{)}^T$ has $w^{T}1=n\ne 0$. Neither method is a strict contraction to a unique solution without fixing the constant nullspace.

For a real symmetric positive definite matrix $A$, the error in each eigenvector direction is multiplied by $1-\tau \lambda$. Convergence from every initial vector is therefore equivalent to $0<\tau <2/{\lambda }_{\max }$. At either endpoint there is a nondecaying error direction. The optimal constant parameter is $2/({\lambda }_{\min }+{\lambda }_{\max })$, giving contraction factor $({\lambda }_{\max }-{\lambda }_{\min })/({\lambda }_{\max }+{\lambda }_{\min })$.

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 a symmetric positive-definite matrix.

To solve a linear system $Ax=b$, split its matrix into the diagonal matrix $D$ and the strictly lower and upper parts $L,U$, retaining their actual signs. Every diagonal entry must be nonzero. A sweep updates coordinates in order:The Jacobi method uses the old vector throughout; the Gauss-Seidel method reuses each fresh coordinate. Thus the update order is part of the method.^[ref]

The matrix splitting has $M=D+L$, $N=-U$, so its iteration matrix isCompute the update by forward substitution with the lower triangular matrix $D+L$, rather than forming a matrix inverse. For a sparse matrix, a sweep only visits stored entries and can overwrite the working vector. Dependencies on fresh coordinates constrain parallel execution. This makes the Gauss-Seidel method an inexpensive solver component, including in a multigrid method.^[ref]

For a real symmetric positive-definite matrix $A=D+L+L^T$, let $e_k$ be the Gauss-Seidel method error and $d_k=e_k-e_{k+1}$. Its recurrence gives $A{e}_k=(D+L)d_k$. Expanding the two squared energy norms yields $2d_k^{T}A{e}_k-d_k^{T}A{d}_k=d_k^{T}D{d}_k$. Every diagonal entry of $D$ is positive, so the error energy strictly decreases unless $d_k=0$. In that case $A{e}_k=0$ and the exact solution has already been reached. This identity exhibits the method as a sequence of energy-reducing coordinate corrections.

Consider the original linear systemDirect substitution verifies the solution. The matrix is a symmetric positive-definite matrix: completing the square in its quadratic form gives $4x^2+2xy+3y^2=4(x+y/4{)}^2+11y^2/4>0$ for every nonzero vector. It is also a strictly diagonally dominant matrix.

Starting from $(x^{(0)},y^{(0)})=(0,0)$, update the first row and then the second:The first sweep gives $x^{(1)}=1/4$ and $y^{(1)}=(2-1/4)/3=7/12$. The next gives $x^{(2)}=(1-7/12)/4=5/48$ and $y^{(2)}=(2-5/48)/3=91/144$. The second row uses $1/4$ during the first sweep, even though the initial first coordinate was zero.

With a stale first coordinate, the Jacobi method would instead give $(1/4,2/3)$ after the first sweep. Both methods have the same fixed point, but changing when coordinates become available changes the entire sequence of vectors.

For the Gauss-Seidel iteration for a two-variable positive-definite system, define the forward error by $e_x^{(k)}=x^{(k)}-x_{\ast }$ and $e_y^{(k)}=y^{(k)}-y_{\ast }$. Subtract the two exact solution equations from the two update equations:The fresh first coordinate passes the old second-coordinate error through two successive factors. The iteration matrix is thereforeIts eigenvalues are $0$ and $1/12$, as seen from the determinant. The zero eigenvalue explains why the old first-coordinate error disappears completely: the first row overwrites it. After one sweep, every remaining forward error lies on the eigenvector line spanned by $(-3,1{)}^T$.

For this zero start, $e_y^{(0)}=-7/11$, so the exact vectors for $k\ge 1$ areThe Euclidean norm of the forward error decreases by exactly $1/12$ per sweep from $k=1$ onward. The first decrease is different because the initial error has not yet reached that eigenvector line. Each row update moves horizontally or vertically in the coordinate plane; sweep endpoints then approach the solution along one straight line.

The linear-system residual is an independent way to check the calculation. Completing a sweep satisfies the second row exactly, but changing $y$ disturbs the first row:Thus a zero residual in the last updated row alone does not certify a solution; inspect the complete linear-system residual.

For the same matrix, the stale schedule of the Jacobi method gives the iteration matrixHere its eigenvalues are $\pm 1/\sqrt{12}$, whereas the fresh schedule gives $\rho (H)=\rho (B{)}^2$. This comparison belongs to this particular linear system; it is not a universal relation between the two methods' spectral radii.

A strictly diagonally dominant matrix or a real symmetric positive-definite matrix guarantees convergence of the Gauss-Seidel method from every initial vector. These are sufficient conditions.^[ref]

For strict diagonal dominance, putInduct through a sweep. Old coordinates have absolute error at most $E$; previously updated coordinates have absolute error at most $qE\le E$. The component update and the triangle inequality therefore bound the new error by $qE$. This proves $\Vert e^{(k+1)}{\Vert }_{\infty }\le q\Vert e^{(k)}{\Vert }_{\infty }$, a maximum norm contraction.

For a symmetric positive-definite matrix, write $A=D+L+L^T$. The Householder-John theorem applies to $M=D+L$ and $N=-L^T$, because $M^T+N=D$ is a positive-definite matrix. Hence the iteration matrix has spectral radius less than one, which gives the convergence criterion for a stationary iteration.

There is also a geometric reason fresh updates help: the Gauss-Seidel method is exact coordinate descent on the convex quadratic functionHolding the other coordinates fixed, minimizing in coordinate $i$ gives the corresponding row update. A change ${\delta }_i$ lowers $F$ by exactly $a_{ii}{\delta }_i^2/2$. Each fresh coordinate is therefore the minimizer for the current vector, and a complete sweep lowers the quadratic form error unless every coordinate already solves its row. This explains the method's beauty without implying monotone decrease in every vector norm.

An invertible matrix and nonzero diagonal entries make the update well defined, but do not guarantee convergence. For the original linear systemthe Gauss-Seidel method updates $x^{(k+1)}=1-2y^{(k)}$ and $y^{(k+1)}=1-2x^{(k+1)}=-1+4y^{(k)}$. Starting at zero gives $(1,-1)$, then $(3,-5)$. The second-coordinate forward error is $e_y^{(k)}=-4^k/3$, and the iteration matrix $H=\left(\begin{array}{cc}0& -2\\ 0& 4\end{array}\right)$ has spectral radius $4$. The linear system has a unique solution while this particular stationary iterative method for a linear system diverges.

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$.

Let $A=D+L+L^T$ be a real symmetric positive-definite matrix, with $D$ diagonal and $L$ strictly lower triangular. Put $B=D/\omega +L$ and $C_{\omega }=I-B^{-1}A$ for $\omega \ne 0$. The matrix norm induced by an energy norm reduces the question to $T=A^{1/2}{C}_{\omega }{A}^{-1/2}$. Direct multiplication and $B+B^T-A=(2/\omega -1)D$ giveThe left side is positive semidefinite. The matrix following the scalar coefficient on the right is positive-definite, since $D$ has positive diagonal and $B^{-1}{A}^{1/2}$ is an invertible matrix. For $0<\omega <2$, every eigenvalue of $T^{T}T$ therefore lies in $[0,1)$. Hence its spectral radius is below one and $\Vert C_{\omega }{\Vert }_A=\Vert T{\Vert }_2<1$. Iteration errors consequently decay geometrically in the energy norm. The argument proves convergence from every initial vector, without requiring the original iteration matrix to be symmetric.

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$.

For a matrix splitting $A=M-N$, the iteration matrix is $H=M^{-1}N=I-M^{-1}A$, where $I$ is the identity matrix. If $A{x}_{\ast }=b$, subtracting its fixed point equation from the update givesThus $b$ determines the fixed point, while $H$ determines how the forward error moves. An eigenvector $v$ with eigenvalue $\lambda$ is an error direction whose coefficient is multiplied by $\lambda$ on every step. A negative real eigenvalue reverses its sign; a zero eigenvalue removes that component in one step.

A stationary iterative method for a linear system converges to its specified fixed point for every initial vector if and only if its iteration matrix satisfies $\rho (H)<1$, where the spectral radius is the largest modulus of an eigenvalue.^[ref]

For a diagonalizable matrix, write $H=V\Lambda V^{-1}$. Then $H^k=V{\Lambda }^k{V}^{-1}$, so each eigenvector coefficient tends to zero exactly when its eigenvalue has modulus less than one. For a general matrix, the Jordan normal form gives the same result: a Jordan block $J=\lambda I+K$ with a nilpotent matrix $K$ of size $m$ satisfiesIf $0<|\lambda |<1$, every coefficient tends to zero because exponential decay beats any fixed polynomial in $k$; if $\lambda =0$, the block vanishes once $k\ge m$. Conversely, an eigenvector with $|\lambda |\ge 1$ provides an initial error that cannot tend to zero. For a real matrix with complex eigenvalues, the same obstruction appears in the real invariant subspace spanned by the real and imaginary parts of an eigenvector.

The words "every initial vector" matter. For example, $H=\mathrm{diag}(3/2,1/2)$ fails the criterion, but $e^{(0)}=(0,1{)}^T$ still tends to zero. Here a generic initial error has a nonzero first coordinate and diverges; the exceptional errors lie on the second coordinate axis. With $H=\mathrm{diag}(-1,1/2)$, generic errors oscillate rather than diverge in norm, while the same exceptional axis still converges. Both are valid matrix splittings with $M=I$ and $A=I-H$. In general the convergent errors form the direct sum of the generalized eigenspaces for $|\lambda |<1$; if $\rho (H)\ge 1$, this is a proper linear subspace.

A small spectral radius describes eventual convergence, but does not imply that the Euclidean norm of the error decreases on every step for a non-normal matrix. An operator norm bound $\Vert H\Vert <1$ does give the stepwise estimate $\Vert e^{(k)}\Vert \le \Vert H{\Vert }^k\Vert e^{(0)}\Vert$. For a real symmetric matrix, the matrix 2-norm equals its spectral radius, making this particularly direct.

The linear-system residual $r^{(k)}=b-A{x}^{(k)}$ is computable without knowing $x_{\ast }$. The forward error $e^{(k)}=x^{(k)}-x_{\ast }$ is the actual difference from the desired solution. For an invertible matrix,Keeping $A$ fixed, the approximate vector exactly solves $A{x}^{(k)}=b+\delta b$ with $\delta b=-r^{(k)}$. Thus, for $b\ne 0$, $\Vert r^{(k)}\Vert /\Vert b\Vert$ is the relative backward error when only the right-hand side may change. For a vector norm and its induced operator norm,A small relative linear-system residual ensures a small relative forward error when the condition number is moderate; an ill-conditioned matrix can amplify it. The bound follows directly from $e=-A^{-1}r$ and $\Vert b\Vert =\Vert A{x}_{\ast }\Vert \le \Vert A\Vert \Vert x_{\ast }\Vert$.^[ref]

For the Jacobi iteration for a three-variable tridiagonal system, the first linear-system residual is $(1,3,1{)}^T$, while the first forward error is $(-1/2,-1,-1/2{)}^T$. In the Euclidean norm, the relative forward error is $\sqrt{3/28}\approx 0.3273$ and the relative linear-system residual is $\sqrt{11/120}\approx 0.3028$. Its spectral condition number of a positive-definite matrix is $(4+\sqrt{2})/(4-\sqrt{2})\approx 2.094$, so the bound is about $0.6340$. The bound is a guarantee, not an equality. In floating-point arithmetic, recompute the linear-system residual from the current vector when checking termination; a small update alone need not certify a small forward error.

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.

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

The Jacobi method solves a linear system by updating every coordinate from the same old vector. It requires every diagonal entry $a_{ii}$ to be nonzero. Isolating coordinate $i$ in row $i$ gives the simultaneous ruleHere $B$ is the iteration matrix. A sweep computes a complete new vector before replacing the old one, so its coordinate updates can run independently.^[ref]

For a sparse matrix, a sweep needs work proportional to the stored nonzero entries, while Gaussian elimination may create fill-in. The Jacobi method is therefore a simple starting point for large linear systems, and the weighted Jacobi method supplies a useful building block of a multigrid method. Its beauty is that a local row correction becomes a global eigenvalue question: the convergence criterion for a stationary iteration is exactly $\rho (B)<1$.

Consider the original linear system with a symmetric matrix that is also a tridiagonal matrix:Here $D=4I$ and the Jacobi method readsStarting from $x^{(0)}=0$, the first three vectors areEvery right-hand side uses superscript $k$, including the middle row, even when a new first coordinate has already been computed.

For comparison, a first Gauss-Seidel method sweep in coordinate order $1,2,3$ givesThe new first coordinate enters the middle update, and the new second coordinate enters the final update. Accidentally overwriting old coordinates during a Jacobi method sweep therefore changes the mathematical method.

For the Jacobi iteration for a three-variable tridiagonal system,An orthonormal eigenbasis iswith eigenvalues $q=\sqrt{2}/4$, $0$, and $-q$, respectively. These are error modes: their shapes persist under the iteration matrix, while their coefficients change. Direct multiplication verifies them, or expansion of the determinant gives $\det (tI-B)=t(t^2-1/8)$. Thus $\rho (B)=q<1$ and convergence holds for every starting vector.

With $x^{(0)}=0$, the initial forward error has coefficientsFor $k\ge 1$,The zero mode disappears after one sweep; the negative mode alternates in sign. The Euclidean norm drops by exactly $q$ per sweep from $k=1$ onward. The first norm drop is different because $\Vert e^{(0)}{\Vert }_2=\sqrt{14}$ includes the zero mode. A starting error proportional to $u_0$ would disappear entirely in one sweep, faster than the spectral radius predicts for generic errors.

The curves are computed iterates and exact formulas for this linear system. Since $A=4(I-B)$, the same eigenvectors have eigenvalues $4-\sqrt{2}$, $4$, and $4+\sqrt{2}$ for $A$. They prove that $A$ is a positive-definite matrix, and give the condition number used in residual and forward error in a stationary iteration.

A strictly diagonally dominant matrix guarantees convergence of the Jacobi method for every initial vector.^[ref]

Indeed, using the maximum norm $\Vert v{\Vert }_{\infty }={\max }_i|v_i|$, the induced operator norm is the largest absolute row sum. The Jacobi method has $b_{ii}=0$ and $b_{ij}=-a_{ij}/a_{ii}$ for $j\ne i$, soThis gives a cheap sufficient check without computing any eigenvalues. For the Jacobi iteration for a three-variable tridiagonal system, the absolute row sums of $B$ are $1/4,1/2,1/4$, giving $\Vert B{\Vert }_{\infty }=1/2$. The true spectral radius $\sqrt{2}/4$ gives a sharper eventual rate.

Strict diagonal dominance is sufficient, not necessary: $A=\left(\begin{array}{cc}1& 2\\ 1/10& 1\end{array}\right)$ violates it in the first row, but its Jacobi method has eigenvalues $\pm 1/\sqrt{5}$ and converges. Conversely, being a positive-definite matrix alone is insufficient: the Jacobi convergence for a three-by-three equicorrelation matrix with $\alpha =3/4$ has positive eigenvalues $5/2,1/4,1/4$ for $A$, but spectral radius $3/2$ for its iteration matrix. The extra tridiagonal matrix structure in Jacobi convergence for a symmetric positive-definite tridiagonal matrix is therefore substantive.

For $A={\mu }^{-1}I+U-U^T$, with $U$ the four-dimensional unit superdiagonal, the Jacobi method has eigenvalues $2i\mu \cos (j\pi /5)$, $j=1,\dots ,4$. The Gauss-Seidel method has two zero eigenvalues and $-{\mu }^2(3\pm \sqrt{5})/2$. Therefore both methods converge for every starting vector exactly when $0<|\mu |<(\sqrt{5}-1)/2$. This equality of convergence ranges follows from their spectra, not from positive-definiteness of the nonsymmetric coefficient matrix.

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

Equivalently, the weighted Jacobi method takes a weighted average of the old vector and its full Jacobi method update: $x^{(k+1)}=(1-\omega )x^{(k)}+\omega x_{\mathrm{Jacobi}}^{(k+1)}$. If $Bv=\lambda v$, its iteration matrix multiplies that eigenvector by $1-\omega +\omega \lambda$. For the diagonal-4 Jacobi iteration for a three-variable tridiagonal system, the factors are $1-\omega$ and $1-\omega \pm \omega \sqrt{2}/4$; a Poisson equation smoothing parameter must not be inferred from this different matrix.

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 five-point Dirichlet Poisson matrix, weighted Jacobi iteration has sine-mode multiplier $1-\omega +(\omega /2)(\cos {\theta }_r+\cos {\theta }_s)$. Call a mode high-frequency if at least one cosine is nonpositive. Then the sum lies in $[-2,1]$, so for $\omega =4/5$ the multiplier lies in $[-3/5,3/5]$. This uniform damping makes the iteration a useful smoother for a multigrid method, even though low-frequency multipliers approach one on fine grids. Balancing $|1-2\omega |$ and $|1-\omega /2|$ shows why $4/5$ is the minimax parameter for this high-frequency interval. The two-dimensional high-frequency set gives a different optimum from the familiar one-dimensional value $2/3$.

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$.

Multiplying both $A$ and $b$ by $-1$ leaves $D^{-1}A$ and the weighted Jacobi method unchanged. Thus the same formula applies to the positive second-difference matrix $T_n$ with diagonal $2$ and neighboring entries $-1$, the finite difference form of the one-dimensional Poisson equation with Dirichlet boundary conditions. Its eigenvectors have components $\sin (jk\pi /(n+1))$, and $D^{-1}{T}_n$ has eigenvalues $1-\cos (k\pi /(n+1))$. At $\omega =2/3$, upper-half modes have factors between $-1/3$ and $1/3$, while low-frequency factors remain close to one on fine grids. This explains why the weighted Jacobi method helps a multigrid method by reducing oscillatory errors, even when it is a slow solver on its own.^[ref]

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 the one-dimensional Dirichlet second-difference grid, high sine modes have eigenvalues $1-\omega t_k$, with $t_k=1-\cos (k\pi /(n+1))$ and $k\ge \lceil (n+1)/2\rceil$. Let $a$ and $b$ be the smallest and largest of these $t_k$. Convexity gives attenuation $\max (|1-\omega a|,|1-\omega b|)$. Balancing its endpoint values with opposite signs gives the displayed exact minimax choice. For odd $n$, $a=1$; for even $n$, $a=1+\sin (\pi /[2(n+1)])$, and always $b=1+\cos (\pi /(n+1))$. Only in the large-grid or uniform-in-grid limit do these become ${\omega }_{\ast }=2/3$, ${\mu }_{\ast }=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.