Bramble-Hilbert lemma

In mathematics, particularly numerical analysis, the Bramble-Hilbert lemma, named after James H. Bramble and Stephen R. Hilbert, bounds the error of an approximation of a function textstyle u by a polynomial of order at most textstyle m-1 in terms of derivatives of textstyle u of order textstyle m. Both the error of the approximation and the derivatives of textstyle u are measured by textstyle L^{p} norms on a bounded domain in textstyle mathbb{R}^{n}. This is similar to classical numerical analysis, where, for example, the error of linear interpolation textstyle u can be bounded using the second derivative of textstyle u. However, the Bramble-Hilbert lemma applies in any number of dimensions, not just one dimension, and the approximation error and the derivatives of textstyle 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 continuously differentiable boundary.

The main use of the Bramble-Hilbert lemma is to prove bounds on the error of interpolation of function textstyle u by an operator that preserves polynomials of order up to textstyle m-1, in terms of the derivatives of textstyle u of order textstyle m. 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.

The one dimensional case

Before stating the lemma in full generality, it is useful to look at some simple special cases. In one dimension and for a function textstyle u that has textstyle m derivatives on interval textstyle left( a,bright) , the lemma reduces to

inf_{vin P_{m-1}}biglVert u^{left( kright) }-v^{left( kright) }bigrVert_{L^{p}left( a,bright) }leq Cleft( mright) left(b-aright) ^{m-k}biglVert u^{left( mright) }bigrVert_{L^{p}left(a,bright) },

where textstyle P_{m-1} is the space of all polynomials of order at most textstyle m-1.

In the case when textstyle p=infty, textstyle m=2, textstyle k=0, and textstyle u is twice differentiable, this means that there exists a polynomial textstyle v of degree one such that for all textstyle xinleft( a,bright) ,

leftvert uleft( xright) -vleft( xright) rightvert leq Cleft(b-aright) ^{2}sup_{left( a,bright) }leftvert u^{primeprime }rightvert.

This inequality also follows from the well-known error estimate for linear interpolation by choosing textstyle v as the linear interpolant of textstyle u.

Statement of the lemma

Suppose textstyle Omega is a bounded domain in textstyle mathbb{R}^{n}, textstyle ngeq1, with boundary textstyle partialOmega and diameter textstyle d. textstyle W_{p}^{k}(Omega) is the Sobolev space of all function textstyle u on textstyle Omega with weak derivatives textstyle D^{alpha}u of order textstyle leftvert alpharightvert up to textstyle k in textstyle L^{p}(Omega). Here, textstyle alpha=left( alpha_{1},alpha_{2},ldots,alpha_{n}right) is a multiindex, textstyle leftvert alpharightvert = textstyle alpha_{1}+alpha_{2}+cdots+alpha_{n} and textstyle D^{alpha } denotes the derivative textstyle alpha_{1} times with respect to textstyle x_{1}, textstyle alpha_{2} times with respect to textstyle alpha_{2}, and so on. The Sobolev seminorm on textstyle W_{p}^{m}(Omega) consists of the textstyle L^{p} norms of the highest order derivatives,

leftvert urightvert _{W_{p}^{m}(Omega)}=left( sum_{leftvert alpharightvert =m}leftVert D^{alpha}urightVert _{L^{p}(Omega)}^{p}right) ^{1/p}text{ if }1leq p


leftvert urightvert _{W_{infty}^{m}(Omega)}=max_{leftvert alpharightvert =m}leftVert D^{alpha}urightVert _{L^{infty}(Omega)}

textstyle P_{k} is the space of all polynomials of order up to textstyle k on textstyle mathbb{R}^{n}. Note that textstyle D^{alpha}v=0 for all textstyle vin P_{m-1}. and textstyle leftvert alpharightvert =m, so textstyle leftvert u+vrightvert _{W_{p}^{m}(Omega)} has the same value for any textstyle vin P_{k-1}.

