Approximation Theory

Track 5 has developed three approximation paradigms, each with its own strengths and limitations:

Each successive paradigm trades specificity for generality. The thread connecting them all is the question: how well can we approximate functions, and what determines the answer?

For $f \in C[a,b]$ and $n \geq 0$, the best polynomial approximation error (or minimax error) of degree $n$ is

$E_n(f) = \inf_{p \in \mathcal{P}_n} \|f - p\|_\infty = \inf_{p \in \mathcal{P}_n} \max_{x \in [a,b]} |f(x) - p(x)|$

where $\mathcal{P}_n$ is the space of polynomials of degree $\leq n$. The infimum is attained — compactness of $[a,b]$, continuity of $f$, and finite dimension of $\mathcal{P}_n$ guarantee the existence of a best approximant $p_n^*$ with $\|f - p_n^*\|_\infty = E_n(f)$.

If $f: [a,b] \to \mathbb{R}$ is continuous, then for every $\varepsilon > 0$ there exists a polynomial $p$ such that

$\|f - p\|_\infty = \max_{x \in [a,b]} |f(x) - p(x)| < \varepsilon.$

Equivalently, $E_n(f) \to 0$ as $n \to \infty$.

In the language of metric spaces: the polynomials $\mathcal{P} = \bigcup_{n=0}^{\infty} \mathcal{P}_n$ are dense in $(C[a,b], \|\cdot\|_\infty)$.

The theorem is an existence result. It guarantees that good polynomial approximants exist but does not:

• Construct the best polynomial for a given $\varepsilon$
• Specify what degree $n$ is needed
• Identify the optimal polynomial $p_n^*$

The Bernstein construction (Section 3) provides an explicit sequence of polynomial approximants. The Chebyshev theory (Section 6) characterizes the best approximant. Jackson’s theorem (Section 7) quantifies the rate.

For $f: [0,1] \to \mathbb{R}$ and $n \geq 1$, the $n$th Bernstein polynomial of $f$ is

$B_n(f; x) = \sum_{k=0}^{n} f\!\left(\frac{k}{n}\right) \binom{n}{k} x^k (1 - x)^{n-k}.$

The Bernstein basis polynomials are

$b_{k,n}(x) = \binom{n}{k} x^k (1 - x)^{n-k}, \quad k = 0, 1, \ldots, n.$

These form a partition of unity: $\sum_{k=0}^n b_{k,n}(x) = 1$ for all $x \in [0,1]$.

Let $S_n \sim \text{Binomial}(n, x)$. Then

$B_n(f; x) = \mathbb{E}\!\left[f\!\left(\frac{S_n}{n}\right)\right].$

Each Bernstein polynomial evaluates $f$ at the random points $k/n$ weighted by the binomial probabilities. As $n \to \infty$, the law of large numbers gives $S_n/n \to x$ in probability, so $f(S_n/n) \to f(x)$ by continuity, giving $B_n(f; x) \to f(x)$. This is the heuristic — the rigorous proof makes it precise.

If $f: [0,1] \to \mathbb{R}$ is continuous, then $B_n(f; x) \to f(x)$ uniformly on $[0,1]$:

$\|B_n(f) - f\|_\infty \to 0 \quad \text{as } n \to \infty.$

The proof uses three identities for the Bernstein basis:

Identity 1 (partition of unity): $\displaystyle\sum_{k=0}^n b_{k,n}(x) = 1$.

Identity 2 (first moment): $\displaystyle\sum_{k=0}^n \frac{k}{n}\, b_{k,n}(x) = x$.

Identity 3 (variance): $\displaystyle\sum_{k=0}^n \left(\frac{k}{n} - x\right)^2 b_{k,n}(x) = \frac{x(1-x)}{n} \leq \frac{1}{4n}$.

Now fix $\varepsilon > 0$. Since $f$ is continuous on the compact set $[0,1]$, it is uniformly continuous: choose $\delta > 0$ such that $|f(s) - f(t)| < \varepsilon$ whenever $|s - t| < \delta$.

For any $x \in [0,1]$, using Identity 1:

