Gauss–Seidel Method¶

A stationary linear-system iteration that sweeps coordinates in order and immediately reuses each newly computed component within the same sweep.

Version: v2 · 2026-09-06 · History
Domain-specific #: 1915
Origin domain: numerical linear algebra
Subdomain: stationary iterative methods
Aliases: Liebmann Method, Method of Successive Displacement

Core Idea¶

The Gauss–Seidel method is a stationary iterative solver for a square linear system \(Ax=b\). It visits the component equations in a declared order, solves each equation for its diagonal variable, and immediately uses every newly computed component in the remaining equations of that same sweep.

Write

\[ A=D+L+U, \]

where \(D\) is diagonal and \(L,U\) are the strict lower and upper parts of \(A\). Assuming the diagonal entries are nonzero, the natural-order iteration is

\[ (D+L)x^{(k+1)}=b-Ux^{(k)}, \]

or

\[ x^{(k+1)}=-(D+L)^{-1}Ux^{(k)}+(D+L)^{-1}b. \]

The inverse is notation for a lower-triangular solve, not a matrix that should be formed. Componentwise,

\[ x_i^{(k+1)} =\frac{1}{a_{ii}} \left( b_i-\sum_{j<i}a_{ij}x_j^{(k+1)} -\sum_{j>i}a_{ij}x_j^{(k)} \right). \]

The mixed superscripts are the identity: current-sweep values are used below the diagonal, previous-sweep values above it. Standard iterative-method references distinguish this successive-displacement schedule from Jacobi's simultaneous old-iterate barrier.^[1]

Structural Signature¶

The square linear system: \(Ax=b\), with the solution sought as a fixed point.
The usable diagonal: every \(a_{ii}\ne0\) in the selected ordering, unless blocks replace scalar pivots.
The ordered split: \(D+L\) contains the diagonal and dependencies already visited; \(U\) contains dependencies not yet visited.
The previous iterate: supplies upper-part values at the start of a sweep.
The in-place sweep: overwrites each \(x_i\) after solving its row equation.
The newest-value rule: later rows consume values computed earlier in the same sweep.
The iteration matrix: \(B_{\mathrm{GS}}=-(D+L)^{-1}U\) governs error propagation.
The convergence/stopping contract: spectral behavior, residual, step change, tolerance, and iteration limit are separately tracked.

Recognition test. Inspect one sweep. If component \(i+1\) uses the newly calculated component \(i\), and the update is derived from the corresponding lower-triangular matrix split of \(Ax=b\), the method is Gauss–Seidel. If all components read only \(x^{(k)}\), it is Jacobi.

What It Is Not¶

It is not direct Gaussian elimination. Elimination factors a matrix and reaches a solution after a finite sequence in exact arithmetic. Gauss–Seidel repeatedly applies one triangular splitting and may converge slowly or diverge.

It is not the Jacobi method. Jacobi computes every component of \(x^{(k+1)}\) from the unchanged vector \(x^{(k)}\); Gauss–Seidel breaks that synchronization barrier. The methods have different iteration matrices and different parallelism and convergence behavior.

It is not Successive Over-Relaxation unless a relaxation parameter is applied. It is not coordinate descent on an arbitrary objective, although for symmetric positive-definite systems its updates can be interpreted as exact coordinate minimizations of a quadratic. It is not guaranteed to converge merely because \(A\) is nonsingular and has nonzero diagonal.

Scope of Application¶

Gauss–Seidel appears in dense and sparse linear-system solving, finite-difference and finite-element discretizations, elliptic partial differential equations, network equations, and relaxation schemes. It is often more important as a smoother or preconditioning component inside multigrid and Krylov methods than as a standalone high-accuracy solver.

The method is defined for any ordering with usable diagonal pivots, but its convergence is matrix- and ordering-dependent. In exact finite dimensions, convergence from every starting vector occurs exactly when

\[ \rho(B_{\mathrm{GS}})<1. \]

Strict diagonal dominance and Hermitian positive definiteness are familiar sufficient conditions for standard forms, not membership criteria and not necessary conditions.^[2] Reordering can change \(D+L\), \(U\), the iteration matrix, and practical convergence.

