2
$\begingroup$

I am working on a Uniform Random Number Generator using a IEEE paper, and I got stuck with the coefficients for a Piecewise Polynomial Approximation using Horner's Rule :

$$ y = ((C_d x + C_{d-1})x + \ldots)x + C_0 $$

where $x$ is the input, $d$ is the polynomial degree, and $C_i$ are the polynomial coefficients.

According to the paper the polynomial coefficients are found in a mini-max sense, that minimizes the maximum absolute error.

Can anyone help with how I can generate these coefficients?

ref:<Link> http://www.ee.usyd.edu.au/people/philip.leong/UserFiles/File/papers/bm_tc06.pdf

$\endgroup$
5
  • $\begingroup$ The segue from "uniform random number generator" to minimax approximation by piecewise polynomials is breathtaking, but I have no idea what your actual Question here is. $\endgroup$
    – hardmath
    Jun 27, 2016 at 23:46
  • $\begingroup$ I am sorry for confusion. My question is how to generate the Coefficients for any function such as sqrt(x) over [1,4), with degree 1 in minimax sense. $\endgroup$ Jun 27, 2016 at 23:57
  • $\begingroup$ Okay, how to find the minimax approximation to a continuous function on a bounded interval (like $\sqrt x$ on $[1,4]$) using a polynomial (not a piecewise polynomial) of a specified degree (say degree $1$). I will revise your tags accordingly. $\endgroup$
    – hardmath
    Jun 28, 2016 at 0:40
  • $\begingroup$ Thanks @hardmath. Also the paper uses Matlab Symbolic toolbox, that contains MAPLE linear algebra package to generate the polynomial coefficient tables. But they have not given the tables. So I need to generate them again. But I don't know how. $\endgroup$ Jun 28, 2016 at 0:43
  • $\begingroup$ Note that you've framed the Question as approximating a function with piecewise polynomials. If the "nodes" (subdividing the domain) are fixed, you could ask for distinct polynomials on each subinterval. However one might be interested in a more refined version of the approximation: (1) what are the best nodes/subintervals to choose, (2) what if the piecewise polynomial is required (perhaps with certain derivatives) to be continuous, and (3) what if the approximation is required to be monotone increasing (as would be so for cumulative distribution functions). "Breathtaking" indeed. $\endgroup$
    – hardmath
    Jul 1, 2016 at 14:20

1 Answer 1

1
$\begingroup$

An iterative method for finding the best "maximum norm" approximation by polynomial of degree at most $d$ to a given smooth function $f(x)$ on a bounded interval $I = [a,b]$ was proposed by Evgeny Yakovlevich Remez in 1934, and has come to be known as the Remez exchange algorithm.

The underlying idea is a characterization of the "mini-max" polynomial approximation called the equioscillation theorem attributed to Chebyshev:

Among all polynomials of degree $d$ or less, the polynomial $p(x)$ minimizes the max-norm of the error $||f - p||_\infty$ on $I = [a,b]$ if and only if there exist $d+2$ points $x_0 \lt x_1 \lt \ldots \lt x_{d+1}$ in $I$ such that the successive errors $f(x_i) - p(x_i)$ are equal in absolute value to the maximum $||f - p||_\infty$ and alternate in signs: $$ f(x_i) - p(x_i) = p(x_{i+1}) - f(x_{i+1}) $$ for $i=0,1,\ldots,d$.

Various implementations of the Remez exchange algorithm are available, and if you are specifically interested in the Matlab environment, see this package by Sherif Tawfik (2005). More about a "built-in" Matlab implementation is discussed under this DSP.SE Question.

The specific problem of approximating $f(x) = \sqrt x$ on $[1,4]$ using a first degree polynomial can be solved almost by inspection. Because of the concavity of this function, the best fit line will have two of its equioscillation points at the ends of the interval, and must necessarily be parallel to the secant line passing through the endpoints $(1,1)$ and $(4,2)$, namely $y = (x+2)/3$.

The only computation we need here is to find where the maximum of:

$$\sqrt{x} - \frac{1}{3}(x + 2) $$

occurs (the critical point) and split that "absolute error" difference with the endpoints.

A standard calculus approach locates the critical point at $x_1 = 9/4$, where the height of curve $\sqrt{x}$ above the secant line is $1/12$. This is illustrated in the graph below by the dotted vertical red line: square root from x=1 to 4

Fig. 1 The graph of $y=\sqrt{x}$ for $1\le x\le 4$ and chord through endpoints

Together with endpoints $x_0=1$ and $x_2=4$, we achieve the equioscillation criteria with:

$$ p(x) = \frac{1}{3}(x + 2) + \frac{1}{24} $$

The interested Reader may wish to simplify this polynomial further.

$\endgroup$
3
  • $\begingroup$ I am a little overwhelmed by the info, i won't deny. But there is small problem, so the limit we wanted the approximation of the function on...is [1,4) with an open bracket at 4, that means 4 is not included in the limit. @hardmath Does your solution still hold? $\endgroup$ Jun 28, 2016 at 4:55
  • $\begingroup$ It does hold, because the limit of $\sqrt x$ as $x\to 4$ is $2$. So there is no difficulty in extending the interval, either for the square root function or for the first degree polynomial $y=mx + b$ you want to approximate $\sqrt x$. $\endgroup$
    – hardmath
    Jun 28, 2016 at 12:39
  • $\begingroup$ I will add a picture to make the solution clearer. In the meantime you might get an insight from this previous SciComp.SE Answer where approximating $y=1/x$ on $[1,2]$ is illustrated. $\endgroup$
    – hardmath
    Jun 28, 2016 at 14:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .