Relative error of machine summation

729 Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

$$ \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. $$