B. Multivariate Bernstein Polynomials

Here we give the proofs of the theorems in Section 7.4.

Theorem B..1   Let $f: I:=[0,1]\times[0,1]\to\mathbb{R}$ be a continuous function. Then the two-dimensional Bernstein polynomials

$$B_{f,n_1,n_2}(x_1,x_2):=\sum_{k_1=0}^{n_1}\sum_{k_2=0}^{n_2} f \l... ... k_1} {n_2\choose k_2} x_1^{k_1} (1-x_1)^{n_1-k_1} x_2^{k_2} (1-x_2)^{n_2-k_2}$$

converge pointwise to $f$ for $n_1,n_2\to\infty$.

Proof. Let $(x_1,x_2)\in I$ be a fixed point. Because of Theorem 7.2 we have

$${\vert B_{f,n_1,n_2}(x_1,x_2)-f(x_1,x_2)\vert}$$

$$\le \vert B_{f,n_1,n_2}(x_1,x_2)-B_{f(.,x_2),n_1}(x_1)\vert + \vert B_{f(.,x_2),n_1}(x_1)-f(x_1,x_2)\vert$$

$$\le 2\epsilon$$

for all $n_1\ge N_1(\epsilon)$ and $n_2\ge N_2(\epsilon)$. The second summand is smaller than $\epsilon$ for $n_1\ge N_1(\epsilon)$ because

$$B_{f(.,x_2),n_1}(x_1) = \sum_{k_1=0}^{n_1} f \left( {k_1\over n_1}, x_2 \right) {n_1\choose k_1} x_1^{k_1} (1-x_1)^{n_1-k_1}$$

is the Bernstein polynomial for $f(.,y)$, and the first summand is smaller than $\epsilon$ for $n_2\ge N_2(\epsilon)$ because $B_{f,n_1,n_2}(x,y)$ is the (one-dimensional) Bernstein polynomial for $B_{f(.,y),n_1}(x)$. Q.E.D.

Definition B..2 (Multivariate Bernstein Polynomials)   Let $n_1,\ldots,n_m\in\mathbb{N}$ and $f$ be a function of $m$ variables. The polynomials

$$B_{f,n_1,\ldots,n_m}(x_1,\ldots,x_m):= \sum_{{0\le k_j\le n_j}\at... ...ght) \prod_{j=1}^m \left( {n_j\choose k_j} x_j^{k_j} (1-x_j)^{n_j-k_j} \right)$$

are called the multivariate Bernstein polynomials of $f$.

Theorem B..3 (Pointwise Convergence)   Let $f: [0,1]^m\to\mathbb{R}$ be a continuous function. Then the multivariate Bernstein polynomials $B_{f,n_1,\ldots,n_m}$ converge pointwise to $f$ for $n_1,\ldots,n_m\to\infty$.

Proof. By applying Theorem 7.2 to each summand in

$${\vert B_{f,n_1,\ldots,n_m}(x_1,\ldots,x_m)-f(x_1,\ldots,x_m)\vert}$$

$$\le \vert B_{f,n_1,\ldots,n_m}(x_1,\ldots,x_m) - B_{f(.,\ldots,.,x_m),n_1,\ldots,n_{m-1}}(x_1,\ldots,x_{m-1})\vert$$

$${} + \vert B_{f(.,\ldots,.,x_m),n_1,\ldots,n_{m-1}}(x_1,\ldots,x_{m-1}) - B_{f(.,\ldots,.,x_{m-1},x_m),n_1,\ldots,n_{m-2}}(x_1,\ldots,x_{m-2})\vert$$

$${} + \cdots + \vert B_{f(.,x_2,\ldots,x_m),n_1}(x_1) - f(x_1,\ldots,x_m)\vert$$

we see that given an $\epsilon>0$ there are $N_1(\epsilon)$,..., $N_m(\epsilon)$ such that

$$\vert B_{f,n_1,\ldots,n_m}(x_1,\ldots,x_m)-f(x_1,\ldots,x_m)\vert \le m\epsilon$$

for all $n_i\ge\max(N_1(\epsilon),\ldots,N_m(\epsilon))$. Q.E.D.

Lemma B..4   For all $x\in\mathbb{R}$

