3
$\begingroup$

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.

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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