Closest polynomial to a continuous function (under the infinity norm metric)

Question

I am trying to solve the following problem:

Let $f$ be a continuous function on $[a,b]$. Let $n$ be a natural number.

We consider the following set: $$ E_n= \left\{ P \in \mathbb{R}_n[X], \|P-f\|_\infty = \inf_{Q \in \mathbb{R}_n[X]} \|Q-f\|_\infty \right\} $$

What I have to show is that:

a) $E_n$ is not an empty set

b) $E_n$ is convex

c) $E_n$ is a unit set (meaning a set containing one element, also known as a singleton)

I actually have a mental block on c). (In the euclidean case, it is straightforward because of the polarization identity. But the infinity norm bans this case).

a) and b) still should help solve c).

Thank you in advance for your help.

NB : $\mathbb{R}_n[X]$ is the set of all polynomials whose degree is below or equal $n$, with coefficients in the ring $\mathbb{R}$. It can be seen as a vector space of dimension $n+1$.

Answer 1

HINT: For c) use the following fact

If $P$ is a closest polynomial of degree $\le n$ to the function $f$, then $|f(t)-P(t)|=\| f-P\|$ for at least $(n+2)$ points $t$. To show this prove the following

Lemma: if $g$ continuous on $[a,b]$ achieves its largest absolute value in at most $(n+1)$ points, then there exists a polynomial $Q$ of degree at most $n$ so that $\|g-Q\|<\|g\|$.

For the proof of the lemma: assume that we have a continuous function $h$ such that $ \operatorname{sign} h(t_i)=\operatorname{sign} g_(t_i)$ at all points $t_i$ at which $|g(t_i)|=\|g\|$. Then for $\epsilon>0$ small enough we have $\|g-\epsilon h\|< \|g\|$. Now for $h$ take a convenient Lagrange interpolation polynomial.

Answer 2

For Q a) and Q b).

The standard notation for the set of continuous $f:[a,b]\to \Bbb R$ is $C[a,b].$ Let $\Bbb R_n$ be the polynomials in $C[a,b]$ of degree at most $n.$

A finite-dimensional linear subspace $L$ of a normed linear space is closed and any closed bounded subset of $L$ is compact.

Let $M=\inf \{\|Q-f\|:Q\in \Bbb R_n\}.$ Let $S=(Q_j)_{j\in \Bbb N}$ be a sequence in $\Bbb R_n$ with $\lim_{j\to \infty}\|Q_j-f\|=M.$

The sequence $S$ is bounded because $\|Q_j\|\le \|Q_j-f\|+\|f\|$ while $\|Q_j-f\|+\|f\|$ converges.

Now $\Bbb R_n$ is a finite-dimensional linear subspace of $C[a,b]$ so the closure in $C[a,b]$ of the bounded set $\{Q_j:j\in \Bbb N\}$ is a bounded closed (and hence compact) subset of $\Bbb R_n.$ So there exists a sub-sequence $T=( Q_{j_k})_{k\in \Bbb N}$ converging to some $g\in R_n.$ Since $\lim_{k\to \infty} \|Q_{j_k}-g\|=0,$ we have $\|g-f\|=\lim_{k\to \infty}\|Q_{j_k}-f\|=M. $

So $g\in E_n.$

If $g_1, g_2\in E_n$ then for any $x\in [0,1]$ we have $xg_1+(1-x)g_2 \in \Bbb R_n$ so by def'n of $M$ we have $M\le \|xg_1+(1-x)g_2-f\|,$ but we also have $$\|xg_1+(1-x)g_2\|=\|x(g_1-f)+(1-x)(g_2-f)\|\le$$ $$\le \|x(g_1-f)\|+\|+(1-x)(g_2-f)\|=$$ $$=xM+(1-x)M=M.$$

So $\|xg_1+(1-x)g_2\|=M,$ so $xg_1+(1-x)g_2\in E_n.$

Q c) is a theorem of Chebyschev but I do not know the proof.