Bramble-Hilbert lemma

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 extstyle u by a polynomial 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 a bounded domain in extstyle mathbb{R}^{n}. This is similar to classical numerical analysis, where, for example, the error of linear 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 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 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 the Sobolev space of all function extstyle u on extstyle Omega with weak derivatives 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 a multiindex, 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

An alternative result was given by Dupont and Scott Todd Dupont and Ridgway Scott. Polynomial approximation of functions in Sobolev spaces. "Math. Comp.", 34(150):441--463, 1980.] under the assumption that the domain extstyle Omega is star-shaped; that is, there exists a ball extstyle B such that for any extstyle xinOmega, the closed convex hull of extstyle left{ x ight} cup B is a subset of extstyle Omega. Suppose that extstyle ho _{max} is the supremum of the diameters of such balls. The ratio extstyle gamma=d/ ho_{max} is called the chunkiness of extstyle Omega.

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} its dual 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.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Bramble-Hilbert-Lemma — In der Mathematik, besonders in der numerischen Analysis, schätzt das Bramble Hilbert Lemma, benannt nach James H. Bramble und Stephen R. Hilbert, den Fehler bei Approximation einer Funktion u durch ein Polynom der maximalen Ordnung m − 1 mit… …   Deutsch Wikipedia

  • Bramble — ist der Familienname folgender Personen: Livingstone Bramble (* 1960), Boxer aus St. Kitts und Nevis Titus Bramble (* 1981), englischer Fußballspieler Sonstiges: Bramble (Indiana), Ort in den Vereinigten Staaten Bramble Cay, nördlichste Insel… …   Deutsch Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of lemmas — This following is a list of lemmas (or, lemmata , i.e. minor theorems, or sometimes intermediate technical results factored out of proofs). See also list of axioms, list of theorems and list of conjectures. 0 to 9 *0/1 Sorting Lemma ( comparison… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”