3
$\begingroup$

Look at problem 8 :

Let $n\geq 1$ be a fixed integer. Calculate the distance: $$\inf_{p,f}\max_{x\in[0,1]}|f(x)-p(x)|$$ where $p$ runs over polynomials with degree less than $n$ with real coefficients and $f$ runs over functions $$ f(x)=\sum_{k=n}^{+\infty}c_k\, x^k$$ defined on the closed interval $[0,1]$, where $c_k\geq 0$ and $\sum_{k=n}^{+\infty}c_k = 1.$

This is what I have so far.

Clearly for $n=1$, we have $1/2$. I am conjecturing for $n>1$, we have $(n-1)^{(n-1)} / n^n$ or something similar to that? (just put $x^{(n-1)}$ and $x^n$ then use AM-GM). it's just weird that the pattern does not fit, so it's probably wrong. Any ideas?

$\endgroup$
6
  • $\begingroup$ What is the problem statement for those of us unwilling to open pdf files from random sites? $\endgroup$ Dec 7 '14 at 19:03
  • $\begingroup$ I will be starting a bounty on this question soon. $\endgroup$
    – user198454
    Dec 9 '14 at 16:05
  • $\begingroup$ @TheMathTroll: for what purpose, if I may dare to ask? $\endgroup$ Dec 9 '14 at 16:20
  • $\begingroup$ to see if there are any elementary solutions / better explained solutions? I am particularly interested in elementary solutions. $\endgroup$
    – user198454
    Dec 10 '14 at 0:20
  • $\begingroup$ The purpose is here: komal.hu/verseny/… $\endgroup$
    – G.Kós
    Dec 10 '14 at 10:11
1
$\begingroup$

Your inequality does not hold since $x^{n-1}$ is not the best approximation polynomial of $x^n$ with respect to the uniform norm. By Chebyshev's theorem we have that if $p(x)$ is the best approximation polynomial for $f(x)$, then $f(x)=p(x)$ holds for $\partial p+1$ points in $[0,1]$.

For instance, if $f(x)=x^n$ and $p(x)$ is the Lagrange interpolation polynomial with respect to the points $x=\frac{k}{n}$ for $k=1,2,\ldots,n$, since $f^{(n)}(x)=n!$ we have: $$\|f(x)-p(x)\|_{\infty} = \left\|\prod_{k=1}^{n}\left(x-\frac{k}{n}\right)\right\|_{\infty}=\frac{n!}{n^n}$$ that is below your bound for any $n\geq 4$.

We can improve this bound by choosing our interpolation points more carefully: by selecting Chebyshev nodes, for instance: $x_k=\cos^2\frac{\pi(2k-1)}{4n}$ for $k=1,\ldots,n$.

In order to find the best approximation polynomial of $x^n$, have a look at the following answer of Noam Elkies on MO: https://mathoverflow.net/questions/70440/uniform-approximation-of-xn-by-a-degree-d-polynomial-estimating-the-error .

Since $\|T_n(2x-1)\|_\infty=1$, with the best choice for the interpolation nodes we have that the uniform error in approximating $x^n$ is always greater than $\color{red}{\frac{2}{4^n}}$.

Since for every function in our class we have $\frac{f^{(n)}(\xi)}{n!}\geq 1$ for any $\xi\in[0,1]$, $f(x)=x^n$ is the easiest function to approximate, and:

$$\inf_{p,f}\|f-p\|_{\infty}=\color{red}{\frac{2}{4^n}}.$$

$\endgroup$
10
  • $\begingroup$ Thanks! I do not understand why is it sufficient to only consider $f(x)=x^n$ since that is the easiest function to approximate? I also don't understand how could $\frac{2}{4^n}$ be achieved here. So we are finding the $f(x)$ and $p(x)$ such that they are the best approximations of each other, right? I understand how did you get the best approximation of $x^n$ (for polynomials with degree less than $n$), but why did you just disregard all other possible polynomials $f(x)$ (that all their terms have degree greater than $n$ and the sum of its coefficients is $1$?) $\endgroup$
    – user198454
    Dec 8 '14 at 5:56
  • $\begingroup$ @TheMathTroll: By the error in the Lagrange approximation, $x^n$ is the best approximable function. With the best choice of interpolation nodes, the uniform error is exactly $\frac{2}{4^n}$. $\endgroup$ Dec 8 '14 at 9:15
  • $\begingroup$ What do you mean the "best approximable function"? Does that mean the function that has the least possible error? How did you show that x&n is the best approximable function? May I see the proof? $\endgroup$
    – user198454
    Dec 8 '14 at 10:03
  • $\begingroup$ @TheMathTroll: yes, the best approximable function is the function for which the uniform error of the best polynomial approximation is the least possible. Again, to prove that $x^n$ is the best approximable function you only need the formula for the error of the Lagrange interpolation. $\endgroup$ Dec 8 '14 at 10:27
  • $\begingroup$ is the formula for the error of the lagrange interpolation the one of the link? By the way, is there an elementary solution to this problem? $\endgroup$
    – user198454
    Dec 8 '14 at 10:28
