HMath.Polynomial¶

Description

Univariate polynomials with ascending coefficients: [a0,a1,...] means a0+a1*x+.... Trailing exact zeros are removed; zero is [] with degree Nothing. Exact algorithms use Rational. Floating root solvers use Complex Double with explicit tolerance and iteration budgets, returning failure when residuals or corrections do not converge.

On this page¶

API	Purpose
Polynomial	Canonical, finite ascending coefficient sequence.
polynomial	Construct a polynomial, deleting trailing exact zeros (no floating tolerance).
coefficients	Ascending coefficients, with no trailing zero; zero gives an empty list.
polynomialDegree	Degree of a nonzero polynomial; zero has no degree.
evaluatePolynomial	Horner evaluation, with the constant coefficient first in storage.
addPolynomial	Coefficientwise addition with canonical exact-zero normalization.
subtractPolynomial	Coefficientwise subtraction.
scalePolynomial	Multiply every coefficient by a scalar.
multiplyPolynomial	Exact schoolbook convolution, including zero polynomials.
composePolynomial	Composition p(q(x)) by polynomial Horner evaluation.
dividePolynomial	Long division over a field.
monicPolynomial	Normalize a nonzero polynomial to leading coefficient one; zero remains zero.
gcdPolynomial	Monic Euclidean GCD over an exact field; gcd(0,0)=0.
differentiatePolynomial	Formal derivative.
integratePolynomial	Formal integral with the supplied integration constant.
squareFreeFactors	Monic square-free factors with positive multiplicities over Rational.
rationalRoots	Rational roots with exact multiplicities using the rational-root theorem.
factorRationalPolynomial	Complete rational factorization by bounded Kronecker interpolation.
sturmSequence	Sturm chain over exact rationals, after removing the derivative GCD.
countRealRoots	Number of distinct real roots in (a,b].
isolateRealRoots	Isolate every distinct real root in rational intervals with disjoint interiors and width at most tolerance.
durandKerner	Durand--Kerner simultaneous complex root iteration.
aberthEhrlich	Aberth--Ehrlich simultaneous iteration, combining Newton corrections with mutual-root repulsion.
companionMatrix	Frobenius companion matrix of a nonconstant polynomial, with ones on the subdiagonal and negated monic coefficients in the last column.
lagrangeInterpolation	Exact Lagrange interpolating polynomial.
newtonInterpolation	Newton divided differences, returned in the standard power basis.
chebyshevPolynomial	Chebyshev T_n, normalized by T_0=1, T_1=x.
legendrePolynomial	Legendre P_n, normalized by P_n(1)=1.
hermitePolynomial	Physicists' Hermite H_n: H_0=1, H_1=2x.
laguerrePolynomial	Ordinary Laguerre L_n with alpha=0 and L_n(0)=1.
bernsteinPolynomial	Bernstein basis binomial(n,k)x^k(1-x)^(n-k) for 0<=k<=n.
polynomialRegression	Least-squares power-basis regression using column-pivoted Householder QR.
chebyshevApproximation	Truncated Chebyshev interpolation at first-kind nodes on [-1,1], returned in power basis.
PowerSeries	A finite Taylor jet, coefficients ascending and zeros retained.
powerSeries	Construct a jet with explicit coefficients, including trailing zeros.
seriesCoefficients	Stored Taylor coefficients; coefficient n multiplies x^n, not x^n/n!.
addSeries	Add jets to their common truncation order.
multiplySeries	Multiply jets by truncated convolution.
reciprocalSeries	Reciprocal jet from coefficient recurrence; constant term must be nonzero.
divideSeries	Divide jets to their common order; denominator constant must be nonzero.
composeSeries	Formal composition to the inner jet's order.
differentiateSeries	Derivative jet has one fewer coefficient.
integrateSeries	Integral jet with supplied constant, one coefficient longer.
expSeries	Exponential of a finite jet from b'=a'b; constant uses the coefficient type's exp.
logSeries	Formal log through derivativedivisionintegration.
RationalFunction	Reduced exact rational function with monic denominator.
rationalFunction	Normalize by polynomial GCD and reject a zero denominator.
rationalNumerator	Reduced numerator.
rationalDenominator	Monic reduced denominator.
evaluateRationalFunction	Exact evaluation, rejecting poles.
addRationalFunction	Exact rational-function addition with cancellation.
multiplyRationalFunction	Exact rational-function multiplication with cancellation.
partialFractions	Exact partial fractions over Q.

Documentation

Polynomial

data Polynomial a Source #

Canonical, finite ascending coefficient sequence.

Instances

Instances details

Show a => Show (Polynomial a) Source #
Instance details Defined in HMath.Polynomial Methods showsPrec :: Int -> Polynomial a -> ShowS # show :: Polynomial a -> String # showList :: [Polynomial a] -> ShowS #
Eq a => Eq (Polynomial a) Source #
Instance details Defined in HMath.Polynomial Methods (==) :: Polynomial a -> Polynomial a -> Bool # (/=) :: Polynomial a -> Polynomial a -> Bool #
(Eq a, Num a) => Ring (Polynomial a) Source #
Instance details Defined in HMath.Algebra Methods negateRing :: Polynomial a -> Polynomial a Source #
(Eq a, Num a) => Semiring (Polynomial a) Source #
Instance details Defined in HMath.Algebra Methods zero :: Polynomial a Source # one :: Polynomial a Source # plus :: Polynomial a -> Polynomial a -> Polynomial a Source # times :: Polynomial a -> Polynomial a -> Polynomial a Source #

polynomial

polynomial :: (Eq a, Num a) => [a] -> Polynomial a Source #

Construct a polynomial, deleting trailing exact zeros (no floating tolerance).

coefficients

coefficients :: Polynomial a -> [a] Source #

Ascending coefficients, with no trailing zero; zero gives an empty list.

polynomialDegree

polynomialDegree :: Polynomial a -> Maybe Int Source #

Degree of a nonzero polynomial; zero has no degree.

evaluatePolynomial

evaluatePolynomial :: Num a => Polynomial a -> a -> a Source #

Horner evaluation, with the constant coefficient first in storage.

addPolynomial

addPolynomial :: (Eq a, Num a) => Polynomial a -> Polynomial a -> Polynomial a Source #

Coefficientwise addition with canonical exact-zero normalization.

subtractPolynomial

subtractPolynomial :: (Eq a, Num a) => Polynomial a -> Polynomial a -> Polynomial a Source #

Coefficientwise subtraction.

scalePolynomial

scalePolynomial :: (Eq a, Num a) => a -> Polynomial a -> Polynomial a Source #

Multiply every coefficient by a scalar.

multiplyPolynomial

multiplyPolynomial :: (Eq a, Num a) => Polynomial a -> Polynomial a -> Polynomial a Source #

Exact schoolbook convolution, including zero polynomials.

composePolynomial

composePolynomial :: (Eq a, Num a) => Polynomial a -> Polynomial a -> Polynomial a Source #

Composition p(q(x)) by polynomial Horner evaluation.

dividePolynomial

dividePolynomial :: (Eq a, Fractional a) => Polynomial a -> Polynomial a -> Either MathError (Polynomial a, Polynomial a) Source #

Long division over a field. Exact coefficient equality controls termination; numerical cancellation is truncated at the eliminated leading coefficient. Zero denominator is rejected.

monicPolynomial

monicPolynomial :: (Eq a, Fractional a) => Polynomial a -> Polynomial a Source #

Normalize a nonzero polynomial to leading coefficient one; zero remains zero.

gcdPolynomial

gcdPolynomial :: (Eq a, Fractional a) => Polynomial a -> Polynomial a -> Polynomial a Source #

Monic Euclidean GCD over an exact field; gcd(0,0)=0.

differentiatePolynomial

differentiatePolynomial :: (Eq a, Num a) => Polynomial a -> Polynomial a Source #

Formal derivative.

integratePolynomial

integratePolynomial :: (Eq a, Fractional a) => a -> Polynomial a -> Polynomial a Source #

Formal integral with the supplied integration constant.

squareFreeFactors

squareFreeFactors :: Polynomial Rational -> [(Polynomial Rational, Int)] Source #

Monic square-free factors with positive multiplicities over Rational. The leading coefficient is omitted; constant polynomials have no factors.

rationalRoots

rationalRoots :: Int -> Polynomial Rational -> Either MathError [(Rational, Int)] Source #

Rational roots with exact multiplicities using the rational-root theorem. Budget applies to integer factorization of numerator and leading coefficient.

factorRationalPolynomial

factorRationalPolynomial :: Int -> Polynomial Rational -> Either MathError (Rational, [(Polynomial Rational, Int)]) Source #

