问题描述:
关于ACM多项式求根的算法求救!
我们题目要求精度是小数点后4位,输入多项式次数n和每项的系数c[i]和根的区间[a,b],求一个根出来.我的算法用牛顿迭代法写完了,但是就是会有误差啊,比如n=4,系数分别为1,4,6,4,1,在区间[-100,0]上,正确解是-1.0000,我的解是-1.0005.不知道该如何改进了.
/* 秦九韶算法 */
double qjs_value(int n,double c[],double x){
\x05int i;
\x05double value=c[n];
\x05for(i=n-1;i>=0;i--)
\x05 value=value*x+c[i];
\x05return value;
}
/* 求f(x) */
double fx(int n,double c[],double x){\x05
\x05return qjs_value(n,c,x);
}
/* 求f'(x) */
double dfx(int n,double c[],double x){\x05
\x05return qjs_value(n-1,c,x);
}
/* 求f''(x) */
double d2fx(int n,double c[],double x){\x05
\x05return qjs_value(n-2,c,x);
}
double Polynomial_Root(int n,double c[],double a,double b,double EPS){
\x05int i;
double x0,x1,fm;
double d[MAXN],e[MAXN];
//
for(i=0;i=EPS/10.0;){
\x05 x0=x1;
/* 判断x0是否是重根 */
\x05 if(fabs(dfx(n,d,x0))=ZERO)
\x05\x05\x05 do{
\x05\x05\x05\x05 x1=x0-fx(n,c,x0)*dfx(n,d,x0)/fm;
\x05\x05\x05\x05 fm=dfx(n,d,x1)*dfx(n,d,x1)-dfx(n,d,x1)*d2fx(n,e,x1);
\x05\x05\x05\x05 x0=x1;
\x05\x05\x05 }while(fabs(fm)>=ZERO);
\x05\x05\x05 return x1;
\x05 }
/* 如果x1不是重根 */
\x05 x1=x0-fx(n,c,x0)/dfx(n,d,x0);
\x05 }
return x1;
}
我们题目要求精度是小数点后4位,输入多项式次数n和每项的系数c[i]和根的区间[a,b],求一个根出来.我的算法用牛顿迭代法写完了,但是就是会有误差啊,比如n=4,系数分别为1,4,6,4,1,在区间[-100,0]上,正确解是-1.0000,我的解是-1.0005.不知道该如何改进了.
/* 秦九韶算法 */
double qjs_value(int n,double c[],double x){
\x05int i;
\x05double value=c[n];
\x05for(i=n-1;i>=0;i--)
\x05 value=value*x+c[i];
\x05return value;
}
/* 求f(x) */
double fx(int n,double c[],double x){\x05
\x05return qjs_value(n,c,x);
}
/* 求f'(x) */
double dfx(int n,double c[],double x){\x05
\x05return qjs_value(n-1,c,x);
}
/* 求f''(x) */
double d2fx(int n,double c[],double x){\x05
\x05return qjs_value(n-2,c,x);
}
double Polynomial_Root(int n,double c[],double a,double b,double EPS){
\x05int i;
double x0,x1,fm;
double d[MAXN],e[MAXN];
//
for(i=0;i=EPS/10.0;){
\x05 x0=x1;
/* 判断x0是否是重根 */
\x05 if(fabs(dfx(n,d,x0))=ZERO)
\x05\x05\x05 do{
\x05\x05\x05\x05 x1=x0-fx(n,c,x0)*dfx(n,d,x0)/fm;
\x05\x05\x05\x05 fm=dfx(n,d,x1)*dfx(n,d,x1)-dfx(n,d,x1)*d2fx(n,e,x1);
\x05\x05\x05\x05 x0=x1;
\x05\x05\x05 }while(fabs(fm)>=ZERO);
\x05\x05\x05 return x1;
\x05 }
/* 如果x1不是重根 */
\x05 x1=x0-fx(n,c,x0)/dfx(n,d,x0);
\x05 }
return x1;
}
问题解答:
我来补答展开全文阅读