= Lipschitz error bound for Bernstein approximation
{c}
{title2=$\|B_nf-f\|_\infty\leq L/(2\sqrt n)$}
If $f$ is <Lipschitz continuous> on $[0,1]$ with <Lipschitz constant> $L$, then <Cauchy-Schwarz inequality> and the <binomial distribution> <variance> give
$$
|B_nf(x)-f(x)|
\leq L\mathbb E|K/n-x|
\leq L\sqrt{\mathbb E[(K/n-x)^2]}
=L\sqrt{\frac{x(1-x)}n}
\leq\frac L{2\sqrt n}.
$$
This is an explicit error guarantee, rather than only an existence theorem. For the <Bernstein approximation of a corner>, choosing $n\geq2500$ guarantees <supremum norm> error at most $0.01$; $n>2500$ guarantees error strictly less than $0.01$. The guarantee is sufficient, not optimal.
\Image[/bernstein-corner-errors-and-probability-bound.png]
{title=The corner's approximation error stays below a <binomial distribution> variance bound}
{description=Left: error profiles for $|x-1/2|$ and selected <Bernstein polynomials>. Right: for even positive degrees, exact maximum error $\binom n{n/2}/2^{n+1}$ is compared with the sufficient bound $1/(2\sqrt n)$. All values are model calculations; no experimental data are represented.}
For this specific target, the error reaches its maximum at $x=1/2$. Indeed the <derivative> of $B_nf$ is a weighted average of the slopes $n[f((k+1)/n)-f(k/n)]$, all in $[-1,1]$: see <derivatives of Bernstein polynomials>. Subtracting the target makes the error nondecreasing to the left of the corner and nonincreasing to its right. For even $n\geq2$, the symmetric <binomial distribution> at $x=1/2$ gives the exact value
$$
\|B_nf-f\|_\infty=B_nf(1/2)
=\frac1{n2^n}\sum_{k=0}^n\binom nk\left|k-\frac n2\right|
=\frac{\binom n{n/2}}{2^{n+1}}.
$$
The last equality follows by pairing terms about $n/2$ and telescoping the <binomial coefficients>. It gives $1/4$ for $n=2$ and $3/16$ for $n=4$.
Back to article page
