# Error-constant estimation under the maximum norm for linear Lagrange interpolation – Journal of Inequalities and Applications

#### ByShirley Mae Galindo, Koichiro Ike and Xuefeng Liu

Aug 13, 2022

In the previous section, we obtained explicit bounds for the interpolation constant for triangles of general shape. Basically, such bounds from theoretical analysis only provide a raw bound for the objective constant. In this section, we propose a numerical algorithm to obtain the optimal estimation of the constant (C^{L}(K)) for specific triangles.

Let us define the space (V^{L}(K):= {u in H^{2}(K) mid u(p_{i}) = 0 (i = 1,2,3) }). Let (mathcal{T}^{h}) be a triangulation of the domain K and define the space

begin{aligned} V^{{F M}}_{h}(K):={}& biggl{ v mid v vert _{K_{h}} in P_{2}(K_{h}), forall {K_{h}} in mathcal{T}^{h}; v(p_{i}) = 0 (i = 1,2,3); v mbox{ is continuous} \ &mbox{at the nodes; } { int _{e} biggl(frac{partial v}{partial overrightarrow{n}} bigg|_{K_{h}} – frac{partial v}{partial overrightarrow{n}} bigg|_{K_{h}’} biggr) ,mathrm{d}s = 0 mbox{ for each } e = K_{h} cap K_{h’} } biggr} . end{aligned}

For (u_{h}, v_{h} in V^{{F M}}_{h}(K)), define the discretized (H^{2})-inner product and seminorm by

begin{aligned} langle u_{h}, v_{h} rangle _{h}:= sum _{{K_{h}} in mathcal{T}^{h}} int _{{K_{h}}} D^{2}{u_{h}|_{K_{h}}} cdot D^{2} {v_{h}|_{K_{h}}} ,mathrm{d} {K_{h}},quad lvert u_{h} rvert _{2,K}:= sqrt{ langle u_{h}, u_{h} rangle _{h}} . end{aligned}

Let us define the two quantities over the triangle K:

begin{aligned} lambda (K):= inf_{u in V^{L}(K)} frac{ lvert u rvert _{2,K}^{2}}{ lVert u rVert _{infty,K}^{2}},qquad lambda _{h}(K):= min_{u_{h} in V_{h}^{{F M}}(K)} frac{ lvert u_{h} rvert _{2,K}^{2}}{ lVert u_{h} rVert _{infty,K}^{2}}. end{aligned}

(8)

Note that (C^{L}(K) = sqrt{lambda (K)}^{-1}) holds. In Theorem 3.1, we describe the algorithm to bound λ by using (lambda _{h}).

Given (u in H^{2}(K)), the Fujino–Morley interpolation (Pi ^{{F M}}_{h} u) is a function satisfying

begin{aligned} Pi ^{{F M}}_{h} u in V^{{F M}}_{h}(K);qquad Pi ^{{F M}}_{h} u |_{{K_{h}}} in P_{2}(K_{h}),quad forall {K_{h}} in mathcal{T}^{h}, end{aligned}

and at the vertices (p_{i}) and edges (e_{i}) of K,

begin{aligned} bigl(u – Pi ^{{F M}}_{h} ubigr) (p_{i}) = 0,qquad int _{e_{i}} frac{partial}{partial n}bigl(u – Pi ^{{F M}}_{h} ubigr) ,mathrm{d}s = 0quad (i = 1,2,3). end{aligned}

The Fujino–Morley interpolation has the property that (see, e.g., [4, 5])

begin{aligned} bigllangle u – Pi ^{{F M}}_{h} u, v_{h} bigrrangle _{h} = 0, quadforall v_{h} in V^{{F M}}_{h}(K). end{aligned}

(9)

Let (V(h):= {u + u_{h} mid u in V^{L}(K), u_{h} in V^{ {F M}}_{h}(K) }). Thus, it is easy to see that the Fujino–Morley interpolation is just the projection (P_{h}: V(h)to V^{{F M}}_{h}(K)) with respect to the inner product (langle cdot, cdot rangle _{h}).

