Difference between revisions of "Example Polynomial Roots"

From Efficient Java Matrix Library
Jump to: navigation, search
 
Line 5: Line 5:
 
External Resources:
 
External Resources:
 
* [https://github.com/lessthanoptimal/ejml/blob/v0.31/examples/src/org/ejml/example/PolynomialRootFinder.java PolynomialRootFinder.java source code]
 
* [https://github.com/lessthanoptimal/ejml/blob/v0.31/examples/src/org/ejml/example/PolynomialRootFinder.java PolynomialRootFinder.java source code]
* <disqus>Discuss this example</disqus>
 
  
 
= Example Code =
 
= Example Code =
Line 11: Line 10:
 
<syntaxhighlight lang="java">
 
<syntaxhighlight lang="java">
 
public class PolynomialRootFinder {
 
public class PolynomialRootFinder {
 
 
     /**
 
     /**
 
     * <p>
 
     * <p>
Line 26: Line 24:
 
     * @return The roots of the polynomial
 
     * @return The roots of the polynomial
 
     */
 
     */
     public static Complex_F64[] findRoots(double... coefficients) {
+
     public static Complex_F64[] findRoots( double... coefficients ) {
         int N = coefficients.length-1;
+
         int N = coefficients.length - 1;
  
 
         // Construct the companion matrix
 
         // Construct the companion matrix
         DMatrixRMaj c = new DMatrixRMaj(N,N);
+
         DMatrixRMaj c = new DMatrixRMaj(N, N);
  
 
         double a = coefficients[N];
 
         double a = coefficients[N];
         for( int i = 0; i < N; i++ ) {
+
         for (int i = 0; i < N; i++) {
             c.set(i,N-1,-coefficients[i]/a);
+
             c.set(i, N - 1, -coefficients[i]/a);
 
         }
 
         }
         for( int i = 1; i < N; i++ ) {
+
         for (int i = 1; i < N; i++) {
             c.set(i,i-1,1);
+
             c.set(i, i - 1, 1);
 
         }
 
         }
  
 
         // use generalized eigenvalue decomposition to find the roots
 
         // use generalized eigenvalue decomposition to find the roots
         EigenDecomposition_F64<DMatrixRMaj> evd = DecompositionFactory_DDRM.eig(N,false);
+
         EigenDecomposition_F64<DMatrixRMaj> evd = DecompositionFactory_DDRM.eig(N, false);
  
 
         evd.decompose(c);
 
         evd.decompose(c);
Line 47: Line 45:
 
         Complex_F64[] roots = new Complex_F64[N];
 
         Complex_F64[] roots = new Complex_F64[N];
  
         for( int i = 0; i < N; i++ ) {
+
         for (int i = 0; i < N; i++) {
 
             roots[i] = evd.getEigenvalue(i);
 
             roots[i] = evd.getEigenvalue(i);
 
         }
 
         }

Latest revision as of 08:31, 7 July 2021

Eigenvalue decomposition can be used to find the roots in a polynomial by constructing the so called companion matrix. While faster techniques do exist for root finding, this is one of the most stable and probably the easiest to implement.

Because the companion matrix is not symmetric a generalized eigenvalue [MatrixDecomposition decomposition] is needed. The roots of the polynomial may also be complex.

External Resources:

Example Code

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>
     *
     * <p>
     * Coefficients are ordered from least to most significant, e.g: y = c[0] + x*c[1] + x*x*c[2].
     * </p>
     *
     * @param coefficients Coefficients of the polynomial.
     * @return The roots of the polynomial
     */
    public static Complex_F64[] findRoots( double... coefficients ) {
        int N = coefficients.length - 1;

        // Construct the companion matrix
        DMatrixRMaj c = new DMatrixRMaj(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_F64<DMatrixRMaj> evd = DecompositionFactory_DDRM.eig(N, false);

        evd.decompose(c);

        Complex_F64[] roots = new Complex_F64[N];

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

        return roots;
    }
}