5 Polynomials

9.1.0.11

5 Polynomials🔗

package: rktsicm

sicm/poly provides functions that work together with or specializes polynomials as defined in sicm/simplify/pcf. Although pcfs can have more than 1 variable, the functions below work on only 1 variable.

procedure
((polynomial-function p) x) → pcf?
p : pcf?
x : number?

Creates a function in 1 variable from the p. If (poly/arity p) is at most 1 then the return value will be a number? instead of a pcf?.

procedure
(roots->poly roots) → pcf?
roots : (listof number?)

Creates an (unscaled) polynomial from its roots.

procedure
(poly-domain->canonical p a b) → pcf?
  p : pcf?
  a : real?
  b : real?

Create a new polynomial with the domain [a b] mapped to [-1 1]

procedure
(poly-domain->general p a b) → pcf?
  p : pcf?
  a : real?
  b : real?

Create a new polynomial with the domain [-1 1] mapped to [a b]

procedure
(poly->roots p) → (listof number?)
p : pcf?

Get the roots of a pcf? (in 1 variable).

5.1 Special polynomials🔗

procedure
(legendre-polynomial n) → pcf?
n : nonnegative-integer?

Returns the nth Legendre polynomial. See https://en.wikipedia.org/wiki/Legendre_polynomials.

procedure
(chebyshev-polynomial n) → pcf?
n : nonnegative-integer?

Returns the nth Chebyshev polynomial of the first kind. See https://en.wikipedia.org/wiki/Chebyshev_polynomials.

5.2 Interpolating polynomials🔗

procedure
((make-hermite-interpolator n) a b) → pcf?
  n : nonnegative-integer?
  a : (listof number? number? ...)
  b : (listof number? number? ...)

Generate an Hermite interpolating pcf? based on the two points a and b, the function value in this points, and the values of the 1sth till the nth derivative of the function in this point. The polynomial has at most degree (+ (* 2 n) 1)

procedure
(make-cubic-interpolant ax ay ady bx by bdy) → pcf?
  ax : number?
  ay : number?
  ady : number?
  bx : number?
  by : number?
  bdy : number?
procedure
(make-quintic-interpolant ax
ay
ady
addy
bx
by
bdy
bddy) → pcf?
  ax : number?
  ay : number?
  ady : number?
  addy : number?
  bx : number?
  by : number?
  bdy : number?
  bddy : number?

Specialized functions for (make-hermite-interpolator 1) and (make-hermite-interpolator 2).

procedure
(lagrange-interpolation-function ys xs) → (-> number? number?)
  ys : (listof number?)
  xs : (listof number?)
procedure
(Lagrange-interpolation-function ys xs) → (-> any? any?)
  ys : (listof any?)
  xs : (listof any?)
procedure
(lagrange ys xs) → expression?
  ys : (listof any?)
  xs : (listof any?)
procedure
(make-interp-poly ys xs) → pcf?
  ys : (listof any?)
  xs : (listof any?)

Generate a Lagrange interpolation of the points (map cons xs ys). The polynomial goes through all points and will have a degree of at most (- (length xs) 1).

procedure
(get-poly-and-errors fct low high order)
→ (List pcf? positive-integer? positive-integer?)
  fct : (-> real? real?)
  low : real?
  high : real?
  order : positive-integer?

Generate an interpolating pcf? of function fct on the interval [low high] of degree (- order 1) using Chebyshev roots. The return list includes the generated pcf? and the maximum and minimum error observed at the bumps.

procedure
(generate-approx-poly fct low high order [eps]) → pcf?
  fct : (-> real? real?)
  low : real?
  high : real?
  order : positive-integer?
  eps : #f = (U #f real?)

Generate an interpolating pcf? of function fct on the interval [low high] using order Chebyshev points. If eps is supplied the degree of the resulting pcf? will be reduced as much as possible to keep the error on the interval just below eps

Examples:

