rroots.cpp File Reference

Finds all roots of polynomial by first finding quadratic factors using Bairstow's method, then extracting roots from quadratics. More...

#include "rroots.h"

Include dependency graph for rroots.cpp:

Go to the source code of this file.

Functions

int roots (double *a, int n, double *wr, double *wi)
 Extract individual real or complex roots from list of quadratic factors.
void deflate (double *a, int n, double *b, double *quad, double *err)
 Deflate polynomial 'a' by division of 'quad'. Return quotient polynomial in 'b' and error (metric based on remainder) in 'err'.
void find_quad (double *a, int n, double *b, double *quad, double *err, int *iter)
 Find quadratic factor using Bairstow's method (quadratic Newton method). A number of ad hoc safeguards are incorporated to prevent stalls due to common difficulties, such as zero slope at iteration point, and convergence problems.
void diff_poly (double *a, int n, double *b)
 Differentiate polynomial 'a' returning result in 'b'.
void recurse (double *a, int n, double *b, int m, double *quad, double *err, int *iter)
 Attempt to find a reliable estimate of a quadratic factor using modified Bairstow's method with provisions for 'digging out' factors associated with multiple roots.
void get_quads (double *a, int n, double *quad, double *x)
 Top level routine to manage the determination of all roots of the given polynomial 'a', returning the quadratic factors (and possibly one linear factor) in 'x'.


Detailed Description

Finds all roots of polynomial by first finding quadratic factors using Bairstow's method, then extracting roots from quadratics.

Implements new algorithm for managing multiple roots.

Date:
(C) 2002, 2003,
Author:
C. Bond. All rights reserved.

Definition in file rroots.cpp.


Function Documentation

void deflate ( double *  a,
int  n,
double *  b,
double *  quad,
double *  err 
)

Deflate polynomial 'a' by division of 'quad'. Return quotient polynomial in 'b' and error (metric based on remainder) in 'err'.

Definition at line 60 of file rroots.cpp.

References i.

Referenced by get_quads().

Here is the caller graph for this function:

void diff_poly ( double *  a,
int  n,
double *  b 
)

Differentiate polynomial 'a' returning result in 'b'.

Definition at line 131 of file rroots.cpp.

References i.

Referenced by get_quads(), and recurse().

Here is the caller graph for this function:

void find_quad ( double *  a,
int  n,
double *  b,
double *  quad,
double *  err,
int *  iter 
)

Find quadratic factor using Bairstow's method (quadratic Newton method). A number of ad hoc safeguards are incorporated to prevent stalls due to common difficulties, such as zero slope at iteration point, and convergence problems.

Definition at line 84 of file rroots.cpp.

References i, and maxiter.

Referenced by get_quads(), and recurse().

Here is the caller graph for this function:

void get_quads ( double *  a,
int  n,
double *  quad,
double *  x 
)

Top level routine to manage the determination of all roots of the given polynomial 'a', returning the quadratic factors (and possibly one linear factor) in 'x'.

Todo:
Should gives error in case roots not founded. But that is commented.

Definition at line 201 of file rroots.cpp.

References deflate(), diff_poly(), err, find_quad(), i, maxiter, and recurse().

Referenced by rrouts().

Here is the call graph for this function:

Here is the caller graph for this function:

void recurse ( double *  a,
int  n,
double *  b,
int  m,
double *  quad,
double *  err,
int *  iter 
)

Attempt to find a reliable estimate of a quadratic factor using modified Bairstow's method with provisions for 'digging out' factors associated with multiple roots.

This resursive routine operates on the principal that differentiation of a polynomial reduces the order of all multiple roots by one, and has no other roots in common with it. If a root of the differentiated polynomial is a root of the original polynomial, there must be multiple roots at that location. The differentiated polynomial, however, has lower order and is easier to solve.

When the original polynomial exhibits convergence problems in the neighborhood of some potential root, a best guess is obtained and tried on the differentiated polynomial. The new best guess is applied recursively on continually differentiated polynomials until failure occurs. At this point, the previous polynomial is accepted as that with the least number of roots at this location, and its estimate is accepted as the root.

Definition at line 162 of file rroots.cpp.

References diff_poly(), and find_quad().

Referenced by get_quads().

Here is the call graph for this function:

Here is the caller graph for this function:

int roots ( double *  a,
int  n,
double *  wr,
double *  wi 
)

Extract individual real or complex roots from list of quadratic factors.

Definition at line 15 of file rroots.cpp.

References DBL_EPSILON.

Referenced by rrouts().

Here is the caller graph for this function:


Generated on Thu May 27 11:53:19 2010 for VERB_CODE_2.0 by  doxygen 1.5.9