多项式求根的算法和程序

发布网友发布时间：2022-04-27 00:32

共4个回答

热心网友时间：2022-06-21 18:28

这题可以用二分法步进试探求解。当然这里说的二分法不是像谭浩强书上的那么简单明了,不是一个f(x1)*f(x2)<0就可以确定的。因为他举例子是在一个单调区间求根，而这里是要求出所有解，区间不一定是单调的。上次我发了一个类似的程序有人评价说不好，那不过是他根本没理解非单调区间找出所有根和单调区间找一个根难度根本不可比较，说明他根本没理解算法目的。

这里的思路是先定一个区间[a,b]然后从a开始以步长h在[a,a+h]内搜索是否有根，然后[a+h,a+2*h],直到区间右端到达b为止。a,b如何大概确定？可以利用高等数学中的高阶导数求出多项式何时恒为正或恒为负决定，这个不难。显然a,b的区间越小程序执行越快。所以a,b尽量定准确一些。程序中定得比较大[-100,150],实际改得越精确越好，当然不能漏根。同时h越小计算时间越长，但是结果精度越高，所以取值要以程序要求的精确度和执行时间综合考虑，这里取0.1。

同时为了提高计算速度，使用了著名的霍纳求值法。即求3x^3-5x^2+x+1转化为求((3x-5)x+1)x+1,因为第一种求法要做7次乘法而带括号的求法只用做3次乘法。当然如果多项式函数是奇函数或偶函数还可以简化[a,b]区间。
程序中设定了一个多项式，实际更改为所求多项式即可。
一个完整的c程序如下,程序在win-tc和Dev-c++下都调试通过。
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

double Equation(double x)
{
double z;
z=(((((x-5.0)*x+3.0)*x+1.0)*x-7.0)*x+7.0)*x-20.0;/*更改为实际多项式*/
return(z);
}

int BinSearchRoot(double a,double b,double h,double eps,double x[],int m) /*用二分法计算非线性方程的实根*/
/*参数意义：
a 要求的根的下界
b 要求的根的上界，即：所求的根落在区间 [a,b]之内
h 递进的步长
eps 精度
x 根的值
m 预计的根的个数*/
{
int n,js;
double z,y,z1,y1,z0,y0;
n=0; z=a; y=Equation(z);
while ((z<=b+h/2.0)&&(n!=m)) /*对给定步长的子区间进行搜索*/
{
if (fabs(y)<eps) /*当前的判定点是方程的根*/
{
n=n+1;
x[n-1]=z;
z=z+h/2.0;
y=Equation(z);
}
else /*当前点不是方程的根*/
{
z1=z+h;
y1=Equation(z1);
if (fabs(y1)<eps) /*下一个点是方程的根*/
{
n=n+1;
x[n-1]=z1;
z=z1+h/2.0;
y=Equation(z);
}
else if (y*y1>0.0) /*该区间内无根*/
{ y=y1; z=z1;}
else /*该区间内有根*/
{
js=0;/*标志，0表示未找到根，1表示已经确定了根*/
while (js==0)
{
if (fabs(z1-z)<eps) /*区间的长度小于给定的精度，可以当作已经找到了根*/
{
n=n+1;
x[n-1]=(z1+z)/2.0; /*把区间的中位值作为根*/
z=z1+h/2.0; /*把寻找的位置放到下一个区间内*/
y=Equation(z);
js=1; /*在当前区间内已经找到了根*/
}
else /*区间比给定的精度大，则进行二分*/
{
z0=(z1+z)/2.0; /*区间二分*/
y0=Equation(z0);
if (fabs(y0)<eps) /*z0位置为根*/
{
x[n]=z0;
n=n+1;
js=1;
z=z0+h/2.0;
y=Equation(z);
}
else if ((y*y0)<0.0) /*[z,z0]内有根*/
{ z1=z0; y1=y0;}
else { z=z0; y=y0;}
}
}
}
}
}
return(n); /*返回根的个数*/
}

int main()
{
int i,n;
static int m=6;
static double x[6];
system("cls");
printf("\nThe Nonlinear function is:\n");
printf("\nf(x)=(((((x-5.0)*x+3.0)*x+1.0)*x-7.0)*x+7.0)*x-20.0\n"); /*更改为实际多项式*/
n=BinSearchRoot(-100.0,150.0,0.1,0.000001,x,m);
printf("\nThe function has %d roots, they are:\n",n);/*输出根的个数*/
for (i=0; i<=n-1; i++)
printf("x(%d)=%10.7f\n",i,x[i]);
system("pause");
return 0;
}

后记:百度是个比较浮躁的地方，个别人说三道四，我一笑了之。真正正确的东西他理解不了，只能说明他还没达到那个层次，要从自身找原因。

显然二分法是不能解决虚根问题的。

参考资料：http://zhidao.baidu.com/question/85631748.html

热心网友时间：2022-06-21 18:28

热心网友时间：2022-06-21 18:29

赚积分

