Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

When dealing with spd matrices of relatively low condition number, how likely is it (and is it easily provable) that the conjugate gradient method will always be able to find the solution without requiring any kind of preconditioning?

How stable are many of the common preconditioners such as JACOBI, MIC, AINV and is there any way of knowing which are likely to fail to converge if any?

share|improve this question

1 Answer 1

The standard error bound for (non-preconditioned) CG is given in terms of the condition number $\kappa$ only, and it is $$ \left\Vert x-x_k\right\Vert_A \leq 2 \left\Vert x-x_0\right\Vert_A\left(\frac{\kappa^{1/2}-1}{\kappa^{1/2}+1}\right)^k $$ (see e.g. Golub and Van Loan, thm 10.2.6). The norm is the energy norm $\left\Vert x\right\Vert_A:=(x^TAx)^{1/2}$.

So the method should converge no matter what the preconditioner is. To have better convergence, you need to ensure that the matrix after preconditioning is "as close to the identity as possible". Partial guesses on the shape its spectrum, deriving e.g. from lower-dimensional versions of the same problem, or on previous knowledge, can help, but there is no one-size-fits-all solution AFAIK.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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