Bramble–Hilbert lemma
In mathematics, particularly numerical analysis, the Bramble–Hilbert lemma, named after James H. Bramble and Stephen Hilbert, bounds the error of an approximation of a function formula_1 by a polynomial of order at most formula_2 in terms of derivatives of formula_1 of order formula_4. Both the error of the approximation and the derivatives of formula_1 are measured by formula_6 norms on a bounded domain in formula_7. This is similar to classical numerical analysis, where, for example, the error of linear interpolation formula_1 can be bounded using the second derivative of formula_1. However, the Bramble–Hilbert lemma applies  in any number of dimensions, not just one dimension, and the approximation error and the derivatives of formula_1 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 formula_1 by an operator that preserves polynomials of order up to formula_2, in terms of the derivatives of formula_1 of order formula_4. 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 (or, in some superconvergence results, a small number of elements). 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 formula_1 that has formula_4 derivatives on interval  formula_17, the lemma reduces to where formula_19 is the space of all polynomials of degree at most formula_2 and formula_21 indicates the formula_22th derivative of a function formula_23. In the case when formula_24, formula_25, formula_26, and formula_1 is twice differentiable, this means that there exists a polynomial formula_28 of degree one such that for all formula_29, This inequality also follows from the well-known error estimate for linear interpolation by choosing formula_28 as the linear interpolant of formula_1. Statement of the lemma. Suppose formula_33 is a bounded domain in formula_34, formula_35, with boundary formula_36 and diameter formula_37. formula_38 is the  Sobolev space of all function formula_1 on formula_33 with weak derivatives formula_41 of order formula_42 up to formula_43 in formula_44. Here, formula_45 is a multiindex, formula_46 formula_47 and formula_48 denotes the derivative formula_49 times with respect to formula_50, formula_51 times with respect to formula_52, and so on. The Sobolev seminorm on formula_53 consists of the formula_54 norms of the highest order derivatives, and formula_57 is the space of all polynomials of order up to formula_43 on formula_34. Note that formula_60 for all formula_61 and formula_62, so formula_63 has the same value for any formula_61. Lemma (Bramble and Hilbert) Under additional  assumptions on the domain formula_33, specified below, there exists a constant formula_66 independent of formula_67 and formula_1 such that for any formula_69 there exists a polynomial formula_61 such that for all formula_71 The original result. The lemma was proved by Bramble and Hilbert under the assumption that formula_33 satisfies the strong cone property; that is, there exists a finite open covering formula_74 of formula_36 and corresponding cones formula_76 with vertices at the origin such that formula_77 is contained in formula_33 for any formula_79 formula_80. 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 formula_81 is equivalent to the formula_82 seminorm. The formula_82 norm is not the usual one but the terms are scaled with formula_37 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 formula_33 cannot be determined from the proof. A constructive form. An alternative result was given by Dupont and Scott  under the assumption that the domain formula_33 is star-shaped; that is, there exists a ball formula_87 such that for any formula_88, the closed convex hull of formula_89 is a subset of formula_33. Suppose that formula_91 is the supremum of the diameters of such balls. The ratio formula_92 is called the chunkiness of formula_33. Then the lemma holds with the constant formula_94, that is, the constant depends on the domain formula_33 only through its chunkiness formula_96 and the dimension of the space formula_97. In addition, formula_98 can be chosen as formula_99, where formula_100 is the averaged Taylor polynomial, defined as  where is the Taylor polynomial of degree at most formula_2 of formula_1 centered at formula_105 evaluated at formula_79, and formula_107 is a function that has derivatives of all orders, equals to zero outside of formula_87, and such that Such function formula_110 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 formula_33 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 formula_112 is a continuous linear functional on formula_82 and formula_114 its dual norm. Suppose that formula_115 for all formula_61. Then there exists a constant formula_117 such that