Package org.djutils.polynomialroots

Class PolynomialRoots2

java.lang.Object

org.djutils.polynomialroots.PolynomialRoots2

public final class PolynomialRoots2
extends Object

PolynomialRoots2 implements functions to find all roots of linear, quadratic, cubic and quartic polynomials, as well as higher order polynomials without restrictions on the order.

Copyright (c) 2020-2020 Delft University of Technology, Jaffalaan 5, 2628 BX Delft, the Netherlands. All rights reserved. See for project information https://djutils.org. The DJUTILS project is distributed under a three-clause BSD-style license, which can be found at https://djutils.org/docs/license.html.

Author:

Alexander Verbraeck, Peter Knoppers

Method Summary

Modifier and Type	Method	Description
static Complex[]	cubicRootsAberthEhrlich(double a3, double a2, double a1, double a0)	CUBIC POLYNOMIAL ROOT SOLVER.
static Complex[]	cubicRootsCardano(double a, double b, double c, double d)	CUBIC POLYNOMIAL ROOT SOLVER.
static Complex[]	cubicRootsDurandKerner(double a3, double a2, double a1, double a0)	CUBIC POLYNOMIAL ROOT SOLVER.
static Complex[]	cubicRootsNewtonFactor(double a3, double a2, double a1, double a0)	CUBIC POLYNOMIAL ROOT SOLVER.
static Complex[]	linearRoots(double q0)	LINEAR POLYNOMIAL ROOT SOLVER.
static Complex[]	linearRoots(double q1, double q0)	LINEAR POLYNOMIAL ROOT SOLVER.
static void	main(String[] args)
static Complex[]	quadraticRoots(double q1, double q0)	QUADRATIC POLYNOMIAL ROOT SOLVER
static Complex[]	quadraticRoots(double q2, double q1, double q0)	QUADRATIC POLYNOMIAL ROOT SOLVER
static Complex[]	quarticRootsAberthEhrlich(double a4, double a3, double a2, double a1, double a0)	QUADRATIC POLYNOMIAL ROOT SOLVER.
static Complex[]	quarticRootsDurandKerner(double a4, double a3, double a2, double a1, double a0)	QUADRATIC POLYNOMIAL ROOT SOLVER.
static double	rootBisection(double[] a, double startMin, double startMax, double allowedError)	Polynomial root finder using the bisection method combined with bisection to avoid cycles and the algorithm going out of bounds.
static double	rootNewtonRaphson(double[] a, double allowedError)	Polynomial root finder using the Newton-Raphson method.
static Complex[]	rootsAberthEhrlich(Complex[] a)	Polynomial root finder using the Aberth-Ehrlich method or Aberth method, with complex coefficients for the polynomial equation.
static Complex[]	rootsDurandKerner(Complex[] a)	Polynomial root finder using the Durand-Kerner method, with complex coefficients for the polynomial equation.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

linearRoots

public static Complex[] linearRoots(double q1,
                                    double q0)

LINEAR POLYNOMIAL ROOT SOLVER.

Calculates the root of the linear polynomial:
q1 * x + q0

Parameters:

q1 - double; coefficient of the x term

q0 - double; independent coefficient

Returns:

Complex[]; the roots of the equation

linearRoots

public static Complex[] linearRoots(double q0)

LINEAR POLYNOMIAL ROOT SOLVER.

Calculates the root of the linear polynomial:
x + q0

Parameters:

q0 - double; independent coefficient

Returns:

Complex[]; the roots of the equation

quadraticRoots

public static Complex[] quadraticRoots(double q2,
                                       double q1,
                                       double q0)

QUADRATIC POLYNOMIAL ROOT SOLVER

Calculates all real + complex roots of the quadratic polynomial:
q2 * x^2 + q1 * x + q0
The code checks internally if rescaling of the coefficients is needed to avoid overflow.

The order of the roots is as follows:
1) For real roots, the order is according to their algebraic value on the number scale (largest positive first, largest negative last).
2) Since there can be only one complex conjugate pair root, no order is necessary.
q1 : coefficient of x term q0 : independent coefficient

Parameters:

q2 - double; coefficient of the quadratic term

q1 - double; coefficient of the x term

q0 - double; independent coefficient

