Michael T Flanagan's Java Library: Polynomials

Michael Thomas Flanagan's Java Scientific Library

Polynomial Class: Real Polynomials

Last update: 14 April 2012 Main Page of Michael Thomas Flanagan's Java Scientific Library

This class defines an object that represents a real polynomial:

The instance variables are:

a one dimensional array of length n holding the coefficients of the polynomial a[i] (double[] coeff).
an integer holding the degree n (int deg).

It includes the methods needed for performing arithmetic on, evaluating and finding the roots of real polynomials.

A complex polynomial class may found in the ComplexPoly.

import directive: import flanagan.math.Polynomial;

Summary table of constructors and methods
Details of constructors and methods
Java source file (Last update: 14 April 2012)
Other classes, in this library, used by this class
Main Page of Michael Thomas Flanagan's Java Scientific Library.

Related classes

ComplexPoly - Complex polynomial class.

SUMMARY OF CONSTRUCTORS AND METHODS

Constructors	public Polynomial(int n)
	public Polynomial(double[] a)
	public Polynomial(float[] a)
	public Polynomial(long[] a)
	public Polynomial(int[] a)
	public Polynomial(ArrayList<Object> a)
	public Polynomial(double a)
	public Polynomial(double a, double b)
	public Polynomial(double a, double b, double c)
	public Polynomial(double a, double b, double c, double d)
Set Values	public void resetPoly(double[] aa)
	public void resetPoly(ArrayList<Object> aa)
	public void resetCoeff(int i, double aa)
		public static Polynomial rootsToPoly(double[] roots)
Get Values	public double[] coefficientsCopy()
	public double[] coefficientsReference()
	public double getCoefficient(int i)
	public int getDeg()
Deep Copy	public Polynomial copy()	public static Polynomial copy(Polynomial aa)
Deep Copy	public Object clone()
Check if highest order coefficient is zero	public Polynomial reducePoly()	public static Polynomial reducePoly(Polynomial aa)
Convert Polynomial to a String	public String toString()
Convert Polynomial to a ComplexPoly	public ComplexPoly toComplexPoly()
s-Transfom of a polynomial	public ArrayList<ComplexPoly> sTransform()	public static ArrayList<ComplexPoly> sTransform(Polynomial poly)
s-Transfom of a polynomial		public static ArrayList<ComplexPoly> sTransform(double[] coeff)
Print to the screen	public void print()
Print to the screen	public void println()
Write to a Text File	public void printToText(String title)
Write to a Text File	public void printToText()
Addition	public Polynomial plus(Polynomial b)	public static Polynomial plus(Polynomial a, Polynomial b)
	public Polynomial plus(double b)	public static Polynomial plus(Polynomial a, double b)
	public Polynomial plus(int b)	public static Polynomial plus(Polynomial a, int b)
Subtraction	public Polynomial minus(Polynomial b)	public static Polynomial minus(Polynomial a, Polynomial b)
	public Polynomial minus(double b)	public static Polynomial minus(Polynomial a, double b)
	public Polynomial minus(int b)	public static Polynomial minus(Polynomial a, int b)
Multiplication	public Polynomial times(Polynomial b)	public static Polynomial times(Polynomial a, Polynomial b)
	public Polynomial times(double b)	public static Polynomial times(Polynomial a, double b)
	public Polynomial times(int b)	public static Polynomial times(Polynomial a, int b)
nth derivative	public Polynomial nthDerivative(int n)
Evaluate Polynomial or a Derivative	public double evaluate(double x)
Evaluate Polynomial or a Derivative	public double nthDerivEvaluate(int n, double x)
Equality test	public boolean equals(Polynomial cp)
Equality test	public boolean isEqual(Polynomial cp)	public static boolean isEqual(Polynomial cp1, Polynomial cp2)
Roots	public Complex[] roots()
	public Complex[] roots(boolean polish)
	public Complex[] roots(double estx)
	public Complex[] roots(Complex estx)
	public Complex[] roots(boolean polish, double estx)
	public Complex[] roots(boolean polish, Complex estx)
		public static Complex[] quadratic(double a, double b, double c)
		public static Complex[] cubic(double a, double b, double c, double d)
	public Complex[] laguerreAll()
	public Complex[] laguerreAll(boolean polish)
	public Complex[] laguerreAll(double estx)
	public Complex[] laguerreAll(Complex estx)
	public Complex[] laguerreAll(boolean polish, double estx)
	public Complex[] laguerreAll(boolean polish, Complex estx)
		public static Complex laguerre(double estx, double[] coeff, int deg)
		public static Complex laguerre(Complex estx, double[] coeff, int deg)
		public static Polynomial rootsToPoly(double[] roots)

