问题标签 [approximation]

具有显着不同的步长，并且没有太多数据。我们有像>--4-6----3-9----4-7----9-3----4-1---->( -is step here ) 这样的数据，在现实生活中，这些数据是循环的。哪些多项式/公式可以帮助我插值这些数据？贝塞尔会起作用吗？

我目前正在做一个需要快速解决 TSP 的项目（大约 50-100 个节点在 2 秒内）。那里有很多近似算法，但我没有时间也不会分析它们并自己编写代码。

有没有可以解决 TSP 问题的免费库（近似值也可以）？像这样的东西sortedNodes = solveTspPrettyPlease(nodes, 2sec)会很棒。

提前致谢。

我正在尝试测试神经网络作为近似函数的效率。

我需要近似的函数有 5 个输入和 1 个输出，我应该使用哪种结构？

我不知道应该应用什么标准来决定隐藏层的数量和每层的节点数量。

提前谢谢你，问候

朱塞佩。

问候。我正在尝试近似函数

Log10[x^k0 + k1]，其中 0.21 < k0 < 21, 0 < k1 < ~2000，x 是整数 < 2^14。

k0 & k1 是常数。出于实际目的，您可以假设 k0 = 2.12，k1 = 2660。所需的精度为 5*10^-4 相对误差。

这个函数实际上与 Log[x] 相同，除了在 0 附近，它有很大不同。

我已经提出了一个 SIMD 实现，它比简单的查找表快约 1.15 倍，但如果可能的话，我想改进它，我认为由于缺乏有效的指令，这非常困难。

我的 SIMD 实现使用 16 位定点算法来评估 3 次多项式（我使用最小二乘拟合）。多项式对不同的输入范围使用不同的系数。有 8 个范围，范围 i 跨越 (64)2^i 到 (64)2^(i + 1)。这背后的原因是 Log[x] 的导数随 x 迅速下降，这意味着多项式将更准确地拟合它，因为多项式完全适合导数为 0 的函数超过一定阶数。

使用单个 _mm_shuffle_epi8() 可以非常有效地完成 SIMD 表查找。我使用 SSE 的 float 到 int 转换来获得用于定点逼近的指数和有效数字。我还对循环进行了软件流水线处理，以获得约 1.25 倍的加速，因此可能不太可能进一步优化代码。

我要问的是在更高级别是否有更有效的近似？例如：

1. 这个函数是否可以分解为具有有限域的函数，如 log2((2^x) * significand) = x + log2(significand)

因此无需处理不同的范围（表查找）。我认为的主要问题是添加 k1 术语会杀死所有我们知道和喜爱的漂亮日志属性，使其成为不可能。或者是吗？

1. 迭代法？不要这么认为，因为 log[x] 的牛顿法已经是一个复杂的表达式

2. 利用相邻像素的局部性？- 如果 8 个输入的范围在相同的近似范围内，那么我可以查找单个系数，而不是为每个元素查找单独的系数。因此，我可以将其用作快速的常见情况，并在不是时使用较慢的通用代码路径。但就我的数据而言，在此属性保持 70% 的时间之前，范围需要为 ~2000，这似乎并没有使这种方法具有竞争力。

请给我一些意见，尤其是如果您是应用数学家，即使您说做不到。谢谢。

去除随机图的dfs树的叶子后，假设剩下的边数为|S|，我们能否证明该图的匹配将是|S|/2？

我看过一个关于顶点覆盖问题（VC，已知 Np 完全问题）的 2 近似算法的问题，但我不知道答案。问题如下：使用“生成树”找到顶点覆盖问题的 2 近似算法。好吧，已经为 VC 提出了许多贪婪的方法，但是使用“生成树”的特殊算法具有挑战性。任何想法？

我正在尝试规范化 4d 矢量。

我的第一个方法是使用 SSE 内在函数——它为我的向量算术提供了 2 倍的速度提升。这是基本代码：（v.v4 是输入）（使用 GCC）（所有这些都是内联的）

我检查了反汇编，它看起来像我所期望的那样。我看不出有什么大问题。

无论如何，然后我尝试使用近似值：（我从谷歌得到这个）

它的运行速度比 SSE 版本稍快！（大约快 5-10%）它的结果也非常准确 - 找到长度时我会说 0.001！ 但是.. 由于类型双关语，GCC 给了我蹩脚的严格别名规则。

所以我修改它：

现在修改后的版本（没有警告）运行速度变慢了！！它的运行速度几乎是 SSE 版本运行速度的 60%（但结果相同）！为什么是这样？

所以这里有问题：

1. 我的 SSE 实施是否正确？
2. SSE 真的比正常的 fpu 操作慢吗？
3. 为什么第三个代码这么慢？

大家好，我正在尝试仅使用移位和加/减来除以无符号常数 - 如果它是乘法，我对此没有任何问题，但我对除法有点难过。

例如，假设常数除数是 192，假设除数是 8000

“完整结果” y = 8000/192 = 41（假设我不保留小数位）

y = 8000 >> 8 ... 31 y = 8000 >> 7 ... 62

但是如何获得更准确的解决方案？

非常感谢！

我需要求解 N 个线性方程组作为数值优化器的中间步骤。AFAIK 相当简单的算法恰好是 O(N^3) （尽管我在一些数学论文中看到了一个非常复杂的算法，它可以用像 O(N^2.8) 这样的巨大常数来实现）。在某些情况下，N 很大，即几千。

有没有什么好的方法可以在小于 O(N^3) 的时间内得到一个线性方程组的近似解？

编辑：

如果它有帮助，这里有一些更多的细节。

1. 我的矩阵是对称的，而不是稀疏的。

2. 它是 Newton-Raphson 的二阶导数矩阵。我正在尝试在 2000 维空间中优化某些东西。

我需要大约 (1-x)^0.25 并具有给定的精度（例如 0.0001）。我正在使用Wikipedia 上的扩展(1+x)^0.25。当当前表达式小于精度时，我需要停止近似。

不要介意长双n。:P 当我不检查当前表达式的值但计算 1000 个或更多表达式时，这很有效。该函数的域是 <-1;1> 并且 s() 可以很好地计算 <-1;~0.6> 中 x 的近似值。参数越大，计算的误差越大。从 0.6 开始，它超过了准确度。

我不确定问题是否足够清楚，因为我不太了解英语数学语言。问题是 while 条件有什么问题以及为什么函数 s() 不能正确近似。

编辑： 问题基本解决了。当 x>0 时，我必须从 1 中减去连续表达式的绝对值。

在那之后准确性增加了很多（当然是狐狸x> 0）。冗余误差源于长期的双重误差。就这样。无论如何，谢谢你们。