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)

  • 1
    $\begingroup$ Do you mean positive semi-definite matrices? $\endgroup$
    – meawoppl
    Commented Mar 2, 2012 at 8:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – faleichik
    Commented Mar 3, 2012 at 7:36
  • 1
    $\begingroup$ 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$ $\endgroup$
    – olamundo
    Commented Mar 3, 2012 at 15:47
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 4, 2012 at 0:53
  • 2
    $\begingroup$ @faleichik: reduced density matrices in quantum mechanics are positive semi-definite in very many cases. $\endgroup$ Commented Mar 4, 2012 at 0:56

2 Answers 2


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

  • $\begingroup$ thanks. Any idea about the "archaic" solvers, e.g SOR Gauss-Seidel etc. $\endgroup$
    – olamundo
    Commented Mar 8, 2012 at 18:33
  • $\begingroup$ They are hardly ever used anymore, and I don't know how these behave. $\endgroup$ Commented Mar 12, 2012 at 18:16
  • $\begingroup$ To clarify: CG most certainly does not work in vanilla form for semi-definite matrices; it may work in theory if B is in the image of A; but this is unlikely to end well in numerical-practice. The very similar krylov-based MINRES is a much better choice here. Also, these "archaic" solvers are widely used in multigrid-type solvers, to name one example. $\endgroup$ Commented Sep 11, 2018 at 9:18

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

The same is very much not true of Jacobi; which is a shame since who wants to bother with Gauss-Seidel on modern computer hardware? If your problem can be split into diagonally-dominant blocks, you are in luck; you can apply Jacobi updates to those blocks in an incremental Gauss-Seidel fashion, and get the best of both for these type of semi-definite problems.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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