# Problem Condition and Algorithm Stability

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.

-
Your application of your definition of condition number to $f_1$ and $f_2$ are incorrect. You are using $f'$ over $f$. –  Ross B. Apr 3 '13 at 16:44
Yeah, sorry. I messed up the formula, I'll edit it. $f'$ should be in the numerator of course. But calculations of condition numbers of both $f_1$ and $f_2$ are still fine. –  Haroogan Apr 3 '13 at 16:46