$$\sum_{k=0}^{n} (k-nx)^2 {n\choose k} x^k (1-x)^{n-k} = nx(1-x).$$

For all $x\in[0,1]$ we have $x(1-x)\le 1/4$ and hence

$$0 \le \sum_{k=0}^{n} (k-nx)^2 {n\choose k} x^k (1-x)^{n-k} \le {n\over 4}.$$

Theorem B..5 (Uniform Convergence)   Let $f: [0,1]^m\to\mathbb{R}$ be a continuous function. Then the multivariate Bernstein polynomials $B_{f,n_1,\ldots,n_m}$ converge uniformly to $f$ for $n_1,\ldots,n_m\to\infty$.

Proof. We first note that because of the uniform continuity of $f$ on  $I:=[0,1]^m$ we have

$$\forall \epsilon>0:\quad \exists \delta>0:\quad \forall x,x'\in I... ... x-x'\Vert<\delta \;\Longrightarrow\;\Vert f(x)-f(x')\Vert < {\epsilon\over2}.$$

Given an $\epsilon>0$, we can find such a $\delta$. In order to simplify notation we set

$$b_j:={n_j\choose k_j} x_j^{k_j} (1-x_j)^{n_j-k_j}$$

and $k:=\left( {k_1\over n_1}, \ldots, {k_m\over n_m} \right)$. $x$ always lies in $I$. We have to estimate

$$B_{f,n_1,\ldots,n_m}(x) - f(x) = \sum_{{0\le k_j\le n_j}\atop{j\in\{1,\ldots,m\}}} (f(k) - f(x)) b_1\cdots b_m$$

and to that end we split the sum into two parts, namely

$$S_1:= \sum\nolimits' (f(k) - f(x)) b_1\cdots b_m,$$

where $\sum\nolimits'$ means summation over all $k_j$ with ${0\le k_j\le n_j}$ (where $j\in\{1,\ldots,m\}$) and $\Vert k - x \Vert _2 \ge \delta$, and

$$S_2:= \sum\nolimits'' (f(k) - f(x)) b_1\cdots b_m,$$

where $\sum\nolimits''$ means summation over the remaining terms. For $S_2$ we have

$$\vert S_2\vert \le \sum\nolimits'' \vert f(k) - f(x)\vert b_1\cdo... ...{{0\le k_j\le n_j}\atop{j\in\{1,\ldots,m\}}} b_1\cdots b_m = {\epsilon\over2}.$$

We will now estimate $S_1$. In the sum $S_1$ the inequality $\Vert k - x \Vert _2 \ge \delta$ holds, i.e.,

$$\left( {k_1\over n_1} - x_1 \right)^2 + \cdots + \left( {k_m\over n_m} - x_m \right)^2 \ge \delta^2.$$

Hence at least one of the summands on the left hand side is greater equal $\delta^2/m$. Without loss of generality we can assume this is the case for the first summand:

$$1 \le {m\over\delta^2}{(k_1-n_1 x)^2\over n_1^2}.$$

Thus, using Lemma B.4,

$$\sum\nolimits' b_1\cdots b_m \le \sum\nolimits' {m\over\delta^2 n_1^2} (k_1-n_1 x)^2 b_1\cdots b_m$$

$$\le {m\over\delta^2 n_1^2} \sum_{{0\le k_j\le n_j}\atop{j\in\{1,\ldots,m\}}} (k_1-n_1 x)^2 b_1\cdots b_m$$

$$= {m\over\delta^2 n_1^2} \sum_{k_1=0}^{n_1} (k_1-n_1 x)^2 {n_1\choose k_1} x_1^{k_1} (1-x_1)^{n_1-k_1}$$

$$\le {m\over\delta^2 n_1^2} {n\over4} = {m \over 4 \delta^2 n_1}.$$

We can now estimate $S_1$. Since $f$ is continuous on a compact set $M:=\max_{x\in I} \vert f(x)\vert$ exists.

$$\vert S_1\vert \le \sum\nolimits' \vert f(k) - f(x)\vert b_1\cdots b_m$$

$$\le 2M \sum\nolimits' b_1\cdots b_m$$

$$\le {2Mm\over4\delta^2 n_1} = {Mm\over2\delta^2 n_1}$$

For $n_1$ large enough we have $Mm / 2\delta^2n_1 < \epsilon/2$ and thus

$$\vert B_{f,n_1,\ldots,n_m}(x) - f(x)\vert \le \vert S_1\vert+\vert S_2\vert < {\epsilon\over2} + {\epsilon\over2} = \epsilon,$$

which completes the proof. Q.E.D.

A reformulation of this fact is the following corollary.

Corollary B..6   The set of all polynomials is dense in $C([0,1]^m)$.

Theorem B..7 (Error Bound for Lipschitz Condition)   If $f: I:=[0,1]^m\to\mathbb{R}$ is a continuous function satisfying the Lipschitz condition

$$\Vert f(x)-f(y)\Vert _2 < L \Vert x-y\Vert _2$$

on $I$, then the inequality

$$\Vert B_{f,n_1,\ldots,n_m}(x) - f(x) \Vert _2 < {L\over2} \biggl( \sum_{j=1}^m {1\over n_j} \biggr)^{1\over2} %$$

holds.

Proof. Abbreviating notation we set $k:=\left( {k_1\over n_1}, \ldots, {k_m\over n_m} \right)$. We will use the Lipschitz condition, Corollary A.7, and Lemma B.4.

$${\Vert B_{f,n_1,\ldots,n_m}(x) - f(x) \Vert _2^2}$$

$$\le \biggl( \sum_{k_1,\ldots,k_m} \Vert f(k) - f(x) \Vert _2 b_1\cdots b_m \biggr)^2$$

$$< \left( L \sum \Vert k-x \Vert _2 b_1\cdots b_m \right)^2$$

$$\le L^2 \left( \sum \Vert k-x \Vert _2^2 b_1\cdots b_m \right) \left( \sum b_1\cdots b_m \right)$$

$$= L^2 \sum \left( \left({k_1\over n_1}-x_1\right)^2 + \cdots + \left({k_m\over n_m}-x_m\right)^2 \right) b_1\cdots b_m$$

$$= L^2 \sum_{j=1}^m {x_j(1-x_j)\over n_j}$$

$$\le L^2 \sum_{j=1}^m {1\over 4 n_j}$$

This completes the proof. Q.E.D.

Theorem B..8 (Asymptotic Formula)   Let $f: I:=[0,1]^m\to\mathbb{R}$ be a $C^2$ function and $x\in I$, then

$$\lim_{n\to\infty} n ( B_{f,n,\ldots,n}(x) - f(x) ) = \sum_{j=1}^m... ...rtial x_j^2} \le {1\over8} \sum_{j=1}^m {\partial ^2 f(x)\over\partial x_j^2}.$$

