Liking cljdoc? Tell your friends :D

sicmutils.numerical.interpolate.polynomial

This namespace contains a discussion of polynomial interpolation, and different methods for fitting a polynomial of degree N-1 to N points and evaluating that polynomial at some different x.

This namespace contains a discussion of polynomial interpolation, and different
methods for fitting a polynomial of degree N-1 to N points and evaluating that
polynomial at some different `x`.
raw docstring

first-termsclj/s

(first-terms tableau)

lagrangeclj/s

(lagrange points x)

Generates a lagrange interpolating polynomial that fits every point in the supplied sequence points (of form [x (f x)]) and returns the value of the polynomial evaluated at x.

The Lagrange polynomial has this form:

g(x) = (f(a) * [(x-b)(x-c)...] / [(a-b)(a-c)...]) + (f(b) * [(x-a)(x-c)...] / [(b-a)(b-c)...]) + ...

for points [a f(a)], [b f(b)], [c f(c)] etc.

This particular method of interpolating x into the polynomial is inefficient; any new calculation requires fully recomputing. Takes O(n^2) operations in the number of points.

Generates a lagrange interpolating polynomial that fits every point in the
supplied sequence `points` (of form `[x (f x)]`) and returns the value of the
polynomial evaluated at `x`.

The Lagrange polynomial has this form:

g(x) =  (f(a) * [(x-b)(x-c)...] / [(a-b)(a-c)...])
      + (f(b) * [(x-a)(x-c)...] / [(b-a)(b-c)...])
      + ...

for points `[a f(a)], [b f(b)], [c f(c)]` etc.

This particular method of interpolating `x` into the polynomial is
inefficient; any new calculation requires fully recomputing. Takes O(n^2)
operations in the number of points.
raw docstring

mn-presentclj/s

(mn-present row)

Returns a (lazy) sequence of estimates by successively adding C values from the first entry of each tableau column. Each C value is the delta from the previous estimate.

Returns a (lazy) sequence of estimates by successively adding C values from the
first entry of each tableau column. Each C value is the delta from the
previous estimate.
raw docstring

modified-nevilleclj/s

(modified-neville points x)

Similar to neville (the interface is identical) but slightly more efficient. Internally this builds up its estimates by tracking the delta from the previous estimate.

This non-obvious change lets us swap an addition in for a multiplication, making the algorithm slightly more efficient.

See the neville docstring for usage information, and info about the required structure of the arguments.

The structure of the modified-neville algorithm makes it difficult to select a particular column. See neville if you'd like to generate polynomial approximations between successive sequences of points.

References:

Similar to `neville` (the interface is identical) but slightly more efficient.
Internally this builds up its estimates by tracking the delta from the
previous estimate.

This non-obvious change lets us swap an addition in for a multiplication,
making the algorithm slightly more efficient.

See the `neville` docstring for usage information, and info about the required
structure of the arguments.

The structure of the `modified-neville` algorithm makes it difficult to select
a particular column. See `neville` if you'd like to generate polynomial
approximations between successive sequences of points.

References:

- "A comparison of algorithms for polynomial interpolation", A. Macleod,
  https://www.sciencedirect.com/science/article/pii/0771050X82900511
- Press's Numerical Recipes (p103), chapter 3: http://phys.uri.edu/nigh/NumRec/bookfpdf/f3-1.pdf
raw docstring

modified-neville-foldclj/s

(modified-neville-fold x)

Returns a function that consumes an entire sequence xs of points, and returns a sequence of successive approximations of x using polynomials fitted to the points in reverse order.

This function uses the modified-neville algorithm internally.

Returns a function that consumes an entire sequence `xs` of points, and returns
a sequence of successive approximations of `x` using polynomials fitted to the
points in reverse order.

This function uses the `modified-neville` algorithm internally.
raw docstring

modified-neville-scanclj/s

(modified-neville-scan x)

Returns a function that consumes an entire sequence xs of points, and returns a sequence of SEQUENCES of successive polynomial approximations of x; one for each of the supplied points.

For a sequence a, b, c... you'll see:

[(modified-neville [a] x) (modified-neville [b a] x) (modified-neville [c b a] x) ...]

