SOR iteration

The previous methods (Jacobi, Gauss-Seidel) lack any parameter that can be adjusted to accelerate convergence in difficult cases.

Let us revisit Gauss-Seidel:

$$D{x}_{GS}^{(k+1)}=b+L{x}_{GS}^{(k+1)}+U{x}^{(k)}$$

Let us rewrite this as

$$x_{GS}^{(k+1)}=x^{(k)}+\Delta x_{GS}$$

Then SOR is defined as

$$x_{SOR}^{(k+1)}=x^{(k)}+\omega \Delta x_{GS}$$

for some parameter $\omega$.

SOR: Successive Over-Relaxation §

Gauss-Seidel update:

$$x_{GS}^{(k+1)}=x^{(k)}+\left[D^{-1}\right(b+L{x}_{GS}^{(k+1)}+U{x}^{(k)})-x^{(k)}]$$

Here is the increment form of this update:

$$\Delta x_{GS}=D^{-1}(b+L{x}_{GS}^{(k+1)}+U{x}^{(k)})-x^{(k)}$$

We can now define the SOR update:

$$x_{SOR}^{(k+1)}=x_{SOR}^{(k)}+\omega \left[D^{-1}\right(b+L{x}_{SOR}^{(k+1)}+U{x}_{SOR}^{(k)})-x_{SOR}^{(k)}]$$

SOR relaxation parameter §

$\omega$ can be used for different purposes.

$$x_{SOR}^{(k+1)}=x_{SOR}^{(k)}+\omega \Delta x$$

• If the method is diverging, we can apply a smaller increment: $\omega <1$.
• $\omega >1$: when possible, we can try to accelerate convergence by applying a larger increment.
• This method is a little similar to the gradient descent optimization algorithm with momentum, if you are familiar with this approach.

Code for SOR §

for k = 1:maxiter
    for i = 1:n
        sigma = 0.
        for j = 1:n
            if j != i
                sigma += A[i,j] * x[j]
            end
        end
        sigma = (b[i] - sigma) / A[i,i]
        x[i] += omega * (sigma - x[i])
    end
end

Ordering §

As in Gauss-Seidel, the ordering matters in this algorithm. Here are 3 simple orderings that are commonly used:

1. 1 to $n$
2. 1 to $n$ followed by $n$ to 1 in Symmetric SOR
3. Or, a different randomized permutation at every iteration