Sollya User's Manual

Name:

remez computes the minimax of a function on an interval.

Usage:

remez(f, n, range, w, quality) : (function, integer, range, function, constant) -> function remez(f, L, range, w, quality) : (function, list, range, function, constant) -> function

Parameters:

f is the function to be approximated
n is the degree of the polynomial that must approximate f
L is a list of monomials that can be used to represent the polynomial that must approximate f
range is the interval where the function must be approximated
w (optional) is a weight function. Default is 1.
quality (optional) is a parameter that controls the quality of the returned polynomial p, with respect to the exact minimax p*. Default is 1e-5.

Description:

remez computes an approximation of the function f with respect to the weight function w on the interval range. More precisely, it searches a polynomial p such that ||p*w-f|| is (almost) minimal among all polynomials p of a certain form. The norm is the infinity norm, e.g. ||g|| = max {|g(x)|, x in range}.
If w=1 (the default case), it consists in searching the best polynomial approximation of f with respect to the absolute error. If f=1 and w is of the form 1/g, it consists in searching the best polynomial approximation of g with respect to the relative error.
If n is given, the polynomial p is searched among the polynomials with degree not greater than n. If L is given, the polynomial p is searched as a linear combination of monomials X^k where k belongs to L. L may contain ellipses but cannot be end-elliptic.
The polynomial is obtained by a convergent iteration called Remez' algorithm. The algorithm computes a sequence p1, ..., pk, ... such that ek = ||pk*w-f|| converges towards the optimal value e. The algorithm is stopped when the relative error between ek and e is less than quality.
Note: the algorithm may not converge in certain cases. Moreover, it may converge towards a polynomial that is not optimal. These cases correspond to the cases when the Haar condition is not fulfilled. See [Cheney - Approximation theory] for details.

Example 1:

   > p = remez(exp(x),5,[0;1]);
   > degree(p);
   5
   > dirtyinfnorm(p-exp(x),[0;1]);
   1.12956984638214536849843017679626063762687501534126e-6

Example 2:

   > p = remez(1,[|0,2,4,6,8|],[0,Pi/4],1/cos(x));
   > canonical=on!;
   > p;
   0.99999999994393749280444571988532724907643631727381 + -0.49999999571557467737204931630836834563663039748203 * x^2 + 4.16666132335010905188253972212748718651775241902969e-2 * x^4 + -1.38865291475286141707180658383176799662601691348739e-3 * x^6 + 2.437267919111162694221738667927916761689966804242e-5 * x^8

Example 3:

   > p1 = remez(exp(x),5,[0;1],default,1e-5);
   > p2 = remez(exp(x),5,[0;1],default,1e-10);
   > p3 = remez(exp(x),5,[0;1],default,1e-15);
   > dirtyinfnorm(p1-exp(x),[0;1]);
   1.12956984638214536849843017679626063762687501534126e-6
   > dirtyinfnorm(p2-exp(x),[0;1]);
   1.12956980227478687332174207517728389861926659249056e-6
   > dirtyinfnorm(p3-exp(x),[0;1]);
   1.12956980227478687332174207517728389861926659249056e-6

See also: dirtyinfnorm, infnorm, fpminimax, guessdegree, taylorform, taylor

Go back to the list of commands