Successive Over-Relaxation

SOR accelerates Gauss-Seidel by over-correcting each update with a relaxation factor, dramatically speeding convergence when the factor is tuned well.

Over-correcting on purpose

Successive over-relaxation (SOR) speeds up Gauss-Seidel by extrapolating each update. It computes the Gauss-Seidel correction, then moves further in that direction by a relaxation factor omega: x_new = (1-omega) x_old + omega x_GS. With omega = 1 it is plain Gauss-Seidel; with 1 < omega < 2 it over-relaxes, and below 1 it under-relaxes.

import numpy as np
def sor(A, b, x, omega, iters):
    n = len(b)
    for _ in range(iters):
        for i in range(n):
            s = A[i,:] @ x - A[i,i]*x[i]
            xgs = (b[i] - s)/A[i,i]
            x[i] = (1-omega)*x[i] + omega*xgs
    return x

The optimal factor

The convergence rate depends sharply on omega. For a class of model problems there is an optimal omega that can reduce the number of iterations from order N to order sqrt(N), a large gain on fine grids. The optimum lies between 1 and 2 and depends on the spectral radius of the Jacobi iteration matrix.

Practical tuning

The exact optimal omega is rarely known in advance and must be estimated or found by experiment. Performance is sensitive: a poor choice can be slower than Gauss-Seidel, and omega at or above 2 diverges. Symmetric SOR (SSOR), which sweeps forward then backward, is a common symmetric preconditioner for Krylov methods.

Legacy and use

SOR was a dominant PDE solver before multigrid and Krylov methods matured. Today it survives mainly as a preconditioner and a smoother, and as an instructive example of how a single extrapolation parameter can transform convergence. It illustrates the value of acceleration before turning to Krylov subspace methods.

Relaxation-based smoothers of this kind feed the multigrid and Krylov solvers used on breeder Hyperion sparse systems.