sicmutils.numerical.interpolate.polynomial — net.littleredcomputer/sicmutils 0.14.0-SNAPSHOT

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.

first-terms clj/s

(first-terms tableau)

lagrange clj/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.

mn-present clj/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.

modified-neville clj/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:

• "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

modified-neville-fold clj/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.

modified-neville-scan clj/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) ...]

neville clj/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:

• 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

neville-fold clj/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.

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.

neville-recursive clj/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:

• 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

neville-scan clj/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) ...]

tableau-fn clj/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.

tableau-fold clj/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.

tableau-fold-fn clj/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.

tableau-scan clj/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.