successive over-relaxation
Successive over-relaxation is Gauss-Seidel with an accelerator pedal. Each Gauss-Seidel sweep moves every unknown a certain distance toward its corrected value. SOR observes that this correction usually points in a good direction but is too timid — so it deliberately overshoots, stepping a bit further than Gauss-Seidel would. A relaxation parameter omega controls how much: omega = 1 reproduces plain Gauss-Seidel, omega between 1 and 2 over-relaxes (overshoots, the useful case), and omega below 1 under-relaxes (a cautious, damped step, sometimes needed for stability).
Mechanically, compute the ordinary Gauss-Seidel update for x_i, call it x_i^{GS}, then take a weighted blend with the old value: x_i^{new} = (1 - omega) x_i^{old} + omega x_i^{GS}. With omega > 1 this pushes past the Gauss-Seidel point. The remarkable payoff: for nice model problems there is an optimal omega (close to 2 for large grids) that transforms the convergence rate from the slow Gauss-Seidel O(n) sweeps down to O(sqrt(n)) sweeps — an enormous speed-up. The classic example is the discretized Poisson equation, where the right omega turns a method that needs thousands of sweeps into one that needs tens.
The catch is that SOR's magic depends entirely on choosing omega well, and the optimal value depends on the spectral properties of the iteration matrix, which you usually do not know in advance. Pick omega too large or too small and you can lose all the gain, or even diverge (omega must stay in (0, 2) just to converge at all for SPD matrices). For this reason classical SOR has largely been superseded by preconditioned Krylov methods and multigrid, which are faster and need no hand-tuned parameter — but SOR remains a historically important idea and still appears as a tunable smoother.
On the standard 5-point Poisson problem on an N-by-N grid, Gauss-Seidel needs O(N^2) sweeps to converge, but SOR with the optimal omega ~ 2 - O(1/N) needs only O(N) sweeps — for N = 100 that is roughly tens of sweeps instead of thousands.
The right over-relaxation parameter omega turns Gauss-Seidel's O(n) sweeps into O(sqrt(n)).
SOR's huge speed-up is real but fragile: it lives or dies by the choice of omega, and the optimal value is rarely known in practice. Modern large-scale solving generally prefers preconditioned conjugate gradient, GMRES, or multigrid, which need no such tuning.