# There exist a degree $n+1$ polynomial of best approximation if there exist a degree $n$ polynomial of best approximation

This is a problem from Mathematical Analysis by Zorich, from the chapter on continuous functions.

Definition: Let $P_n$ be a polynomial of degree $n$. For a function $f:[a,b]\to\mathbb{R}$, Let $\Delta(P_n) = \sup_{x\in[a,b]} |f(x)-P_n(x)|$. and $E_n(f) = \inf_{P_n} \Delta(P_n)$. A polynomial $P_n$ is the best approximation of degree $n$ of $f$ is $\Delta(P_n) = E_n(f)$.

I have already proved the following:

There exist a polynomial $P_0(x) = a$ of best approximation of degree 0.

If $Q_\lambda(x) = \lambda P_n(x)$ for some fixed polynomial $P_n$. Then there exist a polynomial $Q_{\lambda_0}$ such that $\Delta(Q_{\lambda_0}) = \min_{\lambda\in \mathbb{R}} \Delta(Q_\lambda)$

I'm stuck on proving the following:

If there exists a polynomial of best approximation of degree $n$, there also exists a polynomial of best approximation of degree $n+1$.

My intuition is to prove $\lambda_0 x^{n+1}+P_n$ is the $n+1$ best approximation for $f$. Where $\Delta(\lambda_0 x^{n+1}) = \min_{\lambda\in \mathbb{R}} \Delta(\lambda x^{n+1})$ and $\Delta(P_n) = E(f(x) - \lambda_0 x^{n+1})$.

I don't know if this approach is right. I'm stuck on how to proceed.

-

Determining the best $n$th degree approximation explicitely is a very difficult problem and cannot be done by a simple induction (see the chapter on Tschebyscheff approximation in your favorite textbook of numerical analysis). But existence is easy, it follows from general principles: You have to set up a certain continuous function $\Phi$ on a certain compact set $K$ in a high-dimensional space.

-
For the benefit of search engines: this is the Chebyshev minimax approximation problem: finding the polynomial approximant to a function with "equi-ripple" error. –  Ｊ. Ｍ. Oct 26 '10 at 9:40
Thanks. I found counter examples of what I suggested. The proof for the 2nd statement can be generalized easily to n-dimension and lead to the result. But the book didn't go into continuous functions in higher-dimensions yet. Are there any other way to solve this problem? –  Chao Xu Oct 26 '10 at 22:33

Here is the original problem from the book:

Let $P_n$ be a polynomial of degree $n$. For a function $f:[a,b]\to\mathbb{R}$, let $\Delta(P_n) = \sup_{x\in[a,b]} |f(x)-P_n(x)|$ and $E_n(f) = \inf_{P_n} \Delta(P_n)$; that is, the infimum is taken over all polynomials of degree $n$. A polynomial $P_n$ is called a polynomial of best approximation of degree $n$ if $\Delta(P_n) = E_n(f)$. Show that:

(a) There exists a polynomial of best approximation of degree zero.

(b) Among polynomials $Q_\lambda(x)$ of the form $\lambda P(x)$ where $P(x)$ is a fixed polynomial, there is a polynomial $Q_{\lambda_0}$ such that $\Delta(Q_{\lambda_0}) = \min_{\lambda\in \mathbb{R}} \Delta(Q_\lambda)$

(c) If there exists a polynomial of best approximation of degree $n$, there also exists a polynomial of best approximation of degree $n+1$.

(d) For any $n$, there exists a polynomial of best approximation of degree $n$.

Like the OP, I have no idea how to prove (c) but can prove (d) directly. Formally I didn't use higher dimensions continuity, but actually I did.

Proof. Let $j: (c_0, c_1, ..., c_n) \rightarrow \mathbb R$ such that $j(c_0, c_1, ..., c_n) = \sup |f(x) - \left( c_0 + c_1 x + ... + c_n x^n \right)|$ . As we are trying to find $c_0, ..., c_n$ such that $j$ attains minimum, we may restrict ourselves to work only with $c_0, ..., c_n$ such that $|c_0 + c_1 x + ... + c_n x^n| \le M$ $\forall x \in [a,b]$ for some $M$. Using, for example Lagrange's interpolation formula, this condition means that $|c_i| \le M_1$ for all $i$. Thus we consider the function $k$ which is the restriction of $j$ on tuples $(c_0,..., c_n)$ satisfying $|c_i| \le M_1$.

By the definition of infimum, there is a sequence $(c_{0m}, c_{1m}, ..., c_{nm}), m \in \mathbb Z$ such that $k(c_{0m}, c_{1m}, ..., c_{nm})$ tends to $t:=\inf k$. Because $c_i$ are bounded, from that sequence we may extract a subsequence $(c_{0p}, c_{1p}, ..., c_{np})$ such that $c_{ip} \rightarrow$ some $t_i$ $\forall i$ when $p$ tends to infinity. Thus when $p$ is large enough, we have $|c_{ip} - t_i| \le \delta$ $\forall i$ and so we have, for each $x$ in $[a,b]$:

$\left| \left|f(x) - (c_{0p} + c_{1p} x + ... + c_{np} x^n) \right| - \left|f(x) - (t_0 + t_1 x + ... + t_n x^n) \right| \right|$ $\le \left| \left( f(x) - (c_{0p} + c_{1p} x + ... + c_{np} x^n) \right) - \left( f(x) - \left(t_0 + t_1 x + ... + t_n x^n \right) \right) \right|$ $=\left| (c_{0p} - t_0) + (c_{1p} - t_1)x + ... + (c_{np} - t_n)x^n \right|$ $\le \delta \left| 1+x+...+x^n \right|$ $\le \delta M_2$ where $M_2$ is some bound for $1+x+...+x^n$ on $[a,b]$.

Therefore $|k(c_{0p}, c_{1p}, ..., c_{np}) - k(t_1, t_2, ..., t_n)|$ $= \left| \sup \left|f(x) - (c_{0p} + c_{1p} x + ... + c_{np} x^n) \right| - \sup \left|f(x) - (t_0 + t_1 x + ... + t_n x^n) \right| \right|$ $\le \delta M_2$ because if each element in some set X oscillates by no more than $\delta M_2$ then set X's supremum oscillates by no more than $\delta M_2$ too. If p is large enough, then $\delta$ is small enough so that $\delta M_2$ can be smaller than any desired $\epsilon$.

What we have done so far is to show that $k(c_{0p}, c_{1p},..., c_{np})$ $\rightarrow k(t_1, t_2, ..., t_n)$. But it is known earlier that $k(c_{0p}, c_{1p},..., c_{np})$ $\rightarrow \inf k$. Thus $\inf k = k(t_1, t_2, ..., t_n)$ and we are done.

-