CONSTRUCTORS

public Polynomial(int n)
public Polynomial(double[] a)
public Polynomial(float[] a)
public Polynomial(long[] a)
public Polynomial(int[] a)
public Polynomial(ArrayList<Object> a)
public Polynomial(double a)
public Polynomial(double a, double b)
public Polynomial(double a, double b, double c)
public Polynomial(double a, double b, double c, double d)

Argument: int
Usage:                      Polynomial cc = new Polynomial(n);
This creates a new instance of Polynomial(), cc, and initialises all n degree polynomial coefficients to zero

Argument: an array double[], float[], long[] or int[]
Usage:                      Polynomial cc = new Polynomial(aa);
This creates a new instance of Polynomial(), cc, and initialises the coefficients to a copy of those in the existing array of coefficients, aa, which may be double[], float[], long[] or int[].

Argument: ArrayList<Object>
Usage:                      Polynomial cc = new Polynomial(aa);
This creates a new instance of Polynomial(), cc, and initialises the coefficients to the list passed as the elements of the ArrayList argument, aa. The elements must be in the order of the coefficients of the polynomial. They may be a single type or a mixture of types. The allowed types are Double, Float, Integer, Long, Short, Byte, BigDecimal or BigInteger.

Argument: double
Usage:                      Polynomial cc = new Polynomial(a);
This creates a new instance of Polynomial(), cc, and initialises an array of a single coefficient (i.e. a constant, a) to a copy of the value in a. The variable, a, must be double. This constructor is needed by the class Loop.

Argument: double, double
Usage:                      Polynomial cc = new Polynomial(a, b);
This creates a new instance of Polynomial(), cc, and initialises an array of two coefficients (i.e. a straight line, a + b.x) to a copy of the values in a and b. The variables, a and b, must be double.

Argument: double, double, double
Usage:                      Polynomial cc = new Polynomial(a, b, c);
This creates a new instance of Polynomial(), cc, and initialises an array of three coefficients (i.e. a quadratic, a + b.x + c.x.x) to a copy of the values in a, b and c. The variables, a, b and c, must be double.

Argument: double, double, double, double
Usage:                      Polynomial cc = new Polynomial(a, b, c, d);
This creates a new instance of Polynomial(), cc, and initialises an array of four coefficients (i.e. a cubic, a + b.x + c.x.x + d.x.x.x) to a copy of the values in a, b, c and d. The variables, a, b, c and d, must be double.

METHODS

SET VALUES
public void resetPoly(double[] aa)
Usage:                      bb.resetPoly(aa);
Resets the coefficients of bb to copies of those in the argument array double[] aa.

public void resetPoly(ArrayList<Object> aa)
Usage:                      bb.resetPoly(aa);
Resets the coefficients of bb to the list passed as the elements of the ArrayList argument, aa. The elements must be in the order of the coefficients of the polynomial. They may be a single type or a mixture of types. The allowed types are double, Double, Float, Integer, Long, Short, Byte, BigDecimal, BigInteger or Phasor.

public void resetCoeff(int i, double aa)
Usage:                      bb.resetCoeff(i, aa);
Resets the ith coefficient of bb to a copy of aa where aa is double.

public static Polynomial rootsToPoly(double[ ] roots)
Usage:                      aa = Polynomial(roots);
Returns a Polynomial, aa, given the roots of this polynomial, stored in the double array, roots.

GET VALUES
public double[] coefficientsCopy()
Usage:                      bb = aa.coefficientsCopy();
Returns a copy of the polynomial coefficients in the Polynomial, aa, to the coefficient array in the double array, bb.

public double[] coefficientsReference() Usage:                      bb = aa.coefficientsReference();
Returns a reference (a pointer) to the polynomial coefficients in the Polynomial, aa, to bb.

public double getCoefficient(int i)
Usage:                      bb = aa.getCoefficient(i);
Returns a copy of the ith coefficient in the Polynomial, aa, to the double, bb.

public int getDeg()
Usage:                      i = aa.getDeg();
Returns the degree of the polynomial.

