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

Question

我是编码的初学者，尤其是Java编码的初学者，我已经尝试了很多次来计算如何在给定范围内找到多项式的实根。该程序应该找到用户提供的给定多项式的所有实根。例如，程序应按如下方式运行: 输入学位:3 输入4个系数:-6 11 -6 1 输入左右端点:-10 10 根发现于:1.00000 根发现于:2.00000 根发现于: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 的符号，您有两个、一个双解或无解。

如果您打算通过要求间隔端点上的交替符号来拒绝这种情况，以便中间值定理保证有根，那么第一个有效的求根方法是 regula falsi 方法的伊利诺伊州变体。

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

<小时/>

如果您确实想在任何情况下找到所有根，那么最好的办法就是分割区间并使用内根半径估计排除所有不包含根的子区间。这被称为 bisection-exclusion algorithm 。最终，系数符号或 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 查看器)