RobWorkProject  24.5.15-
Public Member Functions | List of all members
PolynomialSolver Class Reference

Find solutions for roots of real and complex polynomial equations. More...

#include <PolynomialSolver.hpp>

Public Member Functions

 PolynomialSolver (const Polynomial< double > &polynomial)
 Create a solver for a polynomial with real coefficients. More...
 
 PolynomialSolver (const Polynomial< std::complex< double >> &polynomial)
 Create a solver for a polynomial with complex coefficients. More...
 
virtual ~PolynomialSolver ()
 Destructor.
 
void setInitialGuess (std::complex< double > guess=0)
 Use a specific initial guess for a root. More...
 
std::vector< double > getRealSolutions (double epsilon=1.0e-14)
 Get all real solutions of the equation. More...
 
virtual std::vector< std::complex< double > > getSolutions (double epsilon=1.0e-14)
 Get all solutions of the equation including complex solutions. More...
 
void setLaguerreIterations (unsigned int iterations=10)
 Set the number of iterations to take in the Laguerre method. More...
 

Detailed Description

Find solutions for roots of real and complex polynomial equations.

The solutions are found analytically if the polynomial is of maximum order 3. For polynomials of order 4 and higher, Laguerre's Method is used to find roots until the polynomial can be deflated to order 3. The remaining roots will then be found analytically.

Some Polynomials are particularly easy to solve. A polynomial of the form \( a x^n + b = 0\) will be solved by taking the n'th roots of \(-\frac{b}{a}\) directly, giving n distinct roots in the complex plane.

To illustrate the procedure, consider the equation: \( 10^{-15} x^8 - 10^{-15} x^7 + x^7 + 2 x^6 - x^4 - 2x^3 + 10^{-15} x= 0\)

The solver will use the following procedure (here with the precision \( \epsilon = 10^{-14}\)):

  1. Remove terms that are small compared to \(\epsilon\): \( x^7 + 2 x^6 - x^4 - 2x^3 = 0\)
  2. Find zero roots and reduce the order: There is a triple root in x = 0 and the remaining polynomial becomes: \( x^4 + 2 x^3 - x - 2 = 0\).
  3. Use Laguerre to find a root of \( x^4 + 2 x^3 - x - 2 = 0\)

Depending on the initial guess for Laguerre, different roots might be found first. The algorithm will proceed differently depending on the found root:

  1. If root x=-2 is found, remaining polynomial after deflation is \( x^3 -1 = 0\). The roots are found directly as the cubic root of 1, which is three distinct roots in the complex plane (one is on the real axis).
  2. If root x=1 is found, remaining polynomial after deflation is \( x^3 + 3 x^2 +3 x + 2 = 0\). The roots are found analytically, giving one real root x=-2 and two complex conjugate roots \( x = -0.5 \pm \frac{\sqrt{3}}{2} i\).
  3. If other roots than x=1 or x=-2 is found (a complex root), remaining polynomial is a third order polynomial with complex coefficients. This polynomial is solved analytically to give remaining two real roots, and one remaining complex root.

Notice that cases 2+3 requires analytical solution of the third order polynomial equation. For higher order polynomials Laguerre would need to be used to find the next root. In this case it is particularly lucky to hit case 1, as this gives the solutions right away no matter what order the remaining polynomial is.

Constructor & Destructor Documentation

◆ PolynomialSolver() [1/2]

PolynomialSolver ( const Polynomial< double > &  polynomial)

Create a solver for a polynomial with real coefficients.

Parameters
polynomial[in] the polynomial to find roots for.

◆ PolynomialSolver() [2/2]

PolynomialSolver ( const Polynomial< std::complex< double >> &  polynomial)

Create a solver for a polynomial with complex coefficients.

Parameters
polynomial[in] the polynomial to find roots for.

Member Function Documentation

◆ getRealSolutions()

std::vector<double> getRealSolutions ( double  epsilon = 1.0e-14)

Get all real solutions of the equation.

Parameters
epsilon[in] the root is considered a real root if \( |im(x)| \leq 2 \epsilon |real(x)|\) .
Returns
a list of real solutions.
Exceptions
rw::core::Exceptionif the Laguerre method fails, or the maximum number of iterations has been reached.
See also
PolynomialSolver for more details about the method used.

◆ getSolutions()

virtual std::vector<std::complex<double> > getSolutions ( double  epsilon = 1.0e-14)
virtual

Get all solutions of the equation including complex solutions.

Parameters
epsilon[in] highest order coefficients will be removed if they have absolute real and imaginary values less than \( \epsilon \) .
Returns
a list of complex solutions.
Exceptions
rw::core::Exceptionif the Laguerre method fails, or the maximum number of iterations has been reached.
See also
PolynomialSolver for more details about the method used.

◆ setInitialGuess()

void setInitialGuess ( std::complex< double >  guess = 0)

Use a specific initial guess for a root.

Parameters
guess[in] a complex initial guess for the algorithm.

◆ setLaguerreIterations()

void setLaguerreIterations ( unsigned int  iterations = 10)

Set the number of iterations to take in the Laguerre method.

Parameters
iterations[in] the maximum number of iterations (default is 10).

The documentation for this class was generated from the following file: