5
$\begingroup$

Assume $x$ and $y$ are two vectors in $\mathbb{R}^3$ and we want to compute the acute angle $\alpha\in(0,\pi/2]$ between these two (noncolinear) vectors. There are (at least) two possibilities:

  1. In the naive approach, we compute the absolute value of the dot product of the normalized vectors $x$ and $y$ $$\frac{x^Ty}{\|x\|\|y\|}$$ and take the inverse cosine of the result.

  2. The less naive approach is based on the fact that $$\|x\times y\|=\|x\|\|y\|\sin\alpha\quad\text{and}\quad|x^Ty|=\|x\|\|y\|\cos\alpha$$ so $\alpha$ is equal to an angle in a right triangle with legs of the length $\|x\times y\|$ and $|x^Ty|$ (for convenience, one can use a variant of the inverse tangent implemented in the atan2 function which is available in most programming languages; the function takes the side lengths of the legs as two arguments).

Now assume that $x$ is given and $y=x+\Delta x$ where $\|\Delta x\|\leq\tau\|x\|$, $\tau\ll 1$, that is, the vectors are almost colinear (for simplicity also of almost same norms). Assume that $\tilde\alpha_1$ and $\tilde\alpha_2$ are, respectively, the angles computed by the naive and the less naive approaches. Recently, I've run several tests which suggest that $$\tag{1} \frac{|\alpha-\tilde\alpha_1|}{\alpha}\leq \epsilon\mathcal{O}(\tau^{-2}) \quad\text{and}\quad \frac{|\alpha-\tilde\alpha_2|}{\alpha}\leq \epsilon\mathcal{O}(\tau^{-1}), $$ where $\epsilon$ is the machine precision. I understand that both algorithms suffer from a certain inaccuracy when $y\approx x$; in particular, both computing the dot and cross products. I suppose the inverse trigonometric functions are not an issue as these are usually implemented to give very accurate results.

I'm not asking anybody for performing any kind of analysis. I was just wondering whether there is a known reference where the accuracy of the two approaches is considered, if possible revealing why (1) (probably) holds. Thanks a lot in advance.

$\endgroup$
4
$\begingroup$

It's easy to see why this is: $\cos(\alpha) \sim 1 - \alpha^2/2$ for $\alpha$ near $0$, so an error of $\delta$ in $\cos(\alpha)$ can produce an error of about $\sqrt{2\delta}$ in $\alpha$ as computed using $\arccos(\cos(\alpha))$.

$\endgroup$
  • $\begingroup$ Thank you for the input. Although it still a bit puzzles me because the cosine is also involved in the second approach. $\endgroup$ – Algebraic Pavel Feb 12 '15 at 22:13
  • $\begingroup$ Ok I understand it now (at least from the "qualitative" point of view). As $\cos(\alpha)\approx 1$ the error of the inverse tangent formula is essentially determined by the error of the norm of the cross product which is of the order $\delta$. $\endgroup$ – Algebraic Pavel Feb 12 '15 at 22:25
3
$\begingroup$

For some background on these sort of issues, this might be interesting: R.W. Sinnott, "Virtues of the Haversine", Sky and Telescope, vol. 68, no. 2, 1984, p. 159

$\endgroup$
  • $\begingroup$ Thank you for the interesting reference. I'll try to look it up. $\endgroup$ – Algebraic Pavel Feb 12 '15 at 22:18

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.