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)Given some point x, returns a fold that accumulates rows of an interpolation
tableau providing successively better estimates (at the value x) of a
polynomial interpolated to all seen points.
The 2-arity aggregation step takes:
previous-row: previous row of an interpolation tableau[x_new (f x_new)]and returns the next row of the tableau using the algorithm described in
modified-neville.
Given some point `x`, returns a fold that accumulates rows of an interpolation tableau providing successively better estimates (at the value `x`) of a polynomial interpolated to all seen points. The 2-arity aggregation step takes: - `previous-row`: previous row of an interpolation tableau - a new point of the form `[x_new (f x_new)]` and returns the next row of the tableau using the algorithm described in [[modified-neville]].
(modified-neville-scan x)Returns a function that consumes an entire sequence xs of points of the form
[x_i, f(x_i)] and returns a lazy sequence of successive approximations of
x using polynomials fitted to the first point, then the first and second
points, etc. using the algorithm described in modified-neville.
Equivalent to ([[modified-neville]] xs x).
Returns a function that consumes an entire sequence `xs` of points of the form `[x_i, f(x_i)]` and returns a lazy sequence of successive approximations of `x` using polynomials fitted to the first point, then the first and second points, etc. using the algorithm described in [[modified-neville]]. Equivalent to `([[modified-neville]] xs x)`.
(modified-neville-sum x)Returns a function that consumes an entire sequence xs of points of the form
[x_i, f(x_i)] and returns the best approximation of x using a polynomial
fitted to all points in xs using the algorithm described
in modified-neville.
Faster than, but equivalent to, (last ([[modified-neville]] xs x))
Returns a function that consumes an entire sequence `xs` of points of the form `[x_i, f(x_i)]` and returns the best approximation of `x` using a polynomial fitted to all points in `xs` using the algorithm described in [[modified-neville]]. Faster than, but equivalent to, `(last ([[modified-neville]] xs 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)Given some point x, returns a fold that accumulates rows of an interpolation
tableau providing successively better estimates (at the value x) of a
polynomial interpolated to all seen points.
The 2-arity aggregation step takes:
previous-row: previous row of an interpolation tableau
a new point of the form [x_new (f x_new)]
and returns the next row of the tableau using the algorithm described in
neville.
Given some point `x`, returns a fold that accumulates rows of an interpolation tableau providing successively better estimates (at the value `x`) of a polynomial interpolated to all seen points. The 2-arity aggregation step takes: - `previous-row`: previous row of an interpolation tableau - a new point of the form `[x_new (f x_new)]` and returns the next row of the tableau using the algorithm described in [[neville]].
(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 [[emmy.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 [[emmy.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 of the form
[x_i, f(x_i)] and returns a lazy sequence of successive approximations of
x using polynomials fitted to the first point, then the first and second
points, etc. using the algorithm described in neville.
Equivalent to ([[neville]] xs x).
Returns a function that consumes an entire sequence `xs` of points of the form `[x_i, f(x_i)]` and returns a lazy sequence of successive approximations of `x` using polynomials fitted to the first point, then the first and second points, etc. using the algorithm described in [[neville]]. Equivalent to `([[neville]] xs x)`.
(neville-sum x)Returns a function that consumes an entire sequence xs of points of the form
[x_i, f(x_i)] and returns the best approximation of x using a polynomial
fitted to all points in xs using the algorithm described in neville.
Faster than, but equivalent to, (last ([[neville]] xs x))
Returns a function that consumes an entire sequence `xs` of points of the form `[x_i, f(x_i)]` and returns the best approximation of `x` using a polynomial fitted to all points in `xs` using the algorithm described in [[neville]]. Faster than, but equivalent to, `(last ([[neville]] xs 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 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.
(tableau-fold-fn prepare merge present)Given prepare and merge and present functions, returns a fold capable of
aggregating a point of the form [x, f(x)] into an accumulating tableau
row (generating the next tableau row).
The 0-arity of the returned function returns an empty row, [].
The 1-arity calls the supplied present on the accumulated tableau row.
The 2-arity scans the supplied merge across all entries in the accumulating
row, producing a new row.
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.
present: Transforms a tableau row into an estimate at some value x of
the polynomial interpolated to hit all supplied points.Given `prepare` and `merge` and `present` functions, returns a fold capable of aggregating a point of the form [x, f(x)] into an accumulating tableau row (generating the next tableau row). The 0-arity of the returned function returns an empty row, `[]`. The 1-arity calls the supplied `present` on the accumulated tableau row. The 2-arity scans the supplied `merge` across all entries in the accumulating row, producing a new 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. - `present`: Transforms a `tableau` row into an estimate at some value `x` of the polynomial interpolated to hit all supplied points.
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |