I know that the the Conjugate Gradient iteration fails when $0\in \mathcal {W}(A^{H})$, which means there's a complex vector $x+iy$ such that $(x+iy)^{T}A^{H}(x+iy)=0$. I wonder how to derive a real initial vector such that the Conjugate Gradient iteration fails if $A$ and $b$ are real based on this complex vector? The thing is that I don't know where I can use the condition $b$ is real.


1 Answer 1


Your statement is not correct, I believe.

The equivalent condition for the real case is that the iteration will fail if there is a vector $x\in{\mathbb R}^n$ so that $x^T A x = 0$, which is equivalent to saying "the iteration will fail if the matrix $A$ has a zero eigenvalue". Or, equivalently "the iteration will fail if the matrix $A$ has a null space".

But that's not actually true (neither necessary nor sufficient) in practice:

  • If the matrix has a null space but the initial residual does not have a component in the null space, then the iteration will give you a solution of the linear system $Ax=b$. This problem does not have a unique solution if $A$ has a null space, but you then simply get that solution that is perpendicular to the null space -- which happens to also be the least-squares solution of the underdetermined problem (or what you would get with the pseudo-inverse, $x=A^\dagger b$).
  • If the matrix has negative eigenvalues, then the CG method will also fail if you run it for enough iterations. But you might get lucky for the first few iterations.

In other words, the situation is substantially more complicated than your simple statement about the null space.


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.