4

I am given the function $$f(x) = \frac{1}{1+2x} - \frac{1-x}{1+x}$$ and I am asked the following:

Explain why for $x \approx 0$ there is a numerical problem. Is the problem in the neighbourhood $x \approx 0$ well conditioned?

My attempt:

There is a numerical problem around $x \approx 0$ because we get there something that looks like $1 - 1$ and difference between $2$ numbers with the same sign can be problematic.

Now, I calculated the condition number $$\gamma(x) = \frac{xf'(x)}{f(x)} = \frac{3x+2}{(2x+1)(1+x)}$$ so for $x \approx 0$ we get $\gamma(0) = 2$. Is this well conditioned? What does conditioning even mean? I am actually not given a definition.

Thanks for any help/insight.

2 Answers2

2

In a numerical evaluation of the difference the first term will have a relative floating point error of about $\pm 2\mu$ and the second term of about $\pm 3\mu$, where the coefficients of the machine precision are the operations counts of the terms (multiplication by 2 is exact). At $x\approx 0$ the terms evaluate to $≈1$ so that the relative are also the absolute errors.

The error of the difference can thus be as large as $\pm 5μ$. However, the exact value by algebraic simplification is $=2x^2+O(x^3)$. Thus the relative error at $x=0$ is expected to behave like $\frac{5\mu}{2x^2}$. Indeed numerical evaluation by computing the relative error for $|x|<10^{-7}$ confirms that estimate:

enter image description here

Lutz Lehmann
  • 126,666
  • Can you explain why the relative error can become arbitrarily bad for $x \approx 0$ when the condition number in this case is $2$? The fact that the condition number is $O(1)$ indicates that a small change in input leads to a small change in output; yet you have demonstrated that for $x$ near $0$, a small change in input can give a drastic change in output. To summarize, the low condition number seems to be in direct contradiction with what you have demonstrated. – ManUtdBloke May 06 '20 at 18:10
  • 1
    The condition number tells you only how the exact function behaves. What I wrote about is the floating point evaluation procedure for the terms as given, as the other answer also shows, different evaluation procedures lead to different floating point error profiles. – Lutz Lehmann May 06 '20 at 19:11
0

The definition of condition number attempts to capture the amount the output changes for small changes in input; the problem is 'well-conditioned' if small changes in input lead to small changes in the output, and poorly conditioned if the output change is large.

Ok, this definition is all fine and well, but I prefer to think of it this way: Does projection of $x$ onto the nearest representable float $\hat{x}$ screw up my computation horribly? If so, the problem is poorly conditioned. And I can think even more precisely, because if $\epsilon$ is the float epsilon for the type, i.e., the number such that $x = \hat{x}(1+\epsilon)$, then I know that the problem will return zero correct digits if $\gamma(x) > 1/\epsilon$. Since your condition number is 2, then you are far from that, since the double epsilon is around $10^{-16}$.

What the problem appears to want you to recognize is the difference between the condition number of the problem and the condition number of the algorithm you use to evaluate it, because even if the problem is well conditioned, you can perform ill-conditioned steps to solve it. The way $f$ is presented suggests an algorithm to evaluate it which leads to subtraction of nearly equal terms. To make it well-conditioned, might I suggest the following form?

$$ f(x) = \frac{2x^2}{(1+x)(1+2x)} $$ Same function, but naive evaluation of the rhs is well-conditioned near $x = 0$.

user14717
  • 4,902
  • Good answer, but can you elaborate on how I can determine if this problem is well conditioned at x = 0? –  Jun 15 '17 at 20:26
  • You have already proven that it is well-conditioned by showing that the condition number is 2, which is much less that a worrisome condition number of $10^16$ that will destroy a double precision calculation. – user14717 Jun 16 '17 at 01:17
  • Ah so for example, if my condition number is $2$, then my precision for a perturbation when the flops operations are done perfectly gives me something around $2 \epsilon$? –  Jun 16 '17 at 07:56
  • Well, the condition number gives a worst-case relative error bound. Your example is a best case absolute error bound. But you've got the essential idea. – user14717 Jun 16 '17 at 15:15