Gauss–Seidel Method¶
A stationary linear-system iteration that sweeps coordinates in order and immediately reuses each newly computed component within the same sweep.
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
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
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
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.
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.
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
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.
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
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.
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 (87th 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