# Existence of stable algorithms

by begeistzwerst   Last Updated October 20, 2018 10:20 AM

Does every well-conditioned problem admit a stable algorithm?

I am aware of this related question and its answer, but I am interested in problems which have a computable solution and are well-conditioned.

Put differently, is there a well-conditioned problem, for which only unstable algorithms are known?

Consider, for instance, the problem of evaluating an expression $$f$$ at $$x\in \mathbb{R}$$. There are many textbook examples of well-conditioned problems, e.g. $$f(x) = \log(1+x)$$ at $$x \approx 0$$, for which the obvious 'algorithm' gives bad results, but a mathematically equivalent rewriting, in this case $$\log(1+x) = 2 \, \mathrm{artanh} \, (x/(x+2))$$, leads to a stable algorithm. Can we be sure that such a trick exists?

These notes seem to give a positive answer, but they lack an explanation. I have also looked at Nicholas J. Higham's Accuracy and Stability of Numerical Algorithms, but was not able to find an answer.

Tags :