HDU.2899.Strange fuction(牛顿迭代)

$Description$

　　求函数$F(x)=6\times x^7+8\times x^6+7\times x^3+5\times x^2-y\times x$在$x\in \left[0,100\right]$时的最小值。

$Solution$

　　$x\geq 0$时$F(x)$为单峰凹函数，三分即可。

　　而且由此可知$F(x)$的导数应是单增的。函数最值可以转化为求导数零点问题，于是也可以二分求$F'(x)$的零点，或者用牛顿迭代求。

　　峰值函数最值也可以用模拟退火求。

　　练习下牛顿迭代。其它代码可以见这。

　　牛顿迭代：$$x=x_0-\frac{F(x_0)}{F'(x_0)}$$

　　对$F(x)$泰勒展开，$F(x)=F(x_0)+F'(x_0)(x-x_0)+\frac{F''(x_0)}{2!}(x-x_0)^2+\ldots+\frac{F^{(n)}(x_0)}{n!}(x-x_0)^n+R_n(x)$

　　为方便计算？只保留线性部分$F(x)=F(x_0)+F'(x_0)(x-x_0)$，令其等于$0$。

　　就可以得到$x=x_0-\frac{F(x_0)}{F'(x_0)}$

　　多次迭代、多次选取$x_0$即可。

//0MS	1628K

#include <cmath>

#include <cstdio>

#include <algorithm>

#define eps (1e-7)

double y;

inline double f(double x){

	return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*x*x-y*x;

}

inline double fd(double x){

	return 42*pow(x,6)+48*pow(x,5)+21*x*x+10*x-y;

}

inline double fdd(double x){

	return 252*pow(x,5)+240*pow(x,4)+42*x+10;

}

double Get_zero(double x)//求导函数零点

{

	double las=x+1;

	while(fabs(las-x)>eps) las=x, x=x-fd(x)/fdd(x);

	return x;

}

int main()

{

	int T; scanf("%d",&T);

	while(T--)

	{

		scanf("%lf",&y);

		double ans=1e15;

		for(int i=0; i<=100; i+=10) ans=std::min(ans,f(Get_zero(i)));

		printf("%.4lf\n",ans);

	}

	return 0;

}

巴特西

HDU.2899.Strange fuction(牛顿迭代)

\(Description\)

\(Solution\)

最新文章

热门文章