问题标签 [polynomial-math]

我遇到了一些高级碰撞检测的情况，我需要计算四次函数的根。

我使用法拉利的通用解决方案编写了一个似乎可以正常工作的函数，如下所示：http ://en.wikipedia.org/wiki/Quartic_function#Ferrari.27s_solution 。

这是我的功能：

唯一的问题是我似乎有一些例外。最值得注意的是当我有两个实根和两个虚根时。

例如，这个等式：y = 0.9604000000000001x^4 - 5.997600000000001x^3 + 13.951750054511718x^2 - 14.326264455924333x + 5.474214401412618

返回根： 1.7820304835380467 + 0i 1.34041662585388 + 0i 1.3404185025061823 + 0i 1.7820323472855648 + 0i

如果我绘制该特定方程，我可以看到实际根更接近 1.2 和 2.9（大约）。我不能将四个不正确的根视为随机的，因为它们实际上是方程一阶导数的两个根：

y = 3.8416x^3 - 17.9928x^2 + 27.9035001x - 14.326264455924333

请记住，我实际上并不是在寻找我发布的方程式的特定根源。我的问题是是否有某种我没有考虑到的特殊情况。

有任何想法吗？

背景

我需要在 Fortran90/95 中使用Horner 方案求解多个变量中的多项式。这样做的主要原因是在使用霍纳方案评估多项式时提高了效率和准确性。

我目前有一个实现单变量/单变量多项式的霍纳方案。然而，使用霍纳的方案开发一个函数来评估多元多项式被证明超出了我的范围。

一个示例二元多项式是： 12x^2y^2+8x^2y+6xy^2+4xy+2x+2y 将分解为 x(x(y(12y+8))+y(6y+4)+2 )+2y，然后评估 x 和 y 的特定值。

研究

我做了研究，发现了一些论文，例如：
staff.ustc.edu.cn/~xinmao/ISSAC05/pages/bulletins/articles/147/hornercorrected.pdf
citeseerx.ist.psu.edu/viewdoc/download ?doi=10.1.1.40.8637&rep=rep1&type=pdf
www.is.titech.ac.jp/~kojima/articles/B-433.pdf

问题

但是，我不是数学家或计算机科学家，所以我在用于传达算法和想法的数学方面遇到了麻烦。

据我所知，基本策略是将多元多项式转换为单独的单变量多项式并以这种方式计算。

谁能帮我？如果有人可以帮助我将算法转换为我自己可以在 Fortran 中实现的伪代码，我将不胜感激。

我想出了一个新的算法来解决子集和问题，我认为它是在多项式时间内。告诉我我要么错了要么完全是个天才。

快速入门事实：

子集和问题是一个 NP 完全问题。在多项式时间内求解它意味着 P = NP。
一组长度为 N 的子集的数量为 2^N。

另一方面，长度为 N 的唯一子集的数量最大为整个集合的总和减去最小元素，或者，任何子集可能产生的和的范围在所有负元素的总和之间和所有正元素的总和，因为没有总和可能大于或小于所有正或负总和，当我们添加额外元素时，它们以线性速率增长。

这意味着随着 N 的增加，重复子集的数量呈指数增长，而唯一有用的子集的数量仅线性增加。如果可以设计一种算法来尽早删除重复的子集，我们将在多项式时间内运行。一个简单的例子很容易取自二进制文件。仅从作为 2 的幂的数字，我们可以为任何整数值创建唯一的子集。因此，任何涉及任何其他数字的子集（如果我们有 2 的所有幂）都是重复的和浪费的。通过不计算它们及其导数，我们几乎可以节省算法的所有运行时间，因为与任何整数相比，作为 2 的幂的数字都是对数出现的。

因此，我提出了一个简单的算法，该算法将删除这些重复项并省去计算它们及其所有导数的麻烦。

首先，我们将对只有 O(N log N) 的集合进行排序，并将其分成两半，正数和负数。负数的过程是相同的，所以我将只概述正数（集合现在仅表示正数，只是为了澄清）。

想象一个由 sum 索引的数组，其中包含所有可能的正边结果总和的条目（记住，这只是线性的）。当我们添加一个条目时，值是子集中的条目。就像，数组 [3] = { 1, 2 }。

一般来说，我们现在开始枚举集合中的所有子集。我们通过从一个长度的子集开始，然后添加到它们来做到这一点。当我们拥有所有独特的子集时，它们形成一个数组，我们只需按照 Horowitz/Sahni 中使用的方式迭代它们。

现在我们从“第一代”价值观开始。也就是说，如果原始数据集中没有重复的数字，则保证这些值中没有重复。也就是说，所有单值子集，以及集合的所有长度减去一个长度的子集。这些可以通过对集合求和并依次减去每个元素来轻松生成。此外，集合本身是有效的第一代总和和子集，以及子集的每个单独元素。

现在我们做第二代价值观。我们遍历数组中的每个值和每个唯一子集，如果没有，我们添加它并计算新的唯一子集。如果我们有重复，就会发生乐趣。我们将其添加到碰撞列表中。当我们添加新的子集时，我们检查它们是否在冲突列表中。我们以不太理想的（通常更大，但可以是任意的）相等子集为关键。当我们添加到子集时，如果我们会产生碰撞，我们什么也不做。当我们来添加更理想的子集时，它会错过检查并添加，生成公共子集。然后我们只是重复其他几代人。