Complete rational factorization by bounded Kronecker interpolation. Returns the original leading scalar and monic irreducible factors with multiplicity. Every candidate is divided exactly. Exhausting the candidate budget reports failure, never an unsupported claim of irreducibility. Intended for small exact polynomials; coefficient divisor enumeration also uses this budget.

sturmSequence

sturmSequence :: Polynomial Rational -> Either MathError [Polynomial Rational] Source #

Sturm chain over exact rationals, after removing the derivative GCD. Zero polynomial is invalid. Square-free normalization ensures a repeated root cannot make every chain member vanish and destroy one-sided variation counts.

countRealRoots

countRealRoots :: Polynomial Rational -> Rational -> Rational -> Either MathError Int Source #

Number of distinct real roots in (a,b]. Endpoints that are roots of the polynomial are rejected to make the interval convention unambiguous.

isolateRealRoots

isolateRealRoots :: Int -> Rational -> Polynomial Rational -> Either MathError [(Rational, Rational)] Source #

Isolate every distinct real root in rational intervals with disjoint interiors and width at most tolerance. Intervals have the root-count convention (a,b]; shared endpoints belong to the interval on their left. Bisection budget bounds visited intervals; all arithmetic is exact.

durandKerner

durandKerner :: Int -> Double -> Polynomial (Complex Double) -> Either MathError [Complex Double] Source #

Durand--Kerner simultaneous complex root iteration. Distinct initial roots are placed on a Cauchy-bound circle; repeated roots may converge slowly.

aberthEhrlich

aberthEhrlich :: Int -> Double -> Polynomial (Complex Double) -> Either MathError [Complex Double] Source #

Aberth--Ehrlich simultaneous iteration, combining Newton corrections with mutual-root repulsion. All roots are verified against a scaled residual.

companionMatrix

companionMatrix :: (Eq a, Fractional a) => Polynomial a -> Either MathError (Matrix a) Source #

Frobenius companion matrix of a nonconstant polynomial, with ones on the subdiagonal and negated monic coefficients in the last column.

lagrangeInterpolation

lagrangeInterpolation :: (Eq a, Fractional a) => [(a, a)] -> Either MathError (Polynomial a) Source #

Exact Lagrange interpolating polynomial. Duplicate nodes are rejected.

newtonInterpolation

newtonInterpolation :: (Eq a, Fractional a) => [(a, a)] -> Either MathError (Polynomial a) Source #

Newton divided differences, returned in the standard power basis.

chebyshevPolynomial

chebyshevPolynomial :: (Eq a, Fractional a) => Int -> Either MathError (Polynomial a) Source #

Chebyshev T_n, normalized by T_0=1, T_1=x.

legendrePolynomial

legendrePolynomial :: (Eq a, Fractional a) => Int -> Either MathError (Polynomial a) Source #

Legendre P_n, normalized by P_n(1)=1.

hermitePolynomial

hermitePolynomial :: (Eq a, Fractional a) => Int -> Either MathError (Polynomial a) Source #

Physicists' Hermite H_n: H_0=1, H_1=2x.

laguerrePolynomial

laguerrePolynomial :: (Eq a, Fractional a) => Int -> Either MathError (Polynomial a) Source #

Ordinary Laguerre L_n with alpha=0 and L_n(0)=1.

bernsteinPolynomial

bernsteinPolynomial :: (Eq a, Fractional a) => Int -> Int -> Either MathError (Polynomial a) Source #

Bernstein basis binomial(n,k)*x^k*(1-x)^(n-k) for 0<=k<=n.

polynomialRegression

polynomialRegression :: RealFloat a => Int -> [(a, a)] -> Either MathError (Polynomial a) Source #

Least-squares power-basis regression using column-pivoted Householder QR. Degree must be nonnegative; undersampling, nonfinite data and rank deficiency are reported by the checked design-matrix solver.

chebyshevApproximation

chebyshevApproximation :: Int -> (Double -> Double) -> Either MathError (Polynomial Double) Source #

Truncated Chebyshev interpolation at first-kind nodes on [-1,1], returned in power basis. Uses degree+1 evaluations; nonfinite values are rejected.

PowerSeries

data PowerSeries a Source #

A finite Taylor jet, coefficients ascending and zeros retained. Its length is the truncation order; operations preserve the shorter operand's order.

Instances

Instances details

