Math::Polynomial::Solve - Find the roots of polynomial equations
戻る
<![CDATA[
NAME
Math::Polynomial::Solve - Find the roots of polynomial equations.
SYNOPSIS
use Math::Complex; # The roots may be complex numbers.
use Math::Polynomial::Solve qw(poly_roots);
my @x = poly_roots(@coefficients);
or
use Math::Complex; # The roots may be complex numbers.
use Math::Polynomial::Solve qw(poly_roots get_hessenberg set_hessenberg);
#
# Force the use of the matrix method.
#
set_hessenberg(1);
my @x = poly_roots(@coefficients);
or
use Math::Complex; # The roots may be complex numbers.
use Math::Polynomial::Solve
qw(linear_roots quadratic_roots cubic_roots quartic_roots);
# Find the roots of ax + b
my @x1 = linear_roots($a, $b);
# Find the roots of ax**2 + bx +c
my @x2 = quadratic_roots($a, $b, $c);
# Find the roots of ax**3 + bx**2 +cx + d
my @x3 = cubic_roots($a, $b, $c, $d);
# Find the roots of ax**4 + bx**3 +cx**2 + dx + e
my @x4 = quartic_roots($a, $b, $c, $d, $e);
DESCRIPTION
This package supplies a set of functions that find the roots of
polynomials. Polynomials up to the quartic may be solved directly by
numerical formulae. Polynomials of fifth and higher powers will be
solved by an iterative method, as there are no general solutions for
fifth and higher powers.
The linear, quadratic, cubic, and quartic *_roots() functions all expect
to have a non-zero value for the $a term.
If the constant term is zero then the first value returned in the list
of answers will always be zero, for all functions.
set_hessenberg()
Sets or removes the condition that forces the use of the Hessenberg
matrix regardless of the polynomial's degree. A non-zero argument forces
the use of the matrix method, a zero removes it.
get_hessenberg()
Returns 1 or 0 depending upon whether the Hessenberg matrix method is
always in use or not.
poly_roots()
A generic function that may call one of the other root-finding
functions, or a polynomial solving method using a Hessenberg matrix,
depending on the degree of the polynomial. You may force it to use the
matrix method regardless of the degree of the polynomial by calling
set_hessenberg(1). Otherwise it will use the specialized root functions
for polynomials of degree 1 to 4.
Unlike the other root-finding functions, it will check for coefficients
of zero for the highest power, and 'step down' the degree of the
polynomial to the appropriate case. Additionally, it will check for
coefficients of zero for the lowest power terms, and add zeros to its
root list before calling one of the root-finding functions. Thus it is
possible to solve a polynomial of degree higher than 4 without using the
matrix method, as long as it meets these rather specialized conditions.
linear_roots()
Here for completeness's sake more than anything else. Returns the
solution for
ax + b = 0
by returning "-b/a". This may be in either a scalar or an array context.
quadratic_roots()
Gives the roots of the quadratic equation
ax**2 + bx + c = 0
using the well-known quadratic formula. Returns a two-element list.
cubic_roots()
Gives the roots of the cubic equation
ax**3 + bx**2 + cx + d = 0
by the method described by R. W. D. Nickalls (see the Acknowledgments
section below). Returns a three-element list. The first element will
always be real. The next two values will either be both real or both
complex numbers.
quartic_roots()
Gives the roots of the quartic equation
ax**4 + bx**3 + cx**2 + dx + e = 0
using Ferrari's method (see the Acknowledgments section below). Returns
a four-element list. The first two elements will be either both real or
both complex. The next two elements will also be alike in type.
EXPORT
There are no default exports. The functions may be named in an export
list.
Acknowledgments
The cubic
The cubic is solved by the method described by R. W. D. Nickalls, "A New
Approach to solving the cubic: Cardan's solution revealed," The
Mathematical Gazette, 77, 354-359, 1993. This article is available on
several different web sites, including
<http://www.2dcurves.com/cubic/cubic.html> and
<http://www.m-a.org.uk/resources/periodicals/online_articles_keyword_ind
ex/>. There is also a nice discussion of his paper at
<http://www.sosmath.com/algebra/factor/fac111/fac111.html>.
The paper is also downloadable from CPAN by choosing the module
Math-Polynomial-Solve-Doc. This module is a documents-only package.
Dr. Nickalls was kind enough to send me his article, with notes and
revisions, and directed me to a Matlab script that was based on that
article, written by Herman Bruyninckx, of the Dept. Mechanical Eng.,
Div. PMA, Katholieke Universiteit Leuven, Belgium. This function is an
almost direct translation of that script, and I owe Herman Bruyninckx
for creating it in the first place.
Dick Nickalls, dicknickalls@compuserve.com
Herman Bruyninckx, Herman.Bruyninckx@mech.kuleuven.ac.be, has web page
at <http://www.mech.kuleuven.ac.be/~bruyninc>. His matlab cubic solver
is at <http://people.mech.kuleuven.ac.be/~bruyninc/matlab/cubic.m>.
The quartic
The method for quartic solution is Ferrari's, as described in the web
page Karl's Calculus Tutor at
<http://www.karlscalculus.org/quartic.html>. I also made use of some
short cuts mentioned in web page Ask Dr. Math FAQ, at
<http://forum.swarthmore.edu/dr.math/faq/faq.cubic.equations.html>.
Quintic and higher.
Back when this module could only solve polynomials of degrees 1 through
4, Matz Kindahl, the author of Math::Polynomial, suggested the
poly_roots() function. Later on, Nick Ing-Simmons, who was working on a
perl binding to the GNU Scientific Library, sent a perl translation of
Hiroshi Murakami's Fortran implementation of the QR Hessenberg
algorithm, and it fit very well into the poly_roots() function. Quintics
and higher degree polynomials can now be solved, albeit through numeric
analysis methods.
Hiroshi Murakami's Fortran routines were at
<http://netlib.bell-labs.com/netlib/>, but do not seem to be available
from that source anymore.
He referenced the following articles:
R. S. Martin, G. Peters and J. H. Wilkinson, "The QR Algorithm for Real
Hessenberg Matrices", Numer. Math. 14, 219-231(1970).
B. N. Parlett and C. Reinsch, "Balancing a Matrix for Calculation of
Eigenvalues and Eigenvectors", Numer. Math. 13, 293-304(1969).
Alan Edelman and H. Murakami, "Polynomial Roots from Companion Matrix
Eigenvalues", Math. Comp., v64,#210, pp.763-776(1995).
For starting out, you may want to read
Numerical Recipes in C, by William Press, Brian P. Flannery, Saul A.
Teukolsky, and William T. Vetterling, Cambridge University Press.
SEE ALSO
Forsythe, George E., Michael A. Malcolm, and Cleve B. Moler (1977),
Computer Methods for Mathematical Computations, Prentice-Hall.
AUTHOR
John M. Gamble may be found at jgamble@ripco.com
]]>
戻る