1
+300
$\begingroup$

Let $$t_n(x) = \frac1{2^{2n-1}} T_n(2x-1).$$ If $f-p=t_n$, i.e. $f(x)=x^n$ és $p(x) = x^n-t_n(x)$ then $$\max_{0\le x\le 1} \big|f(x)-p(x)\big| = \max_{0\le x\le 1} \big|t_n(x)\big| = \frac1{2^{2n-1}} \max_{-1\le x\le 1} \big|T_n(x)\big| = \frac1{2^{2n-1}}. $$

We show that this is the minimal possible value. For all functions $f(x)$ and different reals $a_0,a_1,\ldots,a_n$, denote by $f[a_0,a_1,\ldots,a_n]$ the divided difference of $f$ on the nodes $a_0,\ldots,a_n$. The divided difference of the power $X^N$ will be denoted by $X^N[a_0,a_1,\ldots,a_n]$. It is well-known (and can be proved by induction) that $$ f[a_0,a_1,\ldots,a_n] = \sum_{j=0}^n \frac{f(a_j)}{\prod\limits_{k\ne j}(a_j-a_k)}, \tag1 $$ and $$ X^N[a_0,a_1,\ldots,a_n] = \sum_{d_0+d_1+\dots+d_n=N-n} a_0^{d_0}a_1^{d_1}\cdots a_n^{d_n} \tag2 $$ where the exponents $d_0,\ldots,d_n$ run over the nonnegative integers. If $N<n$ then the sum is empty.

Let $a_k=\frac12(1+\cos\frac{k\pi}n)$; then $t_n(a_k)=\frac{(-1)^k}{2^{2n-1}}$. On the RHS of $(2)$ all summands are nonnegative; if $N\ge n$ then one of the terms is $a_0^{N-n}=1$. Hence, \begin{align*} X^N[a_0,\ldots,a_n] &= 0 \quad \text{if $N<n$}; \\ X^N[a_0,\ldots,a_n] &=1 \quad \text{if $N=n$}. \\ X^N[a_0,\ldots,a_n] &\ge 1 \quad \text{if $N>n$}. \tag{3} \end{align*}

Taking the divided difference term by term, we can see that $$ t_n[a_0,\ldots,a_n] = X^n[a_0,\ldots,a_n] = 1. $$

Now let $f(x) = \sum\limits_{k=n}^\infty c_k x^k$, and let $p(x)=-\sum\limits_{k=0}^{n-1}c_kx^k$ be an arbitrary plynomial with degree less than $n$. Let $M=\max\limits_{[0,1]}|f-p|$ and consider the divided difference $(f-p)[a_0,\ldots,a_n]$.

From (1) we get \begin{gather*} (f-p)[a_0,\ldots,a_n] = \sum_{j=0}^n \frac{f(a_j)-p(a_j)}{\prod\limits_{k\ne j}(a_j-a_k)} \le \sum_{j=0}^n \frac{M}{\Big|\prod\limits_{k\ne j}(a_j-a_k)\Big|} = \\ = 2^{2n-1}M \sum_{j=0}^n \frac{(-1)^j/2^{2n-1}}{\prod\limits_{k\ne j}(a_j-a_k)} = 2^{2n-1}M \sum_{j=0}^n \frac{t_n(a_j)}{\prod\limits_{k\ne j}(a_j-a_k)} = \\ = 2^{2n-1}M \cdot t_n[a_0,\ldots,a_n] = 2^{2n-1}M. \end{gather*}

On the other hand, by (3), $$ (f-p)[a_0,\ldots,a_n] = \sum_{k=0}^\infty c_k \cdot X^k[a_0,\ldots,a_n] \ge \sum_{k=0}^{n-1} c_k \cdot 0 + \sum_{k=n}^\infty c_k \cdot 1 = \sum_{k=n}^\infty c_k = 1. $$

Therefore, $1 \le (f-p)[a_0,\ldots,a_n] \le 2^{2n-1}M$, so $M\ge\dfrac1{2^{2n-1}}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.