Why would an ill-conditioned problem not be solvable with much accuracy when using floating-point arithmetic?

Question

Could anyone explain using an example why an ill-conditioned problem would not be solvable with much accuracy when using floating-point arithmetic to compute an approximate solution?

Answer 1

Consider the common problem of computing $y = f(x)$ where $f :\mathbb{R} \rightarrow \mathbb{R}$ is a differentiable function. If the algorithm is relative backward stable, then the computed value $\hat{y}$ of $y$ satisfies $$ \hat{y} = f(\hat{x})$$ where $$\left|\frac{x-\hat{x}}{x}\right| \leq C u.$$ Here $u$ is the unit round off and $C>0$ is a constant independent of $u$. A good algorithm has a small value of $C$. This is as good as it gets. Now if the problem is ill-conditioned, then small changes in the input can cause large changes in the output. Specifically, if $\bar{x}$ is an approximation of $x$, then we cannot hope to do better than $$\left| \frac{f(x)-f(\bar{x})}{f(x)} \right| \approx \kappa_f(x) \left|\frac{x-\bar{x}}{x}\right|,$$ where $ \kappa_f(x)$ is the relative condition number of $f$ at the point $x$ given by $$\kappa_f(x) = \left| \frac{xf'(x)}{f(x)} \right|.$$ A rigorous deriviation of this relation from an abstract definition of the condition number can be found in this answer to a related question.

In particular, we have the following bound for the forward relative error $$\left| \frac{ y - \hat{y} }{y} \right| = \left| \frac{f(x)-f(\hat{x})}{f(x)} \right| \approx \kappa_f(x) \left|\frac{x-\hat{x}}{x}\right| \leq C \kappa_f(x) u.$$ In summary, the best we can hope for is a small relative backward error, but this is not enough to guarantee a small relative forward error when the problem is ill-conditioned, i.e., when $\kappa_f(x)$ is large relative to $u$. Conversely, if $C\kappa_f(x)u$ is tiny then all is well and the forward relative error is always small.