Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 5 down vote favorite
1

I want to know which of the classic linear solvers (e.g Gauss-Seidel, Jacobi, SOR) are guaranteed to converge for the problem $Ax=b$ where $A$ is positive semi definite and of course $b \in im(A)$

(Notice $A$ is semi definite and not definite)

share|improve this question
1  
Do you mean positive semi-definite matrices? – meawoppl Mar 2 '12 at 8:57
1  
What's the use of solving linear system with such matrix? If I'm not mistaken, if your positive semidefinite matrix is non-singular then it is simply positive definite. – faleichik Mar 3 '12 at 7:36
1  
Yes, I am sure. I have to refresh my memory as for the actual proof, but per what you were saying - if the denominator in the calculation of $\alpha$ is zero, it means that $A P_k$ is zero, which means that all the "search directions" in which A is not singular have been exhausted, and the residual you are left with in not in the span of A (and thus this is the "optimal" solution). In the case that in fact $b \in span(A)$, this won't happen as the residual will reach zero just before the first time $AP_k=0$ – noam Mar 3 '12 at 15:47
1  
Set $x_0=b$. Then $A^nb\in Im(A)$. CG will converge due to $x_n^\ast Ax_n> 0$ for all $0\ne x_n\in Im(A)$. In other words, you never leave $Im(A)$ for which $A$ is positive-definite. – Deathbreath Mar 4 '12 at 0:53
2  
@faleichik: reduced density matrices in quantum mechanics are positive semi-definite in very many cases. – Deathbreath Mar 4 '12 at 0:56
show 7 more comments

1 Answer

up vote 7 down vote accepted

The conjugate gradient algorithm works for semidefinite problems and produces the minimal norm solution.

share|improve this answer
thanks. Any idea about the "archaic" solvers, e.g SOR Gauss-Seidel etc. – noam Mar 8 '12 at 18:33
They are hardly ever used anymore, and I don't know how these behave. – Arnold Neumaier Mar 12 '12 at 18:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.