计算科学 - 验证代码是否为良好的球形代码 - 吾爱随笔录

验证代码是否为良好的球形代码

计算科学优化麻木的浮点

2021-12-24 05:25:41

抱歉，如果这是一个微不足道的问题。如果是这样的话，我想我会受益于有人解释我缺乏理解的地方。

我在解释 N. Sloane 网站上列出的（假定为最佳）球形代码时遇到了一些麻烦。

例如，对于 40 点，最知名的球面代码在维度 5 中的第一个坐标在此处列出为

7.071067811865475700e-01
7.071067811865475700e-01
-2.531063763564293100e-21
2.856464746130754600e-21
8.243943086078260200e-21

这应该位于 5 维单位超球面上，所以它的范数应该是 1。

如果我用以下方法测试numpy：

a = np.array([7.071067811865475700e-01,
    7.071067811865475700e-01,
    -2.531063763564293100e-21,
    2.856464746130754600e-21,
    8.243943086078260200e-21])

我明白了

np.linalg.norm(a) == 1.0

输出True，这看起来不错。但后来我发现

np.linalg(a[0:2]) == 1.0

也输出True。所以看起来其他数字对于来说太小了numpy。

我玩过例如 using dtype=np.longdouble，但这似乎使问题变得更糟，因为标准随后被计算为1.0000000000000000683。

我认为问题只是我们正在处理有限精度算术，所以我们不能指望得到“准确”的算术。如果是这样，可以使用什么计算方法来确认链接配置实际上是一个好的球形代码？或者，我想指出（或概述！）用于生成这些球形代码的算法也可能会消除我的困惑 - 它们似乎没有在网站上列出。

编辑：我打算删除这个问题，因为它不够好，但网站政策不鼓励删除已收到赞成答案的问题，所以我将它留在这里。可以在此处查看一个新的、希望表述得更好的问题。

2个回答

如果是这样，可以使用什么计算方法来确认链接配置实际上是一个好的球形代码？

你不能，用给定的数据。只有 16 位有效数字可用，您永远不会知道该数量是否正好是 1。或者即使你得到了Float128s 或具有 2000 位有效数字的数字，就此而言。如果您想知道范数是否正好是1，则需要这些数字的精确表达式，以及允许您从它们计算精确结果的算术运算（符号计算）。这不是浮点运算可以解决的问题。

程序解决问题

将 n 个点放在 d 维的球体上，以使它们之间的最小距离（或等效的最小角度）最大化。

顺便说一句，让我们采取 $n = 3$ 和 $d = 2$ . 那么解决方案是相隔 120° 的圆上的三个点。但这意味着我们有坐标 $(0,0)$ , $(cos(2\pi/3),sin(2\pi/3))$ 和 $(cos(2\pi/3),-sin(2\pi/3))$ . 这意味着无法用有限精度算术描述完美的解决方案，因此没有程序可以返回它。

要对其进行测试，您需要确保程序返回的点至少非常接近预期的解决方案。因此，如果 $x^*$ 是真正的解决方案，并且 $x$ 程序返回的解决方案，你想要那个 $||x^* - x|| \le \epsilon$ ，在哪里 $\epsilon$ 代表一些小的公差，通常是机器精度。

在几乎所有应用中，这样的解决方案都足够好。

其它你可能感兴趣的问题

上一篇线性方程组的最简单求解器下一篇给定一个对称矩阵，是否可以应用 Cholesky 分解来查看它是否具有负特征值？