Below, let us introduce the theorem that provides an explicit lower bound of λ. Such a result is inspired by the idea of [17] for the lower bounds of eigenvalue problems.

Let (C_{h}^{{F M}}) be a quantity that makes the following inequality hold.

begin{aligned} bigllVert u – Pi ^{{scriptsize F M}}_{h} u bigrrVert _{ infty,K} le C^{{F M}}_{h} bigllvert u – Pi ^{{scriptsize F M}}_{h} u bigrrvert _{2,K},quad forall u in V^{L}(K). end{aligned}

(10)

The existence of (C_{h}^{{F M}}) is confirmed by the argument in Sect. 3.1.

### Theorem 3.1

With the quantity (C_{h}^{{F M}}), we have a lower bound of (lambda (K)) as follows:

begin{aligned} lambda (K) ge frac{lambda _{h}}{1+(C_{h}^{{F M}})^{2}lambda _{h}} . end{aligned}

(11)

### Proof

For any (u in V^{L}(K)), noting that (lvert Pi ^{{scriptsize F M}}_{h} u rvert _{2,K} ge sqrt{lambda _{h}} lVert Pi ^{{scriptsize F M}}_{h} u rVert _{infty,K}) and applying the inequality (10), we have

begin{aligned} lVert u rVert _{infty,K}& = bigllVert Pi _{h}^{{ scriptsize F M}}u + u-Pi _{h}^{{scriptsize F M}}u bigrrVert _{ infty,K} \ & le bigllVert Pi _{h}^{{scriptsize F M}}u bigrrVert _{ infty,K} + bigllVert u-Pi _{h}^{{scriptsize F M}}u bigrrVert _{infty,K} \ & le frac{ lvert Pi _{h}^{{scriptsize F M}}u rvert _{2,K}}{sqrt{lambda _{h}}} + C_{h}^{{F M}} bigllvert u-Pi _{h}^{{scriptsize F M}}u bigrrvert _{2,K} \ & le sqrt{frac{1}{lambda _{h}} + bigl(C_{h}^{{F M}} bigr)^{2}} sqrt{ bigllvert Pi _{h}^{{scriptsize F M}}u bigrrvert ^{2}_{2,K} + bigllvert u-Pi _{h}^{{scriptsize F M}}u bigrrvert ^{2}_{2,K}} . end{aligned}

From the orthogonality in (9), we have

begin{aligned} bigllvert Pi _{h}^{{scriptsize F M}}u bigrrvert ^{2}_{2,K} + bigllvert u-Pi _{h}^{{scriptsize F M}}u bigrrvert ^{2}_{2,K} = lvert u rvert _{2,K}^{2}. end{aligned}

Thus,

begin{aligned} lVert u rVert _{infty,K} le sqrt{ frac{1+(C_{h}^{{F M}})^{2}lambda _{h}}{lambda _{h}}} lvert u rvert _{2,K}, quad forall u in V^{L}(K). end{aligned}

From the definition of λ in (8), we draw the conclusion. □

To apply Theorem 3.1 for bounding λ, an explicit value of (C_{h}^{{F M}}) is needed. Below, let us describe the way to obtain this explicit value by utilizing the raw bound of (C^{L}(alpha,theta )).

### Explicit estimation of (C^{{F M}}_{h})

To have an explicit value of (C^{{F M}}_{h}), we first define the quantity (C^{{F M}}_{mathrm{res}}({K_{h}})) for each element ({K_{h}}) in the triangulation (mathcal{T}^{h}):

begin{aligned} C^{{F M}}_{mathrm{res}}({K_{h}}):= sup _{u in H^{2}( {K_{h}})} frac{ lVert u-Pi _{h}^{{scriptsize F M}}u rVert _{infty, {K_{h}}}}{ lvert u-Pi _{h}^{{scriptsize F M}}u rvert _{2,{K_{h}}}} = sup_{w in W_{1}} frac{ lVert w rVert _{infty, {K_{h}}}}{ lvert w rvert _{2,{K_{h}}}}. end{aligned}

