GuideLinear systemsadvanced

Over-relaxation methods (SOR)

How a relaxation parameter ω speeds up the classical methods: relaxed Jacobi (JSOR) and SOR, which generalizes Gauss-Seidel (ω=1).

Relaxing with a parameter ω

Over-relaxation methods introduce a parameter ω\omega that weights between the old and new value. Relaxed Jacobi (JSOR) mixes the Jacobi iteration with the previous point:

xi(k+1)=ωaii(bi−∑j≠iaijxj(k))+(1−ω)xi(k)x_i^{(k+1)}=\frac{\omega}{a_{ii}}\left(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\right)+(1-\omega)x_i^{(k)}

The SOR method applies the same idea over Gauss-Seidel. With x̄^{(k+1)} the Gauss-Seidel iterate, the vector form is a weighted average:

(D+ωL)x(k+1)=(−ωU+(1−ω)D)x(k)+ωb,x(k+1)=(1−ω)x(k)+ω xˉ(k+1)(D+\omega L)x^{(k+1)}=\bigl(-\omega U+(1-\omega)D\bigr)x^{(k)}+\omega b,\qquad x^{(k+1)}=(1-\omega)x^{(k)}+\omega\,\bar x^{(k+1)}