🚀 go-pugleaf

Does anyone knows of a lower bound for the convergence rate of the
Gauss-Seidel algorithm for a positive definite matrix. It always
converges for positive definite matrix however, I am looking for
information on its dependence on the conditioning of the matrix.

Something like if the matrix is ill-conditioned then the slower the
convergence rate. Or is it independent of the conditioning?

Some sort of relation can be shown for consistently ordered matrices
where the asymptotic convergence rate is the square of that for Jacobi's
method and the later is equal to

	\rho(GS)=\rho(J)^2=((c(A)-1)/(c(A)+1))^2
where

	c(A) = cond(S*A*S)

and S is a scaling matrix that makes all diagonal elements of S*A*S
equal to one.

When the matrix is not consistently ordered then the expression above is
a lower bound on the convergence of Jacobi's method but in general
Jacobi's method does not necessarily converge for arbitrary positive
definite matrices while Gauss-Seidel does.

ANy ideas or suggestions, I will post a summary if I get enough
responses.



Miguel Velez

mvelezre@athena.mit.edu