Correctness of direct numerical solution of ill-conditioned linear system

Question

To what extent can you put trust in a numerical solution obtained by direct solver for an ill-conditioned linear system? In other words, how can you test the solution? Dropping it into the system says nothing, because small residual can lead to a big error for an ill-conditioned system.

Answer 1

One thing you can do to test it is computing the residual $b - A \tilde{x}$ in higher precision. If the residual is small (and this will always happen with an accurate solution), then you can testify that the solution is accurate by the classical bound $$ \frac{\|\tilde{x}-x\|}{\|x\|} \leq \kappa(A)\frac{\|b-A\tilde{x}\|}{\|b\|}. $$ Note in particular that this requires you to know $A$ and $b$ to higher precision, too; for instance, because they are exact integers, or because you can evaluate the formulas that produced them in higher precision, too. If you don't have these data available, then you cannot compute $x$ with a better relative error than $\kappa(A)$ times the machine precision anyway, because this is the intrinsic error coming from the uncertainty in your inexact input data.