Solve a diagonally-dominant linear system iteratively using the Gauss-Seidel method.
Gauss-Seidel walks through the equations one at a time and immediately reuses each value it has just computed within the same pass. That single change from Jacobi propagates corrections through the system far faster, typically halving the number of passes needed. The relaxation factor generalises the method: at 1.0 you get plain Gauss-Seidel, while values above 1.0 give successive over-relaxation, deliberately overshooting each update to accelerate convergence, and values below 1.0 under-relax to stabilise awkward systems. Optimal omega for a well-behaved system often lands between 1.2 and 1.8, but too large a value oscillates and diverges. The reported residual is the true measure of quality: how far the coefficient matrix times the solution still sits from the right-hand side.
Gauss-Seidel update
x_i(target) = (d_i - sum of a_ij x_j using the newest available values) / a_ii
Relaxation
x_i(new) = x_i(old) + omega x (x_i(target) - x_i(old))
Residual
residual = max over rows of |(M x)_i - d_i|
It scales how far each variable moves toward its freshly computed target. At omega = 1 the variable jumps exactly there, which is classic Gauss-Seidel. Above 1 it overshoots deliberately, which often reaches the solution in noticeably fewer passes. Below 1 it moves cautiously, which can rescue a system that otherwise oscillates.
The pass count only tells you the updates got small. A residual measures the thing you actually care about: how far the coefficient matrix times your solution still is from the right-hand side. Small updates with a large residual is the signature of a nearly singular system creeping along rather than converging.
Yes. Convergence for over-relaxation requires omega below 2, and in practice values much above the optimum cause the iteration to oscillate with growing amplitude. If the solution starts swinging, pull omega back toward 1.