3
$\begingroup$

If you compute 1+x for x less than the machine precision, the answer will be 1 which is the exact result for x = 0. But this would then imply that the relative backward error is |0 - x| / |x| = 1, i.e. this method is not backwards stable and no method based on standard floating point arithmetic can ever be.

It feels like this finding must be wrong, because how can what is literally the simplest possible operation not be backwards stable? So where is fault in the above reasoning?

$\endgroup$
  • 2
    $\begingroup$ The relative error is $(1+x-1)/(1+x) = x/(1+x) \approx x$ which is small since $x$ is small. $\endgroup$ – cpraveen Dec 1 '18 at 2:59
  • $\begingroup$ But that's the forward error. What confused me is that people usually call backwards stability the "gold standard" that every algorithm should aim for. $\endgroup$ – gTcV Dec 1 '18 at 18:09
  • $\begingroup$ You are right, it is not backward stable. $\endgroup$ – cpraveen Dec 2 '18 at 2:43
2
$\begingroup$

It is indeed true that this function does not allow for a backwards stable algorithm.

The confusion arose because the lecture notes that I was reading seemed to imply that backwards stability is what every algorithm should aim for, however as the above example clearly shows there are algorithms for which no backwards stable algorithms exist. I did some more more reading in the meantime and I learnt that it is not backwards stability, but rather mixed stability that you should aim for. According to Wikipedia:

The usual definition of numerical stability uses a more general concept, called mixed stability, which combines the forward error and the backward error.

$\endgroup$
1
$\begingroup$

There is I think another reason why this result is surprising, apart from the fact that we're used to aiming for backward-stable algorithms like you said in your answer.

Suppose $y$ is the result of an approximate computation, that $y\approx1$, and we're trying to compute $y+x$ with $x\approx0$. With this trivial change, the computation is now backward stable: any small absolute perturbation in $x$ is equivalent to a small relative perturbation in $y$, giving a small relative backward error.

So I think the second reason why $1+x$ not being backward stable is surprising is that it is legitimately surprising. Its backward stability depends on some fairly small details of how you define the problem. In particular, in a real numerical program, it might not be a priori obvious whether $1+x$ or $y+x$ is the right way to think about your program's behaviour. Different people might end up modelling program behaviour differently.

$\endgroup$

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.