Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
For the benefit of search engines: this is the Chebyshev minimax approximation problem: finding the polynomial approximant to a function with "equi-ripple" error. –  J. M. 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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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