确定特定范围内多项式的实根

Question

我是一个编程初学者，尤其是在java中，我已经尝试了很多次如何在给定范围内找到多项式的实数根。该程序应该找到用户提供的给定多项式的所有实数根。例如，程序应按以下方式运行：输入度数：3输入4个系数：-6 11-6 1输入左右端点：-10 10根在：1.00000根在：2.0000根在：3.00000。下面是我的节目格式。

import java.util.Scanner;
class Roots{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
double resolution=0.01;
double tolerance=0.0000001;
double threshold=0.001;
double roots;
System.out.print("Enter the degree: ");
int degree =sc.nextInt();
System.out.print("Enter "+(degree+1)+" coefficients: ");
double[] C=new double[degree+1];
for(int i=0; i<C.length;i++){
C[i]=sc.nextDouble();
}
System.out.print("Enter the left and right endpoints: ");
double a=sc.nextInt();
double b=sc.nextInt();
if(poly(C,a)*poly(C,b)<0){
roots=findRoot(C,a,b,tolerance);
}
}
}
static double poly(double[] C, double x){
int n=C.length-1;
int K;
double sum=0.0;
for(int i=0;i<n;i++){
sum+=C[i]*(Math.pow((x-i),n));
}
return sum;
}
static double[] diff(double[] C){
int n=C.length-1;
int K;
double[]D=new double[n];
for(int i=0;i<n;i++){
D[i]=C[i]*(n-1);
}
return D;
}
static double findRoot(double[] C, double a, double b, double tolerance){
//loops here
}

}

Answer 1

您必须解决的一个问题是捕获区间为[-1,1]且多项式为x^2+a的场景。根据a的符号，你有两个、一个双重或没有解决方案。

如果你想通过在区间端点上要求交替符号来拒绝这种情况，这样中间值定理就保证了一个根，那么第一个有效的寻根方法就是regu-falsi方法的Illinois变体。

也请通过Horner方案查找多项式的评估，只有当你有像x^100-3*x^37+5x-1这样的稀疏多项式时，才建议使用Math.pow。

---

如果你真的想在任何情况下找到所有根，那么你能做的最好的事情就是细分区间，并使用内根半径估计排除所有不包含根的子区间。这就是所谓的平分排除算法。最终，系数符号或Sturm序列会告诉你在剩下的小区间内是否有根。

---

平分排除方法的详细信息：它们需要多项式的泰勒移位，即将p(x+h)的系数评估为h中的多项式，这是O(n^2)运算。原始排除算法通过将多项式移位到中点x＝(a+b)/2并计算内根半径r来递归地扫描区间[a，b]。然后，将其应用于区间[a、x-r]和[x+r，b]上。

排除算法的简单形式描述(http://algo.inria.fr/seminars/sem92-93/yakoubsohn.ps‎)(需要Postscript查看器)

Answer 2

一个可能足够强大的变体可以捕获除极端情况外的所有情况，如下所示：

探索的时间间隔是[a，b]。多项式f(x)的次数为d。设N=3+d*d。(这可能需要进行实验)和h=(b-a)/N。

在点x0=a+k*h上迭代，k=0,1，。。。，N.使用该x=x0作为初始点，执行牛顿迭代dx=-f(x)/df(x), x=x+dx。除了通常的成功检查外，abs(dx)<eps1、abs(f(x))<eps2*scale_f还实现了一个失败检查2*abs(x-x0)>h，如果迭代距离初始点超过1/2，则会触发该检查，因此，如果有，则只找到接近根。