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 ).

See also: http://en.wikipedia.org/wiki/Bramble-Hilbert_lemma

$latex \displaystyle

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: