4

Does every well-conditioned problem admit a stable algorithm?

This related question as well as Carl Christian's comments suggest that in its original form my question is probably too broad to have a satisfying answer. Therefore:

Consider the problem of evaluating a real expression $f$ (an elementary function, if you like) at $x\in \mathbb{R}$ using a fixed floating point number system. Assume that $x$ and $f(x)$ do not over- or underflow and that the relative condition number of $f$ at $x$, $$ \left| \frac{xf'(x)}{f(x)} \right|, $$ is close to $1$. Is there a problem of this type for which only unstable algorithms are known?

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 to my original, broad question (2nd item in the summary), 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.

I am also happy about (partial) answers to special cases other than evaluation of a real function.

begeistzwerst
  • 645
  • 1
    What precisely do you mean when you say that a problem has a computable solution? Must the solution lie in the representable range? Otherwise $f(x) = 2x$ is a function for which the naive algorithm breaks any forward stability bound when $x$ is so large that $2x$ overflows. I don't see any viable alternative to the naive algorithm in this case. – Carl Christian Oct 20 '18 at 21:42
  • With "computable solution" I am mainly trying to exclude answers like the one given to the linked question. I also want to exclude problems where stability issues are caused by over- or underflow of the solution (or input). – begeistzwerst Oct 21 '18 at 13:25
  • 1
    It is entirely possible for a linear system to be well conditioned in the sense of Skeel and overflow unless the right-hand side/solution is scaled dynamically during the solved. Examples exist where overflow protection flushes to zero a critical component of the right-hand side incurring an arbitrarily large error and a relative error of unity. Currently, the only known cure is to extend the set of exponents. Is this permitted or not? Must all computations use a single working precision? – Carl Christian Oct 21 '18 at 20:42
  • 1
    I am very happy that this question has been raised. The exact notes that you refer to came up in a previous session and I was left with the same question as you. It seems to me that the main difficulty lies in specifying the scope of the question. What class of problems are we looking at and what sort of tricks are permitted. In principle we can approximate a smooth function using piecewise polynomials, but only if we can compute accurate approximations at any necessary point, a statement which is not very satisfying either. – Carl Christian Oct 22 '18 at 15:06

0 Answers0