Bernstein approximations and Weierstrass' theorem #

THIS FILE IS SYNCHRONIZED WITH MATHLIB4. Any changes to this file require a corresponding PR to mathlib4.

We prove that the Bernstein approximations

∑ k : fin (n+1), f (k/n : ℝ) * n.choose k * x^k * (1-x)^(n-k)

for a continuous function f : C([0,1], ℝ) converge uniformly to f as n tends to infinity.

Our proof follows [Richard Beals' Analysis, an introduction][beals-analysis], §7D. The original proof, due to Bernstein in 1912, is probabilistic, and relies on Bernoulli's theorem, which gives bounds for how quickly the observed frequencies in a Bernoulli trial approach the underlying probability.

The proof here does not directly rely on Bernoulli's theorem, but can also be given a probabilistic account.

Consider a weighted coin which with probability x produces heads, and with probability 1-x produces tails.
The value of bernstein n k x is the probability that such a coin gives exactly k heads in a sequence of n tosses.
If such an appearance of k heads results in a payoff of f(k / n), the n-th Bernstein approximation for f evaluated at x is the expected payoff.
The main estimate in the proof bounds the probability that the observed frequency of heads differs from x by more than some δ, obtaining a bound of (4 * n * δ^2)⁻¹, irrespective of x.
This ensures that for n large, the Bernstein approximation is (uniformly) close to the payoff function f.

(You don't need to think in these terms to follow the proof below: it's a giant calc block!)

This result proves Weierstrass' theorem that polynomials are dense in C([0,1], ℝ), although we defer an abstract statement of this until later.

source

noncomputable def bernstein (n ν : ℕ) :

C(↥unit_interval , ℝ )

The Bernstein polynomials, as continuous functions on [0,1].

Equations

bernstein n ν = (bernstein_polynomial ℝ n ν).to_continuous_map_on unit_interval

source

@[simp]

theorem bernstein_apply (n ν : ℕ) (x : ↥unit_interval) :

⇑(bernstein n ν) x = ↑(n.choose ν) * ↑x ^ ν * (1 - ↑x) ^ (n - ν)

source

theorem bernstein_nonneg {n ν : ℕ} {x : ↥unit_interval} :

0 ≤ ⇑(bernstein n ν) x

We now give a slight reformulation of bernstein_polynomial.variance.

source

noncomputable def bernstein.z {n : ℕ} (k : fin (n + 1)) :

↥unit_interval

Send k : fin (n+1) to the equally spaced points k/n in the unit interval.

Equations

bernstein.z k = ⟨↑k / ↑n, _⟩

source

theorem bernstein.probability (n : ℕ) (x : ↥unit_interval) :

finset.univ.sum (λ (k : fin (n + 1)), ⇑(bernstein n ↑k) x) = 1

source

theorem bernstein.variance {n : ℕ} (h : 0 < ↑n) (x : ↥unit_interval) :

finset.univ.sum (λ (k : fin (n + 1)), (↑x - ↑(bernstein.z k)) ^ 2 * ⇑(bernstein n ↑k) x) = ↑x * (1 - ↑x) / ↑n

source

noncomputable def bernstein_approximation (n : ℕ) (f : C(↥unit_interval , ℝ )) :

C(↥unit_interval , ℝ )

The n-th approximation of a continuous function on [0,1] by Bernstein polynomials, given by ∑ k, f (k/n) * bernstein n k x.

Equations

bernstein_approximation n f = finset.univ.sum (λ (k : fin (n + 1)), ⇑f (bernstein.z k) • bernstein n ↑k)

We now set up some of the basic machinery of the proof that the Bernstein approximations converge uniformly.

A key player is the set S f ε h n x, for some function f : C(I, ℝ), h : 0 < ε, n : ℕ and x : I.

This is the set of points k in fin (n+1) such that k/n is within δ of x, where δ is the modulus of uniform continuity for f, chosen so |f x - f y| < ε/2 when |x - y| < δ.

We show that if k ∉ S, then 1 ≤ δ^-2 * (x - k/n)^2.

source

@[simp]

theorem bernstein_approximation.apply (n : ℕ) (f : C(↥unit_interval , ℝ )) (x : ↥unit_interval) :

⇑(bernstein_approximation n f) x = finset.univ.sum (λ (k : fin (n + 1)), ⇑f (bernstein.z k) * ⇑(bernstein n ↑k) x)

source

noncomputable def bernstein_approximation.δ (f : C(↥unit_interval , ℝ )) (ε : ℝ) (h : 0 < ε) :

ℝ

The modulus of (uniform) continuity for f, chosen so |f x - f y| < ε/2 when |x - y| < δ.

Equations

bernstein_approximation.δ f ε h = f.modulus (ε / 2) _

source

theorem bernstein_approximation.δ_pos {f : C(↥unit_interval , ℝ )} {ε : ℝ} {h : 0 < ε} :

0 < bernstein_approximation.δ f ε h

source

noncomputable def bernstein_approximation.S (f : C(↥unit_interval , ℝ )) (ε : ℝ) (h : 0 < ε) (n : ℕ) (x : ↥unit_interval) :

finset (fin (n + 1))

The set of points k so k/n is within δ of x.

Equations

bernstein_approximation.S f ε h n x = {k : fin (n + 1) | has_dist.dist (bernstein.z k) x < bernstein_approximation.δ f ε h}.to_finset

source

theorem bernstein_approximation.lt_of_mem_S {f : C(↥unit_interval , ℝ )} {ε : ℝ} {h : 0 < ε} {n : ℕ} {x : ↥unit_interval} {k : fin (n + 1)} (m : k ∈ bernstein_approximation.S f ε h n x) :

|⇑f (bernstein.z k) - ⇑f x| < ε / 2

If k ∈ S, then f(k/n) is close to f x.

source

theorem bernstein_approximation.le_of_mem_S_compl {f : C(↥unit_interval , ℝ )} {ε : ℝ} {h : 0 < ε} {n : ℕ} {x : ↥unit_interval} {k : fin (n + 1)} (m : k ∈ (bernstein_approximation.S f ε h n x)ᶜ) :

1 ≤ bernstein_approximation.δ f ε h ^ -2 * (↑x - ↑(bernstein.z k)) ^ 2

If k ∉ S, then as δ ≤ |x - k/n|, we have the inequality 1 ≤ δ^-2 * (x - k/n)^2. This particular formulation will be helpful later.

source

theorem bernstein_approximation_uniform (f : C(↥unit_interval , ℝ )) :

filter.tendsto (λ (n : ℕ), bernstein_approximation n f) filter.at_top (nhds f)

The Bernstein approximations

∑ k : fin (n+1), f (k/n : ℝ) * n.choose k * x^k * (1-x)^(n-k)

for a continuous function f : C([0,1], ℝ) converge uniformly to f as n tends to infinity.

This is the proof given in [Richard Beals' Analysis, an introduction][beals-analysis], §7D, and reproduced on wikipedia.