3

我正在尝试实现寻根算法。我正在使用在数值配方中找到的混合 Newton-Raphson 算法，效果非常好。但是我在括号中遇到了问题。

在实现求根算法时，我意识到在某些情况下，我的函数有 1 个实根和所有其他虚根（其中几个，通常为 6 或 9 个）。我感兴趣的唯一根源是真正的根源，所以问题不存在。问题是该函数像三次函数一样接近根，与 y=0 轴的点接触......

Newton-Rapson 方法需要一些不同符号的括号，而我发现的所有括号方法都不适用于这种特定情况。

我能做些什么？在我的程序中找到那个根非常重要......

编辑：更多问题：有时由于真的很小的数值错误，比如说1e-6“三次”函数的某个值的变化没有那个真正的根，它只是一个可忽略的虚数部分的虚数......（用matlab检查）

编辑2：有关该问题的更多信息。

好的，我需要寻根算法。

我有的信息：

  • 我需要找到的根在 [0-1] 之间，如果在该部分之外还有更多根，我对它们不感兴趣。
  • 根是真实的，可能有虚构的根，但我不想要它们。
  • 可能所有其余的根都将是虚构的
  • 在那一点上，根可能是双倍的，但我认为这实际上与数值分析问题无关
  • 在整个计算过程中，我需要多次使用求根算法，但函数始终是多项式
  • 在求根的一种特殊情况下，我的多项式将类似于使 Y=0 与该点接触的二次函数。一个真实案例的例子： 在此处输入图像描述
  • 该系数可能不是 100% 精确的，并且真正轻微的不精确可能会使函数不接触 Y=0 轴。
  • 我无法解决这种特定情况，因为在其他情况下，多项式可能非常正常并且不会产生任何“奇怪”的事情。
  • 我实际使用的方法是 NewtonRaphson 混合，如果导数非常小，它会进行二等分而不是 NewRaph（在数值配方中找到）。

Matlab对图像上的函数的回答：roots：

0.853553390593276 + 0.353553390593278i
0.853553390593276 - 0.353553390593278i
0.146446609406726 + 0.353553390593273i
0.146446609406726 - 0.353553390593273i
0.499999999999996 + 0.000000040142134i
0.499999999999996 - 0.000000040142134i

该函数是我准备的一个真实示例，我知道我想要的答案是0.5

注意：我还没有完全检查你们给我的一些答案（谢谢！），我只是想提供我已经完成问题的所有信息。

4

6 回答 6

3

假设您有一个一维多项式问题（我从想象的解决方案中假设），您可以使用 Sturm 序列将所有实根括起来。参见Sturm 定理。

于 2012-10-10T14:53:52.790 回答
2

欢迎来到数值方法的奇妙世界。注意你的发际线；当你沮丧地拔出头发时，它可能会开始消退。

首先，通过数字根查找，如果你不能解决问题，你就完蛋了。一旦接近，Newton Raphson 非常适合完善解决方案，并且它仅在根附近的导数远离零时才有效。您总是需要手头有一些较慢的技术作为备用，因为 Newton Raphson 可以将您送至永无止境的地方（即，在支架之外的某个地方）。如果你的函数不是多项式，首先要尝试的是布伦特方法。如果您的函数是多项式，请尝试 Laguerre 方法或 Jenkins-Traub。

顺便说一句，听起来你有病态问题。你不应该期望特别好的性能。病态问题是病态的。

附录
如果您对看似是根但不是根的事物有问题，您需要注意如何评估您的功能。如果确实有多项式，请形成多项式的每一项，按绝对值排序，然后将最小到最大相加。大多数情况下，这会产生更好的准确性，但如果您有总和几乎为零的大项，则会失败。如果是这种情况，您可能希望单独添加这些取消项，将其余的最小添加到最大，然后计算总计 - 您仍然有点搞砸了。几乎取消的那个大加法会损失很多精度。除了扩展精度算术之外，别无他法。

于 2012-10-10T15:36:58.203 回答
1

