# Ngô Quốc Anh

## April 22, 2010

### The Bramble-Hilbert lemma

Filed under: Giải tích 9 (MA5265) — Ngô Quốc Anh @ 14:27

In numerical analysis, the Bramble-Hilbert lemma, named after James H. Bramble and Stephen R. Hilbert, bounds the error of an approximation of a function $u$ by a polynomial of order at most $k$ in terms of derivatives of $u$ of order $k+1$. Both the error of the approximation and the derivatives of $u$ are measured by $L^p$ norms on a bounded domain in $\mathbb R^n$.

Theorem. Over a sufficiently domain $\Omega$, there exists a constant $C(\Omega)$ such that

$\displaystyle\mathop {\inf }\limits_{v \in {P_k}(\Omega )} {\left\| {u - v} \right\|_{{W^{k + 1,p}}(\Omega )}} \leqslant C(\Omega ){\left| u \right|_{{W^{k + 1,p}}(\Omega )}}$

for every $u \in W^{k+1,p}(\Omega)$ where $\| \cdot \|$ and $| \cdot|$ denote the norm and semi-norm of the Sobolev space $W^{k+1,p}(\Omega)$.

This is similar to classical numerical analysis, where, for example, the error of linear interpolation $u$ can be bounded using the second derivative of $u$. However, the Bramble-Hilbert lemma applies in any number of dimensions, not just one dimension, and the approximation error and the derivatives of $u$ are measured by more general norms involving averages, not just the maximum norm.

Additional assumptions on the domain are needed for the Bramble-Hilbert lemma to hold. Essentially, the boundary of the domain must be “reasonable”. For example, domains that have a spike or a slit with zero angle at the tip are excluded. Lipschitz domains are reasonable enough, which includes convex domains and domains with $C^1$ boundary.

The main use of the Bramble-Hilbert lemma is to prove bounds on the error of interpolation of function $u$ by an operator that preserves polynomials of order up to $k$, in terms of the derivatives of $u$ of order $k+1$. This is an essential step in error estimates for the finite element method. The Bramble-Hilbert lemma is applied there on the domain consisting of one element.

Proof. Let $N =\dim P_k(\Omega)$ and let $f_ i$, $1 \leqslant i \leqslant N$, be a basis of the dual space of $P_k(\Omega)$. Using the Hahn-Banach extension theorem, there exist continuous linear forms over the space $W^{k+1,p}(\Omega)$, again denoted $f_i$, $1 \leqslant i \leqslant N$, such that for any $p\in P_k ( \Omega)$, we have $f_i ( p ) = 0$, $1 \leqslant i \leqslant N$, if and only if $p \equiv 0$. We will show that there exists a constant $C(\Omega)$ such that

$\displaystyle {\left\| u \right\|_{{W^{k + 1,p}}(\Omega )}} \leqslant C(\Omega )\left( {{{\left| u \right|}_{{W^{k + 1,p}}(\Omega )}} + \sum\limits_{i = 1}^N {\left| {{f_i}(u)} \right|} } \right)$

for every $u \in W^{k+1,p}(\Omega)$. We assume for a moment the above inequality holds, we show that the theorem follows.

Indeed, given any function $u \in W^{k+1,p}(\Omega)$, let $v_0 \in P_k(\Omega)$ such that

$\displaystyle f_i(u-v_0)=0, \quad\forall 1 \leqslant i \leqslant N$.

we then have

$\displaystyle {\left\| {u - {v_0}} \right\|_{{W^{k + 1,p}}(\Omega )}} \leqslant C(\Omega )\left( {{{\left| {u - {v_0}} \right|}_{{W^{k + 1,p}}(\Omega )}} + \sum\limits_{i = 1}^N {\left| {{f_i}(u - {v_0})} \right|} } \right) = C(\Omega ){\left| {u - {v_0}} \right|_{{W^{k + 1,p}}(\Omega )}}$

which becomes

$\displaystyle {\left\| {u - {v_0}} \right\|_{{W^{k + 1,p}}(\Omega )}} \leqslant C(\Omega ){\left| u \right|_{{W^{k + 1,p}}(\Omega )}}$

where the last inequality comes from the fact that any $(k+1)$th derivatives of $v_0 \in P_k(\Omega)$ equals zero.