$|B_n(f;x) - f(x)| = \left|\sum_{k=0}^n \bigl[f(k/n) - f(x)\bigr]\, b_{k,n}(x)\right| \leq \sum_{k=0}^n |f(k/n) - f(x)|\, b_{k,n}(x).$

Split the sum into two parts. Let $M = \|f\|_\infty$.

Near terms ($|k/n - x| < \delta$): Here $|f(k/n) - f(x)| < \varepsilon$, so these terms contribute at most $\varepsilon \cdot \sum b_{k,n}(x) \leq \varepsilon$.

Far terms ($|k/n - x| \geq \delta$): Here $|f(k/n) - f(x)| \leq 2M$, and by Identity 3:

$\sum_{|k/n - x| \geq \delta} b_{k,n}(x) \leq \frac{1}{\delta^2}\sum_{k=0}^n \left(\frac{k}{n} - x\right)^2 b_{k,n}(x) \leq \frac{1}{4n\delta^2}.$

These terms contribute at most $2M \cdot \frac{1}{4n\delta^2} = \frac{M}{2n\delta^2}$.

Combining: $|B_n(f;x) - f(x)| \leq \varepsilon + \frac{M}{2n\delta^2}$.

Choose $n > \frac{M}{2\varepsilon\delta^2}$. Then $|B_n(f;x) - f(x)| < 2\varepsilon$ for all $x \in [0,1]$, so $\|B_n(f) - f\|_\infty < 2\varepsilon$.

Since $\varepsilon > 0$ was arbitrary, $B_n(f) \to f$ uniformly. $\square$

The function $f(x) = |2x - 1|$ is continuous but not differentiable at $x = 1/2$. Its Bernstein polynomials $B_n(f; x) = \sum_k |2k/n - 1|\, b_{k,n}(x)$ are smooth polynomials that converge uniformly to $f$, rounding the corner at $x = 1/2$. At $n = 5$, the approximation is visibly smooth; at $n = 50$, it is nearly indistinguishable from $f$ except in a narrow region around $x = 1/2$.

For the smooth function $f(x) = x(1-x)$, the Bernstein polynomial satisfies $B_n(f; x) = x(1-x)(n-1)/n$, giving $\|B_n(f) - f\|_\infty = 1/(4n) = O(1/n)$ — faster than the general $O(1/\sqrt{n})$ because $f$ is smooth.

For $f(x) = |2x - 1|$ (Lipschitz but not $C^1$), $\|B_n(f) - f\|_\infty = O(1/\sqrt{n})$ — the worst-case rate for Lipschitz functions.

This illustrates that Bernstein convergence is slow — adequate for proving the Weierstrass theorem, but not optimal for computation.

A set $\mathcal{A} \subset C(K)$ is a subalgebra of $C(K)$ if it is closed under addition, scalar multiplication, and pointwise multiplication. $\mathcal{A}$ separates points if for any $x \neq y$ in $K$, there exists $g \in \mathcal{A}$ with $g(x) \neq g(y)$. $\mathcal{A}$ vanishes nowhere if for every $x \in K$, there exists $g \in \mathcal{A}$ with $g(x) \neq 0$. If $\mathcal{A}$ contains the constant functions, it automatically vanishes nowhere.

Let $K$ be a compact metric space and let $\mathcal{A} \subset C(K, \mathbb{R})$ be a subalgebra that separates points and contains the constant functions. Then $\mathcal{A}$ is dense in $C(K, \mathbb{R})$ under the sup-norm:

$\overline{\mathcal{A}} = C(K, \mathbb{R}).$

Take $K = [a,b]$ and $\mathcal{A} = \mathcal{P}$, the polynomials. Polynomials form a subalgebra (closed under $+$, $\cdot$, scalar multiplication). They separate points: $p(x) = x$ distinguishes any $x \neq y$. They contain the constants. Therefore $\overline{\mathcal{P}} = C[a,b]$ by Stone-Weierstrass. This is precisely Theorem 1.

