Prove that the normalized Chebyshev polynomials are the best approximation to zero in $[-1,1]$

Question

This is the exercise 13 of Analysis I of Amann and Escher, page 349.

Define the normalized Tchebyshev polynomials by $\tilde T_n:=T_n/2^{n-1}$ and $\tilde T_0:=T_0$. Let $\mathcal P_n\subset\Bbb R[X]$ for $n\in\Bbb N_{\ge 0}$ such that if $p\in\mathcal P_n$ then $\deg(p)=n$ and $[x^n]p(x)=1$. Prove that the $\tilde T_n$ is the best approximation of zero in $\mathcal P_n$ in $[-1,1]$, that is $$\|\tilde T_n\|_\infty\le \|p\|_\infty,\quad p\in\mathcal P_n$$

This exercise is killing me. Previous known facts:

• $T_n(x)=\cos(n\arccos x)=\sum_{k\ge 0}\binom{n}{2k}x^{n-2k}(x^2-1)^k$.

• $T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)$.

• The local extrema of $T_n$ are attained at $y_k:=\cos\frac{k\pi}{n}$ for $k=0,1,\ldots,n$, i.e. $T_n(y_k)=(-1)^k$.

• The zeros of $T_n$ are $x_k:=\cos\frac{(2k-1)\pi}{2n}$ for $k=1,2,\ldots,n$.

• If we define $\tilde T_n(x):=\sum_{k=0}^n a_kx^k$ then $a_n=1$.

• From above we have the identity $\tilde T_n(x)=\prod_{k=1}^{n}(x-x_k)$.

From all of this we know that $\|\tilde T_n\|_\infty=1/2^{n-1}$. But I dont know exactly where start or what to do to prove the statement of the exercise.

I tried to start proving that for each $p\in\mathcal P_n$ with some zero it must exists some $x_0\in[-1,1]$ such that $|p(x_0)|=1/2^{n-1}$ (but now Im not sure that this deduction was correct or useful).

I tried induction over $n$ for polynomials in $p_n\in\mathcal P_n$, writing something like $p_{n+1}=xp_n+c$, but I dont get something useful.

The exercise comes after some theory about Taylor theorem and some polynomial approximation based in Newton/Lagrange polynomials (there is no theory in the book, by now, related to integration). But trying to relate the exercise to the theory was fruitless.

Some hint (or solution) will be appreciated.

---

UPDATE: I think I get the way to do, but the proof below is not (by now) totally correct.

We knows that $\|\tilde T_n\|_\infty=1/2^{n-1}$, so the statement to prove must be re-written as

$$\frac1{2^{n-1}}\le \|p\|_\infty,\quad \forall p\in\mathcal P_n$$

Now define $p_n:=p$ for any $p\in\mathcal P_n$, i.e. the degree of $p_n$ is $n$. I define too $p_n(0):=c_n$. Then if $|c_n|\ge\frac1{2^{n-1}}$ we are done.

Then suppose that $|c_n|<\frac1{2^{n-1}}$. Now we prove by induction:

1. Base case: $\|p_1\|_\infty=\|x+c_1\|\ge 1$ for $x\in[-1,1]$.

2. Induction hypothesis: assume that $\|p_n\|_\infty\ge 1/2^{n-1}$.

3. Induction step: first observe that $p_{n+1}=xp_n+c_{n+1}$ for some $p_n$, then we want to prove that $$\|p_{n+1}\|_\infty=\|xp_n+c_{n+1}\|_\infty\ge1/2^n$$

   Then

   $$\|xp_n\|+|c_{n+1}|\ge\|xp_n+c_{n+1}\|_\infty\ge\big|\|xp_n\|_\infty-|c_{n+1}|\big|\ge\ldots \text{(working around)}$$

Answer 1

The version of your solution before your edit (that just occurred) was correct if you know that $x_0$, which was the largest $x$ such that $|p_n(x)|=\|p_n\|$ is $x_0=1$.

Proof that $|p_n(1)|=\|p_n\|$: Suppose instead that $|p_n(1)|<\|p_n\|.$

Let $|p_n(1)|< (1-s)\|p_n\|$ with $0<s<1.$ For some (sufficiently small) $r>0$ such that $(1+r/2)^n(1-s)=1-t$ ( with $0<t<1$) we have $$\forall x\in [1,1+r]\;(|p_n(x)|< (1-s)\|p_n\|).$$ Let $q_n(x)=(1+r/2)^{-n}p_n(y)$ where $y=(2+r)(x+1)/2-1.$

We have $x\in [-1,1]\iff y\in [-1,1+r].$ Then deg$(q_n)=n$. The leading coefficient of $q_n$ is $1.$ But $$\{|q_n(x)|:|x|\leq 1\}=\{|(1+r/2)^n p_n(y)|: y\in [-1,1+r]\} \subset [-(1-t)\|p_n|,(1-t)\|p_n\|]$$ implying $\|q_n\|<\|p_n\|,$ contradicting the minimality of $\|p_n\|.$

I only know this part because I worked on this problem once. Your inductive step was the one piece I couldn't find. You really should have written $x_n$ for $x_0$ in your earlier version.... I have read that there is a deeper theorem of Chebyshev, that if $P(n)$ is the set of polynomials of degree $\leq n,$ then for any $f\in C[-1,1]$ there is a unique $p\in P_n$ that minimizes $\{\|f-q\|_{\infty}:q\in P(n)\}.$ The uniqueness is the hard part, as closures of non-empty open balls in this norm are not strictly convex . (I.e. there are linearly independent $g,h\in C[-1,1]$ with $\|g\|=\|h\|=\|(g+h)/2\|$.)

Answer 2

I found a very elegant proof of this (old) question. I can see now what @DanielWainfleet was trying to show me.

---

We knows that $\|\tilde T_n\|_\infty=1/2^{n-1}$, so the statement to prove can be re-written as $$ \frac1{2^{n-1}}\le \|p\|_\infty,\quad \forall p\in\mathcal P_n $$ Let $p\in\mathcal P_n$ and suppose that $\|p\|_\infty <\frac1{2^{n-1}}$, then because $T_n(y_k)=(-1)^k$ for $y_k$ defined as in the previous exercise for $k=0,1,\ldots,n$ we find that $g:=p-\tilde T_n$ belongs to $\mathcal P_{n-1}$ and $\operatorname{sign}(g(x_k))=(-1)^k$ for $k=0,1,\ldots,n$. Then $g$ changes of sign $n+1$ times so it must have $n$ distinct roots. However $\deg(g)=n-1$ so it is not possible that it have $n$ distinct roots. This shows that necessarily $\|p\|_\infty\ge\frac1{2^{n-1}}$, as desired.

Answer 3

\emph{Proof.} Per previous discussion we know that the coefficient of the highest degree term of $T_{n}(x)$ is $2^{n-1}$, so to make it monic, we define $$\tilde{T}_{n}(x)=\frac{1}{2^{n-1}}T_{n}(x)$$

Also we know that $\max_{x\in[-1,1]}|T_{n}(x)|=1$, then $$\max_{x\in[-1,1]}|\tilde{T}_{n}(x)|=\frac{1}{2^{n-1}}$$ So we only need to prove that for any (monic) polynomial of degree $n$ ($P\in\mathcal{P}_{n}$), $$\max_{x\in[-1,1]}|P_{n}(x)|\ge\frac{1}{2^{n-1}}$$

Try to use mathematical induction. At $n=1$, the polynomials must be in form $P_{1}(x)=x+a$. It is a straight line with no internal extremum; on interval $[-1,1]$, \begin{align*} P_{1}(-1)=-1+a=a-1\\ P_{1}(1)=1+a=a+1 \end{align*} Obviously, $a>0\Rightarrow a+1>1$, $a<0\Rightarrow a-1<-1$, so to let $\max\{|a-1|,|a+1|\}$ be the minimal, it is imperative to have $a=0$, which leads to $P_{1}(x)=x$, and $\min\max|P_{1}(x)|=1=2^{1-1}$.\

At $n=2$, we have $P_{2}(x)=x^{2}+ax+b$, which can always be written as $P_{2}(x)=(x-p)^{2}+q$. At $x=p$, $P_{2}(x)$ has minimal value $q$. Similar to the case of $P_{1}(x)$, To keep $(x-p)^{2}$ be minimal on $[-1,1]$, it is imperative that $p=0$: $$\begin{cases} p>0\Rightarrow -1-p<-1\\ p<0\Rightarrow 1+p>1 \end{cases}$$ At $p=0$, we have $P_{2}(x)=x^{2}+q$, so $P_{2}(-1)=P_{2}(1)=1+q$, while the internal extremum is $P_{2}(0)=q$. so $$\begin{cases} q>-\frac{1}{2}\Rightarrow 1+q>\frac{1}{2}\\ q<-\frac{1}{2}\Rightarrow |q|>\frac{1}{2} \end{cases}$$

Therefore we have returned to $P_{2}(x)=\tilde{T}_{n}(x)=x-\frac{1}{2}$ and $\min\max|P_{2}(x)|=\frac{1}{2}$.

Now assume this is correct up to $P_{k}$, ie, $$\min\max|P_{k}(x)|=\frac{1}{2^{k-1}}$$

At $k+1$, assume we have $P_{k+1}(x)$ such that $$\min\max|P_{k+1}(x)|<\frac{1}{2^{k}}$$ then consider polynomial $$g(x)=P_{k+1}(x)-\tilde{T}_{k+1}(x)$$

Since both $P_{k+1}(x)$ and $\tilde{T}_{n+1}(x)$ are monic, the highest degree term canceled, so $\deg(g(x))=k$ and \begin{align*} \min\max|g(x)|\le&\min\max|P_{k+1}(x)|+\min\max|T_{k+1}(x)|\\ <&\frac{1}{2^{k}}+\frac{1}{2^{k}}=\frac{2}{2^{k}}=\frac{1}{2^{k-1}} \end{align*}

Which contradicts the assumption that $\min\max|P_{k}(x)|\ge\frac{1}{2^{k-1}}$.Q.E.D.