Polynomial roots-solving functions
[The Polynomial Templates]

Detailed Description

Operations specifically related to the general polynomial roots-solving problem.


Functions

template<class T, class U>
int jenkinsTraubZeros (const Polynomial< T > &P, std::vector< std::complex< U > > &zeros, bool polish)
template<class T, class U>
int laguerreZeros (const Polynomial< T > &P, std::vector< std::complex< U > > &zeros, bool polish)
template<class T, class U>
int mullerZeros (const Polynomial< T > &P, std::vector< std::complex< U > > &zeros, bool polish)
template<class T, class U, class V>
bool newtonZero (const Polynomial< T > &p, U &z, U &pz, V &mpz, bool adaptive=false)
template<class T>
int removeNullZeros (Polynomial< T > &p)
template<class T>
void sortZeros (std::vector< std::complex< T > > &zeros)
template<class T>
T solveDegree1 (const T &a, const T &b)
template<class T, class U>
void solveDegree2 (const T &a, const T &b, const T &c, U &z1, U &z2)

Function Documentation

template<class T, class U>
int jenkinsTraubZeros (  const Polynomial< T > &  P,
std::vector< std::complex< U > > &  zeros,
bool  polish
) 
 

Jenkins-Traub polynomial zeros evaluator.

returns all zeros of polynomial $P(x)$

Parameters:
[in] P polynomial to evaluate. T coeficients type can be either real or complex.
[out] zeros vector to hold zeros.
[in] polish if set to true, the zeros will be polished by Newton-Raphson algorithm on the original polynomial before deflation. This 'quick and dirty' polishing can lead to problems on large polynomials.
Returns:
The number of zeros found. This number can be checked against the degree of $P(x)$ to check for errors.
See also:
class Polynomial
newtonZero()

Definition at line 55 of file jenkinstraub.h.

template<class T, class U>
int laguerreZeros (  const Polynomial< T > &  P,
std::vector< std::complex< U > > &  zeros,
bool  polish
) 
 

modified Laguerre polynomial zeros evaluator.

Returns all zeros of polynomial $P(x)$ .

This is a very good roots evaluator, that can be pushed to the limits. It will quickly find the roots of even quite large polynomials (>1000 coeficients) in a reasonable amount of time.

It is also very precise and the roots usually will not need any further polishing.

Parameters:
[in] P polynomial to evaluate. T coeficients type can be either real or complex.
[out] zeros vector to hold zeros.
[in] polish if set to true, the zeros will be polished by Newton-Raphson algorithm on the original polynomial before deflation. This 'quick and dirty' polishing can lead to problems on large polynomials.
Returns:
The number of zeros found. This number can be checked against the degree of $P(x)$ to check for errors.
See also:
class Polynomial
newtonZero()

Definition at line 62 of file laguerre.h.

template<class T, class U>
int mullerZeros (  const Polynomial< T > &  P,
std::vector< std::complex< U > > &  zeros,
bool  polish
) 
 

Muller'method polynomial roots evaluator.

returns all zeros of polynomial $P(x)$

Parameters:
[in] P polynomial to evaluate. T coeficients type can be either real or complex.
[out] zeros vector to hold zeros.
[in] polish if set to true, the zeros will be polished by Newton-Raphson algorithm on the original polynomial before deflation. This 'quick and dirty' polishing can lead to problems on large polynomials.
Returns:
The number of zeros found. This number can be checked against the degree of $P(x)$ to check for errors.
See also:
class Polynomial
newtonZero()

Definition at line 55 of file muller.h.

template<class T, class U, class V>
bool newtonZero (  const Polynomial< T > &  p,
U &  z,
U &  pz,
V &  mpz,
bool  adaptive = false
) 
 

resolves closest zero by Newton-Raphson iterations.

This function requires an initial zero estimate that is fairly close.

Parameters:
[in] p polynomial being evaluated. template parameter T can be any IEEE floating-point type, real or complex.
[in,out] z on entry, the original estimate for zero. On exit, the refined zero. Template parameter U can be IEEE floating-point type, real or complex.
[out] pz on exit, contains $p(z)$
[out] mpz on exit, contains $|p(z)|$ , the asolute value of $p(z)$ .
[in] adaptive indicates wether to use the classic Newton-Raphson algorithm, or the adaptive version. The adaptive algorithm is more efficient for resolving multiple zeros, but can be much is slower when the original estimate is very close to the actual zero.
See also:
Polynomial

