[ VIGRA Homepage | Class Index | Function Index | File Index | Main Page ]

details Polynomials and root determination VIGRA


Classes

class  Polynomial
class  PolynomialView
class  StaticPolynomial

Functions

template<...> bool polynomialRoots (POLYNOMIAL const &poriginal, VECTOR &roots, bool polishRoots)
template<...> bool polynomialRealRoots (POLYNOMIAL const &p, VECTOR &roots, bool polishRoots)


Detailed Description


Classes to represent polynomials and functions to find polynomial roots.


Function Documentation


  bool polynomialRealRoots (...)
 
 

Determine the real roots of the polynomial p.

This function simply calls polynomialRoots() and than throws away all complex roots. Accordingly, VECTOR must be compatible to std::vector with a value_type compatible to the type POLYNOMIAL::Real.

Declaration:

pass arguments explicitly:

    namespace vigra {
        template <class POLYNOMIAL, class VECTOR>
        bool 
        polynomialRealRoots(POLYNOMIAL const & p, VECTOR & roots, bool polishRoots = true);
    }

Usage:

#include "vigra/polynomial.hxx"
Namespace: vigra

    // encode the polynomial  x^4 - 1
    Polynomial<double> poly(4);
    poly[0] = -1.0;
    poly[4] =  1.0;

    ArrayVector<double> roots;
    polynomialRealRoots(poly, roots);

See also:
polynomialRealRootsEigenvalueMethod()


  bool polynomialRoots (...)
 
 

Determine the roots of the polynomial poriginal.

The roots are appended to the vector roots, with optional root polishing as specified by polishRoots (default: do polishing). The function uses an improved version of Laguerre's algorithm. The improvements are as follows:

  • It uses a clever initial guess for the iteration, according to a proposal by Tien Chen
  • It estimates each root's multiplicity, again according to Tien Chen, and reduces multiplicity by switching to the polynomial's derivative (which has the same root, with multiplicity reduced by one), as proposed by C. Bond.
The algorithm has been successfully used for polynomials up to order 80. The function stops and returns false if an iteration fails to converge within 80 steps. The type POLYNOMIAL must be compatible to vigra::PolynomialView, VECTOR must be compatible to std::vector with a value_type compatible to the type POLYNOMIAL::Complex.

Declaration:

pass arguments explicitly:

    namespace vigra {
        template <class POLYNOMIAL, class VECTOR>
        bool 
        polynomialRoots(POLYNOMIAL const & poriginal, VECTOR & roots, bool polishRoots = true);
    }

Usage:

#include "vigra/polynomial.hxx"
Namespace: vigra

    // encode the polynomial  x^4 - 1
    Polynomial<double> poly(4);
    poly[0] = -1.0;
    poly[4] =  1.0;

    ArrayVector<std::complex<double> > roots;
    polynomialRoots(poly, roots);

See also:
polynomialRootsEigenvalueMethod()

© Ullrich Köthe (koethe@informatik.uni-hamburg.de)
Cognitive Systems Group, University of Hamburg, Germany

html generated using doxygen and Python
VIGRA 1.3.3 (18 Aug 2005)