> (define fct sqrt)
> (define xs '(2 3 5 11))
> (define ys (map fct xs))
> (define (Δ clr lbl P+)
    (define-values (P eps) (if (pcf? P+)
                               (values P+ #f)
                               (values (car P+) (cadr P+))))
    (define F (polynomial-function P))
    (function (λ (x) (- (fct x) (F x))) #:color clr
              #:label (string-append lbl (format " ~a°" (poly:degree P))
                                     (if eps (format " ε<~a" (/ (round (* eps 1000)) 1000)) ""))))
> (plot (list (Δ 1 "Lagrange" (make-interp-poly ys xs))
              (Δ 2 "Chebyshev" (get-poly-and-errors fct 2 11 4))
              (Δ 3 "Chebyshev" (get-poly-and-errors fct 2 11 6))
              (Δ 4 "Chebyshev" (list (generate-approx-poly fct 2 11 8 0.1) 0.1))
              (points (map (λ (x) (list x 0)) xs)))
        #:x-min 1 #:x-max 12 #:y-min -0.1 #:legend-anchor 'bottom-right)

5.3 Chebyshev expansions🔗

Chebyshev expansions are givven by a list of coefficients so that:

(for/sum ([a (in-list cheb-exp)]
[i (in-naturals)])
(* a (chebyshev-polynomial i)))

value
scaled-chebyshev-expansions : (streamof (listof integer?))
value
chebyshev-expansions : (streamof (listof integer?))

Chebyshev expansions for the (scaled) power series

(stream 1 x (* 2 (expt x 2)) … (* (expt 2 (+ n 1)) (expt x n)))

and for the power series

(stream 1 x (expt x 2) … (expt x n))

procedure
(poly->cheb-exp p) → (listof real?)
p : pcf?
procedure
(cheb-exp->poly cheb-exp) → pcf?
cheb-exp : (listof real?)

Convert a polynomial to a cheb-expansion and back. This only works for real-valued pcf?s.

procedure
(trim-cheb-exp cheb-exp eps) → (listof real?)
cheb-exp : (listof real?)
eps : positive-real?

Given a cheb-exp and an error criterion eps, trim the tail of those coefficients whose absolute sum is <= eps.

procedure
(cheb-econ p low high eps) → pcf?
  p : pcf?
  low : real?
  high : real?
  eps : positive-real?

Reduce the degree of polynomial p keeping the maximum error on the interval [low high] smaller than eps (if possible).

procedure
(cheb-root-list n) → (listof real?)
n : nonnegative-integer?

Get the roots of the nth chebyshev-polynomial

procedure
(first-n-cheb-values n x [half?]) → (listof real?)
  n : nonnegative-integer?
  x : real?
  half? : #f = (U #f 'HALF)

For the first n chebyshev-polynomial’s, return (poly:value (chebyshev-polynomial i) x). If the optional argument half? is 'HALF the first term is 1/2 in stead of 1

procedure
(cheb-exp-value cheb-exp x) → real?
cheb-exp : (listof real?)
x : real?

Evaluate the cheb-expansion at x.

procedure
(generate-cheb-exp fct low high order) → (listof real?)
  fct : (-> real? real?)
  low : real?
  high : real?
  order : nonnegative-integer?

Generate a chebyshev-expansion of order to approximate the function fct. The expansion is mapped to interval [-1 1] to behave as fct on interval [low high].

5.4 Piecewise polynomials🔗

procedure
(ppa-make-from-poly low high poly) → ppa
  low : real?
  high : real?
  poly : pcf?
procedure
(ppa-low-bound ppa) → real?
  ppa : ppa
procedure
(ppa-high-bound ppa) → real?
  ppa : ppa
procedure
(ppa-body ppa) → ppa-body
  ppa : ppa
procedure
(ppa-poly ppa-body) → pcf?
  ppa-body : ppa-body

Basic constructor and data extractors for a piecewise polynomial (ppa). The polynomials will always be evaluated on the interval [-1 1] so before evaluation an x ϵ [low high] will be remaped to [-1 1] for the relevant piece of the ppa.

procedure
(ppa-terminal? ppa-body) → boolean?
ppa-body : ppa-body
procedure
(ppa-split? ppa-body) → boolean?
ppa-body : ppa-body

Check if the ppa-body is a terminal or if it is split into more pieces.

procedure
(ppa-split ppa-body) → real?
ppa-body : ppa-body

Get the value at which to go from the low to the high side of the split ppa-body

procedure
(ppa-low-side ppa-body) → ppa-body
ppa-body : ppa-body
procedure
(ppa-high-side ppa-body) → ppa-body
ppa-body : ppa-body

Get the body at the low or high side of the ppa-split.

procedure
(ppa-max-degree ppa) → nonnegative-integer?
ppa : ppa

Get the highest degree of the pieces of the ppa

procedure
(ppa-size ppa) → nonnegative-integer?
ppa : ppa

Get the number of pieces used in the ppa

procedure
(ppa-adjoin ppa0 ppa1) → ppa
ppa0 : ppa
ppa1 : ppa

Connect two ppas. This will fail if (not (= (ppa-high-bound pp0) (ppa-low-bound pp1))).

procedure
(ppa-value ppa0 x) → real?
ppa0 : ppa
x : real?

Evaluate the ppa in x.

procedure
(make-ppa fct low high order esp) → ppa
  fct : (-> real? real?)
  low : real?
  high : real?
  order : positive-integer?
  esp : positive-real?
procedure
(ppa-memo fct low high order esp) → (-> real? real?)
  fct : (-> real? real?)
  low : real?
  high : real?
  order : positive-integer?
  esp : positive-real?

Generate a piecewise approximation for function fct on interval [low high]. Each piece is generated with a Chebyshev polynomial of at most degree (- order 1), ensuring the error stays below eps, but in general this will not not guarantee continuity of the function at the splits. If continuity is required consider using make-smooth-ppa.

procedure
(make-smooth-ppa fct low high esp) → ppa
  fct : (listof (-> real? real?))
  low : real?
  high : real?
  esp : positive-real?
procedure
(smooth-ppa-memo fct low high esp) → (-> real? real?)
  fct : (listof (-> real? real?))
  low : real?
  high : real?
  esp : positive-real?

Generate a piecewise approximation for function (car fcts), each next function in fcts should be the next derivative of the first function. Interpolation is done using Herite fitting.

Example:

> (plot (list (function sin #:color 0)
              (function (ppa-memo sin 0 4 3 0.2) #:color 1 #:label "Chebyshev")
              (function (smooth-ppa-memo (list sin) 0 4 0.2) #:color 2 #:label "Hermite"))
        #:x-min 1 #:x-max 3 #:legend-anchor 'bottom)

contents ← prev up next →

1	Introduction
2	General
3	Kernel
4	Display
5	Polynomials
6	Calculus

5.1	Special polynomials
5.2	Interpolating polynomials
5.3	Chebyshev expansions
5.4	Piecewise polynomials