多项式最小不动点的高效计算
令 P(x) 表示所讨论的多项式。 P 的最小不动点 (LFP) 是 x 的最小值，使得 x=P(x)。多项式具有实数系数。一般来说，不能保证 LFP 会存在，尽管如果次数为奇数且 ≥ 3，则保证存在 LFP。如果次数为 3，我知道一个有效的解决方案。x=P(x) 因此 0=P( x)-x。有一个封闭形式的三次公式，求解 x 有点微不足道，可以硬编码。 2 级和 1 级同样容易。我遇到麻烦的是更复杂的情况，因为我似乎无法为任意程度提出一个好的算法。
编辑：
我只考虑真正的不动点并取其中最少的，不一定是绝对值最小的不动点。
Let P(x) denote the polynomial in question. The least fixed point (LFP) of P is the lowest value of x such that x=P(x). The polynomial has real coefficients. There is no guarantee in general that an LFP will exist, although one is guaranteed to exist if the degree is odd and ≥ 3. I know of an efficient solution if the degree is 3. x=P(x) thus 0=P(x)-x. There is a closed-form cubic formula, solving for x is somewhat trivial and can be hardcoded. Degrees 2 and 1 are similarly easy. It's the more complicated cases that I'm having trouble with, since I can't seem to come up with a good algorithm for arbitrary degree.
EDIT:
I'm only considering real fixed points and taking the least among them, not necessarily the fixed point with the least absolute value.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
只需使用您最喜欢的数值方法求解
f(x) = P(x) - x即可。例如，您可以迭代您通常找不到封闭式公式，因为 没有任何五次和更高多项式的封闭式公式。因此，对于五次及更高次数，您必须使用某种数值方法。
Just solve
f(x) = P(x) - xusing your favorite numerical method. For example, you could iterateYou won't find closed-form formula in general because there aren't any closed-form formula for quintic and higher polynomials. Thus, for quintic and higher degree you have to use a numerical method of some sort.
由于您想要最小不动点，因此如果不找到 P(x) - x 的所有实根并选择最小的根，就无法逃脱。
找到多项式的所有根是一个棘手的问题。如果您有黑盒例程，请务必使用它。否则，请考虑以下技巧：
，但这需要您能够访问用于查找特征值的例程（这是另一个棘手的问题，但有很多好的库）。
否则，您可以实现 Jenkins-Traub 算法，这是一种高度一段不平凡的代码。
我真的不建议找到一个零（例如牛顿法）和放气直到你达到了一级：如果做得不好，它会非常不稳定，并且你会失去很多准确性（并且用它来处理多个根是非常困难的）。正确的做法实际上是上面提到的 Jenkins-Traub 算法。
Since you want the least fixed point, you can't get away without finding all real roots of P(x) - x and selecting the smallest.
Finding all the roots of a polynomial is a tricky subject. If you have a black box routine, then by all means use it. Otherwise, consider the following trick:
but this requires you have access to a routine for finding eigenvalues (which is another tricky problem, but there are plenty of good libraries).
Otherwise, you can implement the Jenkins-Traub algorithm, which is a highly non trivial piece of code.
I don't really recommend finding a zero (with eg. Newton's method) and deflating until you reach degree one: it is very unstable if not done properly, and you'll lose a lot of accuracy (and it is very difficult to tackle multiple roots with it). The proper way do do it is in fact the above-mentioned Jenkins-Traub algorithm.
这个问题试图找到多项式的“最小”（这里我不确定你的意思是幅度还是实际上最小，这可能是最负的）根。对于大次多项式来说，没有封闭形式的解，但是有无数的数值方法可以求根。
通常情况下，维基百科是开始搜索的好地方。
如果你想找到最小的根，那么你可以使用符号规则来固定找到它存在的区间，然后使用某种数值方法在该区间中找到根。
This problem is trying to find the "least" (here I'm not sure if you mean in magnitude or actually the smallest, which could be the most negative) root of a polynomial. There is no closed form solution for polynomials of large degree, but there are myriad numerical approaches to finding roots.
As is often the case, Wikipedia is a good place to begin your search.
If you want to find the smallest root, then you can use the rule of signs to pin down the interval where it exists and then use some numerical method to find roots in that interval.