1
$\begingroup$

I would like to solve system $Ax=b$, where $A$ is SPD, but very ill-conditioned ($\text{cond}(A)>10^{11}$). I am interested in using UNpreconditioned version of the conjugate gradient method.

Is there any estimate on norm of residual to which method can actually converge in double precision arithmetic? I am not interested in solving system numerically. I am looking for error bounds that incorporate limited precision floating point arithmetic.

$\endgroup$
  • 1
    $\begingroup$ If the condition number is that high then you already know that CG without preconditioning will be very slow to converge and should understand that any solution you do eventually obtain will not be very accurate. Please step back, explain the scientific problem that you started with, and ask about reasonable ways of addressing the problem that don't involve solving a very badly conditioned system of equations. $\endgroup$ – Brian Borchers Feb 7 at 16:06
  • $\begingroup$ I am interested in numerical properties of the CG method. I do not want to actually solve system numerically. $\endgroup$ – computational_scientist Feb 7 at 16:33
  • $\begingroup$ I'd suggest updating your question to make it clear that you're aren't actually interested in solving a system of equations but are looking for error bounds that incorporate limited precision floating point arithmetic. $\endgroup$ – Brian Borchers Feb 7 at 16:48
2
$\begingroup$

Let $x$ denote the solution of $Ax=b$ and let $\hat{x}$ denote the computed solution. We cannot hope to do better than $$\hat{x} = \text{fl}(x),$$ i.e., the floating point representation of $x$. In this, the most favorable case, we have $\hat{x}_j = x_j(1+\delta_j)$ where $|\delta_j| \leq u$ and $u$ is the unit roundoff. It follows, that $\|x-\hat{x}\|_2 \leq u \|x\|_2$. Now, let $r$ denote the residual given by $$ r = b - A\hat{x} = A(x-\hat{x}).$$ We have $$\|r\|_2 \leq \|A\|_2 \|x-\hat{x}\|_2 \leq u \|A\|_2 \|x\|_2 \leq u \|A\|_2 \| A^{-1} \|_2 \|b\|_2.$$ We conclude that the relative residual satisfies $$ \frac{\|r\|_2}{\|b\|_2} \leq u \, \kappa_2(A), $$ where $\kappa_2(A) = \|A\|_2 \| A^{-1} \|_2$ denotes the 2-norm condition number of the matrix $A$.


The estimate above is true for a general matrix $A$. In practice, you will find that the relative residual of iterative methods stagnates at the level of $u \kappa_2(A)$. There is no hope of the CG algorithm doing better in general.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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