Take $K = \mathbb{T} = \mathbb{R}/(2\pi\mathbb{Z})$ (the circle) and $\mathcal{A}$ the trigonometric polynomials. They form a subalgebra (products of trig functions are trig functions), separate points (if $e^{ix} \neq e^{iy}$ then $\cos x \neq \cos y$ or $\sin x \neq \sin y$), and contain the constants. Stone-Weierstrass gives density, consistent with the Fourier series theory from Topic 19, which proved this concretely via Parseval’s identity.

Take $K \subset \mathbb{R}^d$ compact and $\mathcal{A}$ the polynomials in $d$ variables. They separate points: the coordinate functions $x_i$ distinguish points that differ in any coordinate. Stone-Weierstrass gives the density of multivariate polynomials in $C(K)$ — a result that would be laborious to prove directly but follows immediately from the abstract theorem.

The theorem applies to $C(K, \mathbb{R})$ with the sup-norm. It does not directly apply to $L^p$ spaces (which require measure theory) or to non-compact domains (which require additional decay conditions). The complex version requires $\mathcal{A}$ to be self-conjugate: $g \in \mathcal{A} \Rightarrow \bar{g} \in \mathcal{A}$. This condition is automatic for real-valued algebras but must be checked for complex ones.

The best $L^2$ approximation of $f \in L^2[a,b]$ from $\mathcal{P}_n$ is the polynomial $p_n^{L^2}$ minimizing

$\|f - p\|_2 = \sqrt{\int_a^b |f(x) - p(x)|^2\,dx}.$

The best uniform (Chebyshev) approximation of $f \in C[a,b]$ from $\mathcal{P}_n$ is the polynomial $p_n^*$ minimizing

$\|f - p\|_\infty = \max_{x \in [a,b]} |f(x) - p(x)|.$

The best $L^2$ polynomial approximation $p_n^{L^2}$ is the orthogonal projection of $f$ onto $\mathcal{P}_n$ in the inner product $\langle f, g \rangle = \int_a^b f(x)g(x)\,dx$. If $\{\phi_0, \phi_1, \ldots, \phi_n\}$ is an orthonormal basis for $\mathcal{P}_n$ (e.g., the Legendre polynomials), then

$p_n^{L^2}(x) = \sum_{k=0}^{n} \langle f, \phi_k \rangle\, \phi_k(x).$

This is exactly the Fourier coefficient formula from Topic 19, with orthogonal polynomials replacing trigonometric functions.

$L^2$ best approximation is easy to compute (orthogonal projection — just compute inner products) but allows large pointwise errors on small sets. Uniform best approximation is hard to compute (a nonlinear optimization problem) but gives a guaranteed pointwise bound everywhere.

In ML: $L^2$ approximation corresponds to minimizing mean squared error (training loss), while uniform approximation corresponds to worst-case guarantees (robustness). A model that minimizes MSE can still have catastrophic errors on rare inputs — the gap between $L^2$ and uniform approximation is the gap between average-case and worst-case performance.

For $f(x) = |x|$ on $[-1,1]$ with $n = 2$ (quadratic approximation): the best $L^2$ approximant is the orthogonal projection $p_2^{L^2}(x) = \frac{1}{2} + \frac{15}{8}\left(x^2 - \frac{1}{3}\right)$ (computed from Legendre coefficients), while the best uniform approximant $p_2^*(x)$ has an equioscillation property — the error alternates between $+E_2(f)$ and $-E_2(f)$ at three points. The two approximants are different polynomials — the norm determines the answer.

The Chebyshev polynomial of the first kind is

$T_n(x) = \cos(n \arccos x), \quad x \in [-1, 1], \quad n \geq 0.$

Equivalently, $T_n$ is the unique polynomial of degree $n$ with leading coefficient $2^{n-1}$ (for $n \geq 1$) satisfying $|T_n(x)| \leq 1$ for $x \in [-1, 1]$.

The zeros are the Chebyshev nodes:

$x_k = \cos\!\left(\frac{2k - 1}{2n}\pi\right), \quad k = 1, \ldots, n.$

Among all monic polynomials of degree $n$ (leading coefficient $= 1$), the one with smallest sup-norm on $[-1,1]$ is $\tilde{T}_n(x) = T_n(x)/2^{n-1}$, and