热心网友时间：2022-06-21 18:30

这题可以用二分法步进试探求解。当然这里说的二分法不是像谭浩强书上的那么简单明了,不是一个f(x1)*f(x2)<0就可以确定的。因为他举例子是在一个单调区间求根，而这里是要求出所有解，区间不一定是单调的。上次我发了一个类似的程序有人评价说不好，那不过是他根本没理解非单调区间找出所有根和单调区间找一个根难度根本不可比较，说明他根本没理解算法目的。
这里的思路是先定一个区间[a,b]然后从a开始以步长h在[a,a+h]内搜索是否有根，然后[a+h,a+2*h],直到区间右端到达b为止。a,b如何大概确定?可以利用高等数学中的高阶导数求出多项式何时恒为正或恒为负决定，这个不难。显然a,b的区间越小程序执行越快。所以a,b尽量定准确一些。程序中定得比较大[-100,150],实际改得越精确越好，当然不能漏根。同时h越小计算时间越长，但是结果精度越高，所以取值要以程序要求的精确度和执行时间综合考虑，这里取0.1。
同时为了提高计算速度，使用了著名的霍纳求值法。即求3x^3-5x^2+x+1转化为求((3x-5)x+1)x+1,因为第一种求法要做7次乘法而带括号的求法只用做3次乘法。当然如果多项式函数是奇函数或偶函数还可以简化[a,b]区间。
程序中设定了一个多项式，实际更改为所求多项式即可。
一个完整的c程序如下,程序在win-tc和Dev-c++下都调试通过。
#include
<math.h>
#include
<stdio.h>
#include
<stdlib.h>
double
Equation(double
x)
{
double
z;
z=(((((x-5.0)*x+3.0)*x+1.0)*x-7.0)*x+7.0)*x-20.0;/*更改为实际多项式*/
return(z);
}
int
BinSearchRoot(double
a,double
b,double
h,double
eps,double
x[],int
m)
/*用二分法计算非线性方程的实根*/
/*参数意义:
a
要求的根的下界
b
要求的根的上界，即:所求的根落在区间
[a,b]之内
h
递进的步长
eps
精度
x
根的值
m
预计的根的个数*/
{
int
n,js;
double
z,y,z1,y1,z0,y0;
n=0;
z=a;
y=Equation(z);
while
((z<=b+h/2.0)&&(n!=m))
/*对给定步长的子区间进行搜索*/
{
if
(fabs(y)<eps)
/*当前的判定点是方程的根*/
{
n=n+1;
x[n-1]=z;
z=z+h/2.0;
y=Equation(z);
}
else
/*当前点不是方程的根*/
{
z1=z+h;
y1=Equation(z1);
if
(fabs(y1)<eps)
/*下一个点是方程的根*/
{
n=n+1;
x[n-1]=z1;
z=z1+h/2.0;
y=Equation(z);
}
else
if
(y*y1>0.0)
/*该区间内无根*/
{
y=y1;
z=z1;}
else
/*该区间内有根*/
{
js=0;/*标志，0表示未找到根，1表示已经确定了根*/
while
(js==0)
{
if
(fabs(z1-z)<eps)
/*区间的长度小于给定的精度，可以当作已经找到了根*/
{
n=n+1;
x[n-1]=(z1+z)/2.0;
/*把区间的中位值作为根*/
z=z1+h/2.0;
/*把寻找的位置放到下一个区间内*/
y=Equation(z);
js=1;
/*在当前区间内已经找到了根*/
}
else
/*区间比给定的精度大，则进行二分*/
{
z0=(z1+z)/2.0;
/*区间二分*/
y0=Equation(z0);
if
(fabs(y0)<eps)
/*z0位置为根*/
{
x[n]=z0;
n=n+1;
js=1;
z=z0+h/2.0;
y=Equation(z);
}
else
if
((y*y0)<0.0)
/*[z,z0]内有根*/
{
z1=z0;
y1=y0;}
else
{
z=z0;
y=y0;}
}
}
}
}
}
return(n);
/*返回根的个数*/
}
int
main()
{
int
i,n;
static
int
m=6;
static
double
x[6];
system("cls");
printf("\nThe
Nonlinear
function
is:\n");
printf("\nf(x)=(((((x-5.0)*x+3.0)*x+1.0)*x-7.0)*x+7.0)*x-20.0\n");
/*更改为实际多项式*/
n=BinSearchRoot(-100.0,150.0,0.1,0.000001,x,m);
printf("\nThe
function
has
%d
roots,
they
are:\n",n);/*输出根的个数*/
for
(i=0;
i<=n-1;
i++)
printf("x(%d)=%10.7f\n",i,x[i]);
system("pause");
return
0;
}
后记:百度是个比较浮躁的地方，个别人说三道四，我一笑了之。真正正确的东西他理解不了，只能说明他还没达到那个层次，要从自身找原因。
显然二分法是不能解决虚根问题的。

全部栏目

多项式 求根的算法和程序

多项式求根的算法和程序