MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Relative error approximation by polynomials

For given continuous real functions $f$ and $g$ defined on $[-1,1]$, let's define $$D(f,g) = \sup_{x \in [-1,1]} \left|{\frac{f(x)-g(x)}{f(x)}}\right|$$ (in this context, let's take $0/0$ to be $0$ and $x/0 = \infty$ for every $x \not= 0$). I am looking for a theory of approximation by polynomials with respect to this error that parallels the existing theory of approximation by polynomials with respect to the $L_\infty$-norm.

For example: is it true that for every real $f$ continuous on $[-1,1]$ and every degree $n$ there exists a best approximating polynomial $p$ of degree $n$ in the sense that $D(f,p)$ is minimal among all polynomials of degree $n$? In such a case, can we find it or characterize it?

I would like to know if this has been studied before and where.

Edit: From the answers I got below, perhaps I should add that, in the application I have in mind, $f(x)$ may or may not be $0$ exactly at one place: at $x = 0$. This rules our infinitely many zeros in $[-1,1]$, and in case $f(0) = 0$, the best approximator $p(x)$ should be such that $p(0) = 0$ (my convention to take $0/0 = 0$ and $x/0 = \infty$ for $x \not= 0$ comes from this).

-
 Whether you're considering linear approximation (like Chebyshev approximation for continuous functions) or nonlinear approximation, one always qualifies "best" with respect to some metric. Is the $D(\cdot, \cdot)$ you've defined even a metric? – Jerry Gagelman Oct 6 2010 at 15:39 I don't know if it is a metric: I just look for a $P$ such that $D(f,P) = \inf_p D(f,p)$. – slimton Oct 7 2010 at 8:09 D is clearly not symmetric in the argument and thus not a metric. – Johan Oct 9 2010 at 11:48

## 5 Answers

According to Johan's answer, the problem is not well posed if the function $f$ has zeroes in $[-1,1]$ (if the number of zeroes is finite, perhaps something could be done). In the following I assume that $f(x)\ne0$ for all $x\in[-1,1]$. Let $n$ be a positive integer and let $\mathbb{P}(n)$ be the set of all real polynomials, and denote by $\|\cdot\|$ the $L^\infty$ norm on $[-1,1]$. Then you ask for the existence of $P\in\mathbb{P}(n)$ such that $$\|1-P/f\|=\inf_{p\in\mathbb{P}(n)}\|1-p/f\|.$$ This can be brought under the theory of approximation in the $L^\infty$ norm. Let $\phi_k(x)=x^k/f(x)$, $1\le k\le n$. Each $\phi_k$ is a continuous function, they are independent and generate an $n$-dimensional subspace of the space of continuous functions on $[-1,1]$ that we denote by $V$, which is nothing but the space of all functions of the form $P/f$ with $P\in\mathbb{P}(n)$. Moreover, each $\phi\in V$ has at most $n$ zeros in $[-1,1]$, so that it satisfies what is called the Haar condition. The original problem is now recast as: find the best approximation in $V$ of the constant function $1$.

The general theory of approximation shows that there is a unique best approximation, and that it can be characterized as follows: $\phi\in V$ is the best approximation in $V$ of the constant function $1$ if and only if there exist $x_1 < x_2 < \dots < x_{n+2}$ in $[-1,1]$ such that

1. $|e(x_k)|=\|e\|$, $1\le k\le n+2$,
2. $e(x_k)=-e(x_{k+1})$, $1\le k\le n+1$,

where $e(x)=1-\phi(x)$ is the error of the approximation. This is Tchebyshev's alternance theorem.

Finally, Remes' algorithm can be used to construct the best approximation.

Edit in response to your comment

If $f$ has a finite number of zeroes in $[-1,1]$ and can be written as $f=q\cdot h$ where $q$ is a polynomial and $h$ is a continuous function such that $h(x)\ne0$ for all $x\in[-1,1]$, then you may consider the space $V$ of all functions of the form $q\cdot p/f=p/h$ whith $p\in\mathbb{P}(n)$. Then $$\frac{|f(x)-q(x)p(x)|}{|f(x)|} =|1-\frac{p(x)}{h(x)}|.$$ If $\phi$ is the best approximation to $1$ in $V$, then $q\cdot \phi$ will be a best approximation to $f$ of degree $n+\hbox{degree}(q)$ in the relative error sense.

-
 This is useful, thanks. However, in the application I have in mind, the function $f(x)$ may or may not be $0$ exactly at one place: at $x = 0$. I wonder if something can be said in that case. Perhaps I should look at the generators $(x-x_0)^k/f(x)$ instead. – slimton Oct 7 2010 at 7:59 The trick to deal with finitely many zeros is wonderful. I can accept your answer now. – slimton Oct 10 2010 at 20:24

Take f to be non-zero but have infinitely many zeros in [-1,1]. A polynomial can only have a finite number of zeros so clearly the D(f,p) you defined will be infinite for every polynomial.

On the other hand if f is bounded from below away from zero there will at least exist a sequence of polynomials such that the relative error converges to zero, by just applying the traditional absolute theory.

Beyond these special cases I do not know anything but presumably relative approximation will have been studied before. I believe that when one chooses polynomials to approximate functions in practice (in calculators for example) one uses the relative error as the objective function.

-

I am not familiar with a useful L-infinity theory for polynomial approximation. Theoretically you can approximate continuous functions arbitrarily closely by polynomials. But it is more practical to minimize an L2 norm using orthogonal polynomials. The Legendre polynomials will minimize the average squared approximation error on [-1,1]. Alternatively you could create polynomials based on a weighted-square criterion, using the reciprocal of your function f(.) or a similar function.

-

Consider $$f(x) = \sqrt{|x|}.$$ Then $D(f,p)= \infty$ for any polynomial $p$. So if you want to allow a zero, then you need to have a condition of the form that the first $k$ derivatives are $0$ and the $k+1$st is non-zero. Of course also various existence claims on these are needed

-
 I do not think your example is correct. It would seem that just taking $p = x^2$ would give a polynomial with a finite value of D(f,p). – Johan Oct 9 2010 at 11:51

I don't see Helge's example as a problem. Remember that this is just on [-1,1]. Actually the 0 function is at distance 1 from any f. It might be that for uniqueness you need to discriminate how much time (or the number of times) the sup is obtained. As I see it, for this function we are constrained to have g(0)=0. This means that $|\frac{f-g}{f}|$ has limit 1 as we approach 0 (since g has bounded derivative at 0) so 1 is the best we could hope for. The 0 function obtains this as does $kx^2$ for any k up to $k=2$. I'm not sure if this problem arises for never-zero functions. I'll have to reread Julián's comments on his excellent answer. Sometimes there is a "best of the best" example which is the limit of the best $L_p$ approximations as p goes to $\infty$.

-