Definition at line 73 of file polyzero.h.

template<class T>
int removeNullZeros (  Polynomial< T > &  p  ) 
 

divides a polynomial $p(x)$ by $x$ , until is has no null roots.

Deflates the polynomial p until it has no null roots, effectively dividing $p(x)$ by $x$ until the coeficient of degree zero is not null.

Example:
// nullzeros.cpp : Demonstrates use of removeNullZeros
//
#include <iostream>
#include "polyzero.h"

using namespace std;

void main() {
    //  this example shows how to remove null roots from a polynomial
    //  using removeNullRoots()

    //  create polynomial p(x)=x^3+x^2 (= x*x*(x+1))
    Polynomial<float> p(3, 0.f, 0.f, 1.f, 1.f);

    // print
    cout << "before deflating P(x)=";
    for (int i = p.degree(); i >= 1; --i)
        cout << p[i] << "*x^" << i << "+";
    cout << p[0] << endl << endl;
        
    int n = removeNullZeros(p);

    cout << "removeNullZeros() removed " << n << " zeros" << endl;

    // print modified polynomial
    cout << "after deflating P(x)=";
    for (int i = p.degree(); i >= 1; --i)
        cout << p[i] << "*x^" << i << "+";
    cout << p[0] << endl;
}
Program output:
before deflating P(x)=1*x^3+1*x^2+0*x^1+0

removeNullZeros() removed 2 zeros
after deflating P(x)=1*x^1+1
Parameters:
[in] p polynomial being evaluated. template parameter T can be any IEEE floating-point type, real or complex.
Returns:
The number of null roots found and removed from the original polynomial.
See also:
Polynomial
Polynomial::shift()

Definition at line 168 of file polyzero.h.

template<class T>
T solveDegree1 (  const T &  a,
const T &  b
)  [inline]
 

returns the root of a degree 1 polynomial.

Returns the unique root of the polynomial $p(x)=ax+b$

Parameters:
[in] a the degree 1 coeficient.
[in] b the degree 0 coeficient.
Returns:
The fraction $-\frac{b}{a}$

Definition at line 350 of file polyzero.h.

template<class T, class U>
void solveDegree2 (  const T &  a,
const T &  b,
const T &  c,
U &  z1,
U &  z2
) 
 

returns the root of a degree 2 polynomial.

Returns the two roots of the polynomial $p(x)=ax^2+bx+c$ .

The roots z1 and z2 are calculated as follows.

\[S=b+\sqrt{b^2-4ac}\]

\[D=b-\sqrt{b^2-4ac}\]

\[q=\left\{ \begin{array}{ll} -S & \mbox{if} \left| S\right| >\left| D\right| \\ -D & \mbox{otherwise}\end{array}\right. \]

\[z_1=\frac{2c}{q}\]

\[z_2=\frac{q}{2a}\]

This method avoids dividing by a very small number and thus reduces error.

Parameters:
[in] a the degree 2 coeficient. Template parameter T can be any floating-point or cvomplex data type.
[in] b the degree 1 coeficient.
[in] c the degree 0 coeficient.
[out] z1 the root with the smallest absolute value. Template parameter U should be a complex type for which operators *, -, / and functions abs() and sqrt() are defined.
[out] z2 the root with the largest absolute value.

Definition at line 383 of file polyzero.h.

template<class T>
void sortZeros (  std::vector< std::complex< T > > &  zeros  )  [inline]
 

sorts the zeros of a polynomial.

Sorts the zeros of a polynomial by ascending order of their real part.

Parameters:
[in,out] zeros zeros of a polynomial.
See also:
Polynomial
laguerreZeros()
mullerZeros()
jenkinsTraubZeros()

Definition at line 328 of file polyzero.h.

Generated on Mon Aug 21 21:00:38 2006 for The Polynomials Templates Library by  doxygen 1.4.5