关于ACM多项式求根的算法求救!我们题目要求精度是小数点后4位,输入多项式次数n和每项的系数c[i]和根的区间[a,b],求一个根出来.我的算法用牛顿迭代法写完了,但是就是会有误差啊,比如n=4,系
来源:学生作业帮助网 编辑:作业帮 时间:2024/09/01 10:23:17
关于ACM多项式求根的算法求救!我们题目要求精度是小数点后4位,输入多项式次数n和每项的系数c[i]和根的区间[a,b],求一个根出来.我的算法用牛顿迭代法写完了,但是就是会有误差啊,比如n=4,系
关于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;
}
关于ACM多项式求根的算法求救!我们题目要求精度是小数点后4位,输入多项式次数n和每项的系数c[i]和根的区间[a,b],求一个根出来.我的算法用牛顿迭代法写完了,但是就是会有误差啊,比如n=4,系
处理重根部分的代码有问题,一来停机准则不对,二来f'f'-ff''也写错了.
如果一定要处理重根,可以先用辗转相除法把f和f'的最大公因子算出来,然后对f/(f,f')求根就行了,这样不会有重根.
另外,可以先用二分法把区间缩小,区间长度小于1的时候再用Newton法比较好,二分法的全局收敛性比较可靠.对于根附近导数较小的情形(比如重根)也是二分法数值上比较稳定.
再有就是你的编程习惯不太好,循环的初始化可以改进,也要注意避免不必要的多项式求值操作.