在Java中寻找多项式的根

Question

我需要找到一个（近似的、数值的）勒让德多项式的解。我尝试了几个Java库，但没有找到我需要的（最接近的是commons-math，甚至有用于在Laguerre求解器中找到解的代码，但它没有公开方法）。是否存在现成的解决方案，或者我需要自己实现？

- Maciej Piechotka

---

@PradeepSimha：在stackoverflow/google上找到了JScience、common-math、JAP和可能还有其他一些库（在发布之前我花了大约4个小时进行搜索）。 - Maciej Piechotka

所以，它们都缺少你所需要的东西。 - mtk

@mtk：是的。JScience和JAP根本没有找到根的功能，而common-math有一种找到根的方法，但commons-math只能找到一个根（可能可以选择适当的初始条件来找到所有根，但对于如此简单的多项式函数来说，没有必要这样做）。至少我没有找到任何相关的功能。 - Maciej Piechotka

Answer 1

你可以使用EJML（Efficient Java Matrix Library）。

请查看下面的示例。

public class PolynomialRootFinder {

    /**
     * <p>
     * Given a set of polynomial coefficients, compute the roots of the polynomial.  Depending on
     * the polynomial being considered the roots may contain complex number.  When complex numbers are
     * present they will come in pairs of complex conjugates.
     * </p>
     *
     * @param coefficients Coefficients of the polynomial.
     * @return The roots of the polynomial
     */
    public static Complex64F[] findRoots(double... coefficients) {
        int N = coefficients.length-1;

        // Construct the companion matrix
        DenseMatrix64F c = new DenseMatrix64F(N,N);

        double a = coefficients[N];
        for( int i = 0; i < N; i++ ) {
            c.set(i,N-1,-coefficients[i]/a);
        }
        for( int i = 1; i < N; i++ ) {
            c.set(i,i-1,1);
        }

        // Use generalized eigenvalue decomposition to find the roots
        EigenDecomposition<DenseMatrix64F> evd =  DecompositionFactory.eigGeneral(N, false);

        evd.decompose(c);

        Complex64F[] roots = new Complex64F[N];

        for( int i = 0; i < N; i++ ) {
            roots[i] = evd.getEigenvalue(i);
        }

        return roots;
    }
}

- Bhavik Ambani

---

如果您不知道上述内容的来源，请查看此论文，特别是第2页“COMPANION MATRICES: FINDING ROOTS OF UNIVARIATE POLYNOMIALS AS AN EIGENVALUE/EIGENVECTOR PROBLEM”。 - Domi

eigGeneral方法现在更改为eig。 - zygimantus

@zygimantus 感谢您的信息和分享知识 :) - Bhavik Ambani

链接仍然有效，但是或许需要更新一下？ - Peter Mortensen

Answer 2

自3.1版本以来，Commons-Math 支持查找多项式函数的所有复数根。

请参见 LaguerreSolver#solveAllComplex。

- T. Neidhart

---

链接已损坏：“未找到。所请求的 URL 在此服务器上未找到。” - Peter Mortensen

Answer 3

Commons-Math 对于多项式有一个合理的 API：

//  -4 + 3 x + x^2
PolynomialFunction polynomial = new PolynomialFunction(new double[]{ -4, 3, 1});
LaguerreSolver laguerreSolver = new LaguerreSolver();
double root = laguerreSolver.solve(100, polynomial, -100, 100);
System.out.println("root = " + root);

- Filip Bláha