opda.approximation module

Approximation of univariate functions.

opda.approximation.lagrange_interpolate(xs, ys)

Interpolate xs and ys with a polynomial.

Interpolate the points with a polynomial, \(p(x)\), such that:

\[\forall i, p(x_i) = y_i\]

If there are n+1 points, then the polynomial will have degree n.

Parameters:

xs1D array of finite floats, required

The x values (asbscissas) to interpolate.

ys1D array of finite floats, required

The y values (ordinates) to interpolate.

Returns:

function

A function that evaluates the interpolating polynomial on arrays of floats, entrywise.

opda.approximation.remez(f, a, b, n, *, atol=None)

Return the reference for the minimax polynomial.

Use the Remez exchange algorithm to compute the reference corresponding to the minimax polynomial approximation to f. The reference is the set of x values at which the minimax polynomial achieves its equioscillating maximal error.

The reference for the minimax polynomial is primarily useful as an input for other approximation theoretic operations. Most users will prefer instead to use other functions that implement these operations such as minimax_polynomial_approximation() to evaluate the minimax polynomial or minimax_polynomial_coefficients() to compute its coefficients.

For background on the Remez algorithm and approximation theory, see “Approximation theory and methods” [1].

Parameters:

ffunction, required

The function to approximate. The function should map floats to floats.

afinite float, required

The lower end point of the interval over which to approximate f.

bfinite float, required

The upper end point of the interval over which to approximate f.

nnon-negative int, required

The degree of the polynomial approximation.

atolnon-negative float or None, optional

The absolute tolerance to use for stopping the computation. The algorithm ends when the current approximation has a maximum error within atol of the best possible approximation. If None, then it will be set to a multiple of machine epsilon.

Only set this value if you encounter numerical or optimization issues. In that case, raise the value until the numerical issues disappear and as long as the new absolute tolerance represents an acceptable level of error above the best approximation.

Returns:

1D array of floats from a to b inclusive

The reference, or x values where the minimax polynomial achieves equioscillating error.

1D array of floats

The y values of f evaluated on the reference.

non-negative float

The worst case absolute error of the minimax polynomial approximation to f from a to b.

See also

minimax_polynomial_approximation

Return a function representing the minimax polynomial.

minimax_polynomial_coefficients

Return the minimax polynomial’s coefficients.

References

[1]

Powell, M.J.D., “Approximation theory and methods” (1981). Cambridge University Press.

opda.approximation.minimax_polynomial_approximation(f, a, b, n, *, atol=None)

Return a function for evaluating the minimax polynomial.

Parameters:

ffunction, required

The function to approximate. The function should map floats to floats.

afinite float, required

The lower end point of the interval over which to approximate f.

bfinite float, required

The upper end point of the interval over which to approximate f.

nnon-negative int, required

The degree of the polynomial approximation.

atolnon-negative float or None, optional

The absolute tolerance to use for stopping the computation. The algorithm ends when the current approximation has a maximum error within atol of the best possible approximation. If None, then it will be set to a multiple of machine epsilon.

Only set this value if you encounter numerical or optimization issues. In that case, raise the value until the numerical issues disappear and as long as the new absolute tolerance represents an acceptable level of error above the best approximation.

See the docstring of the remez() function for details.

Returns:

function

A function that evaluates the minimax polynomial on arrays of floats, entrywise.

non-negative float

The worst case absolute error of the minimax polynomial approximation to f from a to b.

See also

minimax_polynomial_coefficients

Return the minimax polynomial’s coefficients.

remez

Return the reference for the minimax polynomial.

opda.approximation.minimax_polynomial_coefficients(f, a, b, n, *, transform=(-1.0, 1.0), atol=None)

Return the minimax polynomial’s coefficients.

Typically, computations for the coefficients of the minimax polynomial suffer from numerical issues when the degree of the polynomial is high (e.g., greater than 20 or so). These numerical issues stem from the fact that the Vandermonde matrix is usually ill-conditioned for high degrees.

For evaluating the minimax polynomial, there exist numerically stable algorithms that should be used instead. See the function: minimax_polynomial_approximation().

Parameters:

ffunction, required

The function to approximate. The function should map floats to floats.

afinite float, required

The lower end point of the interval over which to approximate f.

bfinite float, required

The upper end point of the interval over which to approximate f.

nnon-negative int, required

The degree of the polynomial approximation.

transformpair of finite floats or None, optional

For numerical stability, it can be helpful to map the inputs to some other range, e.g. -1 to 1, compute the minimax polynomial’s coefficients in this space, and then transform the coefficients back to the original space. The intervals from -1 to 1 or 0 to 1 are good choices. If None, then no transformation is applied.

atolnon-negative float or None, optional

The absolute tolerance to use for stopping the computation. The algorithm ends when the current approximation has a maximum error within atol of the best possible approximation. If None, then it will be set to a multiple of machine epsilon.

Only set this value if you encounter numerical or optimization issues. In that case, raise the value until the numerical issues disappear and as long as the new absolute tolerance represents an acceptable level of error above the best approximation.

See the docstring of the remez() function for details.

Returns:

1D array of finite floats

The coefficients of the minimax polynomial approximation to f, starting with the constant term followed by coefficients of increasing order.

non-negative float

The worst case absolute error of the minimax polynomial approximation to f from a to b.

See also

minimax_polynomial_approximation

Return a function representing the minimax polynomial.

remez

Return the reference for the minimax polynomial.

opda.approximation.piecewise_polynomial_knots(f, a, b, ns, *, atol=None)

Return knots for the minimax piecewise polynomial approximation.

The knots of a piecewise polynomial (i.e., spline) are the points that divide the domain into pieces. This function computes the minimax polynomial approximation to f independently on each piece, so in general the piecewise polynomial will be discontinuous. The returned points are chosen such that the worst case approximation error is minimized.

Parameters:

ffunction, required

The function to approximate. The function should map floats to floats.

afinite float, required

The lower end point of the interval over which to approximate f.

bfinite float, required

The upper end point of the interval over which to approximate f.

ns1D array of non-negative ints, required

The degree of the polynomial approximation on each piece. The length of ns determines the number of pieces.

atolnon-negative float or None, optional

The absolute tolerance to use for stopping the computation. The algorithm ends when the current approximation has a maximum error within atol of the best possible approximation. If None, then it will be set to a multiple of machine epsilon.

Only set this value if you encounter numerical or optimization issues. In that case, raise the value until the numerical issues disappear and as long as the new absolute tolerance represents an acceptable level of error above the best approximation.

See the docstring of the remez() function for details.

Returns:

1D array of floats from a to b inclusive

The len(ns) + 1 knots defining the optimal pieces.

non-negative float

The worst case absolute error of the piecewise minimax polynomial approximation to f from a to b using the returned knots.