Algorithms and Parallel Computing

20.6 SUCCESSIVE OVER RELAXATION (SOR) (ITERATIVE TECHNIQUE)

Iterative techniques are suited for large matrices. A simple iterative technique for solving linear equations is the Jacobi iteration, which is suited for matrices that have nonzero diagonal elements. Assume we are given the system of linear equations

(20.47)

we can express the ith row of the above system explicitly:

(20.48)

where we have isolated the term involving x_i. We can “solve” for x_i from the above equation as

(20.49)

Of course, we need to iterate several times before we converge to the correct solution. At iteration k, we can estimate as

(20.50)

Gauss–Seidel iteration differs from the Jacobi iteration in that it uses the most recently found values of in the iterations:

(20.51)

The order of evaluation of ...