roots.c File Reference
`#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.

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.

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.

Here is the call graph for this function: