Package org.ddogleg.solver.impl

Class FindRealRootsSturm

java.lang.Object
org.ddogleg.solver.impl.FindRealRootsSturm
public class FindRealRootsSturm extends Object

Uses a Sturm sequence to bound the location of real roots in the polynomial. After the roots have been found to the specific precision they are then refined. If a root has not been found to within tolerance during bisection then the current best estimate will be used during refinement.

NOTE: Polynomial division by small coefficients can produce erratic results. There are systems that the Eigenvalue method will produce accurate solutions for but that this algorithm will fail at. An example of one such system is provided below. Maybe someone can come up with a fix/reformulation which works better and is still fast.

 Polynomial.wrap(0.06496129844668003,-0.20388125146277708,-0.5346822141623102,3.8451325925247914,
                                -8.125384551749551,7.281661653591961,-0.1827681555908356,-4.918274060516843,
                                3.6136415842421954,-0.8418091530846867,5.662137425588298E-15)

  • Constructor Details

    • FindRealRootsSturm

      public FindRealRootsSturm(int maxCoefficients, double searchRadius, double boundTolerance, int maxBoundIterations, int maxRefineIterations)
      Configures search parameters.
      Parameters:
      maxCoefficients - The maximum number of coefficients a polynomial will have.
      searchRadius - If > 0 then roots are searched for inside of -searchRadius ≤ x ≤ searchRadius. If ≤ 0 then it will find all roots.
      boundTolerance - How accurately roots are found using bisection. Should be close enough that refinement can accurately converge to the correct root.
      maxBoundIterations - Maximum number of iterations each step can perform when bounding.
      maxRefineIterations - Maximum number of iterations when refining.

  • Method Details

    • getRoots

      public double[] getRoots()

    • getNumberOfRoots

      public int getNumberOfRoots()

    • getMaxRoots

      public int getMaxRoots()

    • process

      public void process(Polynomial poly)
      Find real roots for the specified polynomial.
      Parameters:
      poly - Polynomial which has less than or equal to the number of coefficients specified in this class's constructor.