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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

This is not a complete proof, but rather a funny way of thinking about this problem.

In question you mentioned that you have successfully solved this problem:

If $𝑄_{𝜆(𝑥)}=𝜆𝑃_𝑛(𝑥)$ for some fixed polynomial $𝑃_𝑛$. Then there exist a polynomial $𝑄_{𝜆_0}$ such that $Δ(𝑄_{𝜆_0})= \min_{𝜆∈ℝ}Δ(𝑄_𝜆)$

We will use weaker version of this statement with $\lambda >0$ and introduce a new notation:

1) best distance($P(x)$) := $Δ(𝑄_{𝜆_0}$), corresponding to this $P(x)$.

2) best polynomial$(P(x)$) := one of the (in general, non-unique) polynomials $𝑄_{𝜆_i}$ that achieves best distance with maximum norm

(easy to check that both of them exist for any nontrivial polynomial)

---

Now let us consider equivalence relation on set of polynomials of degree $\le n$ having at least 1 nonzero coefficient:
$P(x) \sim Q(x) \iff P(x) = \lambda Q(x) , \lambda \in \mathbb{R}^{>0}$

On the one hand, polynomials are considered as eqiuvalent if vectors of their coefficients lie on the same ray with initial point zero.

On the other hand, polynomials are considered as equivalent if their $𝑄_{𝜆_0}$ from previous problem (and also best polynomials) are the same.

Now if we consider a point zero in $\mathbb{R}^n$, in each direction there exists a unique equivalence class corresponding to unique best distance and unique best polynomial.

Let $Bp$ be set of best polynomials (some subset of $\mathbb{R}^n$) and $Bd$ be set of best distances (some subset of $\mathbb{R}^1$)

It would be natural to consider these maps: $$(P_n(x) / \sim ) \xrightarrow{F} S^{n-1} \xrightarrow{G} Bp \xrightarrow{H} Bd$$

And notice that $S^{n-1}$ is compact. Then if $G$ and $H$ are continuous then Bd is compact and we proved initial theorem about best approximation polynomial for all $n \in \mathbb{N}$

Answer 4

I think Zorich's original idea on induction is to establish a mapping from $(P_n,\lambda)=(a_1,...,a_n,\lambda)\mapsto \mathbb{R}$. Prove it's a continuous mapping (similar to part b) on a compact interval (using the fact from part b and our inductive assumption for $n$).

But the claim is wrong since $\lambda$ can be $0$, where we may not extend from $n$ to $n+1$. A very simple counter-example is $f(x)=0$ on $[-1,1]$. There exists a polynomial of best approximation of degree $0$, that is $P_0(x)=0$. But there is not any polynomial $P_1(x)$ of best approximation with degree $1$.

Answer 5

Here is another solution to this old problem.

The solution described here is based on the following well known result in analysis:

Theorem: Suppose $X$ is a real (or complex) topological vector space, let $Y$ be subspace of $X$ with $n:=\operatorname{dim}(Y)<\infty$. Then $Y$ is a closed subset of $X$ and $X$ is linearly homeomorphic to $\mathbb{R}^d$ (or $\mathbb{C}^d$) equipped with the Euclidean norm $\|\;\|_2:\mathbf{x}=[x_1,\ldots,x_n]\mapsto \sqrt{\sum^n_{k=1}|x_k|^2}$

This result can be found in Rudin, W. Functional Analysis, McGraw-Hill, 2nd edition, pp. 16-17.

---

Although the OP does not required that level of generality, the ideas behind this result is the same whatever the nature of the topological linear space $X$ is.

The main idea behind the proof is to consider a basis $\{\mathbf{y}_k:1\leq k\leq n\}$ of $Y$ define a linear map $\Lambda:\mathbb{F}^n\rightarrow Y$- where $\mathbb{F}=\mathbb{R}$ or $\mathbb{F}=\mathbb{C}$ according to whether $X$ is a real or complex linear space- by setting $\Lambda(\mathbf{e}_k)=\mathbf{y}_k$, where $\{\mathbf{e}_k:1\leq k\leq n\}$ is the standard basis in $\mathbb{F}^n$. It is not difficult to show that $\Lambda$ is bijective and continuous. The tricky part is then to show that $\Lambda^{-1}:Y\rightarrow\mathbb{F}^n$ is also continuous. this can be achieved by considering the closed unit ball $B\subset\mathbb{F}^n$ and its boundary $\mathbb{S}^{n-1}$. Each sets are compact, and it follows that $K=\Lambda(\mathbb{S}^{n-1})$ is compact in $X$ and $\mathbf{0}\notin K$. Exploiting this observations, one can find an open neighborhood $V$ of $\mathbf{0}$ in $X$ such that $\Lambda^{-1}(V\cap Y)\subset \operatorname{Int}(B)$.

