**Previous:** The Successive Overrelaxation Method

**Up:** The Successive Overrelaxation Method

**Previous Page:** The Successive Overrelaxation Method

**Next Page:** The Symmetric Successive Overrelaxation Method

If , the SOR method simplifies trivially back
to the Gauss-Seidel method. A theorem due to
Kahan [130] shows that SOR fails to
converge if is outside the interval . Though
technically the term * underrelaxation*
should be used when , for convenience the term
overrelaxation is now used for any value
of .

In general, it is not possible to compute in advance the value of that is optimal with respect to the rate of convergence of SOR. Even when it is possible to compute the optimal value for , the expense of such computation is usually prohibitive. Frequently, some heuristic estimate is used, such as where is the mesh spacing of the discretization of the underlying physical domain.

If the coefficient matrix is symmetric and positive definite, the
SOR iteration is guaranteed to converge for * any*
value of between 0 and 2, though the choice of can
significantly affect the rate at which the SOR iteration
converges. Sophisticated implementations of the SOR
algorithm (such as that found in ` ITPACK ` [138]) employ adaptive
parameter estimation schemes to try to home in on the appropriate
value of by estimating the rate at which the iteration is
converging.

For coefficient matrices of a special class called * consistently
ordered with property A* (see
Young [212]), which includes certain orderings of matrices
arising from the discretization of elliptic PDEs, there is a direct
relationship between the spectra of the Jacobi
and SOR iteration matrices. In principle, given the
spectral radius of the
Jacobi iteration matrix, one can determine *
a priori* the theoretically optimal value of for SOR:

This is seldom done, since calculating the spectral radius of the Jacobi matrix requires an impractical amount of computation. However, relatively inexpensive rough estimates of (for example, from the power method, see Golub and Van Loan [108], p.351) can yield reasonable estimates for the optimal value of .