1
$\begingroup$

I am solving a problem involving the line with the set of points $(x_3,y_3)$ that are equidistant to two given points $(x_1,y_1)$ and $(x_2,y_2)$. The equation for this line is

$$(x_3 - x_1)^2 + (y_3 - y_1)^2 = (x_3 - x_2)^2 + (y_3 - y_2)^2$$

which boils down to

$$2 (x_1 - x_2) x_3 + 2 (y_1 - y_2) y_3 = x_1^2 + y_1^2 - x_2^2 - y_2^2$$

The question I have is quite simple: how should I write the right hand side of this equation? I know that there is more than one way to do it and that some alternatives might be more numerically accurate than others, due to floating point errors. \begin{align} &x_1^2 + y_1^2 - x_2^2 - y_2^2 = \\ &(x_1^2 + y_1^2) - (x_2^2 + y_2^2) = \\ &(x_1^2 - x2^2) + (y_1^2 - y_2^2) = \\ &(x_1 + x_2) (x_1-x_2) + (y_1 + y_2) (y_1 - y_2) = \\ & \vdots \end{align} How do I compute the right hand sidein the most accurate way?

$\endgroup$
1
$\begingroup$

Compute each of the additive terms, sort them, then add up the list. If each of your expressions is going to be this short, the cost of the sorting might not kill your performance.

$\endgroup$
  • $\begingroup$ What do I do with the negative numbers? Do I have to sort by magnitude? $\endgroup$ – hugomg Oct 22 '15 at 14:07
  • $\begingroup$ Sort by magnitude. $\endgroup$ – Bill Barth Oct 22 '15 at 14:13
  • $\begingroup$ Ok. And is there a difference between summing the 4 squares and using another formula based on the $a^2 - b^2 = (a+b)(a-b)$ identity? $\endgroup$ – hugomg Oct 22 '15 at 14:20
  • 1
    $\begingroup$ Yes, if you get some really bad cancellation in $(a-b)$, it could affect your overall result quite strongly in a way that might not appear in $a^2-b^2$. You have the option, for short expressions, to either write out all the possibilities and pick the best order to sum them, or to write your expressions symbolically and use a compiler of sorts to find the best order to compute them in. That's a false dichotomy, of course, you could also try using an arbitrary precision arithmetic package and just compute very high precision results for these expressions. $\endgroup$ – Bill Barth Oct 22 '15 at 14:42
  • 1
    $\begingroup$ @BillBarth Are you saying $a^2-b^2$ is better than $(a+b)(a-b)$? While both are ill-conditioned at $a=b$, it is the latter that is numerically stable. For example, for $b=1$, $a=1+x$, $\mathrm{fl}(a^2-b^2)$ has relative error $\sim (\delta_1-\delta_2)/(2x)$, while $\mathrm{fl}((a+b)(a-b))$ has relative error $\sim\delta_1+\delta_2+\delta_3$ (the $\delta$'s being the individual round-off errors for intermediate expressions). $\endgroup$ – Kirill Oct 22 '15 at 20:40

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.