$\min_{\text{monic } p,\, \deg p = n} \|p\|_\infty = \frac{1}{2^{n-1}},$

achieved uniquely by the normalized Chebyshev polynomial.

For $f \in C[a,b]$, a polynomial $p^* \in \mathcal{P}_n$ is the best uniform approximation if and only if the error $f - p^*$ equioscillates at least $n + 2$ times: there exist $a \leq x_0 < x_1 < \cdots < x_{n+1} \leq b$ such that

$f(x_j) - p^*(x_j) = (-1)^j \|f - p^*\|_\infty$

(alternating sign, full magnitude). This characterizes the best approximant uniquely.

Consider interpolating $f(x) = 1/(1 + 25x^2)$ on $[-1, 1]$ using polynomial interpolation. With $n + 1$ equispaced nodes, the interpolant diverges near the endpoints as $n \to \infty$ — the maximum interpolation error grows without bound. With Chebyshev nodes $x_k = \cos((2k-1)\pi/(2n+2))$, the interpolant converges uniformly.

The Runge phenomenon is the polynomial interpolation analog of the Gibbs phenomenon from Topic 19: equispaced sampling is suboptimal, and the right node distribution matters enormously.

The identity $T_n(\cos\theta) = \cos(n\theta)$ means that Chebyshev approximation on $[-1,1]$ is equivalent to Fourier cosine approximation on $[0, \pi]$ under the substitution $x = \cos\theta$. This connects Topic 20 back to Topic 19: the Chebyshev coefficients of $f$ are the Fourier cosine coefficients of $f(\cos\theta)$, and the coefficient decay rates from Topic 19 translate directly into approximation rates for Chebyshev expansions.

The modulus of continuity of $f \in C[a,b]$ is

$\omega(f; \delta) = \sup_{|x - y| \leq \delta} |f(x) - f(y)|, \quad \delta > 0.$

$f$ is Lipschitz (with constant $L$) if $\omega(f; \delta) \leq L\delta$. $f$ is Hölder continuous with exponent $\alpha \in (0, 1]$ if $\omega(f; \delta) \leq C\delta^\alpha$. The modulus quantifies “how continuous” $f$ is — it is the most refined scalar measure of regularity for continuous functions.

If $f \in C[-1, 1]$, then for every $n \geq 1$,

$E_n(f) \leq C \cdot \omega\!\left(f; \frac{1}{n}\right),$

where $C$ is an absolute constant. More generally, if $f \in C^r[-1,1]$ (i.e., $f$ is $r$ times continuously differentiable), then

$E_n(f) \leq \frac{C_r}{n^r}\, \omega\!\left(f^{(r)}; \frac{1}{n}\right).$

The smoother $f$ is, the faster $E_n(f) \to 0$.

If $E_n(f) = O(n^{-r-\alpha})$ for some integer $r \geq 0$ and $0 < \alpha < 1$, then $f \in C^r[-1,1]$ and $f^{(r)}$ is Hölder continuous with exponent $\alpha$:

$\omega(f^{(r)}; \delta) = O(\delta^\alpha).$

The converse of Jackson’s theorem: fast approximation rates imply smoothness.

(a) $f(x) = |x|$ is Lipschitz ($\omega(f; \delta) = \delta$), so Jackson gives $E_n(f) = O(1/n)$.

(b) $f(x) = x|x|$ is $C^1$ with Lipschitz derivative, so $E_n(f) = O(1/n^2)$.

(c) $f \in C^\infty$ (analytic) has $E_n(f) = O(e^{-cn})$ — superalgebraic convergence.

This mirrors the Fourier coefficient decay hierarchy from Topic 19: the same smoothness conditions control both Fourier coefficient decay and polynomial approximation rates.

Together, Jackson’s and Bernstein’s theorems establish that

$E_n(f) \asymp n^{-r-\alpha} \quad \Longleftrightarrow \quad f^{(r)} \text{ exists and is Hölder-}\alpha.$

Approximation rate and smoothness are two sides of the same coin. This tight equivalence has no analog in Fourier theory (where coefficient decay characterizes smoothness of periodic functions).