1
$\begingroup$

So the Remez algorithm is an algorithm for finding optimal polynomial approximations or at the very least for converging towards them. To find an approximation of $f$ by an $N$th degree polynomial the algorithm samples $N+2$ points and solves a particular system of equations using those points to create a first approximation. That's all fairly straightforward. The next step is however vague and confusing to me. The next step asks you to find the "points of local maximum error" defined as $|f(x) - p(x)|$ where $p$ is the approximating polynomial. Finally it asks that you use those as your samples in the next iteration (or if a certain condition on the error is met you can quit) which implies that you need $N+2$ such samples.

If I'm using single precision floating points then I'm sure I could loop over every possible value on the range I care about but that's very inefficient. Assuming the function I'm trying to approximation is twice differentiable then I can probably find at least one critical point using Newton's method. But I need to find N+2 points of maximum local error not just one!

I know that if I started the Newton's algorithm from several points then I should likely be able to find N-1 points of maximum error but I'm not entirely sure how that should be done. Are there any algorithms for achieving this?

Improve this question
$\endgroup$
6
  • $\begingroup$ The points of maximum error satisfy $f'(x) = p'(x)$. Does that help? $\endgroup$ Commented May 15, 2021 at 18:16
  • $\begingroup$ Right so that's a rephrasing of where the critical points of the error function are. $f(x) - p(x)$ is the error function (sans absolute value) and $f'(x) - p'(x) = 0$ is where the critical points are and where $f(x) - p(x)$ I wasn't clear about it but that's what I was referring to with "at least one critical point" method. $\endgroup$ Commented May 15, 2021 at 18:33
  • 1
    $\begingroup$ You can find a critical point between any two solutions of $f(x) = p(x)$. $\endgroup$ Commented May 15, 2021 at 18:34
  • $\begingroup$ Ah ok, so E in the Remez algorithm is the error of approximation at the sample points and and it alternates so we can find a root between those points giving us N+1 roots...now that you have N+1 roots you can find N roots of f'(x) - p'(x) between the roots of f(x) - p(x) and those are your points of maximum error. You can add in the end points as freebie critical points to get N+2 new samples! $\endgroup$ Commented May 15, 2021 at 18:56
  • 1
    $\begingroup$ You’ll have to detect it somehow. The algorithm will seem to fail. $\endgroup$ Commented May 16, 2021 at 4:58

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.