2
$\begingroup$

Guys I was reading about CG method to solve the sparse systems. I came across that the method is defined for positive definite symmetric matrices. I was wondering does it converges for negative definite matrices too ?

  • 2
    Not directly, CG minimizes a convex quadratic. However, you could solve $(-A)x = (-b)$, or modify the algorithm by changing signs at appropriate places (as in the difference between minimization and maximization is 'just' a sign difference).2012-11-16

1 Answers 1

3

$Ax =b \iff (-A) x = -b$, and if $A$ is symmetric negative definite then $-A$ is symmetric positive definite. So you can use CG to solve $-Ax = -b$.

  • 0
    So for convergence we compute 2-norm(b-Ax) < tolerance value. If yes then we say that it has converged to a solution. In this case we need to check for 2-norm( (-b) - (-Ax)) < tolerance, which is as good as 2-norm (Ax - b).. is that right ?2012-11-16
  • 0
    Yes, sounds good.2012-11-16
  • 0
    ok. And what if we would like to solve for non-symmetric full-rank matrices using CG? In that case can we solve Ax = b as A'Ax = A'b using CG ?2012-11-16
  • 0
    You could do that, but I don't think it's the best option. $A^T A$ may not be as well-conditioned as $A$, and applying $A^T A$ to a vector is twice as expensive as applying $A$ to a vector. For a non-symmetric matrix, I think you should investigate other methods such as GMRES. Trefethen's book Numerical Linear Algebra is very good for this subject.2012-11-16
  • 0
    The theory would be satisfied by that approach, although the condition number of A'A will be worse than that of A.2012-11-16
  • 1
    Thank You all for your help.2012-11-16
  • 1
    @Anonym: If the Answer littleO gave is satisfactory, you can express your approval by Accepting it, which will also help others who may come across this thread to know it was well resolved.2012-11-16
  • 0
    I have another question like how can we prove for a general matrix that the CG will always converge within the n steps where n is the size of the matrix. ?2012-11-17