---

In particular, if $X$ is a normed space, it follows from the theorem above that any bounded closed set in $Y$ is compact.

Another application of the Theorem above yields the following result:

Proposition: Suppose $K$ be a compact Hausdorff topological space. Let $X$ be the space $(\mathcal{C}(K)$ equipped with the uniform norm $\|\;\|_u$, and suppose $Y$ is a finite dimensional subspace of $X$. We show that for any $f\in X$, there exists $g_f\in Y$ such that \begin{align} \|f-g_f\|&=d(f,Y)\tag{0}\label{best-approx}\end{align}

Proof: It follows from the theorem above that any closed and bounded subset of $Y$ is compact. As $d(f,G)\leq \|f-0\|_u=\|f\|_u$, the set $F:=\{g\in Y:\|g-f\|\leq \|f\|_u\}$ is closed and bounded in $Y$ and so, $F$ is compact. Since the function $g\mapsto \|f-g\|_u$ on $F$ is continuous, it attains its minimum value at some $g_*\in F$. It is immediate that $g_*$ satisfies \eqref{best-approx}.

---

A particular application is for $K=[a,b]$, a compact interval in $\mathbb{R}$, and $Y_n$ be the space spanned by the polynomials $\{1,x,\ldots,x^n\}$. In this case, for any $f\in C([a,b])$ and $n\in\mathbb{Z}_+$, there is a polynomial $p_n$ of degree less than $n$ (or $p_n\equiv 0$) such that $\|f-p_n\|_u=d(f,Y_n)$.

Remarks:

• This in combination with the Stone-Weierstrass theorem implies that $d(f,Y_n)\xrightarrow{n\rightarrow\infty}0$.

• With the addition of Chebyshev's alternation theorem (See for example Kincaid, D. and Cheney, W. Numerical Analysis, Brooks/Cole, 1991, pp. 380-381) one can obtained a sequence of interpolating polynomials $p_n$ with $n+1$ nodes in $(a,b)$ such that $\|f-p_n\|_u\xrightarrow{n\rightarrow\infty}0$.

Answer 6

Polynomial of degree n, according to the new version of the book, should be understood as of degree at most n. The following proof involves only one-variable continuity and is done by induction if I am not wrong.

Consider the function $g(\lambda)=E_{n}(f(x)-\lambda x^{n+1})$. By induction hyposthesis, we are able to find a polynomial $P_{n}(x;\lambda)$ of best approximation of degree $n$ to $f(x)-\lambda x^{n+1}$, Then for $\lambda \neq 0$,
\begin{aligned} g(\lambda)&=\|f(x)-\lambda x^{n+1}-P_{n}(x;\lambda)\|\\ &\geq \|\lambda x^{n+1}+P_{n}(x;\lambda)\|-\|f(x)\|\\ &=|\lambda|\cdot \|x^{n+1}+\lambda^{-1}\cdot P_{n}(x;\lambda)\|-\|f(x)\|\\ &\geq |\lambda|\cdot E_{n}(x^{n+1})-\|f(x)\| \end{aligned}
and it is not difficult to verify that $E_{n}(x^{n+1})>0$ (which is a result of the induction hypothesis). Thus, $g(\lambda) \to +\infty$, as $\lambda \to \infty$.

Now the continuity of $g(\lambda)$ would suffice to prove the assertion for $n+1$.

Without of loss of generality, we may show that $\lim_{\lambda \to 0}{E_{n}(f-\lambda x^{n+1})}=E_{n}(f)$.

Let $A=\{\lambda \in \mathbb{R}|E_{n}(f-\lambda x^{n+1})\geq E_{n}(f)\}$

and $B=\{\lambda \in \mathbb{R}|E_{n}(f-\lambda x^{n+1})\leq E_{n}(f)\}$.

Let $G(x)$ be a polynomial of best approximation of degree $n$ to $f(x)$

and $P_{n}(x;\lambda)$ be a polynomial of best approximation of degree $n$ to $f(x)-\lambda x^{n+1}$.

Note that

$ E_{n}(f)-|\lambda|\cdot \|x^{n+1}\| \leq \|f(x)-\lambda x^{n+1}-G(x)\|\leq E_{n}(f)+|\lambda|\cdot \|x^{n+1}\| $

and similarly

$ E_{n}(f-\lambda x^{n+1})-|\lambda|\cdot \|x^{n+1}\| \leq \|f(x)-P_{n}(x;\lambda)\|\leq E_{n}(f-\lambda x^{n+1})+|\lambda|\cdot \|x^{n+1}\| $

If $0$ is a limit point of $A$, since for any $\lambda$ in $A$ we have

$ E_{n}(f)\leq E_{n}(f-\lambda x^{n+1}) \leq \|f(x)-\lambda x^{n+1}-G(x)\| $

then

$ 0\leq E_{n}(f-\lambda x^{n+1})-E_{n}(f) \leq \|f(x)-\lambda x^{n+1}-G(x)\|-E_{n}(f) \leq |\lambda|\cdot \|x^{n+1}\| $

thus

$ \lim_{A\ni \lambda \to 0}{E_{n}(f-\lambda x^{n+1})}=E_{n}(f) $

and similarly by assuming $0$ is a limit point of $B$ we derive (the case when $0$ is a limit point of only one of the two sets is trivial)

$ \lim_{B\ni \lambda \to 0}{E_{n}(f-\lambda x^{n+1})}=E_{n}(f) $

Since the union of A and B is the real line, the limit holds for $\mathbb{R} \ni\lambda \to 0$. which shows the continuity.

Is anything wrong?

Answer 7

I also do not see how to prove the induction step, but it seems easier instead to prove the existence of polynomial of best approximation for all natural degrees. One of possible ways to follow those principles, mentioned by @ChristianBlatter is below.

---

$\alpha, \beta \in \mathbb{R}^n$

$P(\alpha) = \alpha_0x_0 + ...+\alpha_nx_n$

We can introduce a metric $d$ on bounded functions at $[a,b]$: $$d(f,g) = \sup_{b \le x \le a} |f(x) - g(x)|$$

Denote $\delta \in \mathbb{R}^{>0}$ - neighborhood of point $\alpha \in \mathbb{R}^n $ related to metric $d$ as $U^{\delta}_{d}{(\alpha)}$

Let's consider triangle inequality for $d$ : $$d(f(x), P(\alpha)) \le d(f(x), P(\beta)) + d(P(\alpha), P(\beta) ) \tag{1} $$ $$ \Rightarrow |d(f(x), P(\alpha)) - d(f(x), P(\beta))| \le d(P(\alpha), P(\beta) ) \tag{2}$$

Assume that we have chosen some fixed $\alpha$. Left-hand side of last inequality is actually bounded from the top by oscillation of function $\Delta(\alpha) := |\sup_{x \in [a,b]} {(f(x) - P(\alpha))} |$ at $d(\alpha, \beta)$ - neighbourhood of point $\alpha$ or shortly: $\le \omega_{\Delta(x)}( U^{d(\alpha, \beta)}_{d}{(\alpha)} )$. In other words, given $P(\beta)$ close enough to $P(\alpha)$, their images under $\Delta$ can become as close as we want.

That is why $\Delta$ is continuous map from $\mathbb{R}^n$ to $\mathbb{R}$. Continious function on set is continuous on subset, so our next goal is to construct a compact subset of $S \subset \mathbb{R}^n$ (each point representing a polynomial of degree $\le n$) such that $\forall x \in {\mathbb{R}^n}\setminus \{S\}$ and $ \exists y \in S$ that: $ \Delta(y) \le \Delta(x)$ (this condition means that minimum of $\Delta$ is certainly NOT in ${\mathbb{R}^n}\setminus \{S\}$ if exists).

Let $S$ be a zero-centered ball (with border) in ${\mathbb{R}^n}$ bounded with sphere of radius $r_0 > 2|\sup_{x \in [a,b]} {f(x)}|$ in metric space with metric $d$. Obviously, $\forall x \in {\mathbb{R}^n}\setminus S : d(f,x) \ge |\sup_{x \in [a,b]} {f(x)}| = d(0, f)$ In other words, $0 \in {\mathbb{R}^n}$ is closer to $f$ than any polynomial outside $S$. $\implies$ If minimum of exists, it is in $S$!

$S$ is compact, $\Delta$ is continuous $\implies$ minimum exists.

q.e.d