Bramble-Hilbert lemma

Hilbert–Bramble lemma

An abstract theoretical tool for studying the approximation error of functions in Sobolev spaces (cf. also Approximation of functions; Sobolev space) by algebraic polynomials. The general formulation of the lemma was given and proven first by J.H. Bramble and S.R. Hilbert [a1] in terms of a class of linear functionals on Sobolev spaces that annihilate the set of polynomials (see the definition below), an intermediate to (polynomials of degree ) and , i.e. . This formulation was motivated by the work of G. Birkhoff, M. Schultz and R.S. Varga [a3] and applied to estimate the error of the Hermite interpolation formula [a1], spline interpolation and Fourier transformation (cf. Fourier transform) [a2].

The Bramble–Hilbert lemma has a wide range of applications. It is used in the analysis of projection operators in the function spaces and for designing optimal domain decomposition and multi-level methods. Its application to the -error of the finite element approximations of elliptic problems of second order leads to sharp estimates with respect to both the regularity of the solution and rate of convergence. It is an indispensible tool in the error analysis of finite element [a4], [a5], finite volume [a8], finite difference [a9], collocation, and boundary element methods for solving partial differential equations. The complete error analysis of the finite difference and finite volume schemes in [a9] is based on the Bramble–Hilbert lemma.

To formulate the lemma, some notation regarding Sobolev spaces of real-valued functions on a bounded domain in -dimensional Euclidean space is needed. It is assumed that satisfies the strong cone condition (cf. Cone condition) and has diameter . The boundary of is denoted by .

The notations , and will be used for multi-indices, with and , where . Let be the set of all functions such that exists and is finite. The norm in is given by . Let be the set of all functions in whose distributional derivatives of order less than equal to (a non-negative integer) are in . It will be assumed that . The norm and the semi-norm on are, respectively,

Let be any subset of the set of multi-indices of length (i.e. ) which contains the indices of the form , for , . The set of polynomials such that for all will be denoted by . Obviously, .

The Bramble–Hilbert lemma ([a1]) is as follows: Let be a bounded linear functional on that vanishes for polynomials in , i.e.

1) , where the constant is independent of and the function ;

2) for . Then there is a constant , independent of and , such that

Note that the lemma deals with function spaces of many variables. For functions in a single variable, the inequality derived by the lemma follows immediately from the Peano kernel theorem for the remainder of the Taylor expansion (see, e.g., [a10]).

In many applications, a given domain is split into a number of non-overlapping subdomains , usually triangles, rectangles, tetrahedra, hexahedra, etc., so that is small. Consider the error of the Lagrange interpolation formula for a function with polynomials of degree over each and take . Here, the domains are non-degenerate simplices in , , , and . Assume that and and let be a piecewise polynomial of degree which interpolates the values of the function at the vertices of each simplex . Consider the linear functional at a fixed point . By the Sobolev imbedding theorem (cf. also Imbedding theorems),

Therefore is bounded in . Obviously, if is a polynomial of degree , since the linear interpolant recovers exactly. Therefore, by the Bramble–Hilbert lemma: . An estimate of the -error for the interpolant over follows immediately after taking this inequality to power and integrating it over . The estimate for the error in the whole domain follows by summing all local estimates, taking the maximal , and using the additivity of the integrals:

If tends to , this estimate gives the rate at which the piecewise-linear interpolant converges to in the -norm. Similarly, one can obtain bounds for the -norm of the first derivatives. This is a typical application of the Bramble–Hilbert lemma in constructive function theory and in numerical methods for differential equations.

The original proof of the lemma was abstract and the size of the constant could not be estimated. This was the reason that T. Dupont and L.R. Scott [a7] gave a new constructive proof of the main result.

Consider the polynomial which is an averaged Taylor polynomial of degree over (for the exact construction, see [a4], Chap. 4). This construction of is related to the polynomials used by S.L. Sobolev [a11] to study the spaces that bear his name. Here, is considered to be a star-shaped domain with respect to a ball , that is, for all , the closed convex hull of is a subset of , and one defines

The revised Bramble–Hilbert lemma now reads ([a4], p. 100): Let be a star-shaped domain with respect to the ball . Then

Here, is the quotient of and the diameter , and the constant does not depend on while its dependence on and is estimated explicitly from above.

This variant of the lemma was proved by Dupont and Scott [a7] for non-integer and for domains that are finite unions of domains that are star-shaped with respect to a ball, while more general results were established in [a6].

References

[a1]	J.H. Bramble, S.R. Hilbert, "Bounds for a class of linear functionals with applications to Hermite interpolation" Numer. Math. , 16 (1971) pp. 362–369
[a2]	J.H. Bramble, S.R. Hilbert, "Estimation of linear functionals on Sobolev spaces with application to Fourier transforms and spline interpolation" SIAM J. Numer. Anal. , 7 (1970) pp. 112–124
[a3]	G. Birkhoff, M. Schultz, R. Varga, "Hermite interpolation in one and two variables with application to partial differential equations" Numer. Math. , 11 (1968) pp. 232–256
[a4]	S.C. Brenner, L.R. Scott, "The mathematical theory of finite element methods" , Springer (1994)
[a5]	P.G. Ciarlet, "The finite element method for elliptic problems" , North-Holland (1978)
[a6]	L.T. Dechevski, E. Quak, "On the Bramble–Hilbert lemma" Numer. Funct. Anal. Optim. , 11 (1990) pp. 485–495
[a7]	T. Dupont, L.R. Scott, "Polynomial approximation of functionals in Sobolev spaces" Math. Comput. , 34 (1979) pp. 441–463
[a8]	R. Li, Z. Chen, W. Wu, "Generalized difference methods for differential equations. Numerical analysis of finite volume methods" , M. Dekker (2000)
[a9]	A.A. Samarskii, R.D. Lazarov, V.L. Makarov, "Finite difference schemes for differential equations having generalized solutions" , Visshaya Shkola Publ., Moscow (1987) (In Russian)
[a10]	A. Sard, "Linear approximation" , Math. Surveys , 9 , Amer. Math. Soc. (1963)
[a11]	S.L. Sobolev, "Applications of the functional analysis in mathematical physics" , Amer. Math. Soc. (1963) (In Russian)