pymath.solve_polynomial

Solves for the real roots of a polynomial of arbitrary degree, optionally restricted to an interval.

The polynomial coefficients are defined in descending power order — the order in which you would write the polynomial down. For a polynomial of degree n the array holds n + 1 numbers and ends at its first nil entry:

coeff[1] * x^n + coeff[2] * x^(n-1) + ... + coeff[n] * x + coeff[n+1]

roots = pymath.solve_polynomial(coeff [, interval, tolerance])

Parameter	Type	Description
coeff	array	The coefficients in descending power order, see above
interval	array {min, max} (optional)	The interval to search. Either bound may be nil or omitted, in which case that side is unbounded. Default: unbounded on both sides.
tolerance	number (optional)	Small positive bound below which a barely-touching or barely-complex root pair still counts as a real root. Default: an implementation defined tolerance.

Return value

Type	Description
roots	A new array of the real roots in ascending order. Empty if the polynomial has no real root in the interval.

Notes:

• The degree follows from the number of coefficients, so {1, -3, 2} is the quadratic x² - 3x + 2. Passing three coefficients gives the same roots as pymath.solve_quadratic with the same arguments, as a sorted array — except that a double root appears only once here, while solve_quadratic returns it twice.
• Leading zeros simply lower the degree, so a padded array such as {0, 0, 1, -2} is solved as the linear polynomial x - 2. This makes it safe to build coefficient arrays of a fixed length.
• Each root is reported once, whatever its multiplicity, so the length of the result is not the degree. At higher degrees a root of even multiplicity may still surface as two near-identical entries.
• A root lying exactly on a min or max bound you specified may or may not be reported. Widen the interval slightly if a boundary root matters.
• The constant polynomial and the identically zero polynomial both return an empty array — in the latter case every number is a root, so there is nothing discrete to report.
• The degree is limited to 64. Note that root finding from coefficients becomes numerically delicate well before that, so prefer the lowest degree that describes your problem.

Implementation:

• Quadratic and Cubic roots are calculated analytically. Higher roots employ an iterative solver
• The implementation currently uses an algorithm that is most suitable for low order polynomials (up to a dozen coefficients). Performance will degrade for higher powers.

Example:

local r = pymath.solve_polynomial({1, -6, 11, -6})    -- x³ - 6x² + 11x - 6
-- r ≈ {1, 2, 3}

local h = pymath.solve_polynomial({1, 0, -1}, {0})    -- x² - 1, only non-negative roots
-- h ≈ {1}                                            -- -1 is outside the interval

local q = pymath.solve_polynomial({1, -3, 2})         -- x² - 3x + 2
-- q ≈ {1, 2}                                         -- same roots as solve_quadratic(1, -3, 2)

local t = pymath.solve_polynomial({1, -2, 1})         -- x² - 2x + 1, touches the axis
-- t ≈ {1}                                            -- double root, reported once

local n = pymath.solve_polynomial({1, 0, 1})          -- x² + 1
-- n == {}                                            -- no real root

Version Support:

Minimum PYTHA Version: V27

See also:

pymath, pymath.solve_quadratic, pymath.solve_linear, pymath.least_squares