Returns:

Complex[]; the roots of the equation

quadraticRoots

public static Complex[] quadraticRoots(double q1,
                                       double q0)

QUADRATIC POLYNOMIAL ROOT SOLVER

Calculates all real + complex roots of the quadratic polynomial:
x^2 + q1 * x + q0
The code checks internally if rescaling of the coefficients is needed to avoid overflow.

The order of the roots is as follows:
1) For real roots, the order is according to their algebraic value on the number scale (largest positive first, largest negative last).
2) Since there can be only one complex conjugate pair root, no order is necessary.
q1 : coefficient of x term q0 : independent coefficient

Parameters:

q1 - double; coefficient of the x term

q0 - double; independent coefficient

Returns:

Complex[]; the roots of the equation

cubicRootsNewtonFactor

public static Complex[] cubicRootsNewtonFactor(double a3,
                                               double a2,
                                               double a1,
                                               double a0)

CUBIC POLYNOMIAL ROOT SOLVER.

Calculates all (real and complex) roots of the cubic polynomial:
a * x^3 + b * x^2 + c * x + d
The roots are found using the Newton-Raphson algorithm for the first (real) root, and then deflate the equation to a quadratic equation to find the other two roots.

The order of the roots is as follows: 1) For real roots, the order is according to their algebraic value on the number scale (largest positive first, largest negative last). 2) Since there can be only one complex conjugate pair root, no order is necessary. 3) All real roots precede the complex ones.

Parameters:

a3 - double; coefficient of the cubic term

a2 - double; coefficient of the quadratic term

a1 - double; coefficient of the linear term

a0 - double; coefficient of the independent term

Returns:

Complex[]; array of Complex with all the roots; there can be one, two or three roots.

cubicRootsCardano

public static Complex[] cubicRootsCardano(double a,
                                          double b,
                                          double c,
                                          double d)

CUBIC POLYNOMIAL ROOT SOLVER.

Calculates all (real and complex) roots of the cubic polynomial:
a * x^3 + b * x^2 + c * x + d
The roots are found using Cardano's algorithm.

The order of the roots is as follows: 1) For real roots, the order is according to their algebraic value on the number scale (largest positive first, largest negative last). 2) Since there can be only one complex conjugate pair root, no order is necessary. 3) All real roots precede the complex ones.

Parameters:

a - double; coefficient of the cubic term

b - double; coefficient of the quadratic term

c - double; coefficient of the linear term

d - double; coefficient of the independent term

Returns:

Complex[]; array of Complex with all the roots; there can be one, two or three roots.

cubicRootsDurandKerner

public static Complex[] cubicRootsDurandKerner(double a3,
                                               double a2,
                                               double a1,
                                               double a0)

CUBIC POLYNOMIAL ROOT SOLVER.

Calculates all (real and complex) roots of the cubic polynomial:
a3 * x^3 + a2 * x^2 + a1 * x + a0
The roots are found using Durand-Kerner's algorithm.

Parameters:

a3 - double; coefficient of the cubic term

a2 - double; coefficient of the quadratic term

a1 - double; coefficient of the linear term

a0 - double; coefficient of the independent term

Returns:

Complex[]; array of Complex with all the roots; there can be one, two or three roots.

cubicRootsAberthEhrlich

public static Complex[] cubicRootsAberthEhrlich(double a3,
                                                double a2,
                                                double a1,
                                                double a0)

CUBIC POLYNOMIAL ROOT SOLVER.

Calculates all (real and complex) roots of the cubic polynomial:
a3 * x^3 + a2 * x^2 + a1 * x + a0
The roots are found using Aberth-Ehrlich's algorithm.

Parameters:

a3 - double; coefficient of the cubic term

a2 - double; coefficient of the quadratic term

a1 - double; coefficient of the linear term

a0 - double; coefficient of the independent term

Returns:

Complex[]; array of Complex with all the roots; there can be one, two or three roots.

quarticRootsDurandKerner

public static Complex[] quarticRootsDurandKerner(double a4,
                                                 double a3,
                                                 double a2,
                                                 double a1,
                                                 double a0)

QUADRATIC POLYNOMIAL ROOT SOLVER.

