1
$\begingroup$

Completely stuck on this floating point question.

Let $x \in \mathbb{R}$ have the following floating point representation: $$ x = (-1)^s[0.a_1a_2\dots a_ta_{t+1}\dots]\cdot \beta^e $$ [Where $\beta$ is the base] Define the floating point round off to $t$ significant figures to be:

$$ fl(x) = (-1)^s[0.a_1a_2\dots\tilde{a}_t] , \quad \tilde{a}_t = \begin{cases} a_t &\text{if}\; a_{t + 1} < \beta /2 \\ a_t + 1 &\text{if}\; a_{t + 1} \geq \beta /2 \end{cases} $$ And the following flop computation for $x, y \in \mathbb{R}$ to be: $$ x \ominus y := fl(fl(x) - fl(y)) $$ Given that the relative error follows: $$ \frac{|x - fl(x)|}{|x|} \leq u \left[= \frac{1}{2}\beta^{1-t} \right] $$ Show that [triangle inequality may help]: $$ \frac{x \ominus y - (x - y)}{|x - y|} \leq u(2 + u)\frac{|x| + |y|}{|x - y|} $$

Any ideas?

$\endgroup$
  • $\begingroup$ What is $\beta$, is it the base? $\endgroup$ – achille hui Oct 19 '14 at 2:02
  • $\begingroup$ yep, just changed it $\endgroup$ – user150324 Oct 19 '14 at 14:43
0
$\begingroup$

I am stuck with a question very similar to yours, but I can answer yours.

\begin{equation*} \left\vert \frac{x \ominus y - (x - y)}{x - y} \right\vert \leq \left\vert \frac{x \ominus y - (fl(x) - fl(y))}{x - y} \right\vert + \left\vert \frac{fl(x) - fl(y) - (x - y)}{x - y}\right\vert. \end{equation*}

Let's find an upper bound for the first addend.

\begin{equation*} \left\vert \frac{x \ominus y - (fl(x) - fl(y))}{x - y}\right\vert = \left\vert \frac{fl(fl(x) - fl(y)) - (fl(x) - fl(y))}{x - y}\right\vert = \left\vert \frac{(fl(x) - fl(y))(1 + \delta) - (fl(x) - fl(y))}{x - y}\right\vert = \left\vert \frac{(fl(x) - fl(y))\delta}{x - y}\right\vert \leq \left\vert \frac{(fl(x) - fl(y))}{x - y}\right\vert u \leq \left\vert \frac{fl(x) - x}{x}x + x + \frac{fl(y) - y}{y}y + y\right\vert \frac{u}{\left\vert x - y\right\vert} \leq \left(\left\vert \frac{fl(x) - x}{x}\right\vert \left\vert x\right\vert + \left\vert x\right\vert + \left\vert\frac{fl(y) - y}{y}\right\vert \left\vert y\right\vert + \left\vert y\right\vert\right) \frac{u}{\left\vert x - y\right\vert} \leq (\left\vert x\right\vert + \left\vert y\right\vert)(u + 1)\frac{u}{\left\vert x - y\right\vert}. \end{equation*}

Let's find an upper bound for the second addend. \begin{equation*} \left\vert \frac{fl(x) - fl(y) - (x - y)}{x - y}\right\vert \leq \left\vert \frac{fl(x) - x}{x - y}\right\vert + \left\vert \frac{fl(y) - y}{x - y}\right\vert = \left\vert \frac{fl(x) - x}{x}\frac{x}{x - y}\right\vert + \left\vert \frac{fl(y) - y}{y}\frac{y}{x - y}\right\vert \leq u\frac{\left\vert x\right\vert + \left\vert y\right\vert}{\left\vert x - y\right\vert}. \end{equation*}

Putting all together we find \begin{equation*} \left\vert \frac{x \ominus y - (fl(x) - fl(y))}{x - y} \right\vert + \left\vert \frac{fl(x) - fl(y) - (x - y)}{x - y}\right\vert \leq (\left\vert x\right\vert + \left\vert y\right\vert)(u + 1)\frac{u}{\left\vert x - y\right\vert} + u\frac{\left\vert x\right\vert + \left\vert y\right\vert}{\left\vert x - y\right\vert} = \frac{\left\vert x\right\vert + \left\vert y\right\vert}{\left\vert x - y\right\vert}((u+1)u + u) = \frac{\left\vert x\right\vert + \left\vert y\right\vert}{\left\vert x - y\right\vert}((u+2)u). \end{equation*}

So your problem is solved. This is mine, very linked to yours Relative error of machine summation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.