When Sollya computes an approximation polynomial for a given function, degree and range, it also returns the approximation error (refered to, in the sequel, as the computedError 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 (referred to, in the sequel, as the targetError ), compute the approximation polynomial and the upper bound of the interval comprised between it and the lower bound for which the approximation error stands.
The idea is to break a given initially “large” interval into a collection of smaller intervals because for the given function-degree-error the initial interval is too large.
The most naive approach is to:
In step 2 you may have to compute several polynomials until the computed error is below or equal to the expected error. But 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 target error).
This process has different aspects:
We use two strategies.
The first is in the inner function that computes the first approximation
polynomial. If the upper bound is too high, we shrink the interval by a non
linear (and complex) factor computed from the ratio beetwen the obtained
error and the target error.
The whole idea is not to end up with a too
small interval.
This only takes into account aspect 1
.The second strategy is in the outer function. In this function the computed intervals returned by the inner function give all correct approximation errors. The computation of next upper bound will take into account the value of the previous interval and that of the previous computed error.
If the errors ratio is lower than 2, we try the same interval length as given by the previous computation. If larger we increase the next interval but by a small margin (log2(errorsRatio).
In this case, aspects 1 and 2 are considered
For the moment, we do not resort to more complex forcasting techniques (using the derivative of the function?). This could be an option if the present strategies did not output enough performance.