We now prove by contradiction. Then there exists a sequence $\{ u_l\}_{l=1}^\infty$ of functions $u_l \in W^{k+1,p}(\Omega)$ such that for any $l\geqslant 1$ we have $\|u_l\|_{W^{k+1,p}(\Omega)}=1$ and

$\displaystyle\mathop {\lim }\limits_{l \to \infty } \left( {{{\left| {{u_l}} \right|}_{{W^{k + 1,p}}(\Omega )}} + \sum\limits_{i = 1}^N {\left| {{f_i}({u_l})} \right|} } \right) = 0$.

Since the sequence $\{ u_l\}_{l=1}^\infty$ is bounded in $W^{k+1,p}(\Omega)$, there exists a subsequence, again denoted by $\{ u_l\}_{l=1}^\infty$ and a function $u_0 \in W^{k,p}(\Omega)$ such that

$\displaystyle\mathop {\lim }\limits_{l \to \infty } {\left\| {{u_l} - u_0} \right\|_{{W^{k,p}}(\Omega )}} = 0$.

This fact comes from the Rellich-Kondrachov Theorem for $1 \leqslant p < \infty$ and from the Arzelà-Ascoli Theorem for $p =\infty$. Since

$\displaystyle\mathop {\lim }\limits_{l \to \infty } {\left| {{u_l}} \right|_{{W^{k + 1,p}}(\Omega )}} = 0$

and

$\displaystyle\mathop {\lim }\limits_{l \to \infty } {\left\| {{u_l} - u_0} \right\|_{{W^{k,p}}(\Omega )}} = 0$

and the fact that the space $W^{k+1,p}(\Omega)$ is complete we conclude that the sequence $\{ u_l\}_{l=1}^\infty$ also converges in the space $W^{k+1,p}(\Omega)$ to $u_0$. The limit $u_0$ of this sequence is such that

$\displaystyle {\left| {{\partial ^\alpha }{u_0}} \right|_{{W^{0,p}}(\Omega )}} = \mathop {\lim }\limits_{l \to \infty } {\left| {{\partial ^\alpha }{u_l}} \right|_{{W^{0,p}}(\Omega )}} = 0$

for very multi-index $\alpha$ such that $|\alpha|=k+1$ and thus $\partial^\alpha u_0=0$ for all multi-index $\alpha$ with $|\alpha|=k+1$. With the connectedness of $\Omega$, it follows from distribution theory that the function $u_0$ is a polynomial of degree less than or equal to $k$. Thus, it follows from

$\displaystyle\mathop {\lim }\limits_{l \to \infty } \left( {{{\left| {{u_l}} \right|}_{{W^{k + 1,p}}(\Omega )}} + \sum\limits_{i = 1}^N {\left| {{f_i}({u_l})} \right|} } \right) = 0$

that

$\displaystyle {f_i}({u_0}) = \mathop {\lim }\limits_{l \to \infty } {f_i}({u_l}) = 0$

so that we conclude that $u_0 = 0$, from the properties of the linear forms $f_i$. But this contradicts the equality

$\displaystyle\|u_l\|_{W^{k+1,p}(\Omega)}=1$

for all $l$.

From the proof above one can easily obtain the following variant

Theorem. Over a sufficiently domain $\Omega$, there exists a constant $C(\Omega)$ and a polynomial $v \in P_k(\Omega)$ such that

$\displaystyle {\left\| {u - v} \right\|_{{W^{k + 1,p}}(\Omega )}} \leqslant C(\Omega ){\left| u \right|_{{W^{k + 1,p}}(\Omega )}}$

for every $u \in W^{k+1,p}(\Omega)$ where $\| \cdot \|$ and $| \cdot|$ denote the norm and semi-norm of the Sobolev space $W^{k+1,p}(\Omega)$.

We also have the following corollary

Corollary. Over a sufficiently domain $\Omega$, there exists a constant $C(\Omega)$ such that

$\displaystyle {\left\| {\dot u} \right\|_{{W^{k + 1,p}}(\Omega )}} \leqslant C(\Omega ){\left| u \right|_{{W^{k + 1,p}}(\Omega )}}$

for any

$\displaystyle\dot u \in {W^{k + 1,p}}(\Omega )/{P_k}(\Omega )$.

\$latex \displaystyle