sicmutils.rational-function.interpolate — sicmutils 0.21.1

This namespace contains a discussion of rational function interpolation, and different methods for fitting rational functions to N points and evaluating them at some value x.

bs-merge clj/s

(bs-merge x)

bs-prepare clj/s

(bs-prepare [x fx])

bulirsch-stoer clj/s

(bulirsch-stoer points x)

(bulirsch-stoer 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.

P(x) is rational function fit (using the Bulirsch-Stoer algorithm, of similar style to Neville's algorithm described in [[sicmutils.numerical.interpolate.polynomial]]) to every point in the supplied sequence points.

"The Bulirsch-Stoer algorithm produces the so-called diagonal rational function, with the degrees of numerator and denominator equal (if m is even) or with the degree of the denominator larger by one if m is odd." ~ Press, Numerical Recipes, p105

The implementation follows Equation 3.2.3 on on page 105 of Press.

Column

If you supply an integer for the third (optional) column argument, bulirsch-stoer will return that /column/ offset 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 2-point approximations between pairs of points; 2 gives 3-point approximations between successive triplets, etc.

References:

• Stoer & Bulirsch, 'Introduction to Numerical Analysis'
• PDF of the same reference
• Press's Numerical Recipes (p105), Section 3.2

bulirsch-stoer-fold clj/s

(bulirsch-stoer-fold x)

Given some point x, returns a fold that accumulates rows of a rational function interpolation tableau providing successively better estimates (at the value x) of a rational function 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)]

Returns a function that accepts:

• previous-row: previous row of an interpolation tableau
• a new point of the form [x (f x)]

and returns the next row of the tableau using the algorithm described in bulirsch-stoer.

bulirsch-stoer-recursive clj/s

(bulirsch-stoer-recursive points x)

Returns the value of P(x), where P is rational function fit (using the Bulirsch-Stoer algorithm, of similar style to Neville's algorithm described in [[sicmutils.numerical.interpolate.polynomial]]) to every point in the supplied sequence points.

points: is a sequence of pairs of the form [x (f x)].

"The Bulirsch-Stoer algorithm produces the so-called diagonal rational function, with the degrees of numerator and denominator equal (if m is even) or with the degree of the denominator larger by one if m is odd." ~ Press, Numerical Recipes, p105

The implementation follows Equation 3.2.3 on on page 105 of Press.

References:

• Stoer & Bulirsch, 'Introduction to Numerical Analysis'
• PDF of the same reference
• Press's Numerical Recipes (p105), Section 3.2

bulirsch-stoer-scan clj/s

(bulirsch-stoer-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 rational functions fitted to the first point, then the first and second points, etc. using the algorithm described in modified-bulirsch-stoer.

Equivalent to ([[bulirsch-stoer]] xs x).

bulirsch-stoer-sum clj/s

(bulirsch-stoer-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 rational function fitted to all points in xs using the algorithm described in modified-bulirsch-stoer.

Faster than, but equivalent to, (last ([[bulirsch-stoer]] xs x))

modified-bulirsch-stoer clj/s

(modified-bulirsch-stoer points x)

Similar to bulirsch-stoer (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 division, making the algorithm slightly more efficient.

See bulirsch-stoer for usage information, and info about the required structure of the arguments.

References:

• Press's Numerical Recipes (p105), Section 3.2

modified-bulirsch-stoer-fold clj/s

(modified-bulirsch-stoer-fold x)

Given some point x, returns a fold that accumulates rows of a rational function interpolation tableau providing successively better estimates (at the value x) of a rational function 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)]

Returns a function that accepts:

• previous-row: previous row of an interpolation tableau
• a new point of the form [x (f x)]

and returns the next row of the tableau using the algorithm described in modified-bulirsch-stoer.

modified-bulirsch-stoer-scan clj/s

(modified-bulirsch-stoer-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 rational functions fitted to the first point, then the first and second points, etc. using the algorithm described in modified-bulirsch-stoer.

Equivalent to ([[modified-bulirsch-stoer]] xs x).

modified-bulirsch-stoer-sum clj/s

(modified-bulirsch-stoer-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 rational function fitted to all points in xs using the algorithm described in modified-bulirsch-stoer.

Faster than, but equivalent to, (last ([[modified-bulirsch-stoer]] xs x))