Difference between revisions of "Example Polynomial Roots"

From Efficient Java Matrix Library
Jump to: navigation, search
 
Line 4: Line 4:
  
 
External Resources:
 
External Resources:
* [https://github.com/lessthanoptimal/ejml/blob/v0.27/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>
 
* <disqus>Discuss this example</disqus>
  
Line 26: Line 26:
 
     * @return The roots of the polynomial
 
     * @return The roots of the polynomial
 
     */
 
     */
     public static Complex64F[] 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
         DenseMatrix64F c = new DenseMatrix64F(N,N);
+
         DMatrixRMaj c = new DMatrixRMaj(N,N);
  
 
         double a = coefficients[N];
 
         double a = coefficients[N];
Line 41: Line 41:
  
 
         // use generalized eigenvalue decomposition to find the roots
 
         // use generalized eigenvalue decomposition to find the roots
         EigenDecomposition<DenseMatrix64F> evd =  DecompositionFactory.eig(N,false);
+
         EigenDecomposition_F64<DMatrixRMaj> evd =  DecompositionFactory_DDRM.eig(N,false);
  
 
         evd.decompose(c);
 
         evd.decompose(c);
  
         Complex64F[] roots = new Complex64F[N];
+
         Complex_F64[] roots = new Complex_F64[N];
  
 
         for( int i = 0; i < N; i++ ) {
 
         for( int i = 0; i < N; i++ ) {

Latest revision as of 16:51, 18 May 2017

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;
    }
}