Octave Remez Implementation

John Bryan

• Equations.
  
  Initial set of points, located in [a,b], \begin{equation} x_i=\frac{b+a}{2}+\frac{b-a}{2}\cos(\frac{i\pi}{N+1}) \tag{eq. 1} \end{equation} for i=0,1,2,...,N+1, where N is the order of the polynomial.
  
  
  \begin{equation} \begin{bmatrix} x_1^N \quad & x_1^{(N-1)} \quad & x_1^{(N-2)} \quad & \cdots \quad & \cdots \quad & x_1^2 \quad & x_1 \quad & 1 \quad & -1^{(1+1)} \quad \\ x_2^N \quad & x_2^{(N-1)} \quad & x_2^{(N-2)} \quad & \cdots \quad & \cdots \quad & x_2^2 \quad & x_2 \quad & 1 \quad & -1^{(1+2)} \quad \\ \vdots \quad & \vdots \quad & \vdots \quad & \cdots \quad & \cdots \quad & \vdots \quad & \vdots \quad & \vdots \quad & \vdots \quad \\ x_{N+1}^N \quad & x_{N+1}^{(N-1)} \quad & x_{N+1}^{(N-2)} \quad & \cdots \quad & \cdots \quad & x_{N+1}^2 \quad & x_{N+1} \quad & 1 \quad & -1^{(1+(N+1))} \quad \\ x_{N+2}^N \quad & x_{N+2}^{(N-1)} \quad & x_{N+2}^{(N-2)} \quad & \cdots \quad & \cdots \quad & x_{N+2}^2 \quad & x_{N+2} \quad & 1 \quad & -1^{(1+(N+2))} \quad \\ \end{bmatrix} \begin{bmatrix} a_N \\ a_{N-1} \\ \vdots \\ a_0 \\ \epsilon \\ \end{bmatrix} = \begin{bmatrix} f(x_1) \\ f(x_2) \\ \vdots \\ f(x_{N+2}) \\ \end{bmatrix} \tag{eq. 2} \end{equation}
  
  
  \begin{equation} \begin{bmatrix} a_N \\ a_{N-1} \\ \vdots \\ a_0 \\ \epsilon \\ \end{bmatrix} = \begin{bmatrix} x_1^N \quad & x_1^{(N-1)} \quad & x_1^{(N-2)} \quad & \cdots \quad & \cdots \quad & x_1^2 \quad & x_1 \quad & 1 \quad & -1^{(1+1)} \quad \\ x_2^N \quad & x_2^{(N-1)} \quad & x_2^{(N-2)} \quad & \cdots \quad & \cdots \quad & x_2^2 \quad & x_2 \quad & 1 \quad & -1^{(1+2)} \quad \\ \vdots \quad & \vdots \quad & \vdots \quad & \cdots \quad & \cdots \quad & \vdots \quad & \vdots \quad & \vdots \quad & \vdots \quad \\ x_{N+1}^N \quad & x_{N+1}^{(N-1)} \quad & x_{N+1}^{(N-2)} \quad & \cdots \quad & \cdots \quad & x_{N+1}^2 \quad & x_{N+1} \quad & 1 \quad & -1^{(1+(N+1))} \quad \\ x_{N+2}^N \quad & x_{N+2}^{(N-1)} \quad & x_{N+2}^{(N-2)} \quad & \cdots \quad & \cdots \quad & x_{N+2}^2 \quad & x_{N+2} \quad & 1 \quad & -1^{(1+(N+2))} \quad \\ \end{bmatrix} ^{-1} \begin{bmatrix} f(x_1) \\ f(x_2) \\ \vdots \\ f(x_{N+2}) \\ \end{bmatrix} \tag{eq. 3} \end{equation}



\begin{equation} P(x)=a_Nx^N+a_{N-1}x^{N-1}+...a_1x+a_0. \tag{eq. 4} \end{equation}


To find a new N+2 values of x, find f(x)-P(x) extrema, \begin{equation} \frac{df}{dx}-\frac{dP}{dx}=0 \tag{eq. 5} \end{equation}


From the N+2 extrema points, compute ratio \begin{equation} \frac{\text{max}|f(x)-P(x)|}{\text{min}|f(x)-P(x)|} \end{equation} If ratio is greater than threshold 1.000005, continue algorithm, inserting new N+2 values of x into equation 3.



• Octave implementation.



• Results.
  $$ f(x)=\cos(\exp(x)), x \in [0,2], N=4 $$
  
  
  
  
  $$ f(x)=\sin(\exp(x)), x \in [-2,2], N=8 $$