That is right. The Remez algorithm finds the minimax polynomial independent of any given prior discretization of the function.
For discrete points you can apply LP or an "iteratively reweighted least square" approach that for this problem converges quickly and is quite accurate. Implementing it in Julia will only take a few lines of code. See my discussion two years ago with Pedro -- from the *chebfun* project -- about why Remez is better than solving this problem as an optimization task: http://scicomp.stackexchange.com/questions/1531/the-remez-algorithm You'll see that the Remez algorithm gets it slightly better. On Tuesday, June 17, 2014 5:12:21 PM UTC+2, Steven G. Johnson wrote: > > Note that Remez algorithm can be used to find optimal (minimax/Chebyshev) > rational functions (ratios of polynomials), not just polynomials, and it > would be good to support this case as well. > > Of course, you can do pretty well for many functions just by sampling at a > lot of points, in which case the minimax problem turns into an > finite-dimensional LP (for polynomials) or a sequence of LPs (for rational > functions). The tricky "Remez" part is finding the extrema in order to > sample at the optimal points, as I understand it. >
