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)
Constructors Constructor Description
(int maxCoefficients, double searchRadius, double boundTolerance, int maxBoundIterations, int maxRefineIterations)Configures search parameters.
Modifier and Type Method Description
Polynomial poly)(Find real roots for the specified polynomial.
FindRealRootsSturmpublic FindRealRootsSturm(int maxCoefficients, double searchRadius, double boundTolerance, int maxBoundIterations, int maxRefineIterations)Configures search parameters.
maxCoefficients- The maximum number of coefficients a polynomial will have.
>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.
getRootspublic double getRoots()
getNumberOfRootspublic int getNumberOfRoots()
getMaxRootspublic int getMaxRoots()
processpublic void process(Polynomial poly)Find real roots for the specified polynomial.
poly- Polynomial which has less than or equal to the number of coefficients specified in this class's constructor.