DEEP COPY
public Polynomial copy()
public Object clone()
public static Polynomial copy(Polynomial aa)
Usage:                      bb = aa.copy();
Usage:                      bb = Polynomial.copy(aa);
Returns a deep copy of the Polynomial, aa, to the Polynomial, bb.

Clone Polynomial
Usage:                      bb = (Polynomial) aa.clone();
Returns a deep copy of the Polynomial, aa, to the Polynomial, bb. This method overrides java.lang.Object.clone()

RETURN A MATCHING POLYNOMIAL IN WHICH THE HIGHEST ORDER COEFFICIENT IS NOT ZERO
public Polynomial reducePoly()
public static Polynomial reducePoly(Polynomial aa)
Usage: bb = aa.reducePoly();
Usage: bb = Polynomial.reducePoly(aa);
Returns a Polynomial, bb, in which the highest order coefficient has been removed if it is zero. The entered Polynomial, aa, is examined iteratively until the highest order coefficient is non-zero, e.g.
3 - 8x would be returned as bb if aa was entered as
3 - 8x + 0.x^2 + 0.x^3

CONVERT THE POLYNOMIAL TO A STRING
public String toString()
Usage:
ss = aa.toString();
Converts the polynomial (in aaa in the above usage) to a String (ss in the above usage) of the form a[0] + a[1].x + a[2].x^2 etc.
.

PRINT THE POLYNOMIAL TO THE SCREEN
public void print()
public void println()
Usage:
aa.print();
Writes the polynomial to the screen in the form a[0] + a[1].x + a[2].x^2 etc.
Usage:
aa.println();
Writes the polynomial to the screen, in the form a[0] + a[1].x + a[2].x^2etc., followed by a line return.

WRITE THE POLYNOMIAL TO A TEXT FILE
public void printToText(public void)
public void printToText()
Usage:
aa.printToText(title);
Opens a text file with the name in the String in the argument, title, with .txt appended. Writes, to this file, the file name, the time and date, the degree of the polynomial in the Polynomial aa and the coefficients of the polynomial in aa.
Usage:
aa.printToText();
Opens a text file PolynomialOutput.txt. Writes, to this file, the file name, the time and date, the degree of the polynomial in the Polynomial aa and the coefficients of the polynomial in aa.

ADDITION OF TWO POLYNOMIALS
public Polynomial plus(Polynomial b)
public Polynomial plus(double b)
public Polynomial plus(int b)
public static Polynomial plus(Polynomial a, Polynomial b)
public static Polynomial plus(Polynomial a, double b)
public static Polynomial plus(Polynomial a, int b)
Usage:
                     c = a.plus(b);
                     c = Polynomial.plus(a,b);
Returns the polynomial, e.g. c, that is the sum of two polynomials (a and b), a polynomial (a) and a double number (b) or a polynomial (a) and an int number (b), e.g. a + b.

SUBTRACTION OF TWO POLYNOMIALS
public Polynomial minus(Polynomial b)
public Polynomial minus(double b)
public Polynomial minus(int b)
public static Polynomial minus(Polynomial a, Polynomial b)
public static Polynomial minus(Polynomial a, double b)
public static Polynomial minus(Polynomial a, int b)
Usage:
                     c = a.minus(b);
                     c = Polynomial.minus(a,b);
Returns the polynomial, e.g. c, that is the difference between two polynomials (a and b), a polynomial (a) and a double number (b) or a polynomial (a) and an int number (b), e.g. a - b.

MULTIPLICATION OF TWO POLYNOMIALS
public Polynomial times(Polynomial b)
public Polynomial times(double b)
public Polynomial times(int b)
public static Polynomial times(Polynomial a, Polynomial b)
public static Polynomial times(Polynomial a, double b)
public static Polynomial times(Polynomial a, int b)
Usage:
                     c = a.times(b);
                     c = Polynomial.times(a,b);
Returns the polynomial, e.g. c, that is the product of two polynomials (a and b), a polynomial (a) and a double number (b) or a polynomial (a) and an int number (b), e.g. a*b.

OBTAIN THE nTH DERIVATIVE COEFFICIENTS
public Polynomial nthDerivative(int n)
Usage: yy = aa.nthDerivative(n);
Returns, as a new Polynomial (yy in the above example), the coefficients and degree of the nth derivative of the polynomial, represented in the above example by aa. The value of n is passed as an integer argument.

