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 ?
Does conjugate gradient converge for negative definite matrices?
2
$\begingroup$
linear-algebra
numerical-methods
numerical-linear-algebra
-
2Not 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
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$.
-
0So 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
-
0Yes, sounds good. – 2012-11-16
-
0ok. 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
-
0You 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
-
0The theory would be satisfied by that approach, although the condition number of A'A will be worse than that of A. – 2012-11-16
-
1Thank 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
-
0I 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