Block Gauss–Seidel replaces scalar pivots with diagonal blocks and performs block triangular solves. Multicolor and parallel variants partition independent updates, but their schedule and convergence analysis must be stated; canonical point Gauss–Seidel is inherently sequential within one sweep.

Clarity¶

Splitting conventions vary. Some texts write \(A=D-L-U\) with \(L,U\) defined as negatives of the off-diagonal parts. This dossier uses \(A=D+L+U\), so the iteration matrix contains the explicit minus sign. Formulas from different conventions must not be mixed.

Nonzero diagonal entries make component updates executable but do not prove convergence. A valid implementation can faithfully generate a divergent sequence. The residual \(r^{(k)}=b-Ax^{(k)}\) should be monitored rather than relying only on component changes.

Ordering is structural, not incidental. Forward, backward, red-black, symmetric, and block sweeps are related schedules with different operators. Calling all in-place coordinate updates “the same” hides their iteration matrices.

Manages Complexity¶

A direct factorization can require substantial memory and fill for a large sparse matrix. A Gauss–Seidel sweep uses the original sparse coefficients and one mutable vector, making each update local and inexpensive. The lower-triangular interpretation gives a simple reusable kernel.

The method converts one global solve into repeated local equation solves. Fresh values transmit information through a sweep faster than Jacobi's one-step delay, though this often trades away easy parallelism. In multigrid, that local propagation can damp certain high-frequency error components effectively.

What the method compresses is the solve, not the convergence proof. Spectral radius, ordering, conditioning, and stopping accuracy remain explicit obligations.

Abstract Reasoning¶

Let \(x^\ast\) solve \(Ax^\ast=b\), and define \(e^{(k)}=x^{(k)}-x^\ast\). Subtracting the exact split equation from the iteration gives

\[ (D+L)e^{(k+1)}=-Ue^{(k)}, \qquad e^{(k+1)}=B_{\mathrm{GS}}e^{(k)}. \]

Therefore \(e^{(k)}=B_{\mathrm{GS}}^ke^{(0)}\). The matrix powers tend to zero for every initial error exactly when the spectral radius is less than one.

The residual-correction form is

\[ (D+L)\Delta^{(k)}=r^{(k)},\qquad x^{(k+1)}=x^{(k)}+\Delta^{(k)}. \]

This shows Gauss–Seidel as a stationary iteration preconditioned by the lower triangular part. It also explains why the method can serve inside a larger solver without becoming identical to that solver.^[3]

Knowledge Transfer¶

The exact sweep transfers from small hand computations to sparse PDE matrices, block systems, and distributed smoothers. Data structures differ, but the ordered triangular dependency and newest-value reuse must remain.

For symmetric positive-definite \(A\), the system is the stationary condition for

\[ \phi(x)=\frac12x^{\mathsf T}Ax-b^{\mathsf T}x. \]

A coordinate Gauss–Seidel update minimizes this quadratic in one coordinate while holding the others at their newest available values. This supplies a legitimate bridge to coordinate descent, restricted to the quadratic linear-system setting.

Outside numerical computation, “use the newest information immediately” is analogy. The portable parent is Iteration; Gauss–Seidel retains matrices, row equations, an ordered split, residuals, and spectral convergence.

Examples¶

Two-by-two sweep. For

\[ \begin{bmatrix}4&1\\2&3\end{bmatrix} \begin{bmatrix}x_1\\x_2\end{bmatrix} = \begin{bmatrix}1\\2\end{bmatrix} \]

and \(x^{(0)}=(0,0)\), the first sweep gives \(x_1^{(1)}=1/4\), then immediately uses it to give \(x_2^{(1)}=(2-2/4)/3=1/2\). A second sweep gives \((1/8,7/12)\), moving toward the exact solution \((1/10,3/5)\).

Jacobi boundary. The same first sweep under Jacobi would give \(x_2^{(1)}=2/3\), because it must use the old \(x_1^{(0)}=0\). This single read-order difference changes the method.

PDE relaxation. A five-point finite-difference Laplacian updates one grid value from its neighbors. Natural-order Gauss–Seidel uses already updated left/up neighbors and old right/down neighbors; red-black ordering changes the schedule for parallelism.

Divergence warning. If \(\rho(B_{\mathrm{GS}})\ge1\), a small first residual reduction does not establish convergence. The spectral or empirical long-run behavior must be checked.

Structural Tensions¶

Fresh information versus parallelism: immediate reuse accelerates propagation but introduces dependencies. Diagnostic: draw the within-sweep read-after-write graph.
Cheap sweep versus uncertain convergence: each pass is inexpensive but may diverge. Diagnostic: check \(\rho(B_{\mathrm{GS}})\) or a valid sufficient condition.
Natural order versus reordered system: permutations can improve locality or convergence but change the operator. Diagnostic: record the row/variable ordering with results.
Component stability versus residual accuracy: small updates can occur in a badly scaled system. Diagnostic: monitor a normalized residual and conditioning context.
Standalone solver versus smoothing component: a few sweeps may be valuable without solving fully. Diagnostic: state whether the target is solution tolerance or error smoothing.
Base method versus relaxation variant: weighting changes the iteration. Diagnostic: report the relaxation parameter and distinguish \(\omega=1\) from SOR.

Structural–Framed Character¶

The method is strongly structural. Its lower/upper split, ordered coordinate schedule, fixed-point operator, and error recurrence survive changes of application domain and implementation.

Its linear-algebra framing is indispensable. Generic immediate feedback does not supply a matrix split, triangular solve, residual, or spectral convergence criterion. Gauss–Seidel is therefore domain-specific.

Structural Core vs. Domain Accent¶

The portable core is iteration whose current round immediately consumes partial results of that round. The domain accent fixes a linear system and makes the dependency order equal to a lower-triangular matrix split.

Iteration supplies the broad repeated-state mechanism. Algorithm supplies procedural framing. Jacobi is the closest sibling, but its old-iterate barrier is the exact opposite scheduling choice. None covers the Gauss–Seidel residual.

prime:iteration is the proposed minimal parent by strict specialization. One Gauss–Seidel sweep maps the current approximation to a new one, and repeated sweeps propagate state toward a fixed point when convergence conditions hold.

prime:algorithm is broader but its strongest finite-termination reading is less exact for a stationary iteration that can diverge. domain_specific:jacobi_method is a sibling under Iteration, not a parent. Dynamic Programming and Linear Programming are semantic false neighbors.

Relationships to Other Abstractions¶

Current abstraction Gauss–Seidel Method Domain-specific

Parents (1) — more general patterns this builds on

Gauss–Seidel Method is a kind of Iteration Prime

prime:iteration is the proposed minimal parent by strict specialization.

Hierarchy path (1) — routes to 1 parentless root

Gauss–Seidel Method → Iteration

Neighborhood in Abstraction Space¶

Gauss–Seidel Method sits in a sparse region of the domain-specific corpus (87^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Jacobi Method — 0.86
Matrix — 0.80
Matrix exponential — 0.80
Hadamard matrix — 0.79
Frontal Solver — 0.78

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Jacobi method: synchronously reads only the preceding iterate.
Successive over-relaxation: weights the raw Gauss–Seidel component update by \(\omega\).
Symmetric Gauss–Seidel: combines forward and backward sweeps.
Block Gauss–Seidel: updates variable blocks through block triangular solves.
Gaussian elimination: a direct finite factorization method.
Coordinate descent: a broader optimization family, coincident under a quadratic SPD interpretation.
Gauss–Newton algorithm: a nonlinear least-squares method.
Gauss–Jacobi quadrature: numerical integration with orthogonal-polynomial nodes.

References¶

[1] Richard Barrett et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2^nd ed., SIAM, 1994, https://www.netlib.org/templates/Templates.html. registry ↩

[2] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2^nd ed., SIAM, 2003, https://www-users.cse.umn.edu/~saad/IterMethBook_2ndEd.pdf. registry ↩

[3] Richard S. Varga, Matrix Iterative Analysis, 2^nd ed., Springer Series in Computational Mathematics 27, 2000, https://doi.org/10.1007/978-3-642-05156-2. registry ↩