使用 Newton-Raphson 是一种绝望的行为。你最好找到代表你的函数的连分数并计算它。CF 会收敛得更快，并且会产生真正的根。此外，由于 CF 产生两个整数的比率，因此您可以严格控制数值精度，而不必担心舍入误差的累积和其他类似的拔毛问题。

要找到任何多项式函数的实根，请参阅 David Rosen (1978) 的“A Continued Fraction Algorithm for Approximating All Real Polynomial Roots”。

------------ 附录 1 --- 10 月 11 日-----

好的，你正在解决一个性问题。你有几个选择。最简单的方法是将泰勒近似（比如 3 阶）与哈雷方法结合使用。这比牛顿要好得多，因为它具有三次收敛性，并且您可以检测虚构的解决方案。缺点是你会遇到四舍五入的问题，这可能会导致错误的答案。

理想的选择是找到表示一元根的连分数，因为这个 CF 可以计算为任何所需精度的整数比，从而消除了舍入问题。

计算该 CF 的一种方法是通过 Jacobi-Perron 算法。请参阅论文 Hendy 和牛仔裤：http ://www.ams.org/mcom/1981-36-154/S0025-5718-1981-0606514-X/S0025-5718-1981-0606514-X.pdf 。本文展示了通过 CF 近似计算三次根和四次根的精确算法。

请注意，如果六分法是可约的，那么它可以转换为四次和二次：http ://elib.mi.sanu.ac.rs/files/journals/tm/21/tm1124.pdf 。然后可以通过 Hendy 论文中的算法求解四次。

可以通过 Rogers-Ramunajan CF 来为六分仪生成 CF 的一般解决方案。该方法参见以下论文：http: //arxiv.org/pdf/1111.6023v2。这将为任何性别生成 CF。

于 2012-10-10T15:20:30.030 回答
1

好吧，如果您的函数触及零但从未超过它，那么您似乎正在寻找最小值（或最大值）。在这种情况下，你最好告诉计算机去做——要么找到导数的根（如果你可以分析地计算它），或者使用最小化例程。然后检查最小值处的函数值是否“足够接近”为零。

只是重申其他人已经说过的话：

  • 不要从 Newton-Raphson 方法开始；从布伦特甚至直接二分法开始几乎总是更好（前提是您可以将根括起来）。
  • 1e-6 量级的“小数值误差”会产生不良影响的不稳定性值得研究。直接怀疑：混合浮点数和双精度数，某处精度损失等。

编辑：因此，根据某些参数，您的函数要么有零交叉，要么具有零值的最小值，这是正确的吗？在这种情况下，我要做的是：使用简单而强大的包围策略（例如，从 开始[-1, 1]，将端点乘以1.1，检查符号，继续相乘，类似这样）。如果成功，则存在过零，请使用寻根例程。如果包围失败，请使用最小化。

于 2012-10-10T16:19:53.647 回答
1

安德，感谢您回答我的问题（关于间隔）；很抱歉延迟跟进 - 我的工作很忙。另外-在我找到您提供的其他信息之前-我想解释很多如何处理这个问题，并且正在考虑如何呈现它。但是，我现在相信您的情况并不太难，我们可以在没有太多额外内容的情况下解决它，因为您显然有一个明确的多项式表达式（各种幂的系数）。

让我们从一个简单的案例开始，来确定方法。

步骤 1。如果您有一个 2 次多项式，它的导数是一阶的并且有一个简单的零（您可以通过括号或简单地通过显式求解方程来找到它）。（是的，我知道二次多项式的根也有一个封闭公式，但为了当前的论点，让我们忘记这一点）。然后，二次多项式的零位于导数零的左侧和右侧。因此，如果您还有要找到原始函数（二次多项式）的根的区间，那么您现在有两个区间 - 导数零的左侧和右侧，每个区间都有一个零。

重要的是要认识到原始函数在每个子区间上都是单调的（其中一个减少，另一个增加）。因此，只需检查（子）区间末尾的函数值，您就可以确定它们是否实际上将零括起来。如果不是，则在导数的零处恰好有多个零（在这种情况下为双），如果函数在那里为零（否则，它是一个双虚根，您现在已经找到了实部）。

