Dan Hussain
Comp Sci 415
A polynomial can be defined over any field (real,
integer, complex, rational, etc.) A
field is simply any set with two operations (usually + and *) defined. The set with the operator + must be an
Abelian (commutative) group, the set with the operator * must be a semi-group
(no multiplicative inverses necessary), and also + must distribute over *. For this reason, the polynomial class is
templated, which means that it could take as parameters various data types, not
only ints and floats (built-in), but also fractions (which was written in last
year’s class), complex numbers (which I wrote to test this concept out), and
almost any other classes that have the
operators {+, *, -, /} defined.
Note that the polynomial class has the ( ) operator
defined, which means that the following syntax is valid:
Polynomial<float> my_special_poly;
float y;
/* … more code … */
y = my_special_poly( 3.141596 );
// returns the value of the
polynomial my_special_poly for x=3.141596
The polynomial class can also differentiate
polynomials. This is used in Newton’s
method for finding roots. In addition,
it can be used to find local minimum and maximum, points of inflection, and
various other interesting calculus points by finding roots of the first and
second derivatives, respectively.
The polynomial can find roots using the functions
Bisection() and/or Newton(). Bisection
requires a root to be bracketed on a closed interval, and it is guaranteed to
come closer to a root, or a singularity, if no root exists, with each
iteration. The function Newton()
requires only a single ‘guess’, and is almost always faster than
Bisection(). However, there is no
guarantee that it approaches the root with each iteration. It may exhibit exotic behavior and “fly off
to infinity”. To account for this, a
maximum iteration counter is used, and a boolean is set if the root is not
found.
The function FindAllRoots() returns an apvector of
all of the (real) roots of the polynomial by the following algorithm:
(1)
Chose
random point on the interval [-100,100].
(2)
Using
Newton’s method, find a root with this random point as a guess.
(3)
If
the root is found within 250 iterations, synthetic division is performed on the
polynomial, yielding a polynomial of one less degree. Note that the roots of this polynomial are precisely the
remaining roots of the original polynomial.*
(4)
The
process is repeated for this new polynomial until no more roots can be found or
all n roots are found.
(5)
These
roots are used as “tentative” roots for a revised guess. Newton’s method is performed on each of
these tentative roots to improve our approximations.
Note: If the random point does
not produce a root within 250 iterations, another random point is
selected. This is done upto 25
times. If no root is found, the
polynomial is labeled as irreducible over the current field. This does not mean that the polynomial can
not be factored over a more complete field, such as the complex field.
* This is true in all fields with no zero
divisors. I.e., this is true if and
only if the following statement is true in our field:
x*y = 0 à x=0 or y=0
Note that the field of integers modulo a composite
integer do not form a field that meats these criteria. Observe:
2*3 mod 6 = 0 à 2=0 or 3=0, which is false
However, all of the fields that we are likely to
work do not have this nasty property.
We can thus be sure that if r is a root of P(x),
then
P(x) = (x-r)*Q(x)
and that the roots of Q(x) are the remaining roots
of P(x).