sageSLZ Notes

The approximation interval problem

When Sollya computes an approximation polynomial for a given function, degree and range, it also returns the approximation error (and the center of the interval as well).

Very often we want to solve a slightly different problem: for a given function, degree, lower bound and approximation error, computed the approximation polynomial and the upper bound of the interval comprised between it and the upper bound for which the approximation error stands.

Very often the idea is to break a given “large” into a collection of smaller intervals because for the given function-degree-error the initial interval is too large.

The naive approach is to:

  1. give it a try with the initial data;
  2. when you get a too large error, reduce (e. g. divide by 2) the interval by lowering the upper bound until the computed error matches the target error;
  3. this upper bound becomes the lower bound of the next interval, always using the orginal upper bound and repeat the process until you can cover the all initial interval with the computed sub-interval.

In step 2 you may have to compute several polynomials until the computed error is below or equal to the expected error. You must not decrease the interval width too agressively. There is no point in getting a too small approximation error since it multiplies the number of interval (and lengthens the subsequent manipulations that are made on each sub-interval).

In step 3 you probably inutily compute polynomials for too large intervals and you could know it from the previous computations.

The whole idea is to reduce the number of polynomial computations and get the maximum width (compatible with the expected approwimaiton error).

This process has different aspects:

  1. for a given interval (be it too small or too large) and the given (computed) error, compute the new best upper bound;
  2. reuse the computation already done in previous steps.

For point 1, can something be done with the derivative at the upper bound or at the center point of the interval (also given by Sollya).

For point 2, can some type of data structure keep the informations (which ones ?) and allow for an efficient reuse.

Adjacent question: is it possible, given a the result of a previous computation, to forecast the effect on the approximation precision of a degree in(de)crease?