The Journal of Online Mathematics and Its Applications, Volume 6 (2006)
The Chebyshev Equioscillation Theorem, Robert Mayans
For sketched functions, the applet records all the pixels selected along the path sketched by the mouse, and puts them together into a piecewise linear function. All points outside the rectangle −1 ≤ x ≤ 1, 0 ≤ y ≤ 1 are omitted.
The applet implements Paul de Casteljau's algorithm to compute the values of the Bernstein polynomials in a numerically stable way. See the article on the de Casteljau algorithm at Wikipedia for more information.
In the next two applets, the oscillating function are generated so that the value of the functions at x = −1.0, −0.9, −0.8, ..., 0.8, 0.9, 1.0 are among the numbers −1, −2 / 3, −1 / 3, 0, 1 / 3, 2 / 3, 1. All upper points, lower points, and section boundaries are among these points, and they are joined together by cubic functions to make a smooth curve. For the applet on generating sections, we start with an alternating set of length two and generate a pattern likely to have several more upper and lower points. For the applet on improving an approximation, the alternating set is constructed to have two, three, or four sections and with the section boundaries well spaced. This make the polynomial improvements not too small and the improvements are usually easy to see.
In our implementation of the second Remes algorithm, the initial polynomial is generated by solving the linear system of the Remes iteration when x0, ..., xn + 1 is defined by xk = cos(k π / (n + 1)). This method to produce a polynomial approximation is called is the method of forced oscillation (see Atkinson (1989)). The algorithm generates a new non-uniform alternating set by moving approximate upper points to local maxima and approximate lower points to local minima, and by exchanging points so that the point of maximum error is included in the new non-uniform alternating set. For a full discussion of the Remes algorithm, see Meinardus (1967)
If the new polynomial does not produce an alternating set of sufficient length by these local changes, the program attempts to find an alternating set by treating zero endpoints as upper or lower points, and by searching the entire range for an alternating set. These changes improve the robustness of the algorithms, but it will not produce an answer for every function it receives. The algorithm halts without a solution if the error grows too large, or if an alternating set cannot be found. The location of the points in the alternating set are determined to within an accuracy of 0.01 or so, and the polynomials actually found must be seen as rough approximations to the true answer.