1

Given $x_i^{*}$ ($i\geq 0$) be positive numbers on the computer, and $\delta$ is a unit round-off error, $x_i^{*} = fl(x_i) = x_i(1+\epsilon_{i})$ with $|\epsilon_{i}|\leq \delta$ ($x_i$ are positive exact numbers).

(a) If $P_n = \prod_{i=0}^{n} x_i$, and $fl(P_n) = P_n^{*}= P_n(1+\theta)$. Show that $\theta\leq \epsilon^{\delta(2n+1)}-1$

(b) Given $S = x_1x_2x_3 + x_4x_5x_6$, and $S^{*}$ be floating point approximation of $S$. Show that $\frac{S^{*}}{S}\leq e^{6\theta}$.

My attempt: Despite spending several hours thinking of part (a), I still don't see where the exponential comes from based on the hypothesis. I completely stuck on this part:p

For part (b), we can use the result from part (a) with $n=2$ for $x_1x_2x_3$ to get: $\frac{fl(x_1x_2x_3)}{x_1x_2x_3}\leq e^{5\theta}$. But I failed to see how to bound the other term.

Can anyone please give me some help on this problem?

ghjk
  • 2,859

1 Answers1

0

(a) Use the Taylor expansion of $\exp(\delta)$ to see that $1 + \delta \leq \exp(\delta)$.

(b) With $a = x_1x_2x_3$ and $b = x_4x_5x_6$ your computer obtains $\hat{a} = a(1+\theta_a)$ and $\hat{b} = b(1 + \theta_b)$, where $|\theta_a|,|\theta_b| \leq \exp(5 \delta) - 1$. You really want to compute $s = a + b$, but the computer will return \begin{equation} \hat{s} = (\hat{a} + \hat{b})(1 + \epsilon), \quad |\epsilon| \leq \delta. \end{equation} Plug in the values for $\hat{a}$, $\hat{b}$, use part (a) and you will obtain your result.

The exponential approximation is a bit crude, but commenly used because it is so convinient to work with. A more accurate and equally flexible technique is to use Higham's $\gamma$-factors, defined by \begin{equation} \gamma_n = \frac{nu}{1 - nu}, \end{equation} where $u$ is the unit round off error and $n$ is a positive integer, such that $nu < 1$. They satisfy $u \leq \gamma_1$ and $\gamma_n + \gamma_m + \gamma_n\gamma_m \leq \gamma_{n + m}$.

Carl Christian
  • 12,583
  • 1
  • 14
  • 37