BRL-CAD
#include "common.h"
#include <math.h>
#include "bio.h"
#include "vmath.h"
#include "bn.h"
#include "raytrace.h"
Include dependency graph for roots.c:

Go to the source code of this file.

Functions

void rt_poly_eval_w_2derivatives (register bn_complex_t *cZ, register bn_poly_t *eqn, register bn_complex_t *b, register bn_complex_t *c, register bn_complex_t *d)
 
int rt_poly_findroot (register bn_poly_t *eqn, register bn_complex_t *nxZ, const char *str)
 
int rt_poly_checkroots (register bn_poly_t *eqn, bn_complex_t *roots, register int nroots)
 
void rt_poly_deflate (register bn_poly_t *oldP, register bn_complex_t *root)
 
int rt_poly_roots (register bn_poly_t *eqn, register bn_complex_t roots[], const char *name)
 

Detailed Description

Find the roots of a polynomial

Definition in file roots.c.

Function Documentation

void rt_poly_eval_w_2derivatives ( register bn_complex_t cZ,
register bn_poly_t eqn,
register bn_complex_t b,
register bn_complex_t c,
register bn_complex_t d 
)

Evaluates p(Z), p'(Z), and p''(Z) for any Z (real or complex). Given an equation of the form:

p(Z) = a0*Z^n + a1*Z^(n-1) +... an != 0,

the function value and derivatives needed for the iterations can be computed by synthetic division using the formulas

p(Z) = bn, p'(Z) = c(n-1), p''(Z) = d(n-2),

where

b0 = a0, bi = b(i-1)*Z + ai, i = 1, 2, ...n c0 = b0, ci = c(i-1)*Z + bi, i = 1, 2, ...n-1 d0 = c0, di = d(i-1)*Z + ci, i = 1, 2, ...n-2

Definition at line 54 of file roots.c.

References bn_cx_add, bn_cx_cons, bn_cx_mul, bn_poly::cf, bn_poly::dgr, and bn_complex::re.

Referenced by rt_poly_findroot().

int rt_poly_findroot ( register bn_poly_t eqn,
register bn_complex_t nxZ,
const char *  str 
)

Calculates one root of a polynomial (p(Z)) using Laguerre's method. This is an iterative technique which has very good global convergence properties. The formulas for this method are

                    n * p(Z)
 newZ  =  Z - -----------------------  ,
            p'(Z) +- sqrt(H(Z))

where H(Z) = (n-1) [ (n-1)(p'(Z))^2 - n p(Z)p''(Z) ],

where n is the degree of the polynomial. The sign in the denominator is chosen so that |newZ - Z| is as small as possible.

Definition at line 97 of file roots.c.

References bn_cx_add, bn_cx_amplsq, bn_cx_div(), bn_cx_mul2, bn_cx_scal, bn_cx_sqrt(), bn_cx_sub, bu_log(), bn_poly::dgr, bn_complex::im, bn_complex::re, rt_poly_eval_w_2derivatives(), and ZERO.

Referenced by rt_poly_roots().

Here is the call graph for this function:

int rt_poly_checkroots ( register bn_poly_t eqn,
bn_complex_t roots,
register int  nroots 
)

Evaluates p(Z) for any Z (real or complex). In this case, test all "nroots" entries of roots[] to ensure that they are roots (zeros) of this polynomial.

Returns - 0 all roots are true zeros 1 at least one "root[]" entry is not a true zero

Given an equation of the form

p(Z) = a0*Z^n + a1*Z^(n-1) +... an != 0,

the function value can be computed using the formula

p(Z) = bn, where

b0 = a0, bi = b(i-1)*Z + ai, i = 1, 2, ...n

Definition at line 195 of file roots.c.

References bn_cx_imag, bn_cx_real, bn_poly::cf, and bn_poly::dgr.

Referenced by rt_poly_roots().

void rt_poly_deflate ( register bn_poly_t oldP,
register bn_complex_t root 
)

Deflates a polynomial by a given root.

Definition at line 235 of file roots.c.

References bn_cx_amplsq, bn_poly_synthetic_division(), bn_poly::cf, bn_poly::dgr, bn_complex::im, bn_complex::re, rem, and ZERO.

Referenced by rt_poly_roots().

Here is the call graph for this function:

int rt_poly_roots ( register bn_poly_t eqn,
register bn_complex_t  roots[],
const char *  name 
)

Definition at line 266 of file roots.c.

References bn_cx_conj, bn_cx_cons, bn_poly_cubic_roots(), bn_poly_quadratic_roots(), bn_poly_quartic_roots(), bn_poly_scale(), bn_poly::cf, bn_poly::dgr, bn_complex::im, bn_complex::re, rt_poly_checkroots(), rt_poly_deflate(), rt_poly_findroot(), SMALL, and ZERO.

Here is the call graph for this function: