diff options
author | zimmerma <zimmerma@211d60ee-9f03-0410-a15a-8952a2c7a4e4> | 2012-10-08 18:56:23 +0000 |
---|---|---|
committer | zimmerma <zimmerma@211d60ee-9f03-0410-a15a-8952a2c7a4e4> | 2012-10-08 18:56:23 +0000 |
commit | 36f4c054b2cfd72007e865d56dfdf1fe61a1db19 (patch) | |
tree | 9faf3ae49164c6a4b600616e08e9a0442bc09417 /doc | |
parent | 2a7a4098219700fafd28a9e6ff9ed9a73dadfc7a (diff) | |
download | mpc-36f4c054b2cfd72007e865d56dfdf1fe61a1db19.tar.gz |
[algorithms.tex] more work on AGM
git-svn-id: svn://scm.gforge.inria.fr/svn/mpc/trunk@1285 211d60ee-9f03-0410-a15a-8952a2c7a4e4
Diffstat (limited to 'doc')
-rw-r--r-- | doc/algorithms.tex | 37 |
1 files changed, 36 insertions, 1 deletions
diff --git a/doc/algorithms.tex b/doc/algorithms.tex index 1e928ad..aa9f1aa 100644 --- a/doc/algorithms.tex +++ b/doc/algorithms.tex @@ -2051,7 +2051,42 @@ $k'_I \leq k$, then $\error (\appro x) \leq 2^{p - N} \Ulp (\appro x)$ and $\error (\appro y) \leq 2^{p - N} \Ulp (\appro y)$. - +If $\Im(z_1) < 0$, then we can use the fact that $\AGM(1,\bar{z_1}) = +\bar{\AGM(1,z_1)}$, thus the same error analysis applies; +and if $\Im(z_1) = 0$, we are computing a real AGM, we can call the +corresponding MPFR function. + +Now assume $z_1$ is the rounding of some complex number $z_0$ with a +relative error at most $2^{1-p}$. Then we have to replace $\epsilon_0 = 0$ +by $\epsilon_0 = 2^{1-p}$ in the above proof. +This gives +\[ \zeta_1 \leq \epsilon_0 + c (1 + \epsilon_0) 2^{1-p} + \leq (2 + 2^{1-p}) 2^{1-p} \leq \frac{5}{2} 2^{1-p}, \] +and +\[ \epsilon_1 \leq \zeta_1 + c (1 + \zeta_1) 2^{1-p} + \leq (\frac{5}{2} + 1 + \frac{5}{2} 2^{1-p}) 2^{1-p} + \leq 4 \cdot 2^{1-p}, \] +as long as $p \geq 4$. Thus the bound $\epsilon_1 \leq r_1 2^{1-p}$ still +holds in that case. + +\paragraph{The general case.} + +Assume now that $a, b$ are two arbitrary complex numbers, and we want to +approximate $z = \AGM(a, b)$. +We first have to precisely define $\AGM(a, b)$. At each step indeed there are +two choices for $b_n = \sqrt{a_{n-1} b_{n-1}}$. We take a \emph{good} choice +so that $|a_n - b_n| \leq |a_n + b_n|$; this corresponds to an \emph{optimal} +AGM sequence \cite{CrTh10}. +In case $|a_n - b_n| = |a_n + b_n|$, we choose $b_n$ such that +$b_n/a_n$ has a positive imaginary part. + +In \cite{Dupont06}, it is shown that if $\lambda$ is a non-zero complex +number, then $(\lambda a, \lambda b)$ is a good choice if and only if +$(a, b)$ is a good choice. As a consequence, taking $\lambda = 1/a$, +it shows that $\AGM(a,b) = a \AGM(1,b/a)$. We can thus restrict ourselves to +the special case $\AGM(1, z)$ studied above. +Since $\AGM(a,b) = \AGM(b,a)$, without loss of generality we can assume +$|z| \leq 1$. \bibliographystyle{acm} \bibliography{algorithms} |