Tridiagonal system solver based on SOR – C++

The attached code solves a tridiagonal system of equations using the (extrapolated) successive over-relaxation method (SOR / ESOR).

Below you can find a very brief description of the SOR and ESOR methods.

Successive Over-Relaxation (SOR / ESOR)

The (extrapolated) successive over-relaxation method is a variant of the Gauss–Seidel method for solving a system of linear equations A*x = b, where:

Linear System


SOR a_hat

The extrapolated successive over-relaxation method is an iterative technique that, in the kth iteration, computes the elements of x(k+1) using the previous value x(k) as follows (until it converges):

Extrapolated successive over-relaxation formula

By setting τ = w, we reach the well-known successive over-relaxation method:

Successive over-relaxation formula

ESOR method for tridiagonal system

The ESOR method can be used to solve a tridiagonal system A*x = d

Tridiagonal system

In the kth iteration, the elements of x(k+1) are computed as follows:

ESOR formula for tridiagonal system

which is easily depicted from the original ESOR formula given the special structure of the A matrix (tridiagonal).