问无图求多项式最大值/最小值的算法
EN

Stack Overflow用户

提问于 2014-01-26 18:32:38

回答 2查看 5.6K关注 0票数 0

对于形式为y=a*x^2+b*x+c的二次方程，最大/最小值出现在x=-b/2a处。对于高次多项式(x>=4)，有没有像这样的硬而快速的方程？对于这样的多项式，我在网上得到的解决方案建议绘制曲线并找到。如何在不作图的情况下求出绝对最大值？

polynomial-math

algorithm

math

algebra

1元体验云点播

覆盖建站/短视频等热门场景，提供媒资管理、短视频 SDK、小程序插件和播放器云+端一体化能力，助您抓住视频风口

回答 2

Stack Overflow用户

发布于 2014-01-26 18:42:20

如果你只处理多项式，那么你应该检查libmatheval。我不会详细介绍这背后的数学原理，也不会详细介绍所需的C代码，您可以在这里找到完整的参考here。然而，以下是该算法的草图：

将多项式解析成函数的导数，在指定的区间内用你喜欢的数值方法(可能是[MININT, MAXINT]或similar).

given

similar).
given
1. )，称其为f的零( g g of [MININT, MAXINT])。评估每个点的f。
2. 还评估在点3使用的搜索间隔的上界和下界的f。
3. 保留点4和5的最大值和最小值。这些值是绝对最大值和最小值。

特别是，第6点的声明得到了a theoretical proof的支持。

如果你考虑任何限制区间之外的多项式(即从-inf到+inf)，那么它们是无界的，因为它们的最大或最小(或两者)都是无穷大的。您可能对有限的max/min感兴趣(如果它们存在的话)。您可以检查max或min是否应该是无穷大的，但您不会从上面的算法中发现这一点，因为计算对值施加了一个数值界限：

如果多项式有奇数次，那么min = -inf和

多项式有偶数次，max和min之间的多项式是有限的。

票数 2

Stack Overflow用户

发布于 2014-01-26 18:47:55

您可以使用<=5次多项式的渐近，通过微分和求解等于0的梯度来解析地解决这个问题。

请注意，这将给出解决方案的几个潜在位置(包括最小值和最大值)，因此您必须评估潜在答案以找到实际的最大值。

例如，使用渐近，我们可以计算四次via的最大值的潜在位置：

from sympy import solve
from sympy.abc import a,b,c,d,e,x
f=a*x*x*x*x+b*x*x*x+c*x*x+d*x+e
A=solve(f.diff(x),x)
for sol in A:
    print sol

给出了3个可能的位置：

(((d/(4*a) - b*c/(8*a**2) + b**3/(32*a**3))**2/4 + (c/(6*a) - b**2/(16*a**2))**3)**(1/2) + d/(8*a) - b*c/(16*a**2) + b**3/(64*a**3))**(1/3)*(1/2 + I*3**(1/2)/2) - (c/(6*a) - b**2/(16*a**2))/((1/2 + I*3**(1/2)/2)*(((d/(4*a) - b*c/(8*a**2) + b**3/(32*a**3))**2/4 + (c/(6*a) - b**2/(16*a**2))**3)**(1/2) + d/(8*a) - b*c/(16*a**2) + b**3/(64*a**3))**(1/3)) - b/(4*a)

(((d/(4*a) - b*c/(8*a**2) + b**3/(32*a**3))**2/4 + (c/(6*a) - b**2/(16*a**2))**3)**(1/2) + d/(8*a) - b*c/(16*a**2) + b**3/(64*a**3))**(1/3)*(1/2 - I*3**(1/2)/2) - (c/(6*a) - b**2/(16*a**2))/((1/2 - I*3**(1/2)/2)*(((d/(4*a) - b*c/(8*a**2) + b**3/(32*a**3))**2/4 + (c/(6*a) - b**2/(16*a**2))**3)**(1/2) + d/(8*a) - b*c/(16*a**2) + b**3/(64*a**3))**(1/3)) - b/(4*a)

(c/(6*a) - b**2/(16*a**2))/(((d/(4*a) - b*c/(8*a**2) + b**3/(32*a**3))**2/4 + (c/(6*a) - b**2/(16*a**2))**3)**(1/2) + d/(8*a) - b*c/(16*a**2) + b**3/(64*a**3))**(1/3) - b/(4*a) - (((d/(4*a) - b*c/(8*a**2) + b**3/(32*a**3))**2/4 + (c/(6*a) - b**2/(16*a**2))**3)**(1/2) + d/(8*a) - b*c/(16*a**2) + b**3/(64*a**3))**(1/3)