com.numericalmethod.suanshu.matrix.doubles.matrixtype.sparse.solver.iterative.stationary
Class SuccessiveOverrelaxationSolver

java.lang.Object
  com.numericalmethod.suanshu.matrix.doubles.matrixtype.sparse.solver.iterative.stationary.SuccessiveOverrelaxationSolver

All Implemented Interfaces:

IterativeLinearSystemSolver

public class SuccessiveOverrelaxationSolver
extends java.lang.Object
implements IterativeLinearSystemSolver

The Successive Overrelaxation method (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. If the weight ω is chosen optimally, SOR may converge faster than the Gauss-Seidel method by an order of magnitude. If the coefficient matrix A is symmetric positive definite, SOR is guaranteed to converge for any value of ω between 0 and 2, though the choice of ω can significantly affect the rate of convergence. In principle, given the spectral radius ρ of the Jacobi iteration matrix, one can determine a priori the theoretically optimal value of ω for SOR:

ω_opt = 2 / (1 + sqrt(1 - ρ²))

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 ρ can yield reasonable estimates for the optimal value of ω.

This implementation does not support preconditioning.

See Also:

Wikipedia: Successive over-relaxation method

Nested Class Summary

Nested classes/interfaces inherited from interface com.numericalmethod.suanshu.matrix.doubles.matrixtype.sparse.solver.iterative.IterativeLinearSystemSolver

IterativeLinearSystemSolver.Solution

Constructor Summary

SuccessiveOverrelaxationSolver(double omega, int maxIteration, Tolerance tolerance)
Construct a SOR solver with the extrapolation factor ω.

Method Summary

IterativeLinearSystemSolver.Solution	solve(LSProblem problem)
IterativeLinearSystemSolver.Solution	solve(LSProblem problem, IterationMonitor<Vector> monitor) Solves iteratively Ax = b until the solution converges, i.e., the norm of residual (b - Ax) is less than or equal to the threshold.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SuccessiveOverrelaxationSolver

public SuccessiveOverrelaxationSolver(double omega,
                                      int maxIteration,
                                      Tolerance tolerance)

Construct a SOR solver with the extrapolation factor ω. Usually, ω is chosen inside the interval (0, 2). It is shown that SOR fails to converge if ω is outside the interval (0, 2). Technically, if ω is within (0, 1), the method becomes under-relaxation. If ω equals to 1, SOR simplifies to the Gauss-Seidel method.

Parameters:

omega - the extrapolation factor

maxIteration - the maximum number of iterations

tolerance - the convergence threshold

Method Detail

solve

public IterativeLinearSystemSolver.Solution solve(LSProblem problem)
                                           throws ConvergenceFailure

Throws:

ConvergenceFailure

solve

public IterativeLinearSystemSolver.Solution solve(LSProblem problem,
                                                  IterationMonitor<Vector> monitor)
                                           throws ConvergenceFailure

Description copied from interface: IterativeLinearSystemSolver

Solves iteratively

Ax = b

until the solution converges, i.e., the norm of residual (b - Ax) is less than or equal to the threshold.

Specified by:

solve in interface IterativeLinearSystemSolver

Parameters:

problem - a system of linear equations

monitor - an iteration monitor

Returns:

an (approximate) solution to the linear problem

Throws:

ConvergenceFailure - if the algorithm fails to converge