algorithms.tex: added complex relative error for addition in same quadrant

git-svn-id: svn://scm.gforge.inria.fr/svn/mpc/trunk@1266 211d60ee-9f03-0410-a15a-8952a2c7a4e4

1 files changed, 62 insertions, 0 deletions

diff --git a/doc/algorithms.tex b/doc/algorithms.tex
index b7002bd..b31a483 100644
--- a/doc/algorithms.tex
+++ b/doc/algorithms.tex
@@ -542,6 +542,68 @@ For subtraction, the same bounds are obtained, except that the simpler bound
 now holds whenever $\appro {x_1}$ and $\appro {x_2}$ resp.
 $\appro {y_1}$ and $\appro {y_2}$ have different signs.
 
+We obtain a useful result with complex relative errors when $z_1$ and $z_2$
+lie in the same quadrant, so that cancellation occurs neither for the real
+nor for the imaginary part.
+
+\begin {lemma}
+\label {lm:arithgeom}
+Let $c_1 = a_1 + i b_1$ and $c_2 = a_2 + i b_2$ lie in the same quadrant,
+that is, $a_1 a_2$, $b_1 b_2 \geq 0$. Then
+\[
+|c_1| + |c_2| \leq \sqrt 2 \cdot |c_1 + c_2|.
+\]
+\end {lemma}
+
+\begin {proof}
+One readily verifies that
+\[
+2 |c_1 + c_2|^2 - (|c_1| + |c_2|)^2
+= (|c_1| - |c_2|)^2 + 4 (a_1 a_2 + b_1 b_2)
+\geq 0
+\]
+\end {proof}
+
+Assume now that $\corr {z_1} = (1 + \theta_1) \appro {z_1}$
+with $\epsilon_1 = |\theta_1|$ and
+$\corr {z_2} = (1 + \theta_2) \appro {z_2}$
+with $\epsilon_2 = |\theta_2|$ lie in the same quadrant.
+Then
+$\corr z = \corr {z_1} + \corr {z_2}
+= (1 + \theta_3) (\appro {z_1} + \appro {z_2})$
+with
+\[
+\theta_3 = \frac {\theta_1 \appro {z_1} + \theta_2 \appro {z_2}}
+                 {\appro {z_1} + \appro {z_2}}.
+\]
+and
+\[
+\epsilon_3 = |\theta_3|
+\leq
+\max (|\theta_1|, |\theta_2|)
+   \frac {|\appro {z_1}| + |\appro {z_2}|}{|\appro {z_1} + \appro {z_2}|}
+\leq
+\sqrt 2 \, \max (|\theta_1|, |\theta_2|)
+\]
+by Lemma~\ref {lm:arithgeom}.
+Now apply Proposition~\ref {prop:comabserror} to
+$\appro {z_1} + \appro {z_2}$ in the place of $\corr z$ and
+$\appro z = \round (\appro {z_1} + \appro {z_2})$ in the place of $\appro z$
+to show that $\appro {z_1} + \appro {z_2} = (1 + \theta_4) \appro z$
+with
+$\epsilon_4 = |\theta_4| \leq c \, 2^{1-p}$,
+where $c = 1/2$ if both the real and the imaginary part are rounded to
+nearest, and $c = 1$ otherwise. So
+$\corr z = (1 + \theta) \appro z$ with
+$\theta = \theta_3 + \theta_4 + \theta_3 \theta_4$ and
+\begin {equation}
+\label {eq:addrel}
+\epsilon = |\theta| \leq \sqrt 2 \, \max (|\theta_1|, |\theta_2|)
++ c \left( 1 + \sqrt 2 \, \max (|\theta_1|, |\theta_2|) \right) 2^{1-p}.
+\end {equation}
+
+
+
 
 \subsubsection {Multiplication}
 \label {sssec:propmul}