EVALUATE A POLYNOMIAL AND ITS DERIVATIVES
Evaluate a polynomial
public double evaluate(double x)
Usage: y = aa.evaluate(x);
Evaluates the polynomial, represented by aa, at a value of x.

Evaluate the nth derivative of a polynomial
public double nthDerivEvaluate(int n, double x)
Usage: y = aa.nthDerivEvaluate(n, x);
Evaluates the nth derivative of the polynomial, represented by aa, at a value of x.

CHECK WHETHER TWO POLYNOLMIALS ARE EQUAL
public boolean equals(Polynomial poly)
public boolean isEqual(Polynomial poly)
public static boolean isEqual(Polynomial poly1, Polynomial poly2)
Usage:                      test = poly1.equals(poly2);
Usage:                      test = poly1.isEqual(poly2);
Usage:                      test = Polynomial.isEqual(poly1, poly2);
Returns true if all the instance variables of the Polynomial, poly1, are identical to those of the Polynomial, poly2. Returns false if they are not.

OBTAIN THE s-TRANSFORM OF A POLYNOMIAL
public ArrayList<ComplexPoly> sTransform()
public static ArrayList<ComplexPoly> sTransform(Polynomial poly)
public static ArrayList<ComplexPoly> sTransform(double[] coeff)
Usage: alist = aa.sTransform();
Usage: alist = Polynomial.sTransform(aa);
Returns the the s-transform of the polynomial, aa,

using the transform

The returned ArrayList [alist] contains two elements. The first is a complex polynomial [a ComplexPoly] representing the numerator of the transformed polynomial. The second is a complex polynomial [a ComplexPoly] representing the denominator of the transformed polynomial.

Usage: alist = Polynomial.sTransform(coeff);
Returns the the s-transform of a polynomial whose coefficients are passed as the argument coeff in the order as defined for the polynomial above.