通过以这种方式删除重复的子集，我们不必继续将重复项与集合的其余部分组合，也不必继续检查它们是否有冲突，也不必对它们求和。最重要的是，通过不创建非唯一的新子集，我们不会从它们生成新子集，我相信这可以将算法从 NP 转变为 P，因为子集的增长不再是指数级的——我们丢弃它们中的绝大多数在它们可以在下一代中“复制”并通过与其他非重复子集组合来创建更多子集之前。

我认为我没有很好地解释这一点。我有照片……它们在我的脑海里。重要的是，通过丢弃重复的子集，您几乎可以消除所有的复杂性。

例如，想象一下（因为我是手工做这个例子）一个简单的数据集，它从 -7 到 7（不是零），我们的目标是零。排序和拆分，所以我们剩下 (1, 2, 3, 4, 5, 6, 7)。总和是 28。但 2^7 是 128。所以 128 个子集适合 1 .. 28 的范围，这意味着我们事先知道 100 个集合是重复的。如果我们有 8 个，那么我们将只有 36 个插槽，但现在有 256 个子集。所以你可以很容易地看到，现在被骗的数量是 220，是以前的两倍多。

在这种情况下，第一代的值为 1, 2, 3, 4, 5, 6, 7, 28, 27, 26, 25, 24, 23, 22, 21，我们将它们映射到它们的组成部分，所以

现在要生成新的子集，我们依次获取每个子集并将其添加到彼此的子集中，除非它们具有相互子集，例如 28 和 27 具有hueg 相互子集。因此，当我们取 1 并将其添加到 2 时，我们得到 3 = { 1, 2 } 但请等待！它已经在数组中。这意味着我们现在不会将 1 添加到任何已经包含 2 的子集中，反之亦然，因为这是 3 的子集的重复。

现在我们有

现在我们将 2 添加到所有。

3?

如您所见，即使我每次都在添加新的子集，但数量只是线性增加。

4？

5?

现在我们有了范围内的每个值，所以我们停下来，将 1-28 添加到我们的列表中。对负数重复，遍历列表。

编辑：

在任何情况下，这个算法都是完全错误的。具有重复总和的子集不是出于可以从中派生子集的目的的重复，因为它们的到达方式不同——即它们不能被折叠。

我有一个多项式 P，我想找到 y 使得 P(y) = 0 模 2^r。

我已经尝试过类似 Hensel 提升的方法，但我不知道这是否可行，因为通常情况 f'(y mod 2) != 0 mod 2 这通常不是真的。

有不同的算法可用吗？或者 Hensel 升降机的变体可以工作吗？

提前致谢

我有方程 y = 3(x+1)^2 + 5(x+1)^4。

使用霍纳的方案，我可以以这种形式评估这个多项式，y = 8+x(26+x(33+x(20+5x)))，因此需要 8 次算术运算。

我也可以用这种形式评估它，y = (x+1)^2 * ((5x+10)x+8)，需要 7 次操作。

有人告诉我这可以在 5 次操作中完成，但霍纳的算法应该是最有效的，它只能在 7 次操作中完成。我错过了什么吗？

我已经阅读了这个问题的答案，它们很有帮助，但我需要帮助。

我在 R 中有一个示例数据集，如下所示：

我想为这些数据拟合一个模型，以便y = f(x). 我希望它是一个三阶多项式模型。

我怎么能在 R 中做到这一点？

此外，R 可以帮助我找到最合适的模型吗？

我需要一些指针来为 3 维点编写多项式回归例程（即找到适合一定数量的 3D 点的 X 阶多项式的系数）。

我找到了二维多项式回归的代码，但是，我需要考虑第三维。

我正在寻找代码示例和/或解释。

我只是想知道最好的在线脚本语言用于“简单”数学计算，例如求解 2 次 3 次或 4 次多项式的根。

例如，创建一个小网络“小程序”，就像在这里找到的那​​样，它将输入的值插入到文本框中，并将它们作为变量输入“二次方程”并求解两个 x 值。

纯 JavaScript 是最好的脚本语言吗？IMO，这真的没有必要成为服务器端。

我正在尝试做一些“复杂”的数学运算，我需要调用一些 JavaScript 的数学属性来求解二次方程。以下方法有效吗？

这看起来正确吗？

出于某种原因，我没有看到正确的结果..

inputa, inputb, 和inputc都是存储来自文本字段的用户输入的变量。

完整代码

人们会期望并希望，如果您要求Mathematica找到多项式的根，它应该给出相同（近似）的答案，无论您是象征性地执行此操作，然后找到这些确切答案的数值近似值，还是您是否以数字方式执行此操作。这是一个示例，它（在Mathematica 7OS X 上运行）严重失败：

（注意：这实际上是一个 Laurent 多项式，如果你乘以一个很大的幂，q问题就消失了。）

这里的最后一行只是证明找到的解决方案非常不同；事实上，这是我们试图在我们正在研究的问题中计算的数量。

如果您仔细查看 和 的输出NSolve[poly == 0, q]，N[Solve[poly == 0, q]您会发现 NSolve 只给出54根而不是预期的56. 这并不是说它只是错过了重复的根或任何东西；它缺少两个最大的量级根（大约+/- 1.59）

这是 Mathematica 中的错误吗？有没有人解释为什么会这样？