org.ddogleg.solver.impl

Class FindRealRootsSturm

java.lang.Object

org.ddogleg.solver.impl.FindRealRootsSturm

public class FindRealRootsSturm
extends java.lang.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 Summary

Constructors

Constructor and Description
FindRealRootsSturm(int maxCoefficients, double searchRadius, double boundTolerance, int maxBoundIterations, int maxRefineIterations) Configures search parameters.

Method Summary

Modifier and Type	Method and Description
int	getMaxRoots()
int	getNumberOfRoots()
double[]	getRoots()
void	process(Polynomial poly) Find real roots for the specified polynomial.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

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 Detail

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.