# Which iterative linear solvers converge for positive semidefinite matrices?

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)

• Do you mean positive semi-definite matrices? – meawoppl Mar 2 '12 at 8:57
• 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
• 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$ – olamundo Mar 3 '12 at 15:47
• 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
• @faleichik: reduced density matrices in quantum mechanics are positive semi-definite in very many cases. – Deathbreath Mar 4 '12 at 0:56

Here is a proof that Gauss-Seidel fits your requirements, given that $b$ is in the image of $A$.