Here, (W_{1}:= {w in H^{2}({K_{h}}) mid w(p_{i}) = 0, int _{e_{i}} frac{partial w}{partial n },mathrm{d}s = 0 (i = 1,2,3) }). Noting that (W_{1} subseteq W_{2}) for (W_{2}:= { w in H^{2}({K_{h}}) mid w(p_{i}) = 0 (i=1,2,3) }), from the definition of (C^{L}) in (3), we have

begin{aligned} C^{{F M}}_{mathrm{res}}({K_{h}}) le sup _{w in W_{2}} frac{ lVert w rVert _{infty, {K_{h}}}}{ lvert w rvert _{2,{K_{h}}}} = C^{L}( {K_{h}}). end{aligned}

Then, the following (C^{{F M}}_{h}) with an upper bound makes certain (10) holds:

begin{aligned} C^{{F M}}_{h}:= max_{{K_{h}} in mathcal{T}^{h}} C^{ {F M}}_{mathrm{res}}({K_{h}}) Bigl( le max _{{K_{h}} in mathcal{T}^{h}} C^{L}({K_{h}}) Bigr). end{aligned}

(12)

### Remark 3.1

Let (mathcal{T}^{h}) be a uniform triangulation of a right isosceles triangle; see a sample mesh in Fig. 8. We choose an explicit upper bound of (C^{{F M}}_{h} ) as (C^{{F M}}_{h} le 1.3712h), since for each ({K_{h}} in mathcal{T}^{h}), (C^{{F M}}_{mathrm{res}} le C^{L}({K_{h}}) le 1.3712h), where h is the leg length of each right triangle element.

### Estimation of (lambda _{h}) by solving the finite-dimensional optimization problem

In this subsection, we present a method to estimate (lambda _{h}), which is required in Theorem 3.1 for bounding λ. Let (M:= operatorname{Dim}(V^{{F M}}_{h})). The estimation of (lambda _{h}) is equivalent to finding the solution to the optimization problem

begin{aligned} lambda _{h} =operatorname{min} mathbf{x}^{T} mathbf{A} mathbf{x}, quadmbox{subject to}quad BiggllVert sum _{i=1}^{M} mathbf{x}_{i} phi _{i} BiggrrVert _{infty,K} ge 1 , end{aligned}

(13)

where the components (a_{ij}) of A are given by (a_{ij} = langle phi _{i}, phi _{j} rangle _{h}), ({phi _{i} }_{i=1,ldots,M}) are the basis functions for the Fujino–Morley space (V^{{F M}}_{h}), and

$\mathbf{x}\in {}^{}$
R
M

denotes the Fujino–Morley coefficient vector of (u_{h} in V^{{F M}}_{h}).

To solve the optimization problem (13) is not an easy task since the (L^{infty})-norm of the function appears in the constraint. Here, we introduce the technique to apply Bernstein polynomials and their convex-hull property to solve the problem. Strictly speaking, a new optimization problem (14) utilizing the Bernstein polynomials will be formulated to provide a lower bound for the solution of (13).

As preparation, let us introduce the definition of Bernstein polynomials along with the convex-hull property; refer to, e.g., [18, 19] for detailed discussion.

### Convex-hull property of Bernstein polynomials

Given a triangle K, let ((u,v,w)) be the barycentric coordinates for a point x in K. A Bernstein polynomial p of degree n over a triangle K is defined by

begin{aligned} {p}:= sum_{i+j+k = n} d_{i,j,k} J^{(n)}_{i,j,k},qquad J^{(n)}_{i,j,k}(x) := frac{n!}{i!j!k!} u^{i} v^{j} w^{k}. end{aligned}

Here, (J^{(n)}_{i,j,k}(x)) are the Bernstein basis polynomials; the coefficients (d_{i,j,k}) are the control points of p. Noting that

begin{aligned} J^{(n)}_{i,j,k}ge 0, qquadsum_{i+j+k = n} J^{(n)}_{i,j,k}=1, end{aligned}

