# Linearization of Remez algorithm rational case

In the rational case, we are interested to find polynomials $$P(x)$$ and $$Q(x)$$ s.t. $$f(x_k)-P(x_k)/Q(x_k)=(-1)^kE$$ for $$k=1,2,\ldots, N$$ where $$N=deg(P)+deg(Q)+2$$

This can be rewritten as $$(1)~~~~~~(f(x_k)-(-1)^kE)Q(x_k)-P(x_k)=0$$

The equation (1) is non-linear. The notes in this document suggest using the following variation of the system of equations for linearizing (1). $$(2)~~~~~~((-1)^k E_0 - f(x_k))\sum_{i=1}^{q}b_i x_k^i+\sum_{i=1}^{p}a_i x_k^i + (-1)^kE=f(x_k)$$

It seems quite different from (1). Is (2) above is the correct interpretation of (1)? How this was derived from the definition? Where the additional $$f(x_k)$$ and $$(-1)^kE$$ come from?

• I applaud anyone exploring this lovely field, its theory and its practical implementation. Commented Mar 6, 2021 at 4:04

I have found that this is Fraser and Hart's variant of the Remez algorithm.

Let us fix the constant term of $$Q(x_k)$$ to $$1$$:

$$f(x_k) - \frac{\sum_{i=0}^{p}a_i x_k^i}{\sum_{i=1}^{q}b_i x_k^i + 1}=(-1)^kE$$

from which we obtain $$f(x_k) + f(x_k)\sum_{i=1}^{q}b_i x_k^i - \sum_{i=0}^{p}a_i x_k^i=(-1)^kE\sum_{i=1}^{q}b_i x_k^i + (-1)^kE$$

regrouping, we get

$$(*)~~~~~~~\left((-1)^kE- f(x_k)\right)\sum_{i=1}^{q}b_i x_k^i + \sum_{i=0}^{p}a_i x_k^i + (-1)^kE = f(x_k)$$

Since we don't know $$E$$, $$(*)$$ is not linear. The approach of Fraser and Hart is to make an initial guess $$E_0$$ so that $$(*)$$ becomes $$(2)$$ which is a linear system.