VERB_code_2.2
2
|
#include "rroots.h"
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. More... | |
void | deflate (double *a, int n, double *b, double *quad, double *err) |
void | find_quad (double *a, int n, double *b, double *quad, double *err, int *iter) |
void | diff_poly (double *a, int n, double *b) |
Differentiate polynomial 'a' returning result in 'b'. More... | |
void | recurse (double *a, int n, double *b, int m, double *quad, double *err, int *iter) |
void | get_quads (double *a, int n, double *quad, double *x) |
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.
Definition in file rroots.cpp.
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, and VC::m.
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.
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 maxiter.
void diff_poly | ( | double * | a, |
int | n, | ||
double * | b | ||
) |
Differentiate polynomial 'a' returning result in 'b'.
Definition at line 131 of file rroots.cpp.
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().
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'.
Definition at line 201 of file rroots.cpp.
References deflate(), diff_poly(), err, find_quad(), VC::m, maxiter, and recurse().