Polynomials and root determination

Classes
class	Polynomial< T >
class	PolynomialView< T >
class	StaticPolynomial< MAXORDER, T >

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

Detailed Description

Classes to represent polynomials and functions to find polynomial roots.

Function Documentation

bool vigra::polynomialRoots	(	POLYNOMIAL const &	poriginal,
		VECTOR &	roots,
		bool	polishRoots
	)

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()

bool vigra::polynomialRealRoots	(	POLYNOMIAL const &	p,
		VECTOR &	roots,
		bool	polishRoots
	)

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()