we can easily obtain the following convex-hull property of Bernstein polynomials:

begin{aligned} lVert{p} rVert _{infty,K} le max lvert d_{i,j,k} rvert. end{aligned}

Given (u_{h} in V^{{F M}}_{h}(K)), for each ({K_{h}} in mathcal{T}^{h}), (u_{h}|_{{K_{h}}} in P_{2}({K_{h}})) can be represented by the Bernstein basis polynomials of degree two. Let B be the (N times M) matrix that transforms the Fujino–Morley coefficients x to the Bernstein coefficients (d^{B}). Note that (u_{h}) is regarded as a piecewise Bernstein polynomial so that its Bernstein coefficient vector (d^{B}) has the dimension (N=6times # {elements}). The dimension of (d^{B}) can be further reduced considering the continuity of (u_{h}) at the vertices of the triangulation. However, it is difficult to utilize the constraints of (u_{h}) that cross the edges to reduce the dimension N. From the convex-hull property of the Bernstein polynomials, the following inequality holds:

begin{aligned} 1 le BiggllVert sum_{i=1}^{M} mathbf{x}_{i} phi _{i} BiggrrVert _{infty,K} le lVert mathbf{Bx} rVert _{ infty}. end{aligned}

Based on this inequality, we propose a new optimization by relaxing the constraint condition of (13):

begin{aligned} lambda _{h,B} = operatorname{min} mathbf{x}^{T} mathbf{Ax}, quadmbox{subject to}quad lVert mathbf{Bx} rVert _{infty} ge 1. end{aligned}

(14)

The solution to problem (14) provides a lower bound for (13), i.e., (lambda _{h} ge lambda _{h,B}).

Below, we propose an algorithm to solve the problem (14). Since A is positive-definite, let us consider the Cholesky decomposition of A: (mathbf{A} = mathbf{R}^{T}mathbf{R}), where R is an (Mtimes M) upper triangular matrix. Then, by letting (mathbf{y}:= mathbf{Rx}) and (mathbf{widehat{B}}:= mathbf{BR}^{-1}), problem (14) becomes

begin{aligned} lambda _{h,B}=operatorname{min} mathbf{y}^{T} mathbf{y},quad mbox{subject to}quad lVert widehat{mathbf{B}} mathbf{y} rVert _{infty} ge 1. end{aligned}

(15)

The following lemma shows the solution for problem (15).

### Lemma 3.1

Let ({b^{T}_{i}}) ((i=1,ldots,N)) be the ith row of (widehat{mathbf{B}}) and (b^{T}_{mathrm{max}}) be a row of (widehat{mathbf{B}}) satisfying (lVert b_{mathrm{max}} rVert _{2} = max_{i=1,ldots,N} lVert b_{i} rVert _{2}). Then, the optimal value of problem (15) is given byFootnote 1

begin{aligned} lambda _{h,B} =frac{1}{ lVert b_{mathrm{max}} rVert _{2}^{2}}. end{aligned}

### Proof

Let (S:= {mathbf{y} mid lVert widehat{mathbf{B}} mathbf{y} rVert _{infty }ge 1 }) and (bar{mathbf{y}}:= lVert b_{mathrm{max}} rVert _{2}^{-2}b_{mathrm{max}}). Then, we have (bar{mathbf{y}}in S) because

begin{aligned} lVert widehat{mathbf{B}}bar{mathbf{y}} rVert _{ infty }= max _{i=1,ldots,N} bigllvert {b^{T}_{i}} bar{ mathbf{y}} bigrrvert ge bigllvert {b^{T}_{mathrm{max}}} bar{ mathbf{y}} bigrrvert = 1. end{aligned}

Hence,

begin{aligned} min_{mathbf{y}in S} mathbf{y}^{T}mathbf{y} le bar{mathbf{y}}^{T} bar{mathbf{y}} = frac{1}{ lVert b_{mathrm{max}} rVert _{2}^{2}}. end{aligned}

(16)

For any (mathbf{y} in S), from the Cauchy–Schwarz inequality,

begin{aligned} 1 le max_{i=1,ldots,N} bigllvert {b_{i}}^{T} mathbf{y} bigrrvert le max_{i=1,ldots,N} lVert b_{i} rVert _{2} lVert mathbf{y} rVert _{2} = lVert b_{mathrm{max}} rVert _{2} lVert mathbf{y} rVert _{2}. end{aligned}

Thus,

begin{aligned} frac{1}{ lVert b_{mathrm{max}} rVert _{2}^{2}} le min_{ mathbf{y}in S} mathbf{y}^{T}mathbf{y}. end{aligned}

(17)

From (16) and (17), we draw the conclusion. □

Note that the diagonal elements of (mathbf{B}mathbf{A}^{-1}mathbf{B}^{T}=widehat{mathbf{B}} widehat{mathbf{B}}^{T}) correspond to (|b_{i}|_{2}^{2}) ((i=1, ldots, N)). Therefore, we can solve problem (14) without performing the Cholesky decomposition of A, as shown by the following lemma.

### Lemma 3.2

Let (mathbf{D}:=mathbf{B} mathbf{A}^{-1}mathbf{B}^{T}). The optimal value of (14) is given by

begin{aligned} lambda _{h,B}=frac{1}{max (mathrm{diag}(mathbf{D}))}, end{aligned}

where (mathrm{diag}(mathbf{D})) is the diagonal elements of D.

Theorem 3.1 gives a lower bound for λ. Since (C^{L}(K) = sqrt{lambda (K)}^{-1}), this lower bound is used to obtain an upper bound for (C^{L}(K)). Below, let us summarize the procedure to obtain a lower bound for λ.

Algorithm for calculating the lower bound of
(lambda (K))

1. a.

Set up the FEM space (V^{{F M}}_{h}(K)=operatorname{span}{phi _{i}}_{i=1}^{M}) over a triangulation of the triangle domain K.

2. b.

Assemble the global matrix (mathbf{A} = ( a_{ij} )_{M times M}) ((a_{ij} = langle phi _{i}, phi _{j} rangle _{h})) and the transformation matrix B from Fujino–Morley coefficients to Bernstein coefficients.

3. c.

Apply Lemma 2.3 to obtain a raw bound for (C^{{F M}}_{h}).

4. d.

Apply Lemma 3.1 or Lemma 3.2 to calculate (lambda _{h,B} (le lambda _{h})).

5. e.

The lower bound for λ is obtained through Theorem 3.1 by using (lambda _{h,B}) and the upper bound of (C^{{F M}}_{h}).

Using uniform triangulation of a domain K, a direct estimation of the lower bound for λ without using (C^{{F M}}_{h}) is available.

### Corollary 3.1

For a uniform triangulation of (K=K_{alpha,theta,h}) with N subdivisions for each side, the following holds:

begin{aligned} lambda (K) ge lambda _{h}bigl(1-(1/N)^{2} bigr). end{aligned}

(18)

### Proof

Since ((C^{L}(K))^{2} = 1/lambda (K)) and each ({K_{h}} in mathcal{T}^{h}) is similar to K, we have,

begin{aligned} lambda (K) ge frac{lambda _{h}}{1+ (C_{h}^{{F M}})^{2} lambda _{h} } ge frac{lambda _{h}}{1+(C^{L}({K_{h}}))^{2} lambda _{h} } = frac{lambda _{h}}{ 1 + (1/N)^{2} lambda _{h}/lambda (K)}. end{aligned}

The conclusion is achieved by sorting the inequality. □

### Remark 3.2

Theoretically, for a refined uniform triangulation, the lower bound (11) using (C_{h}^{{F M}}) is sharper (i.e., larger) than (18). This can be confirmed by utilizing the following relation:

begin{aligned} frac{lambda _{h}}{1+ (C_{h}^{{F M}})^{2} lambda _{h} } ge lambda _{h} bigl(1-(1/N)^{2}bigr) quadiffquad 1 ge bigl(N^{2}-1bigr) bigl(C_{h}^{{F M}}bigr)^{2} lambda _{h}. end{aligned}

(19)

For a small value of (h=1/N), we have

begin{aligned} bigl(N^{2}-1bigr) bigl(C_{h}^{{F M}} bigr)^{2} approx bigl(N C_{h}^{{F M}} bigr)^{2} = bigl(C_{mathrm{res}}^{ {F M}}( {K_{h}})bigr)^{2}, lambda _{h}approx lambda =bigl(C^{L}( {K_{h}})bigr)^{-2}. end{aligned}

Thus, the second equality of (19) holds due to (C_{mathrm{res}}^{{F M}}({K_{h}}) < C^{L}({K_{h}})). However, in practical computation, the raw estimate of (C_{mathrm{res}}^{{F M}}({K_{h}})) will produce a worse bound of λ than (18).

Using Corollary 3.1, the following steps are modified from the algorithm to obtain a lower bound for λ, without using the quantity of (C_{h}^{{F M}}):

Revision of algorithm for calculating the lower bound of
(lambda (K))

1. c*.

Apply Lemma 3.1 or Lemma 3.2 to calculate (lambda _{h,B} (le lambda _{h})).

2. d*.

Solve the lower bound for λ using Corollary 3.1 along with (lambda _{h,B}).

### Remark 3.3

To compare the efficiencies of the two formulas (11) and (18), we apply them to estimate λ for a unit right isosceles (K_{1,pi /2}). By using uniform triangulation of size (h=1/64), the estimate (11) gives (lambda ge 5.7659) and (18) gives a sharper bound as (lambda ge 5.7798). Hence, a sharper upper bound is obtained using (18) and we have the following estimation:

begin{aligned} bigllVert u-Pi ^{L} u bigrrVert _{infty,K_{1,pi /2,h}} le 0.41596 h lvert u rvert _{2,K_{1,pi /2,h}}. end{aligned}

As a comparison, the result (5) will yield a raw bound as (C^{L}(1,pi /2,h) le 1.3712h).

For a triangle (K_{alpha,theta}) with two fixed vertices (p_{1}(0,0), p_{2}(1,0)), let us vary the vertex (p_{3}(x, y)) and calculate the approximate value of (C^{L}(alpha,theta )) for each position of (p_{3}). Note that (C^{L}) can be regarded as a function with respect to the coordinate ((x,y)) of (p_{3}), which is denoted by (C^{L}(x,y)). In Fig. 9, we draw the contour lines of (C^{L}(x,y)), where the abscissa and the ordinate denote x– and y– coordinates of (p_{3}), respectively.

### Lower bound of the constant

To confirm the precision of the obtained estimation for the Lagrange interpolation constant, the lower bounds of the constants are calculated. Let (u_{h}) be the function obtained by numerical computation solving the minimization problem. To obtain the lower bound, an appropriate polynomial f over K of higher degree d is selected by solving the minimization problem below:

begin{aligned} min_{f in P_{d}(K)} sum_{i=1}^{n} bigllvert f(p_{i}) – u_{h}(p_{i}) bigrrvert ^{2} quadbigl(n: # {mbox{nodes of triangulation}} bigr), end{aligned}

where (p_{i}) denote the nodes of the triangulation of K. From the definition of (lambda (K)) in (8) and the relation (C^{L}(K)=1/sqrt{lambda (K)}), we have a lower bound of (C^{L}(K)) as follows:

begin{aligned} C^{L}(K) ge frac{ lVert f rVert _{infty,K}}{ lvert f rvert _{2,K}}. end{aligned}

### Remark 3.4

For the unit right isosceles triangle (K_{1, pi /2}), the upper bound for the constant is obtained by solving the optimization problem with mesh size (1/64). Meanwhile, the lower bound of the constant is obtained by using a polynomial of degree 9. The two side bounds read:

begin{aligned} 0.40432 le C^{L} biggl(1,frac{pi}{2} biggr) le 0.41596. end{aligned}