level – they oscillate between +1 and −1 in the interval [−1, 1]. has N+2 level extrema. This means that the error between f(x) and its Chebyshev expansion out to is close to a level function with N+2 extrema, so it is close to the optimal Nth-degree polynomial. In the graphs above, note that the blue error function is sometimes better than (inside of) the red function, but sometimes worse, meaning that it is not quite the optimal polynomial. The discrepancy is less serious for the exp function, which has an extremely rapidly converging power series, than for the log function. Chebyshev approximation is the basis for Clenshaw–Curtis quadrature, a numerical integration technique. Remez's algorithm The Remez algorithm (sometimes spelled Remes) is used to produce an optimal polynomial P(x) approximating a given function f(x) over a given interval. It is an iterative algorithm that converges to a polynomial that has an error function with N+2 level extrema. By the theorem above, that polynomial is optimal. Remez's algorithm uses the fact that one can construct an Nth-degree polynomial that leads to level and alternating error values, given N+2 test points. Given N+2 test points , , ... (where and are presumably the end points of the interval of approximation), these equations need to be solved: The right-hand sides alternate in sign. That is, Since , ..., were given, all of their powers are known, and , ..., are also known. That means that the above equations are just N+2 linear equations in the N+2 variables , , ..., , and . Given the test points , ..., , one can solve this system to get the polynomial P and the number . The graph below shows an example of this, producing a fourth-degree polynomial approximating over [−1, 1]. The test points were set at −1, −0.7, −0.1, +0.4, +0.9, and 1. Those values are shown in green. The resultant value of is 4.43 × 10−4 Note that the error graph does indeed take on the values at the six test points, including the end points, but that those points are not extrema. If the four interior test points had been extrema (that is, the function P(x)f(x) had maxima or minima there), the polynomial would be optimal. The second step of Remez's algorithm consists of moving the test points to the approximate locations where the error function had its actual local maxima