Proof. We define the vector $h$ through $h_j:=k_j/n-x_j$, where the $k_j$ are the integers over which we sum in $B_{f,n,\ldots,n}$. Using Theorem A.14 we see

$$f\left({k_1\over n},\ldots,{k_m\over n}\right) = f(x) + \sum_{j=1}^m \left( {k_j\over n}-x_j \right) {\partial f(x)\over\partial x_j}$$

$${} + {1\over2} \sum_{i=1}^m\sum_{j=1}^m \left( {k_i\over n}-x_i \... ...) {\partial ^2 f(x_0)\over \partial x_i \partial x_j} + \Vert h\Vert^2 \rho(h),$$

where $\lim_{h\to0} \rho(h)=0$. Summing this equation like the sum in $B_{f,n,\ldots,n}$ we obtain

$$B_{f,n,\ldots,n} = f(x) + {1\over2} \sum_{i=1}^m {x_j(1-x_j)\over... ...r \partial x_j^2} + \sum_{k_1,\ldots,k_m} \Vert h\Vert^2 \rho(h) b_1\cdots b_m$$

since many terms vanish or can be summed because of Lemma B.4. Noting $\lim_{h\to0} \rho(h)=0$ we can apply the same technique as in the proof of Theorem B.5 for estimating the last sum in the last equation, i.e., splitting the sum into two parts for $\Vert h\Vert\ge\delta$ and $\Vert h\Vert<\delta$. Hence we see that for all $\epsilon$ this sum is less equal $\epsilon/n$ for all sufficiently large $n$, which yields the claim. Q.E.D.