The successive overrelaxation method (SOR) is a method of solving a linear system of equations derived by extrapolating 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
where the matrices , , and represent the diagonal, strictly lower-triangular, and strictly
upper-triangular parts of , respectively.
If ,
the SOR method simplifies to the Gauss-Seidel
method. A theorem due to Kahan (1958) shows that SOR fails to converge if
is outside the interval .
In general, it is not possible to compute in advance the value of that will maximize the rate of convergence of SOR. Frequently,
some heuristic estimate is used, such as where is the mesh spacing of the discretization of the underlying
physical domain.
derived by extrapolating 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,
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.
![x^((k))=(D-omegaL)^(-1)[omegaU+(1-omega)D]x^((k-1))+omega(D-omegaL)^(-1)b,](/images/equations/SuccessiveOverrelaxationMethod/NumberedEquation2.svg)
, 
, and 
represent the diagonal, strictly lower-triangular, and strictly
upper-triangular parts of 
, respectively.
,
the SOR method simplifies to the Gauss-Seidel
method. A theorem due to Kahan (1958) shows that SOR fails to converge if 
is outside the interval 
.
that will maximize the rate of convergence of SOR. Frequently,
some heuristic estimate is used, such as 
where 
is the mesh spacing of the discretization of the underlying
physical domain.
