Problem Condition and Algorithm Stability

Question

Consider 2 mathematical problems:

$$ f_1(x) = a - x \\ f_2(x) = e^x -1 $$

The condition number for a function is defined as follows:

$$ k(f) = \left| x \cdot \frac{f'}{f} \right| $$

Lets analyze conditioning first:

$$ k(f_1) = \frac{x}{x - a}, $$

which means that $f_1$ is ill-conditioned near $x = a$;

$$ k(f_2) = \frac{x \cdot e^x}{e^x - 1}, $$

which is undefined near $x = 0$, so lets use L'Hospital:

$$ k(f_2) = \frac{e^x + x \cdot e^x}{e^x}, $$

which means that $f_2$ is well-conditioned everywhere (including $x = 0$ proximity).

Now lets analyze stability of these 2 algorithms (if we were to implement them on the computer directly):

$$ \frac{(a - x) \cdot (1 + \epsilon_1) - (a - x)}{a - x} = \epsilon_1, $$

where $\epsilon_1 \leq \epsilon_m$, and which means that no (numerical) amplification of errors occurs and the algorithm is stable;

$$ \frac{(e^x \cdot (1 + \epsilon_1) - 1) \cdot (1 + \epsilon_2) - (e^x - 1)}{e^x - 1} \approx \{\epsilon_1 \cdot \epsilon_2 \to 0\} \approx \frac{e^x \cdot \epsilon_1 + (e^x - 1) \cdot \epsilon_2}{e^x - 1} = \epsilon_2 + \epsilon_1 \cdot \frac{e^x}{e^x - 1}, $$

where $\epsilon_1, \epsilon_2 \leq \epsilon_m$, and which means that the algorithm is unstable near $x = 0$.

Although everything is allright from the mathematical point of view, i.e. if we obey the formulas and raw theory when obtaining such results, but I begin to doubt in the validity of these results when I try add some logic and reasoning behind it.

First of all, as far as I understand, when we study conditioning of the mathematical problem we think of it in exact arithmetics (i.e. we do not think about computers, rounding, floating-point arithmetic, and etc.). Therefore, if I forget for a moment about the result obtained by analyzing $k(f_1)$ and just look on the simple mathematical problem $f_1(x) = a - x$, then I merely don't see how on earth it could be ill-conditioned near $x = a$. What is the physical reasoning behind it? What kind of bad thing can happen in exact arithmetic near $x = a$?

My curriculum pointed out cancellation error as an explanation. What kind of cancellation error? From my point of view, there is no such thing as cancellation error in exact arithmetic...

So, my reason against it would be straightforward, since ill-condition implies that the output changes drastically when the input changes slightly, then $f_1$ is clearly linear (moreover with coefficient $1$) and any slight changes of $x$ (regardless of whether near $a$ or not) will always result in the quantitatively equal change of $y = f_1(x)$ (i.e. $\Delta x \equiv \Delta y$). Therefore, I insist that $f_1$ can in no way be ill-conditioned neither at $x = a$ nor anywhere else.

Are there any flaws in my reasoning? Please, clarify this for me as I'm actually stuck on it.

Secondly, why it turns out that $f_2$ is well-conditioned while it looks the same as $f_1$? I mean if I follow the same logic as for $f_1$ (i.e. that it's ill-conditioned at $x = a$ because of cancellation as my curriculum states), then I could say the same here - ill-conditioned at $x = 0$, just by looking on the definition of $f_2$! However, mathematics show us that it's not true, but rather that the direct implementation of $f_2$ evaluation on computer would result in unstable algorithm. Due to what? I guess now it's cancellation error because we are in the floating-point world now. But why?

And still the question is why these two seemingly similar problems are actually so different? I'd really appreciate an exhaustive breakdown of these problems as I feel that I'm missing something very basic and it might prevent my understanding of more challenging phenomena.

Answer 1

(This just addresses the first part of your question).

The subtlety here is in your definition of the condition number -- as defined here, it is a ratio of relative error in the output to relative error in the input (ie these notes). As you've discovered, near $x=a$, the relative error of the input is order $\epsilon$, while the relative error of the output is order $\epsilon / \epsilon = 1$.

The problem is not the function, but your choice of error norms. For this problem, the relative norm isn't a good choice near $f = 0$. In basically any other choice of error norm, things would have been better conditioned. For the case of a problem we know to be well scaled (i.e. all input and output are expected to approximately order 1), we can guess that the absolute error might have been a better choice. Then we would define a new condition number,

$k_{abs}$ = absolute error output / absolute error input

$k_{abs} = \frac{|f(x_0 + \epsilon) - f(x_0)|}{|(x_0 + \epsilon) - x_0|} \approx |f'(x_0)| = 1 $

which suggests (correctly) that $f_1$ is well-conditioned everywhere.

Take home message: our condition number is dependent upon the choice of error norms, and care is required in the choice of definition in the general case. You're right to question these sort of things, and subtleties are common and require more thought than just rote application of formulas.

Note that for most real applications, in selecting a valid solution, the norm used is some combination of absolute and relative error for just this reason.

Answer 2

As $f_1$, the bad condition number is completely obvious.

Let us assume that $a = 0$. For large $x$, pertubations do not induce large relative error, so $x+\epsilon / x$ is small for $x$ large. If $x$ gets smaller and smaller, then $1 + \epsilon / x$ is fairly large.

I do not see any problem with that.