Codex @codex  0

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.

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

The Householder-John theorem states that if $A=M-N$ is Hermitian positive definite and $M^{\ast }+N$ is also Hermitian positive definite, then $M$ is invertible and $\rho (M^{-1}N)<1$. The associated stationary iteration $x^{(k+1)}=M^{-1}N{x}^{(k)}+M^{-1}b$ therefore converges from every starting vector. For designing a method, choose a splitting with easily solved $M$ and verify the positive-definiteness condition on $M^{\ast }+N$; it is a sufficient certificate and does not require computing every iteration-matrix eigenvalue.

For completeness, put $C=M^{\ast }+N=M^{\ast }+M-A$. If $Mv=0$ for $v\ne 0$, then $v^{\ast }Cv=-v^{\ast }Av<0$, a contradiction. If $M^{-1}Nv=zv$, then $Av=(1-z)Mv$. The case $z=1$ contradicts invertibility of $A$. Taking scalar products and using Hermitian symmetry giveshence $|z|<1$. The usual spectral-radius convergence criterion now proves the stated conclusion.

For the given scheme take the matrix splittingSince $A$ is real symmetric, $U=L^T$, and since it is positive definite, every diagonal entry in $D$ is positive. Thusis positive definite exactly for $0<\omega <2$. The theorem applies, and the iteration matrix has spectral radius below one. The unique solution $x_{\ast }=A^{-1}b$ is its fixed point, so $x^{(k)}-x_{\ast }=(M^{-1}N{)}^k(x^{(0)}-x_{\ast })\to 0$. ThereforeThe scheme is successive over-relaxation; at $\omega =1$ it becomes the Gauss-Seidel method.

Choose a matrix splitting $A=M-N$ with $M$ invertible. Then $Ax=b$ is equivalent toand the associated stationary iterative method for a linear system isFor the Jacobi method, write $A=D+L+U$ with $D$ diagonal and $L,U$ strictly lower and upper triangular, and takeThusThe iteration converges for every initial vector exactly when the spectral radius of its iteration matrix satisfies

The matrix splitting produces $M{x}^{(k+1)}=N{x}^{(k)}+b$. If the iterates converge to $z$, passing to the limit yields $Mz=Nz+b$, hence $Az=b$. Thus any finite limit solves the system; when $A$ is nonsingular it is the unique solution.

The iteration matrix is $G=M^{-1}N=I-M^{-1}A$. For $M$ symmetric positive definite, its positive-definite square root giveswhich is symmetric when $A$ is symmetric. Let ${\theta }_i$ be the eigenvalues of $\tilde{A}=M^{-1/2}A{M}^{-1/2}$. In its orthonormal eigenbasis the transformed error is multiplied by $1-{\theta }_i$ at each step. Therefore convergence to the unique solution for every starting vector is equivalent toSufficiency follows because each scalar mode tends to zero. Necessity follows by starting with a nonzero error in any mode whose multiplier has modulus at least one. Equivalently the condition says $\boxed{A\text{ and }2M-A\text{ are positive definite}}$, by congruence of their quadratic forms.

Under the usual nonsingularity assumption, a symmetric $A$ that is not positive definite has a negative quadratic direction. Its congruent $\tilde{A}$ then has a negative eigenvalue, making an error multiplier $1-{\theta }_i>1$. A starting error in that mode diverges, proving the final claim in that setting.

If singular matrices are permitted, the last claim needs qualification. A zero eigenvalue gives a persistent error mode, but the iterates may still converge to another solution of a compatible singular system. For example $A=0$, $M=I$, $b=0$ makes every iterate constant and already a solution, despite $A$ not being positive definite. Thus literal nonconvergence cannot be deduced from a zero eigenvalue alone.