SuanShu, a Java numerical and statistical library

## 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 SuccessiveOverrelaxationSolverextends java.lang.Objectimplements 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 - ρ2))
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.

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

SuanShu, a Java numerical and statistical library