Iterative Methods for Solving Sparse Matrices
There are many iterative methods which can be applied to solve any matrix equation but are particularly effective in sparse matrices as they directly exploit “zero structure”
Here we look at three simplest or stationary methods - so called because iteration equation is the same at each iteration
The Jacobi method is based on solving for every variable locally with respect to the other variables; one iteration of the method corresponds to solving for every variable once. The resulting method is easy to understand and implement, but convergence is slow.
The Gauss-Seidel method is like the Jacobi method, except that it uses updated values as soon as they are available. In general, it will converge faster than the Jacobi method, though still relatively slowly.
Successive Overrelaxation (SOR) can be derived from the Gauss-Seidel method by introducing an extrapolation parameter ?. For the optimal choice of ?, SOR converges faster than Gauss-Seidel by an order of magnitude.