Documentation
¶
Overview ¶
Package poly provides polynomial evaluation, arithmetic, least-squares fitting and root finding with the semantics of numpy.polyfit, numpy.roots, numpy.poly1d helpers and the numpy.polynomial package (Chebyshev, Legendre, Hermite, HermiteE and Laguerre series), in pure Go (CGO_ENABLED=0).
Coefficient order: read this first ¶
Two conventions coexist, exactly as in NumPy, and they are NOT the same:
- HIGHEST degree first (np.poly1d, np.polyfit, np.roots, np.polyval ...): Polyval, PolyvalComp, Polyder, Polyint, Conv, Deconv, Polyadd, Polysub, Polymul, PolyFromRoots, Polyfit, Roots. The slice {1, -3, 2} is x^2 - 3x + 2.
- LOWEST degree first (numpy.polynomial): Basis, Series, Val, Vander, Der, Int, FitBasis, FitSeries, RootsBasis. The slice {2, -3, 1} is 2 + (-3) B_1(x) + B_2(x), B_k being the k-th basis polynomial.
Faithfulness to NumPy ¶
Evaluation, Vandermonde matrices, differentiation and integration follow NumPy's arithmetic operation by operation, each product rounded before its sum (explicit float64 conversions forbid fused multiply-add), so their results are bit-identical to NumPy's; the README lists the measured equality. Least-squares fits use Householder QR on the column-scaled design matrix, NumPy's SVD answer being recovered through github.com/go-ndarray/ndarray's Lstsq whenever the fit is rank-deficient or nearly so. Roots are eigenvalues of the companion matrix (Edelman and Murakami 1995, doi:10.1090/S0025-5718-1995-1262279-2), in LAPACK's order; the series companion ("comrade") matrices are NumPy's. PolyvalComp is the compensated Horner scheme of Graillat, Langlois and Louvet (2009), as accurate as Horner computed in twice the precision.
Where NumPy raises an exception the functions return an error. Only float64 data, one-dimensional coefficient and data arrays, and a single integer degree are supported (see the README's "Gaps").
Index ¶
- Variables
- func Conv(a, v []float64) ([]float64, error)
- func Deconv(u, v []float64) (q, r []float64, err error)
- func Der(b Basis, c []float64, m int, scl float64) ([]float64, error)
- func FitSeries(b Basis, x, y []float64, deg int, o *SeriesFitOptions) (Series, Fit, error)
- func GetDomain(x []float64) ([2]float64, error)
- func Int(b Basis, c []float64, m int, k []float64, lbnd, scl float64) ([]float64, error)
- func MapDomain(dst, x []float64, old, new [2]float64) []float64
- func MapParms(old, new [2]float64) (off, scl float64)
- func PolyFromComplexRoots(roots []complex128) (coef []complex128, realOnly bool)
- func PolyFromRoots(roots []float64) []float64
- func Polyadd(a, b []float64) []float64
- func Polyder(p []float64, m int) ([]float64, error)
- func Polyint(p []float64, m int, k []float64) ([]float64, error)
- func Polymul(a, b []float64) []float64
- func Polysub(a, b []float64) []float64
- func Polyval(p []float64, x float64) float64
- func PolyvalAll(dst, p, x []float64) []float64
- func PolyvalComp(p []float64, x float64) float64
- func PolyvalCompAll(dst, p, x []float64) []float64
- func Roots(p []float64) ([]complex128, error)
- func RootsBasis(b Basis, c []float64) ([]complex128, error)
- func Val(b Basis, c []float64, x float64) (float64, error)
- func ValAll(b Basis, dst, c, x []float64) ([]float64, error)
- func Vander(b Basis, x []float64, deg int) ([]float64, error)
- type Basis
- type CovMode
- type Fit
- type FitOptions
- type Series
- type SeriesFitOptions
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrArg = errors.New("poly: invalid argument")
ErrArg is returned for an invalid argument (negative order, short k, ...), where NumPy raises ValueError.
var ErrBasis = errors.New("poly: unknown basis")
ErrBasis is returned for an unknown Basis value.
var ErrEmpty = errors.New("poly: empty input")
ErrEmpty is returned where NumPy raises because an input array is empty.
var ErrNonFinite = errors.New("poly: non-finite value in least-squares problem")
ErrNonFinite is returned when a least-squares problem contains NaN or Inf (NumPy's lstsq raises LinAlgError there).
var ErrRankDeficient = errors.New("poly: rank-deficient fit has no covariance")
ErrRankDeficient is returned when a covariance matrix is requested for a rank-deficient fit.
Functions ¶
func Conv ¶
Conv is numpy.convolve(a, v) in "full" mode, a direct O(len(a)*len(v)) sum. Either input empty is an error, as in NumPy.
func Deconv ¶
Deconv is numpy.polydiv (scipy.signal.deconvolve's long division): the quotient and remainder of u by v, highest degree first. Leading remainder entries with |r| <= 1e-8 are dropped, which is what NumPy's allclose(r[0], 0, rtol=1e-14) (default atol 1e-8) does. A zero leading coefficient of v gives Inf/NaN as in NumPy. Empty inputs are an error.
Example ¶
package main
import (
"fmt"
"github.com/go-approx/poly"
)
func main() {
q, r, _ := poly.Deconv([]float64{1, 3, 3, 1}, []float64{1, 1}) // (x+1)^3 / (x+1)
fmt.Println(q, r)
}
Output: [1 2 1] [0]
func Der ¶
Der is numpy's chebder/legder/hermder/hermeder/lagder: the m-th derivative of the series c (lowest degree first), each derivative scaled by scl (scl = d(window)/d(domain) for a variable change).
func FitSeries ¶
FitSeries is ABCPolyBase.fit (e.g. Chebyshev.fit): the domain is taken from x unless given, x is mapped onto the window, and the fit is FitBasis.
Example ¶
package main
import (
"fmt"
"github.com/go-approx/poly"
)
func main() {
// Fit y = x^2 on [0, 2] with Chebyshev polynomials: the domain [0, 2]
// is mapped to the window [-1, 1].
x := []float64{0, 0.5, 1, 1.5, 2}
y := []float64{0, 0.25, 1, 2.25, 4}
s, _, err := poly.FitSeries(poly.Chebyshev, x, y, 2, nil)
if err != nil {
panic(err)
}
v, _ := s.Val(1.5)
fmt.Printf("domain %v coef %.4f value %.4f\n", s.Domain, s.Coef, v)
}
Output: domain [0 2] coef [1.5000 2.0000 0.5000] value 2.2500
func GetDomain ¶
GetDomain returns [min(x), max(x)] (polyutils.getdomain); a NaN in x gives NaN, as numpy's min/max. Empty x is an error.
func Int ¶
Int is numpy's chebint/legint/hermint/hermeint/lagint: the m-fold integral of the series c (lowest degree first) with integration constants k (missing ones are 0), lower bound lbnd, each integral scaled by scl.
func MapDomain ¶
MapDomain maps x from the interval old to new (polyutils.mapdomain), into dst (allocated when too short) and returns it.
func MapParms ¶
MapParms returns (off, scl) such that x -> off + scl*x maps the interval old onto new (numpy.polynomial.polyutils.mapparms).
func PolyFromComplexRoots ¶
func PolyFromComplexRoots(roots []complex128) (coef []complex128, realOnly bool)
PolyFromComplexRoots is numpy.poly for complex roots. The coefficients are complex; when the roots are closed under conjugation (as numpy checks, by sorting) the imaginary parts are dropped (set to 0) and realOnly is true.
func PolyFromRoots ¶
PolyFromRoots is numpy.poly for real roots: the monic polynomial with the given roots, highest degree first. No roots gives [1].
func Polyder ¶
Polyder is numpy.polyder: the m-th derivative of p (highest degree first). The derivative of a constant is the empty slice, as in NumPy.
func Polyint ¶
Polyint is numpy.polyint: the m-fold antiderivative of p (highest degree first) with integration constants k (nil: zeros; one value: reused for every integration; otherwise at least m values, k[0] being the constant of the first integration).
func Polymul ¶
Polymul is numpy.polymul: the product of two polynomials (highest degree first); like numpy.poly1d it strips leading zeros of both operands first.
func Polyval ¶
Polyval evaluates the polynomial p (coefficients HIGHEST degree first) at x by Horner's rule, with NumPy's exact arithmetic: y = 0; y = y*x + c for every coefficient, each product rounded before the sum (no fused multiply-add), so the result is bit-identical to numpy.polyval. As in NumPy the start value 0*x makes the result NaN for an infinite x.
Example ¶
package main
import (
"fmt"
"github.com/go-approx/poly"
)
func main() {
// 2x^2 - 3x + 1, coefficients highest degree first.
fmt.Println(poly.Polyval([]float64{2, -3, 1}, 4))
}
Output: 21
func PolyvalAll ¶
PolyvalAll evaluates p at every element of x, writing into dst (allocated when nil or too short) and returning it.
func PolyvalComp ¶
PolyvalComp evaluates p (highest degree first) at x with the compensated Horner scheme of Graillat, Langlois and Louvet (2009): the result is as accurate as Horner's rule computed in twice the working precision, then rounded, whatever the arch's FMA fusing (TwoSum and an explicit math.FMA TwoProduct are used).
Example ¶
package main
import (
"fmt"
"math"
"math/big"
"github.com/go-approx/poly"
)
func main() {
// (x-1)^8 at x = 1.01 is 1e-16, but Horner works with terms of size 1:
// it loses every digit to cancellation, the compensated scheme keeps
// them. The exact value comes from math/big.
p := []float64{1, -8, 28, -56, 70, -56, 28, -8, 1}
x := 1.01
exact := new(big.Float).SetPrec(2000)
bx := new(big.Float).SetPrec(2000).SetFloat64(x)
for _, c := range p {
exact.Mul(exact, bx).Add(exact, big.NewFloat(c))
}
ex, _ := exact.Float64()
rel := func(v float64) float64 { return math.Abs(v-ex) / ex }
fmt.Println("Horner is off by more than 100%:", rel(poly.Polyval(p, x)) > 1)
fmt.Println("compensated is within 1e-14: ", rel(poly.PolyvalComp(p, x)) < 1e-14)
}
Output: Horner is off by more than 100%: true compensated is within 1e-14: true
func PolyvalCompAll ¶
PolyvalCompAll applies PolyvalComp to every element of x.
func Roots ¶
func Roots(p []float64) ([]complex128, error)
Roots is numpy.roots: the roots of the polynomial p (coefficients HIGHEST degree first). Leading zeros are stripped, each trailing zero adds a zero root (appended last), and the others are the eigenvalues of the companion matrix (Edelman & Murakami 1995 show the companion eigenvalue method is backward stable for balanced companions), in LAPACK order. NaN or Inf in p is an error (numpy raises LinAlgError through eig). The result is always complex128; NumPy returns a real array when every imaginary part is zero.
Example ¶
package main
import (
"fmt"
"github.com/go-approx/poly"
)
func main() {
roots, err := poly.Roots([]float64{1, -3, 2, 0}) // x^3 - 3x^2 + 2x
if err != nil {
panic(err)
}
for _, r := range roots {
fmt.Printf("%.4f ", real(r))
}
fmt.Println()
}
Output: 2.0000 1.0000 0.0000
func RootsBasis ¶
func RootsBasis(b Basis, c []float64) ([]complex128, error)
RootsBasis is numpy's chebroots/legroots/hermroots/hermeroots/lagroots: the roots of the series c (lowest degree first, trailing zeros trimmed) as eigenvalues of the companion (comrade) matrix of the three-term recurrence, sorted lexicographically (real, then imaginary part). An empty c is an error; NaN/Inf coefficients are an error through the eigensolver.
func Val ¶
Val evaluates the series sum c[i]*B_i(x) by Clenshaw's recurrence with numpy's exact operation order (chebval, legval, hermval, hermeval, lagval): every product is rounded before its sum, so results are bit-identical to NumPy's. An empty c is an error (NumPy raises IndexError).
func Vander ¶
Vander returns the pseudo-Vandermonde matrix of the family, row-major len(x) rows by deg+1 columns: element (i,j) is B_j(x[i]), computed by numpy's forward recurrences (bit-identical to chebvander, legvander, ...).
Example ¶
package main
import (
"fmt"
"github.com/go-approx/poly"
)
func main() {
v, _ := poly.Vander(poly.Chebyshev, []float64{0.5, 1}, 3) // rows: T0..T3
fmt.Println(v)
}
Output: [1 0.5 -0.5 -1 1 1 1 1]
Types ¶
type Basis ¶
type Basis int
Basis names an orthogonal-polynomial family of numpy.polynomial.
Coefficient order: the Basis / Series API follows numpy.polynomial and stores coefficients LOWEST degree first (Coef[i] multiplies the i-th basis polynomial). The np.poly1d-style functions (Polyval, Polyfit, Roots, ...) store them HIGHEST degree first.
const ( Chebyshev Basis = iota // T_n, numpy.polynomial.chebyshev Legendre // P_n, numpy.polynomial.legendre Hermite // physicists' H_n, numpy.polynomial.hermite HermiteE // probabilists' He_n, numpy.polynomial.hermite_e Laguerre // L_n, numpy.polynomial.laguerre )
The supported families.
type CovMode ¶
type CovMode int
CovMode selects the covariance estimate returned by Polyfit, as numpy.polyfit's cov argument.
type Fit ¶
type Fit struct {
// Coef are the coefficients: HIGHEST degree first for Polyfit, LOWEST
// degree first for FitBasis.
Coef []float64
// Rank is the effective rank of the (scaled) design matrix.
Rank int
// Residuals is [sum of squared residuals] when the rank is full and there
// are more points than coefficients, empty otherwise (as numpy's lstsq).
Residuals []float64
// Cov is the row-major (deg+1)x(deg+1) covariance matrix, in the order of
// Coef, or nil when not requested.
Cov []float64
}
Fit is the result of a least-squares fit.
func FitBasis ¶
FitBasis is numpy.polynomial.<basis>.<basis>fit: a least-squares fit in the given family WITHOUT any domain mapping (x is used as is). The columns of the pseudo-Vandermonde matrix are scaled to unit norm (a zero column keeps scale 1), then solved by the same Householder QR as Polyfit. Coefficients are lowest degree first.
func Polyfit ¶
func Polyfit(x, y []float64, deg int, o *FitOptions) (Fit, error)
Polyfit is numpy.polyfit(x, y, deg, rcond, w=, cov=): the least-squares polynomial of degree deg, coefficients HIGHEST degree first. The Vandermonde matrix columns are scaled to unit 2-norm, then solved by Householder QR (see lstsqQR for the rank-deficient path).
Example ¶
package main
import (
"fmt"
"github.com/go-approx/poly"
)
func main() {
x := []float64{0, 1, 2, 3, 4}
y := []float64{1, 3, 7, 13, 21} // x^2 + x + 1
fit, err := poly.Polyfit(x, y, 2, nil)
if err != nil {
panic(err)
}
fmt.Printf("%.6f rank=%d\n", fit.Coef, fit.Rank)
}
Output: [1.000000 1.000000 1.000000] rank=3
Example (Covariance) ¶
package main
import (
"fmt"
"github.com/go-approx/poly"
)
func main() {
x := []float64{0, 1, 2, 3, 4, 5}
y := []float64{0.1, 1.1, 1.9, 3.2, 3.9, 5.1}
fit, err := poly.Polyfit(x, y, 1, &poly.FitOptions{Cov: poly.CovScaled})
if err != nil {
panic(err)
}
fmt.Printf("slope %.4f +- %.4f\n", fit.Coef[0], sqrt(fit.Cov[0]))
}
func sqrt(v float64) float64 {
z := v
for i := 0; i < 60; i++ {
z = (z + v/z) / 2
}
return z
}
Output: slope 0.9914 +- 0.0325
type FitOptions ¶
type FitOptions struct {
// W are the weights: rows of the Vandermonde matrix AND the right-hand
// side are multiplied by W[i], as NumPy does (so W[i] = 1/sigma[i], not
// 1/sigma²). nil means unweighted.
W []float64
// Rcond is the relative cutoff on singular values; 0 means NumPy's
// default len(x)*eps.
Rcond float64
// Cov selects the covariance matrix.
Cov CovMode
}
FitOptions are the optional arguments of Polyfit.
type Series ¶
Series is numpy.polynomial's ABCPolyBase: coefficients LOWEST degree first, in one of the Basis families, with a Domain mapped linearly onto the Window where the basis polynomials live.
func NewSeries ¶
NewSeries returns a series with the family's default domain and window. The coefficients are copied; an empty slice is an error (NumPy raises).
func (Series) Der ¶
Der returns the m-th derivative (ABCPolyBase.deriv: derivatives scaled by the domain-to-window slope).
func (Series) Int ¶
Int returns the m-fold integral (ABCPolyBase.integ): integrals are scaled by 1/slope; lbnd, when non-nil, is a point of the DOMAIN mapped to the window (nil means the window origin 0, as NumPy's lbnd=None).
func (Series) Roots ¶
func (s Series) Roots() ([]complex128, error)
Roots returns the roots of the series in the domain, sorted by real part then imaginary part.
Example ¶
package main
import (
"fmt"
"github.com/go-approx/poly"
)
func main() {
// 1 - 2x^2 in the Legendre basis is not what it looks like: P2 = (3x^2-1)/2.
s, _ := poly.NewSeries(poly.Legendre, []float64{0, 0, 1})
roots, _ := s.Roots()
fmt.Printf("%.4f %.4f\n", real(roots[0]), real(roots[1]))
}
Output: -0.5774 0.5774
type SeriesFitOptions ¶
type SeriesFitOptions struct {
// Domain, when nil, defaults to [min(x), max(x)] (widened to
// [min-1, max+1] when they are equal, as NumPy).
Domain *[2]float64
// Window, when nil, is the family's default window.
Window *[2]float64
// W are the weights (rows of the design matrix and y are multiplied).
W []float64
// Rcond is the singular-value cutoff; 0 means len(x)*eps.
Rcond float64
}
SeriesFitOptions are the optional arguments of FitSeries.