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`.
(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.
(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 neville
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 [[neville]] 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"](https://www.sciencedirect.com/science/article/pii/0771050X82900511), A. Macleod - [Press's Numerical Recipes (p103), chapter 3](http://phys.uri.edu/nigh/NumRec/bookfpdf/f3-1.pdf)
(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.
(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: ```clojure [([[modified-neville]] [a] x) ([[modified-neville]] [b a] x) ([[modified-neville]] [c b a] x) ...] ```
(neville points x)
(neville points x column)
Takes:
points
of the form [x (f x)]
andx
to interpolateand 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]$$
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, [Neville's Algorithm](https://en.wikipedia.org/wiki/Neville%27s_algorithm)
(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.
(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.
(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]((https://en.wikipedia.org/wiki/Neville%27s_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, [Neville's Algorithm](https://en.wikipedia.org/wiki/Neville%27s_algorithm)
(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: ```clojure [([[neville]] [a] x) ([[neville]] [b a] x) ([[neville]] [c b a] x) ...] ```
(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 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.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.
(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.
(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 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.
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.
(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:
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.
cljdoc is a website building & hosting documentation for Clojure/Script libraries
× close