I am trying to prove a lemma which will (probably) help me answer a previous question.
Let $f:[0,1] \to [0,1]$ be a continous function.
For each positive integer $n$, let $p_n:[0,1] \to[0,1]$ be the unique $n$-th degree polynomial such that $f(i/n)=p_n(i/n)$ for each $i \in \{0,1,...,n\}$.
Fix $\epsilon>0$.
Does there exist an $n$ such that $|f-p_n|< \epsilon$?
I am pretty sure that the answer is "yes," but am having trouble showing it rigorously.
My informal intuition motivates me to show somehow that $p_n(x)$ can only move around "a little bit" as $x$ moves from $\frac {i-1} n \to \frac i n$. I know that each $f-p_n$ is uniformly continous, so we can choose a $\delta _n>0$ such that $|x-y|< \delta_n \to |(f-p_n)(x)-(f-p_n)(y)|< \epsilon$. If $\delta_n$ is $1/n$ or less, then it's our lucky day. But what if $\delta_n>1/n$? The problem also seems complicated since $\delta_n$ might be different for different $n$.
The answer is no. Not only is there no $n$ with $|f(x) - p_n(x)| < \epsilon$ for all $n$, but in fact it sometimes happens that $\lim_{n\rightarrow \infty} \max_x |f(x) - p_n(x)| = \infty$, so no bound is possible. This is called Runge's phenomenon. An example is given by $f(x) = 1 / (1 - 25x^2)$ on $[-1,1]$, called the "witch of Agnesi" for some reason. (If you want to stick to $x \in [0,1]$, just apply the appropriate transformation.) Here is a nice lab exercise demonstrating the problem. With ten equally spaced points, we get
With 40 equally spaced points, the fit looks like this:
giving increasingly wild results as $n \rightarrow \infty$.
This is a classic example of overfitting: we have $0$ error on our "training set" (the equally spaced points) but very high error on our "test set" (the remaining points in the interval.) The interpolating polynomial will have very large coefficients; if loosen the restriction that $p_n$ fits exactly at each point, but "punish" the fit for having large coefficients using some form of regularization, the results may be better. Alternatively, we could try to be more clever in which points we choose to interpolate at (see the lab.)
Note that that we can find a sequence of polynomials $p_n$ with $p_n \rightarrow f$ uniformly on a compact interval, for any continuous $f$. This is Stone-Weierstrass. However, this particular polynomial sequence - the interpolating polynomial with equally spaced points - will not work in general.