作业帮关于ACM多项式求根的算法求救!我们题目要求精度是小数点后4位,输入多项式次数n和每项的系数c[i]和根的区间[a,b],求一个根出来.我的算法用牛顿迭代法写完了,但是就是会有误差啊,比如n=4,系
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/01 00:31:18
![关于ACM多项式求根的算法求救!我们题目要求精度是小数点后4位,输入多项式次数n和每项的系数c[i]和根的区间[a,b],求一个根出来.我的算法用牛顿迭代法写完了,但是就是会有误差啊,比如n=4,系](/uploads/image/z/5175227-11-7.jpg?t=%E5%85%B3%E4%BA%8EACM%E5%A4%9A%E9%A1%B9%E5%BC%8F%E6%B1%82%E6%A0%B9%E7%9A%84%E7%AE%97%E6%B3%95%E6%B1%82%E6%95%91%21%E6%88%91%E4%BB%AC%E9%A2%98%E7%9B%AE%E8%A6%81%E6%B1%82%E7%B2%BE%E5%BA%A6%E6%98%AF%E5%B0%8F%E6%95%B0%E7%82%B9%E5%90%8E4%E4%BD%8D%2C%E8%BE%93%E5%85%A5%E5%A4%9A%E9%A1%B9%E5%BC%8F%E6%AC%A1%E6%95%B0n%E5%92%8C%E6%AF%8F%E9%A1%B9%E7%9A%84%E7%B3%BB%E6%95%B0c%5Bi%5D%E5%92%8C%E6%A0%B9%E7%9A%84%E5%8C%BA%E9%97%B4%5Ba%2Cb%5D%2C%E6%B1%82%E4%B8%80%E4%B8%AA%E6%A0%B9%E5%87%BA%E6%9D%A5.%E6%88%91%E7%9A%84%E7%AE%97%E6%B3%95%E7%94%A8%E7%89%9B%E9%A1%BF%E8%BF%AD%E4%BB%A3%E6%B3%95%E5%86%99%E5%AE%8C%E4%BA%86%2C%E4%BD%86%E6%98%AF%E5%B0%B1%E6%98%AF%E4%BC%9A%E6%9C%89%E8%AF%AF%E5%B7%AE%E5%95%8A%2C%E6%AF%94%E5%A6%82n%3D4%2C%E7%B3%BB)
关于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法比较好,二分法的全局收敛性比较可靠.对于根附近导数较小的情形（比如重根）也是二分法数值上比较稳定.
再有就是你的编程习惯不太好,循环的初始化可以改进,也要注意避免不必要的多项式求值操作.