relative error of division and subtraction

Question

My task is to calculate the relative error of

(1) $\frac{1}{n} - \frac{1}{n+1}$

(2) $\frac{1}{n(n+1)}$

with the definition $|\frac{z-rd(z)}{z}|$ for the relative error and $rd(x+y)=(x+y)(1+e)$ with $|e| \le eps$. ($*, /, -$ analog)

So far, I have for (1) $rd(z) = (\frac{1}{n}(1+e_{3}) - \frac{1}{(n+1)(1+e_{1})}(1+e_{2}))(1+e_{4})$.

Can somebody help?

Answer 1

You result is correct, but your representation of the error can be streamlined. The analysis that produces $$rd(x \circ y) = (x \circ y)(1 + \delta)$$ where $$|\delta| \leq u$$ and $u$ is the unit roundoff can also yield $$ rd(x \circ y) = \frac{x \circ y}{1 + \epsilon}, \quad |\epsilon| \leq u.$$ I discuss this aspect of floating point computations in this answer. Now if $z = \frac{1}{n} - \frac{1}{n+1}$ and $\hat{z}$ denotes the computed value, then $$ \hat{z} = \left( \frac{1}{n}(1+\delta_1) - \frac{1}{n+1}(1+\delta_2) (1+\delta_3) \right) (1 + \delta_4).$$ The new expression can be simplified as follows. First we define $\gamma_k$ using $$\forall k \in \mathbb{N} \: : \: \gamma_k = \frac{ku}{1 - ku}.$$ This definition assumes that $ku < 1$. It is straight forward to verify that $$u \leq \gamma_1$$ and if $(m+l)u < 1$ then $$\gamma_m + \gamma_l + \gamma_m \gamma_l \leq \gamma_{m+l}.$$ We now write $$ \hat{z} = \frac{1}{n}(1 + \theta_1) - \frac{1}{n+1}(1 + \theta_2) $$ where the $\theta_i$ are given by $$ 1 + \theta_1 = (1+ \delta_1)(1+ \delta_4), \quad 1 + \theta_2 = (1+\delta_2)(1 + \delta_3)(1+ \delta_4) $$ It is straight forward to verify that $$ |\theta_1| \leq \gamma_2, \quad |\theta_2| \leq \gamma_3. $$ We can now write the error as $$ z - \hat{z} = \frac{1}{n}\theta_1 - \frac{1}{n+1} \theta_2. $$ We deduce that $$ | z - \hat{z} | \leq \gamma_3 \left( \frac{1}{n} + \frac{1}{n+1} \right). $$ We conclude that we cannot be certain that the relative error is small, because the right hand-side of the inequality $$ \frac{| z - \hat{z} |}{|z|} \leq \gamma_3 \frac{ \frac{1}{n} + \frac{1}{n+1} }{ \frac{1}{n} - \frac{1}{n+1}} = \gamma_3 (2n+1)$$ is unbounded as $n$ tends to infinity. This last observation is the result that your instructor wishes you to discover. In contrast, the alternative expression namely $$ t = \frac{1}{n(n+1)}$$ has a computed value $\hat{t}$ that satisfies $$\hat{t} = t(1 + \theta), \quad |\theta| \leq \gamma_3.$$ We see that the alternative expression is always evaluated with a small relative error that is bounded by $\gamma_3$. Strictly speaking we have not shown that $\hat{z}$ will be have a large relative error, but experience shows that unless you force computers to be accurate they will seize this opportunity to misbehave and produce garbage. Since our miscalculations can have real life consequences we are obligated to use expressions that are safe.

---

Final remarks:

1. Your notation suggest that $n$ is a positive integer. I have quietly assumed that $n$ was positive. If this is not the case, then remember to apply the absolute value sign when applying the triangle inequality. Moreover, if $n$ is an integer, then $1+n$ will computed exactly unless $n$ is too large. We can therefore take $\delta_2 = 0$. Moreover, we can use Sterbenz lemma to show that $\delta_4 = 0$ is frequently true. These are small issues that do not change the overall conclusion, i.e., the attempt to subtract two real numbers that are very close will almost certainly produce a large relative error as the effect of all previous errors, i.e., the impact of the terms $\theta_1, \theta_2$ can be dramatically amplified by the subtraction.
2. It is possible to streamline the analysis of simple arithmetic operation even further and completely eliminate the need for naming values $\delta_i$. I discuss this option and reference the relevant textbook in this answer.