- Bramble-Hilbert lemma
In
mathematics , particularlynumerical analysis , the Bramble-Hilbert lemma, named afterJames H. Bramble andStephen R. Hilbert , bounds the error of anapproximation of a function extstyle u by apolynomial of order at most extstyle m-1 in terms of derivatives of extstyle u of order extstyle m. Both the error of the approximation and the derivatives of extstyle u are measured by extstyle L^{p} norms on abounded domain in extstyle mathbb{R}^{n}. This is similar to classical numerical analysis, where, for example, the error oflinear interpolation extstyle u can be bounded using the second derivative of extstyle u. However, the Bramble-Hilbert lemma applies in any number of dimensions, not just one dimension, and the approximation error and the derivatives of extstyle u are measured by more general norms involving averages, not just themaximum 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 domain s are reasonable enough, which includesconvex domains and domains withcontinuously differentiable boundary.The main use of the Bramble-Hilbert lemma is to prove bounds on the error of interpolation of function extstyle u by an operator that preserves polynomials of order up to extstyle m-1, in terms of the derivatives of extstyle u of order extstyle 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 extstyle u that has extstyle m derivatives on interval extstyle left( a,b ight) , the lemma reduces to
:inf_{vin P_{m-1iglVert u^{left( k ight) }-v^{left( k ight) }igrVert_{L^{p}left( a,b ight) }leq Cleft( m ight) left( b-a ight) ^{m-k}iglVert u^{left( m ight) }igrVert_{L^{p}left( a,b ight) },
where extstyle P_{m-1} is the space of all polynomials of order at most extstyle m-1.
In the case when extstyle p=infty, extstyle m=2, extstyle k=0, and extstyle u is twice differentiable, this means that there exists a polynomial extstyle v of degree one such that for all extstyle xinleft( a,b ight) ,
:leftvert uleft( x ight) -vleft( x ight) ightvert leq Cleft( b-a ight) ^{2}sup_{left( a,b ight) }leftvert u^{primeprime } ightvert.
This inequality also follows from the well-known error estimate for linear interpolation by choosing extstyle v as the linear interpolant of extstyle u.
tatement of the lemma
Suppose extstyle Omega is a bounded domain in extstyle mathbb{R}^{n}, extstyle ngeq1, with boundary extstyle partialOmega and
diameter extstyle d. extstyle W_{p}^{k}(Omega) is theSobolev space of all function extstyle u on extstyle Omega withweak derivative s extstyle D^{alpha}u of order extstyle leftvert alpha ightvert up to extstyle k in extstyle L^{p}(Omega). Here, extstyle alpha=left( alpha_{1},alpha_{2},ldots,alpha_{n} ight) is amultiindex , extstyle leftvert alpha ightvert = extstyle alpha_{1}+alpha_{2}+cdots+alpha_{n} and extstyle D^{alpha } denotes the derivative extstyle alpha_{1} times with respect to extstyle x_{1}, extstyle alpha_{2} times with respect to extstyle alpha_{2}, and so on. The Sobolev seminorm on extstyle W_{p}^{m}(Omega) consists of the extstyle L^{p} norms of the highest order derivatives,:leftvert u ightvert _{W_{p}^{m}(Omega)}=left( sum_{leftvert alpha ightvert =m}leftVert D^{alpha}u ightVert _{L^{p}(Omega)}^{p} ight) ^{1/p} ext{ if }1leq p
and
:leftvert u ightvert _{W_{infty}^{m}(Omega)}=max_{leftvert alpha ightvert =m}leftVert D^{alpha}u ightVert _{L^{infty}(Omega)}
extstyle P_{k} is the space of all polynomials of order up to extstyle k on extstyle mathbb{R}^{n}. Note that extstyle D^{alpha}v=0 for all extstyle vin P_{m-1}. and extstyle leftvert alpha ightvert =m, so extstyle leftvert u+v ightvert _{W_{p}^{m}(Omega)} has the same value for any extstyle vin P_{k-1}.
Lemma (Bramble and Hilbert) Under additional assumptions on the domain extstyle Omega, specified below, there exists a constant extstyle C=Cleft( m,Omega ight) independent of extstyle p and extstyle u such that for any extstyle uin W_{p}^{k}(Omega) there exists a polynomial extstyle vin P_{m-1} such that for all extstyle k=0,ldots,m,
:leftvert u-v ightvert _{W_{p}^{k}(Omega)}leq Cd^{m-k}leftvert u ightvert _{W_{p}^{m}(Omega)}.
The original result
The lemma was proved by Bramble and Hilbert J. H. Bramble and S. R. Hilbert. Estimation of linear functionals on Sobolev spaces with application to Fourier transforms and spline interpolation. "SIAM J. Numer. Anal.", 7:112--124, 1970.
] under the assumption that extstyle Omega satisfies the
strong cone property ; that is, there exists a finite open covering extstyle left{ O_{i} ight} of extstyle partialOmega and corresponding cones extstyle {C_{i}} with vertices at the origin such that extstyle x+C_{i} is contained in extstyle Omega for any extstyle x extstyle 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 extstyle W_{p}^{m}(Omega)/P_{m-1} is equivalent to the extstyle W_{p}^{m}(Omega) seminorm. The extstyle W_{p}^{m}(Omega) norm is not the usual one but the terms are scaled with extstyle 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 extstyle Omega cannot be determined from the proof.
A constructive form
Then the lemma holds with the constant extstyle C=Cleft( m,n,gamma ight) , that is, the constant depends on the domain extstyle Omega only through its chunkiness extstyle gamma and the dimension of the space extstyle n. In addition, v can be chosen as v=Q^{m}u, where extstyle Q^{m}u is the averaged
Taylor polynomial , defined as:Q^{m}u=intlimits_{B}T_{y}^{m}uleft( x ight) psileft( y ight) dx,
where
:T_{y}^{m}uleft( x ight) =sumlimits_{k=0}^{m-1}sumlimits_{leftvert alpha ightvert =k}frac{1}{alpha!}D^{alpha}uleft( y ight) left( x-y ight) ^{alpha}
is the Taylor polynomial of degree at most extstyle m-1 of extstyle u centered at extstyle y evaluated at extstyle x, and extstyle psigeq0 is a function that has derivatives of all orders, equals to zero outside of extstyle B, and such that
:intlimits_{B}psi dx=1.
Such function extstyle psi always exists.
For more details and a tutorial treatment, see the monograph by Brenner and Scott Susanne C. Brenner and L. Ridgway Scott. "The mathematical theory of finite element methods", volume 15 of "Texts in Applied Mathematics". Springer-Verlag, New York, second edition, 2002. ISBN 0-387-95451-1
] . The result can be extended to the case when the domain extstyle 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
Philippe G. Ciarlet . "The finite element method for elliptic problems", volume 40 of "Classics in Applied Mathematics". Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. Reprint of the 1978 original [North-Holland, Amsterdam] . ISBN 0-89871-514-8] . It is essentially Theorem 2 from .
Lemma Suppose that extstyle ell is a
continuous linear functional on extstyle W_{p}^{m}(Omega) and extstyle leftVert ell ightVert _{W_{p}^{m}(Omega )^{^{prime} itsdual norm . Suppose that extstyle ellleft( v ight) =0 for all extstyle vin P_{m-1}. Then there exists a constant extstyle C=Cleft( Omega ight) such that:leftvert ellleft( u ight) ightvert leq CleftVert ell ightVert _{W_{p}^{m}(Omega)^{^{prime}leftvert u ightvert _{W_{p}^{m}(Omega)}.
References
External links
*
* http://aps.arxiv.org/abs/0710.5148 - Jan Mandel: The Bramble-Hilbert Lemma
Wikimedia Foundation. 2010.