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.

Figure 8
figure 8

A uniform triangulation of a right isosceles triangle

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

x
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.

Figure 9
figure 9

Contour lines of (C^{L}(alpha,theta )) w.r.t. vertex (p_{3}(x,y))

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}$$

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Disclaimer:

This article is autogenerated using RSS feeds and has not been created or edited by OA JF.

Click here for Source link (https://www.springeropen.com/)