Calculates all (real and complex) roots of the cubic polynomial:
a4 * x^4 + a3 * x^3 + a2 * x^2 + a1 * x + a0
The roots are found using Durand-Kerner's algorithm.

Parameters:

a4 - double; coefficient of the quartic term

a3 - double; coefficient of the cubic term

a2 - double; coefficient of the quadratic term

a1 - double; coefficient of the linear term

a0 - double; coefficient of the independent term

Returns:

Complex[]; array of Complex with all the roots; always 4 roots are returned; there can be double roots

quarticRootsAberthEhrlich

public static Complex[] quarticRootsAberthEhrlich(double a4,
                                                  double a3,
                                                  double a2,
                                                  double a1,
                                                  double a0)

QUADRATIC POLYNOMIAL ROOT SOLVER.

Calculates all (real and complex) roots of the cubic polynomial:
a4 * x^4 + a3 * x^3 + a2 * x^2 + a1 * x + a0
The roots are found using Aberth-Ehrlich's algorithm.

Parameters:

a4 - double; coefficient of the quartic term

a3 - double; coefficient of the cubic term

a2 - double; coefficient of the quadratic term

a1 - double; coefficient of the linear term

a0 - double; coefficient of the independent term

Returns:

Complex[]; array of Complex with all the roots; always 4 roots are returned; there can be double roots

rootsDurandKerner

public static Complex[] rootsDurandKerner(Complex[] a)

Polynomial root finder using the Durand-Kerner method, with complex coefficients for the polynomial equation. Own implementation. See https://en.wikipedia.org/wiki/Durand%E2%80%93Kerner_method for brief information.

Parameters:

a - Complex[]; the complex factors of the polynomial, where the index i indicate the factor for x^i, so the polynomial is
a[n]x^n + a[n-1]x^(n-1) + ... + a[2]a^2 + a[1]x + a[0]

Returns:

Complex[] all roots of the equation, where real roots are coded with Im = 0

rootsAberthEhrlich

public static Complex[] rootsAberthEhrlich(Complex[] a)

Polynomial root finder using the Aberth-Ehrlich method or Aberth method, with complex coefficients for the polynomial equation. Own implementation. See https://en.wikipedia.org/wiki/Aberth_method for brief information.

Parameters:

a - Complex[]; the complex factors of the polynomial, where the index i indicate the factor for x^i, so the polynomial is
a[n]x^n + a[n-1]x^(n-1) + ... + a[2]a^2 + a[1]x + a[0]

Returns:

Complex[] all roots of the equation, where real roots are coded with Im = 0

rootNewtonRaphson

public static double rootNewtonRaphson(double[] a,
                                       double allowedError)

Polynomial root finder using the Newton-Raphson method. See https://en.wikipedia.org/wiki/Newton%27s_method for brief information about the Newton-Raphson or Newton method for root finding.

Parameters:

a - double[]; the factors of the polynomial, where the index i indicate the factor for x^i, so the polynomial is
a[n]x^n + a[n-1]x^(n-1) + ... + a[2]a^2 + a[1]x + a[0]

allowedError - double; the allowed absolute error in the result

Returns:

double the root of the equation that has been found on the basis of the start value, or NaN if not found within the allowed error bounds and the allowed number of steps.

rootBisection

public static double rootBisection(double[] a,
                                   double startMin,
                                   double startMax,
                                   double allowedError)

Polynomial root finder using the bisection method combined with bisection to avoid cycles and the algorithm going out of bounds. Implementation based on Numerical Recipes in C, section 9.4, pp 365-366. See https://en.wikipedia.org/wiki/Newton%27s_method for brief information about the Newton-Raphson or Newton method for root finding.

Parameters:

a - double[]; the factors of the polynomial, where the index i indicate the factor for x^i, so the polynomial is
a[n]x^n + a[n-1]x^(n-1) + ... + a[2]a^2 + a[1]x + a[0]

startMin - double; the lowest initial search value

startMax - double; the highest initial search value

allowedError - double; the allowed absolute error in the result

Returns:

double the root of the equation that has been found on the basis of the start values, or NaN if not found within the allowed error bounds and the allowed number of steps.

main

public static void main(String[] args)

Parameters:

args - String[] not used