Lemma (Bramble and Hilbert) Under additional assumptions on the domain textstyle Omega, specified below, there exists a constant textstyle C=Cleft(m,Omegaright) independent of textstyle p and textstyle u such that for any textstyle uin W_{p}^{k}(Omega) there exists a polynomial textstyle vin P_{m-1} such that for all textstyle k=0,ldots,m,

leftvert u-vrightvert _{W_{p}^{k}(Omega)}leq Cd^{m-k}leftvert urightvert _{W_{p}^{m}(Omega)}.

The original result

The lemma was proved by Bramble and Hilbert under the assumption that textstyle Omega satisfies the strong cone property; that is, there exists a finite open covering textstyle left{ O_{i}right} of textstyle partialOmega and corresponding cones textstyle {C_{i}} with vertices at the origin such that textstyle x+C_{i} is contained in textstyle Omega for any textstyle x textstyle inOmegacap O_{i}.

The statement of the lemma here is a simple rewriting of the right-hand inequality stated in Theorem 1 in . The actual statement in is that the norm of the factorspace textstyle W_{p}^{m}(Omega)/P_{m-1} is equivalent to the textstyle W_{p}^{m}(Omega) seminorm. The textstyle W_{p}^{m}(Omega) norm is not the usual one but the terms are scaled with textstyle d so that the right-hand inequality in the equivalence of the seminorms comes out exactly as in the statement here.

In the original result, the choice of the polynomial is not specified, and the value of constant and its dependence on the domain textstyle Omega cannot be determined from the proof.

A constructive form

An alternative result was given by Dupont and Scott under the assumption that the domain textstyle Omega is star-shaped; that is, there exists a ball textstyle B such that for any textstyle xinOmega, the closed convex hull of textstyle left{ xright} cup B is a subset of textstyle Omega. Suppose that textstyle rho _{max} is the supremum of the diameters of such balls. The ratio textstyle gamma=d/rho_{max} is called the chunkiness of textstyle Omega.

Then the lemma holds with the constant textstyle C=Cleft( m,n,gammaright) , that is, the constant depends on the domain textstyle Omega only through its chunkiness textstyle gamma and the dimension of the space textstyle n. In addition, v can be chosen as v=Q^{m}u, where textstyle Q^{m}u is the averaged Taylor polynomial, defined as

Q^{m}u=intlimits_{B}T_{y}^{m}uleft( xright) psileft( yright) dx,


T_{y}^{m}uleft( xright) =sumlimits_{k=0}^{m-1}sumlimits_{leftvert alpharightvert =k}frac{1}{alpha!}D^{alpha}uleft( yright) left(x-yright) ^{alpha}

is the Taylor polynomial of degree at most textstyle m-1 of textstyle u centered at textstyle y evaluated at textstyle x, and textstyle psigeq0 is a function that has derivatives of all orders, equals to zero outside of textstyle B, and such that

intlimits_{B}psi dx=1.

Such function textstyle psi always exists.

For more details and a tutorial treatment, see the monograph by Brenner and Scott . The result can be extended to the case when the domain textstyle Omega is the union of a finite number of star-shaped domains, which is slightly more general than the strong cone property, and other polynomial spaces than the space of all polynomials up to a given degree.

Bound on linear functionals

This result follows immediately from the above lemma, and it is also called sometimes the Bramble-Hilbert lemma, for example by Ciarlet . It is essentially Theorem 2 from .

Lemma Suppose that textstyle ell is a continuous linear functional on textstyle W_{p}^{m}(Omega) and textstyle leftVert ellrightVert _{W_{p}^{m}(Omega )^{^{prime}}} its dual norm. Suppose that textstyle ellleft( vright) =0 for all textstyle vin P_{m-1}. Then there exists a constant textstyle C=Cleft( Omegaright) such that

leftvert ellleft( uright) rightvert leq CleftVert ellrightVert _{W_{p}^{m}(Omega)^{^{prime}}}leftvert urightvert _{W_{p}^{m}(Omega)}.


External links

  • - Jan Mandel: The Bramble-Hilbert Lemma

Search another word or see chunkinesson Dictionary | Thesaurus |Spanish
Copyright © 2015, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature