Using the Remez algorithm, implemented using multi-precision library, in certain functions that I want to approximate, the error curve does not oscillate in between reference points, and so no roots can be found (subsequently no extrema).

For example, this happens when I try to approximate $ln$ (natural logarithm) over the interval of $I=[a=0.5, b=1]$, with a rational polynomial $P/Q$ of degrees $n=deg(P)=6$ and $m=deg(Q)=5$.

For the first set of reference points, Chebyshev nodes are computed using the following: $$ x_i^{(0)} = 0.5 \cdot (a + b) + 0.5 \cdot (b - a) * \cos(\frac{(2i-1)\cdot \pi}{2n}) $$ $$ i = 1,\ldots,N=n+m+2 $$

The figure below shows the first iteration of the error function with the first set of nodes marked in circles. enter image description here

Next, the extrema are found: enter image description here

The extrema, together with the reference points of interval bound, i.e., $x_a$ and $x_b$ compose the next set of reference points ${x^{(1)}}$

The following figure shows the error function in the second step, with the reference points marked with circles. enter image description here

Here, the 7th and the 8th reference points are both below the x-axis and so no root will be found in between them. Regardless, this error curve has 10 extrema. Together with the two bounding reference points, there will be at most 12 new reference points which is less than 13, the minimum required for this approximation. So it seems that the error curve, in this step, does not oscillate enough. How this can be fixed so that more oscillation occurs?

  • $\begingroup$ Could you make the example more concrete by spelling out the function you are trying to approximate? In my experience rational approximation with Remez is a bit iffy. It is hard to reproduce the issue and diagnose the root cause just from the graph. You may want to try smoothly skewing the initial set of points to the left or right by exponentiation with a factor around unity (total range of maybe 0.5 to 2). I guess one could automatically skew based on the where the error function has the largest peak, but I do it by hand when needed. $\endgroup$
    – njuffa
    Commented Oct 5, 2020 at 21:11
  • $\begingroup$ Could you document in the question how you are picking the initial points, normalized to the interval $[0,1]$? It is easiest to discuss in terms of that interval; the points can be scaled to any interval $[a,b]$ in a separate step. $\endgroup$
    – njuffa
    Commented Oct 5, 2020 at 22:21
  • $\begingroup$ For a polynomial approximation $P(x)$ of degree $n$, one sets up $n+2$ linear equations of the form $P(x)-f(x) \pm E=0$, and uses the locations of the $n+2$ extrema of a Chebyshev polynomial of degree $n+1$ as the initial points $x_i$. Same approach applied to rational approximation $P(x)/Q(x)$ would lead to equations of the form $P(x) - (f(x) \pm E)Q(x) = 0$, where the term $(\pm E)Q(x)$ makes the equations non-linear. How are you addressing this issue? $\endgroup$
    – njuffa
    Commented Oct 6, 2020 at 5:03
  • $\begingroup$ @njuffa Please see I have added details regarding your comments. I tried skewing the set of points. Skewing them right (by using powers less than 1) the error curve becomes "flatten" while trying skewing them left does not move them by much, and in any case, the issue described still exists just in between a different pair of reference points. $\endgroup$
    – Daniel
    Commented Oct 6, 2020 at 14:48
  • $\begingroup$ @njuffa I use the Fraser Hart method addressing the non-linearity of the system. See here I asked the same question and provided my own answer: scicomp.stackexchange.com/questions/36035/… I use 0 as the inial guess and |E| (E derived from the solution to the system) for the subsequent steps. $\endgroup$
    – Daniel
    Commented Oct 6, 2020 at 14:53


Your Answer

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

Browse other questions tagged or ask your own question.