1
$\begingroup$

Let $\mathbb{F}(b,t,L,U)$ (briefly $\mathbb{F}$) the set of all machine numbers. The definition is the usual, i.e. $\mathbb{F}$ is defined as \begin{equation*} \mathbb{F} := \left\lbrace (-1)^{s} m b^{e-t}\right\rbrace \end{equation*} where $b^{t-1} \leq m \leq b^{t}-1$, $L \leq e \leq U$ and $s \in \left\lbrace 0,1\right\rbrace$. The lower bound imposed on $m$ guarantees the uniqueness of the representation.

I want to give an upper bound to the relative error resulting from a summation $x \fbox{+} y$ Let's remind how the summation $\fbox{+}$ is defined.

$fl(x): \mathbb{R} \mapsto \mathbb{F}$ maps $x$ to the nearest element of $\mathbb{F}$. In the special case in which $x$ it is exactly in the middle of two machine numbers we choose the biggest one (rounding).

If $x, y \in \mathbb{F}$ then $x \fbox{+} y$ is defined by the unique $z \in \mathbb{F}$ such that $z = (x + y)(1+\delta)$ and $\vert\delta\vert \leq u := \frac{1}{2}b^{1-t}$ ($u$ it is usually called roundoff unit and $b^{1-t}$ is the machine epsilon, i.e. the smaller value in $\mathbb{F}$ which is greater than $1$).

If $x, y \in \mathbb{R}$ then $x \fbox{+} y$ it is defined as $fl(fl(x)+ fl(y))$.

I want to give an upper bound to \begin{equation*} \frac{\vert x \fbox{+} y - (x + y)\vert}{\left\vert x + y\right\vert}. \end{equation*}

I found that \begin{equation*} \frac{\vert x \fbox{+} y - (x + y)\vert}{\left\vert x + y\right\vert} \leq u(u+2)\frac{\left\vert x\right\vert + \left\vert y\right\vert}{\left\vert x + y\right\vert}. \end{equation*} While my book says that \begin{equation*} \frac{\vert x \fbox{+} y - (x + y)\vert}{\left\vert x + y\right\vert} \leq u(u+1)\frac{\left\vert x\right\vert + \left\vert y\right\vert}{\left\vert x + y\right\vert} + u. \end{equation*}

If you want I can post my all my calculations, but now I post only the hint from the text

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

Any ideas?

EDIT: Here you can find my calculations. Machine Floating Point Theorem

$\endgroup$
  • $\begingroup$ There's a typo in definition of $x \boxplus y$. I suppose that $z = (1 + \delta) \color{red}{(x + y)}$ for $x, y \in \mathbb F$. $\endgroup$ – uranix Aug 27 '16 at 9:11
  • $\begingroup$ you are right, now I change it. $\endgroup$ – Nisba Aug 27 '16 at 9:16
1
$\begingroup$

$$ \frac{|x \boxplus y - (x + y)|}{|x+y|} = \frac{|fl(fl(x) + fl(y)) - (x + y)|}{|x+y|} \leq \\ \leq \frac{|fl(fl(x) + fl(y)) - (fl(x) + fl(y))|}{|x+y|} + \frac{|fl(x) - x|}{|x+y|} + \frac{|fl(y) - y|}{|x+y|}. $$ The last two terms can be respectively bound by $u\frac{|x|}{|x+y|}$ and $u\frac{|y|}{|x + y|}$, resulting in $u \frac{|x|+ |y|}{|x + y|}$.

The first term can be bound by $$ \frac{|fl(fl(x) + fl(y)) - (fl(x) + fl(y))|}{|x+y|} \leq u \frac{|fl(x) + fl(y)|}{|x+y|} = \\ = u \frac{|fl(x) + fl(y) - (x+y) + (x+y)|}{|x+y|} \leq u\frac{|fl(x) - x|}{|x+y|} + u\frac{|fl(y) - y|}{|x+y|} + u \leq\\ \leq u^2 \frac{|x| + |y|}{|x + y|} + u. $$ Summing that together we get the bound $$ (u^2 + u)\frac{|x| + |y|}{|x + y|} + u. $$

$\endgroup$
  • $\begingroup$ Thank you! I was quite near. $\endgroup$ – Nisba Aug 27 '16 at 9:53

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.