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.

Related Questions

Analysis for Karatsuba algorithm for multiplication

Updated September 14, 2017 15:20 PM

how to show the convergence of an algorithm

Updated April 08, 2015 18:08 PM

Shifted QR algorithm

Updated March 20, 2017 07:20 AM