如果导数的零位于总区间之外，则区间内最多有一个根，并且您只需要检查那个特定的（子）区间。

步骤 2. 现在考虑一个三阶多项式。它的导数是二阶的。那个二阶多项式的导数又是一阶的，你像以前一样继续得到两个子区间来找到原始函数的导数的根。这两个根为您提供三个（最多）间隔，您将在其中找到原始（三阶）函数的 3 个根。同样在这里，您将有区间 (3)，其中原始函数是单调的（交替增加/减少），使得每个子区间的分析非常容易。

同样，零可能重合（2 个或什至全部 3 个）并且可能另外变成复值（即具有非零虚部）。案例分析很简单：检查区间边界处的函数值，以评估是否存在符号变化（函数在每个子区间上是单调的）和/或函数在子区间边界之一处是否为零。

步骤 4. 用已知多项式对此进行推广。比方说 - 你的例子 - 它是 6 阶：

a) 构造五阶导数（即将原始多项式简化为一阶多项式）。计算它为零（在您的示例中恰好为 0.5）。在这种情况下，您已经完成了，但假设您没有意识到这一点。所以你现在有 2 个区间 0..0.5 和 0.5..1

b) 构造四阶导数。检查其在子区间边界 (0, 0.5, 1) 处的值 对于每个子区间，确定其内部是否有实零。如果是这样，您使用找到的两个零（您忘记了五阶导数的零）将原始区间重新划分为 3 个子区间。如果它们重合（在上一次切割中，0.5），您坚持使用 0.5（不管您是否在那里找到了四阶导数的真正双零或“双虚数”）并且仍然只有 2 个间隔，但是为了争论，假设你现在有 3 个。

c) 构造三阶导数并像以前一样做。然后，您将有 4 个（最多）间隔。

d) 等等。以这种方式处理二阶导数后，您有 5 个（最多）区间，在处理一阶导数后，您有 6 个区间（或更少......）并且知道函数在每个子区间上是单调的，您将快速确定如果有一个真正的根，那么在它们中的每一个中，总是使用每个最终子区间中函数的已知单调性。

在评估函数时添加关于数值准确性的注释：减少噪声的第一个（在这种情况下可能足够）方法不是以原始形式建议的方式评估您的函数（即 a6 x *6 + a5 x *5 +..)，但将其重写为：

a0 + x*(a1 + x*(a2 + x*(a3 + x*(a4 + x*(a5 + x*a6)))))

所以，在评估你继续：

tmp = a6

tmp = x*tmp + a5

tmp = x*tmp + a4

等等。

如果这个小小的重写不足以保持数值稳定性，你应该用（例如）切比雪夫多项式展开式重写你的多项式，并用它的递归关系来评估它。两者（获得扩展和应用递归关系进行评估）都相当简单。如果您需要帮助，我可以解释，但我想这里没有必要。

在所有情况下，您都必须允许一些不准确性，即接受计算通常不会给您数学上精确的函数值。所以评估函数是否在某个点可能为零必须包括一些“容差”，不幸的是，没有办法解决这个问题；您可以达到的最佳目标是尽量减少噪音。

于 2012-10-11T20:56:22.250 回答
1

与您的情况一样，您对实数多项式的实数分解感兴趣。人们可能会看到所有复数根都以共轭对形式出现，它们对应于一个实数二次因子。通过找到这个实数二次方并完成平方得到表格(x-r)^2 + s，您将能够看到“实数”偶数阶根r，并带有由 给出的“错误” s。如果s > 0太大，您可以将其丢弃，因为它可能很复杂。如果s < 0也很大，那么您有两个由 给出的遥远实根x = r ± √(-s)。如果s非常小，那么您可能会怀疑r是真正的双根并保留它。

可以使用Bairstow 方法找到这样的二次因子，该方法实际上应用了二维牛顿法。这给出x^2 + ux + v和r = -u/2; s = v - r^2。

于 2020-09-27T03:07:02.880 回答