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?

  • 1
    $\begingroup$ I applaud anyone exploring this lovely field, its theory and its practical implementation. $\endgroup$ Mar 6, 2021 at 4:04

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.