# 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.

• I do not understand your limit $\epsilon_1 \cdot \epsilon_2 \rightarrow 0$. Could you please rewrite this? – shuhalo Apr 4 '13 at 12:43
• When we open brackets we get $\epsilon_1 \cdot \epsilon_2$ which goes to zero much faster than $\epsilon_1$ or $\epsilon_2$ alone. Therefore, we can cross their product out. – Alexander Shukaev Apr 4 '13 at 12:57
• Downvoters, please provide comments. – Alexander Shukaev Apr 5 '13 at 11:22
• I'm not a downvoter, but I find it confusing that you describe two equations as "mathematical problems" and then jump to notions of conditioning and "algorithm stability". Perhaps the problem being addressed is one of root-finding, and it would be worth highlighting this in the first sentence. – hardmath Apr 5 '13 at 15:30
• @RSFalcon7: I know this paper, read it long time ago, and feel confident with the concepts in it, and beyond. Thanks though. – Alexander Shukaev Apr 17 '13 at 1:28

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.

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.

• Didn't you mess up the notation? You write a sum of absolute value and its relative perturbation: $x + \frac{\epsilon}{x}$, where $\epsilon$ is absolute perturbation in your notation I suspect, but that's wrong from the physical point of view. I think you should have used either $x \cdot (1 + \epsilon)$ or $x + \Delta x$, where $\epsilon = \frac{\Delta x}{x}$ is relative perturbation, and $\Delta x$ is absolute perturbation. – Alexander Shukaev Apr 4 '13 at 13:02
• @Haroogan: Your notation is not clear. Are you using notation from a book like Accuracy and Stability of Numerical Algorithms by Higham? It's not obvious to a general computational science audience what you mean by $\epsilon$ (versus $\Delta{x}$) unless they read your comment, and even then, it could probably stand to be clarified. – Geoff Oxberry Apr 4 '13 at 16:28
• I'm not discussing my notation here. I don't know this book. To people who are involved in computational science everyday the notation I gave is absolutely clear and sort of conventional. Yes, there are variations, however even if it's not the notation you are used to, you could still easily infer what's going on if you once again have good CS background. – Alexander Shukaev Apr 4 '13 at 16:42
• Secondly, I have to downvote this obviously wrong answer. I get the point which Martin is trying to draw, but the way he reasons it is false. If you set $a = 0$ - you get completely different case in which you would end up with $k(f_1) \equiv 1$ on the whole domain. Which means that it would be unconditionally well-conditioned. It happens because when $a = 0$, essentially what you do is you turn it into $f_1(x) = -x$, and by definition of $k$ it is well-conditioned everywhere on the domain. – Alexander Shukaev Apr 4 '13 at 16:47
• @Haroogan: You're the one who brought up notation, and if you are asking a question, it is your duty to communicate what you are asking clearly. Computational science is a diverse field (with diverse notation!), and what is "obvious" to some is not obvious to all. – Geoff Oxberry Apr 4 '13 at 18:07