多项式最小不动点的有效计算

Question

设P(x)表示所讨论的多项式.P的最小不动点(LFP)是x的最小值,使得x = P(x).多项式具有实系数.一般不能保证存在LFP,但如果度数是奇数且≥3,则保证存在LFP.如果度数为3,我知道有效的解决方案.x = P(x)因此0 = P( x)的-x.有一个封闭形式的立方公式,求解x有点微不足道,可以硬编码.度数2和1同样容易.这是我遇到麻烦的更复杂的情况,因为我似乎无法想出任意程度的好算法.

编辑:

我只考虑真正的固定点并且在它们中间取得最少,不一定是具有最小绝对值的固定点.

Answer 1

只需f(x) = P(x) - x使用您喜欢的数值方法解决.例如,您可以迭代

x_{n + 1} = x_n - P(x_n) / (P'(x_n) - 1).

一般情况下,您不会找到闭式公式,因为对于五次和更高次多项式没有任何闭式公式.因此,对于五次和更高的度数,你必须使用某种数值方法.

Answer 2

既然你想要最不固定的点,你就无法在没有找到P(x) - x的所有真实根并选择最小值的情况下逃脱.

找到多项式的所有根是一个棘手的主题.如果您有黑盒子例程,那么一定要使用它.否则,请考虑以下技巧:

• 形式M 是P(x) - x 的伴随矩阵
• 找到M的所有特征值

但这要求您可以访问查找特征值的例程(这是另一个棘手的问题,但是有很多好的库).

否则,您可以实现Jenkins-Traub算法,这是一个非常重要的代码片段.

我真的不建议找到一个零(用例如牛顿的方法)并放气直到达到一级:如果做得不好就会非常不稳定,你会失去很多准确性(并且很难解决)用它来多个根).这样做的正确方法实际上是上面提到的Jenkins-Traub算法.