Show a => Show (PowerSeries a) Source #
Instance details Defined in HMath.Polynomial Methods showsPrec :: Int -> PowerSeries a -> ShowS # show :: PowerSeries a -> String # showList :: [PowerSeries a] -> ShowS #
Eq a => Eq (PowerSeries a) Source #
Instance details Defined in HMath.Polynomial Methods (==) :: PowerSeries a -> PowerSeries a -> Bool # (/=) :: PowerSeries a -> PowerSeries a -> Bool #

powerSeries

powerSeries :: [a] -> PowerSeries a Source #

Construct a jet with explicit coefficients, including trailing zeros.

seriesCoefficients

seriesCoefficients :: PowerSeries a -> [a] Source #

Stored Taylor coefficients; coefficient n multiplies x^n, not x^n/n!.

addSeries

addSeries :: Num a => PowerSeries a -> PowerSeries a -> PowerSeries a Source #

Add jets to their common truncation order.

multiplySeries

multiplySeries :: Num a => PowerSeries a -> PowerSeries a -> PowerSeries a Source #

Multiply jets by truncated convolution.

reciprocalSeries

reciprocalSeries :: (Eq a, Fractional a) => PowerSeries a -> Either MathError (PowerSeries a) Source #

Reciprocal jet from coefficient recurrence; constant term must be nonzero.

divideSeries

divideSeries :: (Eq a, Fractional a) => PowerSeries a -> PowerSeries a -> Either MathError (PowerSeries a) Source #

Divide jets to their common order; denominator constant must be nonzero.

composeSeries

composeSeries :: (Eq a, Num a) => PowerSeries a -> PowerSeries a -> Either MathError (PowerSeries a) Source #

Formal composition to the inner jet's order. Inner constant must be zero, so unknown higher outer coefficients cannot affect the returned jet.

differentiateSeries

differentiateSeries :: Num a => PowerSeries a -> PowerSeries a Source #

Derivative jet has one fewer coefficient.

integrateSeries

integrateSeries :: Fractional a => a -> PowerSeries a -> PowerSeries a Source #

Integral jet with supplied constant, one coefficient longer.

expSeries

expSeries :: Floating a => PowerSeries a -> PowerSeries a Source #

Exponential of a finite jet from b'=a'b; constant uses the coefficient type's exp. The output has the same truncation order.

logSeries

logSeries :: (Ord a, Floating a) => PowerSeries a -> Either MathError (PowerSeries a) Source #

Formal log through derivativedivisionintegration. Requires positive real constant term, with exact truncation matching the input jet.

RationalFunction

data RationalFunction Source #

Reduced exact rational function with monic denominator.

Instances

Instances details

Show RationalFunction Source #
Instance details Defined in HMath.Polynomial Methods showsPrec :: Int -> RationalFunction -> ShowS # show :: RationalFunction -> String # showList :: [RationalFunction] -> ShowS #
Eq RationalFunction Source #
Instance details Defined in HMath.Polynomial Methods (==) :: RationalFunction -> RationalFunction -> Bool # (/=) :: RationalFunction -> RationalFunction -> Bool #

rationalFunction

rationalFunction :: Polynomial Rational -> Polynomial Rational -> Either MathError RationalFunction Source #

Normalize by polynomial GCD and reject a zero denominator.

rationalNumerator

rationalNumerator :: RationalFunction -> Polynomial Rational Source #

Reduced numerator.

rationalDenominator

rationalDenominator :: RationalFunction -> Polynomial Rational Source #

Monic reduced denominator.

evaluateRationalFunction

evaluateRationalFunction :: RationalFunction -> Rational -> Either MathError Rational Source #

Exact evaluation, rejecting poles.

addRationalFunction

addRationalFunction :: RationalFunction -> RationalFunction -> Either MathError RationalFunction Source #

Exact rational-function addition with cancellation.

multiplyRationalFunction

multiplyRationalFunction :: RationalFunction -> RationalFunction -> Either MathError RationalFunction Source #

Exact rational-function multiplication with cancellation.

partialFractions

partialFractions :: Int -> RationalFunction -> Either MathError (Polynomial Rational, [(Polynomial Rational, Polynomial Rational, Int)]) Source #

Exact partial fractions over Q. Each term is (numerator,monic irreducible denominator,power) and numerator degree is smaller than denominator degree. Supports repeated and nonlinear factors. Kronecker factorization and linear elimination are bounded by the supplied candidate budget.