# Local Lagrange Interpolations Using BivariateC2 Splines of Degree Seven on Triangulated Quadrangulations

Authors: Xuqiong Luo; Qikui Du
Journal: Journal of Mathematics
 (2013)

---

## Abstract

A local Lagrange interpolation scheme using bivariateC2 splines of degree seven over a checkerboard triangulated quadrangulation is constructed. The method provides optimal order approximation of smooth functions.


---

## Body

## 1. Introduction

Suppose thatΔ is a regular triangulation of a connected polygonal domain Ω. For integers 0≤r≤d, we define
(1)Sdr(Δ):={s∈Cr(Ω):s∣T∈Pd,∀T∈Δ},
where Pd is the ((d+2)(d+1))/2 dimensional space of bivariate polynomials of degree d. For integers r≤ρ≤d, we further define the following super spline space:
(2)Sdr,ρ(Δ):={s∈Cr(Ω):s∈Cρ(v),∀v∈Δ},
where, as usual, s∈Cρ(v) means that all polynomials on triangles sharing the vertex v have common derivatives up to order ρ at that vertex.We consider the following Lagrange interpolation problem.Problem 1.
Let𝒱:={ηi}i=1n be a set of points in the plane, and let ◊ be a quadrangulation with vertices at the points of V. Find a triangulation Δ of ◊ and a set of additional points {ηi}i=n+1N such that, for every choice of the data {zi}i=1N, there is a unique spline s∈𝒮 satisfying
(3)s(ηi)=zi,i=1,…,N.
We call𝒫:={ηi}i=1N a Lagrange interpolation set for 𝒮 and 𝒫 and 𝒮 a Lagrange interpolation pair. Although constructing Lagrange interpolation pairs sounds simple at first glance, it is in fact a complex problem, especially since we want a local and stable method which has linear complexity and provides optimal order approximation. In order to construct Lagrange interpolation pairs, both 𝒮 and 𝒫 must be carefully chosen.
Forr=1, the first result on local Lagrange interpolation by splines on triangulations was given by Nürnberger and Zeilfelder [1], where, by subdividing about half of the triangles with a Clough-Tocher split, a local Lagrange interpolation scheme for cubic C1 splines on triangulations whose interior vertices have degree six was developed. Nürnberger and Zeilfelder [2] constructed a local Lagrange interpolation set for S21(∆PS1), where ∆PS1 is the refining triangulation of Powell-Sabin type (I). Nürnberger and Zeilfelder [3] used a coloring algorithm to divide all the triangles in ∆ into two kinds: white triangles and black triangles, got a new triangulation ∆¯CT through refining all the white triangles by the Clough-Tocher refinement, and then gave a local Lagrange interpolation set for S31(∆¯CT). As to more results, the reader is referred to several survey papers [4–6].
Forr=2, Nürnberger et al. [7] constructed a local Lagrange interpolation set for S72(∆¯CT). Liu and Fan [8] constructed a local Lagrange interpolation set for S52,3(∆¯DCT), where ∆¯DCT is the triangulation by refining some of triangles in ∆ with the double Clough-Tocher splits.
For general casesr≥1, a local Lagrange interpolation of Sdr,ρ(∆¯CT) has been proposed by Nürnberger et al. in [9], where r, ρ, and d are taken as the following related values
(4)(ρ,d):={(3m+1,6m+3),r=2m+1,(3m,6m+1),r=2m,
with m=⌊r/2⌋.
Let◊ be a quadrangulation of Ω which consists of nondegenerate convex quadrilaterals. By adding one or two diagonals of each quadrilateral, some triangulated quadrangulations can be obtained. Nürnberger et al. [10] constructed a Lagrange interpolation scheme based on C1 cubic splines on certain triangulations obtained from checkerboard quadrangulations. In [11], they also constructed a local Lagrange interpolation method based on C1 cubic splines on certain triangulations obtained from a separable quadrangulation. Further they [12] described local Lagrange interpolation methods based on C1 cubic splines on triangulations obtained from arbitrary strictly convex quadrangulations by adding one or two diagonals. Their construction makes use of a fast algorithm for coloring quadrangulations, and the overall algorithm has linear complexity while providing optimal order approximation of smooth functions.
However, to the authors' knowledge, the local Lagrange interpolation schemes based onC2 splines on any triangulated quadrangulation have not been developed. In this paper, we shall construct a Lagrange interpolation scheme on S72,3() over the triangulation    obtained by adding the two diagonals of each quadrilateral from checkerboard quadrangulations.
The paper is organized as follows. In Section2 we introduce some notation and describe the Bernstein-Bézier representation of splines. In Section 3 we introduce the checkerboard triangulations. In Section 4 several lemmas of Lagrange minimal determining sets are established. In Section 5 the main results of construction of the Lagrange interpolation pair 𝒫,S72,3() and error bounds for the interpolating splines are presented.


## 2. Preliminaries

Throughout the paper we shall make extensive use of the well-known Bernstein-Bézier representation of splines. LetT:=〈v1,v2,v3〉 in Δ with vertices v1,v2,v3, and the corresponding polynomial piece s∣T is written in the form:
(5)s∣T=∑i+j+k=d‍cijkTBijkd,
where Bijkd are the Bernstein basis polynomials of degree d associated with T. As usual, we identify the Bernstein-Bézier coefficients {cijkT}i+j+k=d with the set of domain points DT:={ξijkT:=(iv1+jv2+kv3)/d}i+j+k=d. We write Dd,Δ for the union of the sets of domain points associated with the triangles of Δ.Given an integer0≤m≤d, let
(6)RmT(v1):={ξijkT:i=d-m},DmT(v1):={ξijkT:i≥d-m}.
We have similar definitions at the other vertices of T. If v is a vertex of a triangulation ∆, we, respectively, define that the ring and the disk of radius m around v are the set
(7)Rm(v):=⋃‍{RmT(v)},Dm(v):=⋃‍{DmT(v)},
where the union is taken over all triangles attached to v.We recall [13] that supposes that 𝒮 is a subspace of Sd0(Δ), and then 𝒫⊆Dd,Δ is said to be a determining set for 𝒮 that provides that, for any s∈𝒮,λξs=0 for all ξ∈𝒫 implies that s≡0. Note that λξ is a linear functional. The set 𝒫 is called a minimal determining set (MDS) for 𝒮 if there is no smaller determining set. Further, following [7], a basis {Bi}i=1n for a spline space 𝒮 is called a stable local basis provided that constants ℓ,K1, and K2 exist depending only on the smallest angle in ∆ such that(1)
for each1≤i≤n, there is a vertex vi of ∆ for which supp(Bi)⊆starℓ(vi),(2)
for all choices of the coefficient vectorc=(c1,…,cn),
(8)K1∥c∥∞≤∥∑i=1n‍ciBi∥∞≤K2∥c∥∞.Here star1(v) is defined to be the set of all triangles surrounding vertex v, and starℓ(v) is defined to be the union of the star1(w), where w are vertices of starℓ-1(v).It is well known that a splines in Sd0(Δ) is uniquely determined by its Bernstein-Bézier coefficient set {cξ}ξ∈Dd,Δ. In order to describe smoothness conditions for splines, we recall some notations introduced in [14]. Suppose that T:=〈v1,v2,v3〉 and T~:=〈v4,v3,v2〉 are two adjoining triangles from Δ, which share the oriented edge e:=〈v2,v3〉, and let
(9)s∣T=∑i+j+k=d‍cijkBijkd,s∣T~=∑i+j+k=d‍c~ijkB~ijkd,
where Bijkd and B~ijkd are the Bernstein polynomials of degree d on the triangles T and T~, respectively. Given integers 0≤n≤j≤d, let τj,en be linear functional defined on Sd0(Δ) by
(10)τj,ens:=cn,d-j,j-n-∑ν+μ+κ=n‍c~ν,μ+j-n,κ+d-jB~νμκn(v1).
These are called smoothness functionals of order n. According to [14], a spline s∈Sd0(Δ) belongs to Cr(T⋃‍T~) for some r>0 if and only if
(11)τm,en=0,n≤m≤d,0≤n≤r.


## 3. Checkerboard Triangulations

Definition 1 (see [10]).
Suppose that◊ is a quadrangulation consisting of quadrilaterals with largest interior angle less than π. Suppose that the quadrilaterals can be colored black and white in such a way that any two quadrilaterals sharing an edge have the opposite color. Then we call ◊ a checkerboard quadrangulation. The triangulation ∆ which is obtained by drawing in both diagonals of all quadrilaterals will be called a checkerboard triangulation.
Letℬ and 𝒲 denote the sets of black and white quadrilaterals of ◊, respectively. Following [10], throughout this paper, we also assume that all interior vertices of ◊ are of degree four. This assumption can ensure that there exists 𝒢⊂ℬ such that for every interior vertex ν of ◊, there is a unique quadrilateral Q∈ℬ sharing the vertex ν. For i=1,2,3,4, let 𝒲i be the set of white quadrilaterals which share i edges with black quadrilaterals. Let nB=#ℬ and ni:=#𝒲i for i=1,2,3,4, and let nV be the total number of vertices of ◊. As shown in Figure 1, a typical checkerboard triangulation is displayed in which the quadrilaterals in the set 𝒢 are shaded grey. It is noted that the other black quadrilaterals have not been colored.Figure 1
The set𝒢 for a checkerboard triangulation.


## 4. Lagrange Minimal Determining Sets

Lemma 2 (see [10]).
The set of all domain points in a triangleT is a Lagrange minimal determining set for the space Pd.LetQ:=〈v1,v2,v3,v4〉 be a quadrilateral with vertices in counterclockwise order and  be the triangulated quadrangulation of Q with vQ being the intersection point of the two diagonals of Q. As shown in Figure 2, let Ti:=〈vQ,vi,vi+1〉 and ei:=〈vi,vQ〉 for i=1,2,3,4, where v5=v1.Figure 2
The stable Lagrange MDSℳ for S72,3() produced by Lemma 3.Lemma 3.
The set(12)ℳ:=(⋃i=12‍D3T1(vi))⋃‍D3T1(vQ)⋃‍D3T2(v3)⋃‍D3T4(v4)⋃‍{ξ133T1,ξ232T1,ξ223T1,ξ331T1,ξ322T1,ξ313T1}⋃‍{ξ133T2,ξ223T2,ξ313T2,ξ403T2}⋃‍{ξ133T4,ξ232T4,ξ331T4,ξ430T4}⋃‍{ξ133T3}
is a stable Lagrange MDS for S72,3(). These domain points are marked with • in Figure 2.Proof.
Equivalently, we consider the related homogenous interpolation problem. By Lemma2, all Bernstein-Bézier coefficients of s∣T1 associated to 36 domain points in T1 must be zero. By the C2 smoothness conditions on the edge 〈vQ,v2〉 and the C3 smoothness conditions at vertex v2, all Bernstein-Bézier coefficients of s∣T2 must be zero except for 14 coefficients cijkT2 (k=4,5,6,7,i+j=7-k), c403T2, c313T2, c223T2 and c133T2. Let
(13)C:=(c007T2,c106T2,c016T2,c205T2,c115T2,c025T2,c304T2,c214T2,c124T2,c034T2,c403T2,c313T2,c223T2,c133T2)T,
then the homogenous Lagrange interpolation conditions at the associated 14 domain points lead to
(14)GC=0,
where(15)G=(100000000000006777667603×6576005×64760005×6376000677706676003×65760005×6476000057772×5676012×55760040×547600080×53760005777567656763×55766×55763×55765×547615×54765×54765×547620×537620×537630×537620×5376577702×56760012×557600040×5476000047773×4676027×457600135×4476000405×437600047772×4676467612×457612×45763×457640×447660×447630×44765×447680×4376160×4376160×437640×4376477746762×46763×457612×457612×45765×447630×447660×447640×44765×437640×437660×4376160×4376477703×46760027×4576000135×44760000377721×3676048×357600320×34760001280×337600037773×3676367627×357618×35763×3576135×347627×34769×34765×3476405×3376540×3376270×337660×337637772×36762×367612×357624×357612×357640×3476130×3476130×347640×347680×3376320×3376480×3376320×3376377736763×36763×357618×357627×35765×347645×3476135×3476135×34765×337660×3376270×3376540×3376).
It is easy to see thatrank(G)=14. Thus all the remaining 14 Bernstein-Bézier coefficients of s∣T2 are zero. Similarly, all the Bernstein-Bézier coefficients of s∣T4 must be also zero by smoothness conditions and given Lagrange interpolation conditions. Further, using C2 smoothness conditions along two edges 〈vQ,v3〉 and 〈vQ,v4〉 and C3 smoothness conditions at vertices v3 and v4, all Bernstein-Bézier coefficients of s∣T3 are zero except for c133T3. Using the interpolation condition at domain point ξ133T3: B1337c133T3=0, that is; c133T3=0 since B1337=14580/117649. Therefore all B coefficients of s∣T3 are zero.
The construction in Lemma3 is stable in the sense that the maximum coefficient of s is bounded by Kmaxξ∈ℳ|p(ξ)|, where K is a constant depending only on the smallest angle in ∆. Thus, we say that ℳ is a stable Lagrange MDS for s∈𝒮72,3(). The proof is completed.In the following lemmas, we will consider four cases depending on how many edges ofQ∈𝒲 adjoin with the other Q∈ℬ.Lemma 4.
Suppose that consists of two triangulated quadrangulations Q1=〈v1,v2,v3,v4〉 and Q2=〈v3,v5,v6,v4〉 sharing the edge 〈v3,v4〉, where Q1∈ℬ and Q2∈𝒲. Let vQ1 and vQ2 be the points where the two diagonals of Q1 and Q2 intersect, respectively. Let the set
(16)ℳ:=ℳQ1⋃‍m1⋃‍m2⋃‍m3,
where ℳQ1 is the set defined in Lemma 3 for the triangulated quadrangulations of Q1 and
(18)m1=⋃‍D3〈vQ2,v4,v3〉(vQ2)⋃‍{ξ331〈vQ2,v4,v3〉,ξ322〈vQ2,v4,v3〉,ξ313〈vQ2,v4,v3〉},m2=⋃‍D3〈vQ2,v3,v5〉(v5)⋃‍{ξ133〈vQ2,v3,v5〉,ξ223〈vQ2,v3,v5〉,ξ313〈vQ2,v3,v5〉,ξ403〈vQ2,v3,v5〉,ξ133〈vQ2,v5,v6〉},m3=⋃‍D3〈vQ2,v6,v4〉(v6)⋃‍{ξ133〈vQ2,v6,v4〉,ξ232〈vQ2,v6,v4〉,ξ331〈vQ2,v6,v4〉,ξ430〈vQ2,v6,v4〉},
be a stable Lagrange MDS for 𝒮72,3(). These domain points are marked with • in Figure 3.Figure 3
The point setℳ produced by Lemma 4.Proof.
Using Lemma3, we can see that all of the B coefficients of s associated with domain points in Q1 are uniquely determined by the data. Writing s∣〈vQ2,v4,v3〉 in B form and using C1, C2, and C3 smoothness conditions, all B coefficients are determined except for the B coefficients associated with m1. Because GC=b, where (19)b:=(p(ξ700〈vQ2,v4,v3〉),p(ξ610〈vQ2,v4,v3〉),p(ξ601〈vQ2,v4,v3〉),p(ξ520〈vQ2,v4,v3〉),p(ξ511〈vQ2,v4,v3〉),p(ξ502〈vQ2,v4,v3〉),p(ξ430〈vQ2,v4,v3〉),p(ξ421〈vQ2,v4,v3〉),p(ξ412〈vQ2,v4,v3〉),p(ξ403〈vQ2,v4,v3〉),p(ξ331〈vQ2,v4,v3〉),p(ξ322〈vQ2,v4,v3〉),p(ξ313〈vQ2,v4,v3〉)(ξ700〈vQ2,v4,v3〉))T,G=(10000000000006777667603×6576005×6476000000677706676003×65760005×647600057772×5676012×55760040×54760000005777567656763×55766×55763×55765×547615×54765×54765×547620×537620×537630×5376577702×56760012×557600040×547600047773×4676027×457600135×447600000047772×4676467612×457612×45763×457640×447660×447630×44765×4476160×4376160×437640×4376477746762×46763×457612×457612×45765×447630×447660×447640×447640×437660×4376160×4376477703×46760027×4576000135×447600037773×3676367627×357618×35763×3576135×347627×34769×34765×3476540×3376270×337660×337637772×36762×367612×357624×357612×357640×3476130×3476130×347640×3476320×3376480×3376320×3376377736763×36763×357618×357627×35765×347645×3476135×3476135×347660×3376270×3376540×3376).
It is easy to see thatrank(G)=13. Thus, all of the remaining B coefficients of m1 are uniquely determined by the data. Then, using Lemma 3 again, it is easy to see that all of the B coefficients of s associated with domain points in Q2 are uniquely and stable determined by the data. Therefore, ℳ is a stable Lagrange MDS for 𝒮72,3(). The proof is completed.Lemma 5.
Suppose that consists of three triangulated quadrangulations Q1, Q2, and Q3 as in Figure 4, where Q1,Q3∈ℬ and Q2∈𝒲. Let the set
(20)ℳ:=ℳQ1⋃‍ℳQ3⋃‍m1⋃‍m2,
where ℳQi is the set defined in Lemma 3 for the triangulated quadrangulations of Qi and
(21)m1=⋃‍D3〈vQ2,v3,v2〉(vQ2)⋃{ξ331〈vQ2,v3,v2〉,ξ322〈vQ2,v3,v2〉,ξ313〈vQ2,v3,v2〉},m2={ξ133〈vQ2,v6,v3〉,ξ430〈vQ2,v6,v3〉,ξ331〈vQ2,v6,v3〉,ξ133〈vQ2,v2,v5〉,ξ403〈vQ2,v2,v5〉,ξ313〈vQ2,v2,v5〉},
be a stable Lagrange MDS for 𝒮72,3(). These domain points are marked with • in Figure 4.Figure 4
The point setℳ produced by Lemma 5.Proof.
Using Lemma3, we can see that all of the B coefficients of s associated with domain points in Q1 and Q3 are uniquely determined by the data. Arguing as in Lemma 4, all the B coefficients of s∣〈vQ2,v3,v2〉 associated with domain points are uniquely determined by the data too. Writing s∣〈vQ2,v2,v5〉 in B form and using C1, C2 and C3 smoothness conditions, all B coefficients are determined except for m:={c403〈vQ2,v2,v5〉,c313〈vQ2,v2,v5〉,c223〈vQ2,v2,v5〉,c133〈vQ2,v2,v5〉}. The Lagrange interpolation and C1 and C2 smoothness conditions at e:=〈vQ2,v5〉 imply that these coefficients must satisfy the linear system GC=b, where
(22)C:=(c403〈vQ2,v2,v5〉,c313〈vQ2,v2,v5〉,c223〈vQ2,v2,v5〉,c133〈vQ2,v2,v5〉,c331〈vQ2,v5,v6〉)T,b:=(p(ξ403〈vQ2,v2,v5〉),p(ξ313〈vQ2,v2,v5〉),p(ξ133〈vQ2,v2,v5〉),0,0)T,G=(1280×337600005×377620×367630×357620×347605×337660×3376270×3376540×33760γ1-100β1γ120-102β1γ1),
where v2=β1ν6+γ1νQ2. The determinant of the matrix G is
(23)-5×103β1(8γ1+9).
By the geometric meaning of the β1 and γ1, we have β1<0 and γ1>0. Thus det(G)≠0. So, all B coefficients of s∣〈vQ2,v2,v5〉 are uniquely determined. By the same principle, all B coefficients of s∣〈vQ2,v6,v3〉 are uniquely determined. Using Lemma 3 again, it is easy to see that all B coefficients of Q2 are uniquely and stable determined by the data. Therefore ℳ is a stable Lagrange MDS for 𝒮72,3(). The proof is completed.Lemma 6.
Suppose that consists of three triangulated quadrangulations Q1, Q2, and Q3 as in Figure 5, where Q1,Q3∈ℬ and Q2∈𝒲. Let the set
(24)ℳ:=ℳQ1⋃‍ℳQ3⋃‍m1⋃‍m2-⋃‍D3〈vQ2,v2,v7〉(v2),
where ℳQi is the set defined in Lemma 3 for the triangulated quadrangulations of Qi and
(25)m1={ξ133〈vQ2,v2,v3〉,ξ403〈vQ2,v2,v5〉,ξ313〈vQ2,v2,v5〉},m2=⋃‍D3〈vQ2,v5,v6〉(v6)⋃‍{ξ133〈vQ2,v5,v6〉,ξ223〈vQ2,v5,v6〉,ξ313〈vQ2,v5,v6〉,ξ403〈vQ2,v5,v6〉},
be a stable Lagrange MDS for 𝒮72,3(). These domain points are marked with • in Figure 5.Figure 5
The point setℳ produced by Lemma 6.Proof.
Using Lemma3 and C1, C2, and C3 smoothness conditions, we can see that all of the B coefficients of s associated with domain points in Q1 and Q3 are uniquely determined by the data. Writing s∣〈vQ2,v3,v6〉 in B form and using C1, C2, and C3 smoothness conditions, all B coefficients are determined except for the B coefficients of m:=⋃‍D3〈vQ2,v3,v2〉(vQ2)⋃‍{ξ331〈vQ2,v3,v2〉,ξ322〈vQ2,v3,v2〉,ξ313〈vQ2,v3,v2〉} associated. The Lagrange interpolation and C1 and C2 smoothness conditions at e:=〈vQ2,v3〉 and e:=〈vQ2,v2〉 imply that these coefficients must satisfy the linear system GC=b, where (26)C:=(c700〈vQ2,v3,v2〉,c610〈vQ2,v3,v2〉,c601〈vQ2,v3,v2〉,c520〈vQ2,v3,v2〉,c511〈vQ2,v3,v2〉,c502〈vQ2,v3,v2〉,c430〈vQ2,v3,v2〉,c421〈vQ2,v3,v2〉,c412〈vQ2,v3,v2〉,c403〈vQ2,v3,v2〉,c331〈vQ2,v3,v2〉,c322〈vQ2,v3,v2〉,c313〈vQ2,v3,v2〉,c313〈vQ2,v6,v3〉,c331〈vQ2,v2,v5〉)T,b:=(p(ξ700〈vQ2,v3,v2〉),p(ξ610〈vQ2,v3,v2〉),p(ξ601〈vQ2,v3,v2〉),p(ξ520〈vQ2,v3,v2〉),p(ξ511〈vQ2,v3,v2〉),p(ξ502〈vQ2,v3,v2〉),p(ξ430〈vQ2,v3,v2〉),p(ξ421〈vQ2,v3,v2〉),p(ξ412〈vQ2,v3,v2〉),p(ξ403〈vQ2,v3,v2〉),p(ξ331〈vQ2,v3,v2〉),p(ξ322〈vQ2,v3,v2〉),0,0,0)T,G=(1000000000000006777667603×6576005×647600000000677706676003×65760005×64760000057772×5676012×55760040×5476000000005777567656763×55766×55763×55765×547615×54765×54765×547620×537620×537630×537600577702×56760012×557600040×54760000047773×4676027×457600135×44760000000047772×4676467612×457612×45763×457640×447660×447630×44765×4476160×4376160×437640×437600477746762×46763×457612×457612×45765×447630×447660×447640×447640×437660×4376160×437600477703×46760027×4576000135×44760000037773×3676367627×357618×35763×3576135×347627×34769×34765×3476540×3376270×337660×33760037772×36762×367612×357624×357612×357640×3476130×3476130×347640×3476320×3376480×3376320×337600000000γ1000β100-10000000000γ200-10β2000000000γ2200002β2γ2), where ν6=β1ν2+γ1νQ2 and ν3=β2ν5+γ2νQ2. The determinant of the matrix G is
(27)-7.07759×10-10β2γ2.
By the geometric meaning of the β2 and γ2, we have β2<0 and γ2>0. Thus det(G)≠0. So, all B coefficients of s∣〈vQ2,v3,v2〉 are uniquely determined. Applying Lemmas 3 and 4, it is easy to see that all B coefficients of Q2 are uniquely and stable determined by the data. Therefore ℳ is a stable Lagrange MDS for 𝒮72,3(). The proof is completed.Lemma 7.
Suppose that  consists of three triangulated quadrangulations Q1, Q2, Q3, and Q4 as in Figure 6, where Q1,Q3,Q4∈ℬ and Q2∈𝒲. Let the set
(28)ℳ:=ℳQ1⋃‍ℳQ3⋃‍ℳQ4⋃‍m1-⋃‍D3〈vQ4,v2,v9〉(v2)⋃‍D3〈vQ4,v10,v5〉(v5),
where ℳQi is the set defined in Lemma 3 for the triangulated quadrangulations of Qi and
(29)m1=⋃‍D3〈vQ2,v2,v5〉(vQ2)⋃‍{ξ322〈vQ2,v2,v5〉,ξ133〈vQ2,v6,v3〉,ξ430〈vQ2,v6,v3〉,ξ313〈vQ2,v5,v6〉,ξ430〈vQ2,v3,v2〉,ξ331〈vQ2,v3,v2〉},
be a stable Lagrange MDS for 𝒮72,3(). These domain points are marked with • in Figure 6.Figure 6
The point setℳ produced by Lemma 7.Proof.
Using Lemma3 and C1, C2, and C3 smoothness conditions, we can see that all of the B coefficients of s associated with domain points in Q1, Q3, and Q4 are uniquely determined by the data. Writing s∣〈vQ2,v2,v5〉 in B form and using C1, C2, and C3 smoothness conditions, all B-coefficients are determined except for the B-coefficients of m:=⋃‍D3〈vQ2,v2,v5〉(vQ2)⋃‍{ξ331〈vQ2,v2,v5〉,ξ322〈vQ2,v2,v5〉,ξ313〈vQ2,v2,v5〉} associated. The Lagrange interpolation and C1, C2 smoothness conditions at e:=〈vQ2,v2〉 and e:=〈vQ2,v5〉 imply that these coefficients must satisfy the linear system GC=b, where (30)C:=(c700〈vQ2,v2,v5〉,c610〈vQ2,v2,v5〉,c601〈vQ2,v2,v5〉,c520〈vQ2,v2,v5〉,c511〈vQ2,v2,v5〉,c502〈vQ2,v2,v5〉,c430〈vQ2,v2,v5〉,c421〈vQ2,v2,v5〉,c412〈vQ2,v2,v5〉,c403〈vQ2,v2,v5〉,c331〈vQ2,v2,v5〉,c322〈vQ2,v2,v5〉,c313〈vQ2,v2,v5〉,c313〈vQ2,v3,v2〉,c331〈vQ2,v5,v6〉)T,b:=(p(ξ700〈vQ2,v2,v5〉),p(ξ610〈vQ2,v2,v5〉),p(ξ601〈vQ2,v2,v5〉),p(ξ520〈vQ2,v2,v5〉),p(ξ511〈vQ2,v2,v5〉),p(ξ502〈vQ2,v2,v5〉),p(ξ430〈vQ2,v2,v5〉),p(ξ421〈vQ2,v2,v5〉),p(ξ412〈vQ2,v2,v5〉),p(ξ403〈vQ2,v2,v5〉),p(ξ322〈vQ2,v2,v5〉),0,0,0,0)T,G=(1000000000000006777667603×6576005×647600000000677706676003×65760005×64760000057772×5676012×55760040×5476000000005777567656763×55766×55763×55765×547615×54765×54765×547620×537620×537630×537600577702×56760012×557600040×54760000047773×4676027×457600135×44760000000047772×4676467612×457612×45763×457640×447660×447630×44765×4476160×4376160×437640×437600477746762×46763×457612×457612×45765×447630×447660×447640×447640×437660×4376160×437600477703×46760027×4576000135×44760000037772×36762×367612×357624×357612×357640×3476130×3476130×347640×3476320×3376480×3376320×337600000000γ2000β200-10000000γ220002β2γ20000000000000γ100-10β10000000002γ1200002β1γ1),
wherev2=β1v6+γ1vQ2, v3=β2v5+γ2vQ2. The determinant of the matrix G is
(31)-1.31659×10-8β1β2γ1γ2.
By the geometric meaning of the β1, β2, γ1, and γ2, we have β1<0, β2<0, γ1>0, and γ2>0. Thus det(G)≠0. So, all B coefficients of s∣〈vQ2,v3,v2〉 are uniquely determined. Applying Lemmas 3 and 4, it is easy to see that all B coefficients of Q2 are uniquely and stable determined by the data. Therefore, ℳ is a stable Lagrange MDS for 𝒮72,3(). The proof is completed.


## 5. Construction of a Lagrange Interpolation Pair

Theorem 8.
Suppose that is checkerboard triangulation. Then
(32)
Moreover, the following set ℳ of domain points is a stable Lagrange MDS:(1)
ifQ∈𝒢, choose points as in Lemma 3,(2)
ifQ∈ℬ∖𝒢, choose points as in Lemma 3, leaving out the points in the sets D3T whenever v is a vertex of Q which is interior to ◊,(3)
suppose thatQ:=〈v1,v2,v3,v4〉∈𝒲, and let ei:=〈vi,vi+1〉 for i=1,2,3,4, where v5=v1 and vQ is the point where the two diagonals of Q intersect:
(a)
ifQ∈𝒲1, choose points as in Lemma 4,(b)
ifQ∈𝒲2, choose points as in Lemmas 5 and 6,(c)
ifQ∈𝒲3, choose points as in Lemma 7,(d)
ifQ sharing four edges with black quadrilaterals, say e1,e2,e3,ande4, choose the points ξ223T1, ξ403T2, ξ403T3, and D3T1(vQ).Proof.
To establish thatℳ is a Lagrange MDS, suppose 𝒮72,3() and that we are given values for s(ξ) for all ξ∈ℳ. We need to show that all of the B coefficients of s are uniquely determined. By Lemma 3, all B-coefficient s associated with domain points lying in quadrilaterals Q∈𝒢 is uniquely determined. Now consider Q∈ℬ∖𝒢. For each vertex v∈Q which is an interior vertex of ◊, the B coefficients corresponding to domain points in the disk D3T are already uniquely determined by C1,C2, and C3 continuity from the neighboring pieces. Leaving the corresponding basis functions out, we can then argue exactly as in Lemma 3 to see that all B coefficients of s corresponding to the remaining domain points in Q are uniquely determined.
Now suppose thatQ∈𝒲. If Q∈𝒲1, then, using Lemma 4, we can see that all B coefficients of s corresponding to the remaining domain points in Q are uniquely determined. If Q∈𝒲2, then, using Lemmas 5 and 6, we can see that all B-coefficients of s corresponding to the remaining domain points in Q are uniquely determined. If Q∈𝒲3, then using Lemma 7, we can see that all B coefficients of s corresponding to the remaining domain points in Q are uniquely determined. If Q shares four edges with black quadrilaterals, we can then argue exactly as in Lemma 7 to see that all B coefficients of s corresponding to the remaining domain points in Q are uniquely determined. Since we have shown that ℳ is a MDS, it follows that dim𝒮72,3()=#ℳ.
Finally, we note that all of the above computations are stable in the sense that the size of the computed B coefficient is bounded by a constant depending only on the smallest angle in the triangulationΔ. This follows from that the computations of Lemmas 2–7 are stable, and the fact that computing coefficients from C1,C2, and C3 smoothness conditions is automatically stable.According to the Theorem8, we have presented a Lagrange MDS for Figure 1 (see Figure 7).Figure 7
The Lagrange MDS produced by Theorem8.Theorem 9.
Let be a checkerboard triangulation, and let ℳ be the set defined in Theorem 8. Then there exists a stable local basis {Bi}i=1n of 𝒮72,3(), where n:=#ℳ.Proof.
It is clear that ifℳ is a MDS for 𝒮72,3(), then, for each ξ∈ℳ, there exists a unique spline Bξ∈S, satisfying ληBξ=δξ,η, for all η∈ℳ. The splines Bξ obviously form a basis for 𝒮72,3(), which is commonly called the dual basis corresponding to ℳ.
The proof of Theorem8 shows that all B coefficients of Bξ are uniquely and stable determined. So we should give the support of Bξ. As in [15], suppose that ξ lies in a quadrilateral Q. Then we claim that(1)
supp(Bξ)=Q if ξ=𝒲,(2)
supp(Bξ)⊂star(Qξ) if ξ∈ℬ∖𝒢,(3)
supp(Bξ)⊂star2(Qξ) otherwise.We are now ready to discuss interpolation. Suppose that is a checkerboard triangulation, and that Bξ are the dual basis function of Theorem 9 corresponding to Lagrange MDS for 𝒮72,3() defined in Theorem 8. Then for every f∈C(Ω), there is a unique spline s=ℐf∈𝒮 which satisfies s(η)=ℐf(η)=f(η), for all η∈ℳ. This defines a linear projector ℐ mapping C(Ω) onto 𝒮. We now give an error bound for this interpolation method.Theorem 10.
Supposef lies in the Sobolev space W∞m+1(Ω) for some 0≤m≤7. Then
(33)∥DxαDyβ(f-ℐf)∥Ω≤K|Δ|m+1-α-β|f|m+1,Ω
for 0≤α+β≤m. Here |•|m+1,Ω is usual Sobolev seminorm, and |Δ| is the maximum of the diameters of the triangles in Δ. The constant K depends only on the smallest angle in Δ.Proof.
It was shown inSection10 of [16] that if a space of splines 𝒮 of degree d contains 𝒫d and has a stable local basis, then it provides optimal order approximations of smooth functions.The result of Theorem10 can also be established with the weak-interpolation methods described in [17].



---

*Source: 638254-2013-03-19.xml*