计算向量之间角度的数值稳定方法

计算科学 算法 精确 数值限制
2021-11-27 22:28:14

当对两个向量之间的角度应用经典公式时:

α=arccosv1v2v1v2

人们发现,对于非常小的/锐角,会损失精度并且结果不准确。正如此 Stack Overflow 答案中所解释的,一种解决方案是使用反正切:

α=arctan2(v1×v2,v1v2)

这确实给出了更好的结果。但是,我想知道这对于非常接近π/2的角度是否会产生不好的结果。是这样吗?如果是这样,是否有任何公式可以准确计算角度而无需检查if分支内的公差?

2个回答

我之前测试过这种方法,我记得它工作正常,但我没有专门针对这个问题测试过。

据我所知,\ v1×v2v1v2如果它们几乎平行/垂直,则可能会遭受灾难性的抵消——如果任一输入关闭,atan2 将无法为您提供良好的准确性。

首先将问题重新表述为找到边长,(这些都是在浮点运算中准确计算的)。由于 Kahan(错误计算针状三角形的面积和角度), Heron 公式有一个众所周知的变体,它允许您计算由边长指定的三角形的面积和角度(在之间),并在数值上稳定地做到这一点。因为这个子问题的归约也是准确的,所以这种方法应该适用于任意输入。a=|v1|b=|v2|c=|v1v2|ab

引用该论文(见第 3 页),假设 , 这里所有的括号都放得很仔细,很重要;如果您发现自己取负数的平方根,则输入边长不是三角形的边长。ab

μ={c(ab),if bc0,b(ac),if c>b0,invalid triangle,otherwise
angle=2arctan(((ab)+c)μ(a+(b+c))((ac)+b))

Kahan 的论文中解释了这是如何工作的,包括其他公式失败的值的示例。公式第 4 页上αC

我建议 Kahan 的 Heron 公式的主要原因是因为它是一个非常好的基元——许多可能很棘手的平面几何问题可以简化为找到任意三角形的面积/角度,所以如果你可以将问题简化为那个,那么一个很好的稳定公式,没有必要自己想出一些东西。

编辑根据 Stefano 的评论,我为代码)绘制了相对误差图。这两行是的相对误差,沿着水平轴。似乎它有效。 v1=(1,0)v2=(cosθ,sinθ)θ=ϵθ=π/2ϵϵ在此处输入图像描述

在Velvel Kahan的另一篇笔记中,这个问题的有效答案并不令人惊讶

α=2arctan(v1v1+v2v2,v1v1v2v2)

其中我使用作为与水平轴的夹角。(在某些语言中,您可能必须颠倒参数的顺序。)arctan(x,y)(x,y)

(我在这里给出了Kahan 公式的Mathematica演示。)