ROOT OF A POLYNOMIAL
For general details of root searching and a discussion of the rounding errors in root searching see Numerical Recipes, The Art of Scientific Computing by W H Press, S A Teukolsky, W T Vetterling & B P Flannery, Cambridge University Press (http://www.nr.com/).

All roots are returned as Complex though they may, in some cases, all be real. See isReal and isRealPerCent methods in the Complex class for checking whether an array of double are all real and see the ArrayMaths class for methods for converting Complex[] to a real array, e.g. double[]

GENERAL
public Complex[] roots()
public Complex[] roots(boolean polish)
public Complex[] roots(double estx)
public Complex[] roots(Complex estx)
public double[] roots(boolean polish, double estx)
public double[] roots(boolean polish, Complex estx)

Usage:                      x = aa.roots();
Usage:                      x = aa.roots(polish);
Usage:                      x = aa.roots(estx);
Usage:                      x = aa.roots(polish, estx);

Returns the roots of the polynomial, represented by aa, into the Complex array, x.

Polynomial degree>3: The method roots(..) uses the Laguerre procedure as described in the methods laguerre() and laguerreAll()
The boolean variable polish invokes root polishing, as described under Laguerre, if true. If polish is not included in the argument list its default value is true. [see below under LAGUERRE for a detailed discussion of polish].
The double or Complex variable estx is the initial estimate of the roots needed by the method laguerre(...). If estx is not included in the argument list its default value is zero. The default value of zero is the preferred value of estx. [see below under LAGUERRE for a detailed discussion of estx].
Though the Laguerre procedure is a robust method it is not possible to guarantee the return of the exact roots for polynomials of degree>3, where laguerre(..) is used. If possible the results should be inspected as to their reasonableness in the light of the physical model that the polynomial represents.
If the number of iterations allowed in laguerre() is exceeded a message to this effect will be printed to screen and the current estimate of the root returned. This may be a good estimate of the exact value as it is difficult to set the convergence criteria to automatically cover all polynomials. Try reseting the convergence parameter testConverge to a value larger than the default value of 1e-7 and compare the results [see LAGUERRE - CONVERGENCE below]. See Press et al. for details of the Laguerre procedure.
Polynomial degree=3: The method roots(..) uses the solution of a cubic as described in the method cubic(a,b,c,d) [see below]
polish and estx are NOT required.
Polynomial degree=2: The method roots(..) uses the solution of a quadratic as described in the method quadratic(a,b,c) [see below]
polish and estx are NOT required.
Polynomial degree=1: The method roots(..) returns -a[0]/a[1]. polish and estx are NOT required.
Polynomial degree=0: The method roots(..) throws an IllegalArgumentException.

QUADRATIC
public static Complex[] quadratic( double a, double b, double c)
Usage:                      xx = Polynomial.quadratic(a, b, c);
Returns the roots of the quadratic
                     a + b.x + c.x²
into the Complex array, xx. NB the order of the coefficients a, b and c.
Uses the procedures needed to avoid rounding errors as described by Press et al.

CUBIC
public static Complex[] cubic(double a, double b, double c, double d)
Usage:                      xx = Polynomial.cubic(a, b, c, d);
Returns the roots of the cubic
                     a + b.x + c.x² + d.x³
into the Complex array, xx. NB the order of the coefficients a, b, c and d.
Uses the procedures needed to avoid rounding errors as described by Press et al.

LAGUERRE - ALL ROOTS
public Complex[] laguerreAll()
public Complex[] laguerreAll(boolean polish)
public Complex[] laguerreAll(double estx)
public Complex[] laguerreAll(Complex estx)
public Complex[] laguerreAll(boolean polish, double estx)
public Complex[] laguerreAll(boolean polish, Complex estx)

Returns all the roots of the polynomial, represented by aa, into the Complex array, x. It uses the Laguerre procedure. It repetitively invokes the method laguerre() [see below], which finds a single root, deflating the polynomial by synthetic division after finding each root. If the boolean argument, polish, is true it then polishes the roots, using laguerre() and the undeflated coefficients. If polish is false the roots are returned without polishing to be polished elsewhere at the users choice. The double or Complex variable, estx, is the initial estimate of each root. Zero is the preferred default option for estx but if laguerre fails changing estx may help. The method laguerreAll(..) returns the roots sorted by their real parts.

Usage:                      x = aa.laguerreAll();
Default values: polish is true; initial estimates are all zero

Usage:                      x = aa.laguerreAll(polish);
polish is boolean.
Default values: initial estimates of the roots are all zero

Usage:                      x = aa.laguerreAll(estx);
The initial estimate of the roots, estx, is double.
Default values: polish is true

Usage:                      x = aa.laguerreAll(polish, estx);
polish is boolean and the initial estimate of the roots, estx, is double.

Though this is a robust method it is not possible to guarantee the return of the exact roots. If possible the results should be inspected as to their reasonableness in the light of the physical model that the polynomial represents. If the number of iterations allowed in laguerre() is exceeded a message to this effect will be printed to screen and the current estimate of the root returned. This may be a good estimate of the exact value as it is difficult to set the convergence criteria to automatically cover all polynomials. Try reseting the convergence parameter testConverge to a value larger than the default value of 1e-7 and compare the results [see LAGUERRE - CONVERGENCE below].
See Press et al. for details.

LAGUERRE - A SINGLE ROOT
public static Complex laguerre(double estx, double[] coeff, int deg)
public static Complex laguerre(Complex estx, double[] coeff, int deg)
Usage:                      x = double.laguerre(xx, aa, deg);
Returns a single root of the polynomial, of degree, deg, whose coefficients are stored in the double array aa, given an initial estimate of the root, xx. It uses the Laguerre procedure.
Though this is a robust method it is not possible to guarantee the return of the exact root. If possible the result should be inspected as to its reasonableness in the light of the physical model that the polynomial represents. If the number of iterations allowed in laguerre() is exceeded a message to this effect will be printed to screen and the current estimate of the root returned. This may be a good estimate of the exact value as it is difficult to set the convergence criteria to automatically cover all polynomials. Try reseting the convergence parameter testConverge to a value larger than the default value of 1e-7 and compare the results [see LAGUERRE - CONVERGENCE below].
The method laguerreAll() [see above] calls this method repetitively to obtain all the roots deflating the polynomial, after finding each root, by synthetic division.
See the method laguerre() above and Press et al. for details.

CREATE A Polynomial GIVEN THE POLYNOMIAL'S ROOTS
public static Polynomial rootsToPoly(double [ ] roots)
Usage:                      aa = Polynomial(roots);
Returns a Polynomial, aa, given the roots of this polynomial, stored in the double array, roots.

OTHER CLASSES USED BY THIS CLASS

This class uses the following classes in this library:

This page was prepared by Dr Michael Thomas Flanagan