++ed by:
DEMIAN
1 non-PAUSE user
Author image John Gamble

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_index/. There is also a nice discussion of his paper at http://www.sosmath.com/algebra/factor/fac111/fac111.html.

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.

Andy Stein has written a version of cubic.m that will work with vectors. It is included with this package in the eg directory.

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