Tutorial 2 of 5: switching to relative error - samhocevar/lolremez GitHub Wiki

In the previous section, we saw that lolremez looked for a polynomial P(x) and the smallest error value E such that:

$$\max_{x \in [-1, 1]}{\big\vert f(x) - P(x)\big\vert} = E$$

Where $f(x) = e^{x}$.

A look at the error graph indicates that the error values in -1 and 1 are the same but the relative error values are not: it is about 0.15% for -1 whereas it is about 0.02% for 1.

Representing the relative error mathematically

We actually want a polynomial $P(x)$ and the smallest error value $E$ such that:

$$\max_{x \in [-1, 1]}{\bigg\lvert\dfrac{\exp(x) - P(x)}{\exp(x)}\bigg\rvert} = E$$

Fortunately lolremez is able to find such a polynomial, too.

Invocation

lolremez --degree 4 --range -1:1 "exp(x)" "exp(x)"

See the subtle change? exp(x) is now passed twice; the second argument is called the weight function. We are now minimising the following expression:

$$\max_{x \in [-1, 1]}{\dfrac{\big\lvert f(x) - P(x)\big\rvert}{\big\lvert g(x)\big\rvert}} = E$$

Where $f(x) = e^{x}$, just like before, and $g(x) = e^{x}$.

After all the iterations the output should be as follows:

/* Approximation of f(x) = exp(x)
 * with weight function g(x) = exp(x)
 * on interval [ -1.0000000000000000000, 1.0000000000000000000 ]
 * with a polynomial of degree 4. */
float f(float x)
{
    float u = 3.9962914225208867552e-2f;
    u = u * x + 1.7648623219024696305e-1f;
    u = u * x + 5.0289865085404914825e-1f;
    u = u * x + 9.9793872910703643074e-1f;
    return u * x + 9.9962789571721377560e-1f;
}

Analysing the results

Again, the polynomial and the original function are undistinguishable:

images/fastexp2.png

However, the error curve now looks like this:

images/fastexp2-error.png

We accomplished our goal: the relative error is minimised; it is about 0.05% for -1 and 0.05% for 1 (versus 0.15% and 0.02% respectively).

Conclusion

You should now be able to weigh your error function to control the final error curve of the minimax polynomial!

Please report any trouble you may have had with this document to [email protected]. You may then carry on to the next section: changing variables for simpler polynomials.