Returns a function that consumes an entire sequence `xs` of points, and returns
a sequence of SEQUENCES of successive polynomial approximations of `x`; one
for each of the supplied points.

For a sequence a, b, c... you'll see:

[(modified-neville [a] x)
 (modified-neville [b a] x)
 (modified-neville [c b a] x)
 ...]
raw docstring

nevilleclj/s

(neville points x)
(neville points x column)

Takes:

  • a (potentially lazy) sequence of points of the form [x (f x)] and
  • a point x to interpolate

and generates a lazy sequence of approximations of P(x). Each entry in the return sequence incorporates one more point from points into the P(x) estimate.

Said another way: the Nth in the returned sequence is the estimate using a polynomial generated from the first N points of the input sequence:

p0 p01 p012 p0123 p01234

This function generates each estimate using Neville's algorithm:

$$P(x) = [(x - x_r) P_l(x) - (x - x_l) P_r(x)] / [x_l - x_r]$$

Column

If you supply an integer for the third column argument, neville will return that /column/ of the interpolation tableau instead of the first row. This will give you a sequence of nth-order polynomial approximations taken between point i and the next n points.

As a reminder, this is the shape of the tableau:

p0 p01 p012 p0123 p01234 p1 p12 p123 p1234 . p2 p23 p234 . . p3 p34 . . . p4 . . . .

So supplying a column of 1 gives a sequence of linear approximations between pairs of points; 2 gives quadratic approximations between successive triplets, etc.

References:

Takes:

- a (potentially lazy) sequence of `points` of the form `[x (f x)]` and
- a point `x` to interpolate

and generates a lazy sequence of approximations of P(x). Each entry in the
return sequence incorporates one more point from `points` into the P(x)
estimate.

Said another way: the Nth in the returned sequence is the estimate using a
polynomial generated from the first N points of the input sequence:

p0 p01 p012 p0123 p01234

This function generates each estimate using Neville's algorithm:

$$P(x) = [(x - x_r) P_l(x) - (x - x_l) P_r(x)] / [x_l - x_r]$$

## Column

If you supply an integer for the third `column` argument, `neville` will
return that /column/ of the interpolation tableau instead of the first row.
This will give you a sequence of nth-order polynomial approximations taken
between point `i` and the next `n` points.

As a reminder, this is the shape of the tableau:

 p0 p01 p012 p0123 p01234
 p1 p12 p123 p1234 .
 p2 p23 p234 .     .
 p3 p34 .    .     .
 p4 .   .    .     .

So supplying a `column` of `1` gives a sequence of linear approximations
between pairs of points; `2` gives quadratic approximations between successive
triplets, etc.

References:

- Press's Numerical Recipes (p103), chapter 3: http://phys.uri.edu/nigh/NumRec/bookfpdf/f3-1.pdf
- Wikipedia: https://en.wikipedia.org/wiki/Neville%27s_algorithm
raw docstring

neville-foldclj/s

(neville-fold x)

Returns a function that consumes an entire sequence xs of points, and returns a sequence of successive approximations of x using polynomials fitted to the points in reverse order.

This function uses the neville algorithm internally.

Returns a function that consumes an entire sequence `xs` of points, and returns
a sequence of successive approximations of `x` using polynomials fitted to the
points in reverse order.

This function uses the `neville` algorithm internally.
raw docstring

neville-incremental*clj/s

(neville-incremental* points x)

Takes a potentially lazy sequence of points and a point x and generates a lazy sequence of approximations of P(x).

entry N in the returned sequence is the estimate using a polynomial generated from the first N points of the input sequence.

Takes a potentially lazy sequence of `points` and a point `x` and generates a
lazy sequence of approximations of P(x).

entry N in the returned sequence is the estimate using a polynomial generated
from the first N points of the input sequence.
raw docstring

neville-recursiveclj/s

(neville-recursive points x)

Top-down implementation of Neville's algorithm.

