Cancellation in Numerical Analysis

Question

How do you find the values of $x$ for which for example, $f(x) = 1-\cos(x)$ cannot be computed accurately? From different websites I see that this happens for large $x$-values, but I am not sure how to determine that.

Answer 1

For numerical computation of $\sin(x)$ or $\cos(x)$, it is usually best to normalize the argument $x$ to be within the range $[-\pi, \pi]$ or $[0, 2\pi]$, depending on the library's implementation of those trigonometric functions.

In numerical computation, subtraction operations destroy precision when the operands are very close in value, i.e. when $\cos(x)$ is near $1$ in your example.

So when the argument $x$, when normalized, is close to $0$ or $2\pi$, it may be better to compute $1-\cos(x)$ as $2\sin^2\left(\dfrac{x}{2}\right)$, or some other equivalent form, instead. It really depends on whether or not the loss of precision really matters for your problem.

Answer 2

Even for small $x$ you have a problem computing $1-\cos x$. The Taylor series shows that for small $x$ we have $\cos x \approx 1-\frac {x^2}2$ If your float has $53$ bits of precision like a typical $64$ bit number, you lose the difference from $1$ when $x \lt 2^{-26}$ The problem was much worse when floats were only $32$ bits with $24$ bits of precision.

Answer 3

The expression $f(x)=1-\cos x$ suggests the algorithm $$ z_1 = \cos x, \qquad z_2 = 1-z_1 $$

Now it is just a matter of computing the relative error of the outcome (i'm assuming $\cos x\ne0$, but this is not a problematic case):

\begin{align*} \varepsilon_{z_1} =& \frac{x (- \sin x)}{\cos x} \varepsilon_x + \varepsilon_{1}\\ \varepsilon_{z_2} = & z_1 \frac{-1}{1-z_1} \varepsilon_{z_1} + \varepsilon_2=-\frac{\cos x}{1-\cos x}\left( \frac{x (- \sin x)}{\cos x} \varepsilon_x + \varepsilon_{1}\right) + \varepsilon_{2}\\ = & \frac{x \sin x}{\cos x - 1} \varepsilon_x + \frac{\cos x}{\cos x - 1} \varepsilon_1 + \varepsilon_2 \end{align*}

This last expression expresses the relative error in the output in terms of the reltive error in the input ($\varepsilon_x$) adn the roundoff errors in the different steps of the algorithm. The algorithm becomes unstable when one or more coefficients are unbounded, which is the case of $\frac{\cos x}{\cos x -1}$. This is just a quantification of an obvious fact: if $\cos x$ is small (but not zero) and it is computed as zero the relative error computing $1-\cos x$ becomes infinite.