From 3220ad9df25ef528a22986b21585a0e4b7c183dc Mon Sep 17 00:00:00 2001
From: enge <enge@211d60ee-9f03-0410-a15a-8952a2c7a4e4>
Date: Thu, 11 Jun 2009 18:25:52 +0000
Subject: alorithms.tex: added relative errors for norm

git-svn-id: svn://scm.gforge.inria.fr/svn/mpc/trunk@601 211d60ee-9f03-0410-a15a-8952a2c7a4e4
---
 doc/algorithms.tex | 68 +++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 49 insertions(+), 19 deletions(-)

diff --git a/doc/algorithms.tex b/doc/algorithms.tex
index ac3179b..ac72589 100644
--- a/doc/algorithms.tex
+++ b/doc/algorithms.tex
@@ -551,32 +551,62 @@ The analogous bound for the second error term yields
 The values $\epsilon_{X, 1}^+$ may be estimated as explained at the end
 of \S\ref {sssec:propmul}.
 
-Alternatively, one might write
-$|\corr {x_1}^2 - \appro {x_1}^2|
-= \appro {x_1}^2 \cdot
-\left| 1 - \left( \frac {|\corr {x_1}|}{|\appro {x_1}|} \right)^2 \right|$
-and estimate the both-sided relative error as in \S\ref {sssec:proprealdiv}
-to obtain, under the assumption that $\epsilon_{R, 1}^- < 2$,
+We also need the relative lower error in the following. This can be obtained
+by writing
 \[
-| \corr {x_1}^2 - \appro {x_1}^2 |
+\appro {x_1}^2 - \corr {x_1}^2
+=
+\left( 1 - \left| \frac {\corr {x_1}}{\appro {x_1}} \right|^2 \right)
+\cdot \appro {x_1}^2
+\leq
+\big( 1 - (1 - \epsilon_{R, 1}^-)^2 \big) \appro {x_1}^2
+=
+\big( \epsilon_{R, 1}^- (2 - \epsilon_{R, 1}^-) \big) \appro {x_1}^2.
+\]
+Adding the corresponding expression for the second term
+$\appro {x_1}^2 - \corr {x_1}^2$ yields
+\begin {equation}
+\label {eq:propnormepsminus}
+\frac {\appro x - \corr x}{\appro x}
+\leq
+\max \big(
+   \epsilon_{R, 1}^- (2 - \epsilon_{R, 1}^-),
+   \epsilon_{I, 1}^- (2 - \epsilon_{I, 1}^-)
+\big)
+=: \epsilon^-,
+\end {equation}
+and under the assumption that $\epsilon^- \geq 0$, inspection of
+Definition~\ref {def:relerror} shows that
+$\epsilon^- \geq \relerror^- (\appro x)$ since
+$\appro x$ and $\corr x$ are positive.
+
+The converse estimation yields
+\begin {equation}
+\label {eq:propnormepsplus}
+\relerror^+ (\appro x)
+\leq
+\epsilon^+
+:=
+\frac {\appro x - \corr x}{\appro x}
 \leq
 \max \big(
    \epsilon_{R, 1}^+ (2 + \epsilon_{R, 1}^+),
-   \epsilon_{R, 1}^- (2 - \epsilon_{R, 1}^-)
+   \epsilon_{I, 1}^+ (2 + \epsilon_{I, 1}^+)
 \big)
-\appro {x_1}^2
-\]
-Adding the corresponding bound on the second term, using
-Proposition~\ref {prop:relerror} and letting
-$k_1 = \max ( k_{R, 1}, k_{I, 1})$ and
+\end {equation}
+and $\relerror (\appro x) \leq \epsilon := \max (\epsilon^-, \epsilon^+)$.
+Letting
 $\epsilon_1 = \max ( \epsilon_{R, 1}^-, \epsilon_{R, 1}^+,
-                     \epsilon_{I, 1}^-, \epsilon_{I, 1}^+ )$
-leads to
+                     \epsilon_{I, 1}^-, \epsilon_{I, 1}^+ )
+            = \max ( \epsilon_{R, 1},   \epsilon_{I, 1} )$
+and $k_1 = \max ( k_{R, 1}, k_{I, 1})$,
+we have
+$\epsilon \leq \epsilon_1 (2 + \epsilon_1) \leq 2 k_1 (2 + \epsilon_1) 2^{-p}$
+by Proposition~\ref {prop:relerror}.
+We obtain an alternative expression for the absolute error as
 \begin {equation}
 \label {eq:propnormalt}
-\error (\appro x)
-\leq
-\epsilon_1 (2 + \epsilon_1) 2^{\Exp (\appro x)}
+\error (\appro x) \leq \epsilon \appro x
 \leq
 2 k_1 (2 + \epsilon_1) 2^{\Exp (\appro x) - p}
 \end {equation}
@@ -594,7 +624,7 @@ Then the propagated error may be derived by cumulating the errors obtained
 for multiplication in \S\ref {sssec:propmul}, the norm in
 \S\ref {sssec:propnorm} and the division by a real in
 \S\ref {sssec:proprealdiv}.
-We note
+We write
 \begin{align*}
 \corr a &= \Re (\corr {z_1} \overline {\corr {z_2}}) &
 \corr b &= \Im (\corr {z_1} \overline {\corr {z_2}}) &
-- 
cgit v1.2.1