the Gauss-Seidel method

Gauss-Seidel is Jacobi with one small, clever change: use new information the moment you have it. As you sweep through the equations updating x_1, then x_2, then x_3, ... by the time you reach x_3 you have already computed fresh values for x_1 and x_2 in this very sweep. Jacobi stubbornly ignores them and uses the old ones; Gauss-Seidel uses the new ones immediately. It is like a row of people passing a message and correcting it as they go, instead of everyone independently guessing from yesterday's version.

The update is x_i^{new} = (b_i - sum over j < i of a_ij x_j^{new} - sum over j > i of a_ij x_j^{old}) / a_ii. Notice the first sum uses already-updated x_j^{new} (for components done earlier this sweep) and the second uses the old values (not yet reached). As a splitting it is M = D - L (the whole lower-triangular part), N = U, so the next iterate solves a triangular system by forward substitution. For symmetric positive-definite matrices and for strictly diagonally dominant matrices, Gauss-Seidel is guaranteed to converge, and it typically converges about twice as fast as Jacobi — using fresh values roughly halves the spectral radius of the iteration matrix on model problems.

The price for that speed is that the updates are now sequential: computing x_i needs x_{i-1}, so you cannot trivially do them all at once, which makes naive Gauss-Seidel harder to parallelize than Jacobi (clever colourings, like red-black ordering, restore parallelism). Like Jacobi, it remains too slow to drive a large solve to full accuracy alone, but it is an excellent smoother inside multigrid and a fine preconditioner. It also has a symmetric variant (one forward sweep then one backward sweep) that pairs well with conjugate gradient on symmetric problems.