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

| Polynomials and root determination |
--- | --- | ---

## 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.4.0 (21 Dec 2005)