关于ACM多项式求根的算法求救!

问题描述:

关于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;
}
1个回答 分类:综合 2014-11-21

问题解答:

我来补答
处理重根部分的代码有问题,一来停机准则不对,二来f'f'-ff''也写错了.
如果一定要处理重根,可以先用辗转相除法把f和f'的最大公因子算出来,然后对f/(f,f')求根就行了,这样不会有重根.
另外,可以先用二分法把区间缩小,区间长度小于1的时候再用Newton法比较好,二分法的全局收敛性比较可靠.对于根附近导数较小的情形(比如重根)也是二分法数值上比较稳定.
再有就是你的编程习惯不太好,循环的初始化可以改进,也要注意避免不必要的多项式求值操作.
再问: 重根部分可以帮我修改么?我觉得我没有错呀。。 牛顿法要是发现dfx趋向于0,就要用二阶的公式了,一直计算到二阶公式的分母也就是fm=dfx*dfx-dfx*d2fx趋向于0为止。书上是这样写的。。。那我应该怎么改啊
再答: 你不能只会抄书,要自己知道原理。 你写的-ff'/(f'f'-f'f'')明显是错误的,如果真是这样为什么不把f'约去呢? 二阶Newton法的增量应该是-ff'/(f'f'-ff''/2),如果是对f/f'用普通Newton法得到的分母也应该是f'f'-ff''。但是不论使用哪种修改方式,以分母小作为停机准则都是不对的,前者不足以应对三阶以上零点,后者则本身就是无穷小量。 不管怎么说,高阶零点的求解总是困难的,你可以按我说的,先把最大公因子除掉,然后再用Newton法解,这时候就不需要处理重根了。
 
 
展开全文阅读
剩余:2000
上一页:减术分裂
下一页:语文学习与巩固
也许感兴趣的知识