the Jacobi method

The Jacobi method is the most transparent way to solve A x = b iteratively. Take any single equation of the system — say the i-th equation, which involves x_i and several other unknowns. Pretend, for a moment, that you already know all the other unknowns, and simply solve that one equation for x_i. Do this for every row, always using the OLD values of the other unknowns from the previous sweep, and you have produced a complete new guess. Repeat. Each variable is updated as if it alone were unknown — a simultaneous relaxation of all the equations.

In a formula, the update for the i-th component is x_i^{new} = (b_i - sum over j not equal to i of a_ij x_j^{old}) / a_ii. You divide by the diagonal entry a_ii, which is why Jacobi needs nonzero diagonals and works best when the diagonal dominates each row. As a splitting it is A = D - (L + U) with M = D (the diagonal), so the iteration matrix is G = D^{-1}(L + U) and it converges exactly when the spectral radius of that matrix is below 1 — guaranteed, for instance, when A is strictly diagonally dominant (each diagonal entry outweighs the sum of the other entries in its row). A wonderful practical feature: because every new value uses only old values, all components can be updated independently and in any order, so Jacobi is trivially parallel.

Its weakness is speed. On a typical discretized PDE, Jacobi reduces the error by only a small constant factor each sweep, so it needs O(n) sweeps to reach accuracy — far too slow on its own for large problems. But it has a redeeming quality: it efficiently kills the high-frequency, jagged part of the error while barely touching the smooth, slowly-varying part. That selective smoothing is precisely what multigrid methods exploit, which is why (often in a damped, weighted form) Jacobi survives as a smoother and as the simplest of all preconditioners — the diagonal preconditioner.