Returns the value of P(x), where P is a polynomial fit (using Neville's algorithm) to every point in the supplied sequence points (of form [x (f x)])

The efficiency and results should be identical to sicmutils.numerical.interpolate/lagrange. This function represents a step on the journey toward more incremental methods of polynomial interpolation.

References:

Top-down implementation of Neville's algorithm.

Returns the value of `P(x)`, where `P` is a polynomial fit (using Neville's
algorithm) to every point in the supplied sequence `points` (of form `[x (f
x)]`)

The efficiency and results should be identical to
`sicmutils.numerical.interpolate/lagrange`. This function represents a step on
the journey toward more incremental methods of polynomial interpolation.

References:

- Press's Numerical Recipes (p103), chapter 3: http://phys.uri.edu/nigh/NumRec/bookfpdf/f3-1.pdf
- Wikipedia: https://en.wikipedia.org/wiki/Neville%27s_algorithm
raw docstring

neville-scanclj/s

(neville-scan x)

Returns a function that consumes an entire sequence xs of points, and returns a sequence of SEQUENCES of successive polynomial approximations of x; one for each of the supplied points.

For a sequence a, b, c... you'll see:

[(neville [a] x) (neville [b a] x) (neville [c b a] x) ...]

Returns a function that consumes an entire sequence `xs` of points, and returns
a sequence of SEQUENCES of successive polynomial approximations of `x`; one
for each of the supplied points.

For a sequence a, b, c... you'll see:

[(neville [a] x)
 (neville [b a] x)
 (neville [c b a] x)
 ...]
raw docstring

tableau-fnclj/s

(tableau-fn prepare merge points)

Returns a Newton-style approximation tableau, given:

  • prepare: a fn that processes each element of the supplied points into the state necessary to calculate future tableau entries.

  • merge: a fn of land r the tableau entries:

l -- return / / / r

the inputs are of the same form returned by prepare. merge should return a new structure of the same form.

  • points: the (potentially lazy) sequence of points used to generate the first column of the tableau.
Returns a Newton-style approximation tableau, given:

- `prepare`: a fn that processes each element of the supplied `points` into
the state necessary to calculate future tableau entries.

- `merge`: a fn of `l`and `r` the tableau entries:

l -- return
   /
  /
 /
r

the inputs are of the same form returned by `prepare`. `merge` should return a
new structure of the same form.

- `points`: the (potentially lazy) sequence of points used to generate the
first column of the tableau.
raw docstring

tableau-foldclj/s

(tableau-fold fold-fn present-fn)

Returns a function that accepts a sequence of points and processes them into a tableau by generating successive rows, one at a time.

The final row is passed into present-fn, which generates the final return value.

This is NOT appropriate for lazy sequences! Fully consumes the input.

Returns a function that accepts a sequence of points and processes them into a
tableau by generating successive rows, one at a time.

The final row is passed into `present-fn`, which generates the final return
value.

This is NOT appropriate for lazy sequences! Fully consumes the input.
raw docstring

tableau-fold-fnclj/s

(tableau-fold-fn prepare merge)

Transforms the supplied prepare and merge functions into a new function that can merge a new point into a tableau row (generating the next tableau row).

More detail on the arguments:

  • prepare: a fn that processes each element of the supplied points into the state necessary to calculate future tableau entries.

  • merge: a fn of land r the tableau entries:

l -- return / / / r

the inputs are of the same form returned by prepare. merge should return a new structure of the same form.

Transforms the supplied `prepare` and `merge` functions into a new function
that can merge a new point into a tableau row (generating the next tableau
row).

More detail on the arguments:

- `prepare`: a fn that processes each element of the supplied `points` into
the state necessary to calculate future tableau entries.

- `merge`: a fn of `l`and `r` the tableau entries:

l -- return
   /
  /
 /
r

the inputs are of the same form returned by `prepare`. `merge` should return a
new structure of the same form.
raw docstring

tableau-scanclj/s

(tableau-scan fold-fn present-fn)

Takes a folding function and a final presentation function (of accumulator type => return value) and returns a NEW function that:

  • accepts a sequence of incoming points
  • returns the result of calling present on each successive row.
Takes a folding function and a final presentation function (of accumulator type
=> return value) and returns a NEW function that:

- accepts a sequence of incoming points
- returns the result of calling `present` on each successive row.
raw docstring

cljdoc is a website building & hosting documentation for Clojure/Script libraries

× close