The Successive Overrelaxation Method, or SOR, is devised by applying extrapolation to the Gauss-Seidel method. This extrapolation takes the form of a weighted average between the previous iterate and the computed Gauss-Seidel iterate successively for each component:
(where 
denotes a Gauss-Seidel iterate, and 
is the
extrapolation factor). The
idea is to choose a value for that will accelerate the rate
of convergence of the iterates to the solution.
In matrix terms, the SOR algorithm can be written as follows:
The pseudocode for the SOR algorithm is given in Figure 
.
