1

我是编码的初学者，尤其是在 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
    }

}

4

2 回答 2

1

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

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

还请通过霍纳方案查找多项式的评估，仅当您有一个稀疏多项式时才建议使用 Math.pow x^100-3*x^37+5x-1。

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

二分排除方法的详细信息：它们需要多项式的泰勒位移，即，将 的系数评估p(x+h)为 h 中的多项式，这是一个 O(n^2) 操作。原始排除算法通过将多项式移动到中点 x=(a+b)/2 并计算内根半径 r 来递归地扫描区间 [a,b]。然后同样适用于区间 [a,xr] 和 [x+r,b]。

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

于 2014-02-19T09:37:43.063 回答
0

一个可能足够强大的变体可以捕捉除极端情况之外的所有情况：

探索的区间是 [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, ，如果迭代远离初始点超过 h/2，则abs(f(x))<eps2*scale_f执行失败检查，以便仅找到附近的根（如果有的话）。2*abs(x-x0)>h

于 2014-02-27T08:28:19.947 回答