Remez’s Algorithm

Remez’s algorithm is one that converges to the minimax polynomial of a function. The author recommends using a polynomial approximation routine/software like Sollya or the one in Maple for beginners, as it is easy to make a buggy implementation of the algorithm.

Given a function \(f\) in \([a,b]\), we want to find \(n+2\) points \(x_{i}\) to utilize the theorem presented here. The algorithm is:

1. Start with an initial set of points in \([a,b]\).
2. Let your polynomial be \(p_{0}+p_{1}x+\cdots+p_{n}x^{n}\). We need to determine \(p_{i}\).
3. Solve the system of equations where you substitute each \(x_{i}\) into the polynomial and subtract from \(f\). Essentially, for each \(x_{i}\), calculate \(||p(x_{i})-f(x_{i}||\). Assign this to \(\pm\epsilon\) (the sign will alternate).
   1. Note that \(\epsilon\) is an unknown.
   2. This system has a unique solution - the matrix will be the Vandermonde matrix (I can’t show this - it is almost Vandermonde, but the \(\epsilon\) is an unknown and leads away from Vandermonde. Need to think this over).
4. Now you have a polynomial. Find the points \(y_{i}\) in \([a,b]\) where \(p-f\) has extremes, and iterate with these sets of points.
5. Iterate until the extrema alternate in sign and are all of magnitude 1.

It has been shown that this process converges (always?). The speed of convergence is quadratic.

The suggested initial set of points is \(x_{i}=\frac{a+b}{2}+\frac{b-a}{2}\cos\left(\frac{i\pi}{n+1}\right)\). This is essentially the points at which \(|T_{n+1}((2x-b-a)/(b-a))|=1\). We do this because often the Chebyshev approximation is close to the minimax approximation.