3. Interpolation operators¶
A video recording of the following material is available here.
Imperial students can also watch this video on Panopto
In this section we investigate how continuous functions can be approximated by finite element functions. We start locally, looking at a single finite element, and then move globally to function spaces on a triangulation.
3.1. Local and global interpolation operators¶
Given a finite element \((K,\mathcal{P},\mathcal{N})\), with corresponding nodal basis \(\{\phi_i\}_{i=0}^k\). Let \(v\) be a function such that \(N_i(v)\) is well-defined for all \(i\). Then the local interpolator \(\mathcal{I}_K\) is an operator mapping \(v\) to \(\mathcal{P}\) such that
We now discuss some useful properties of the local interpolator.
The operator \(I_K\) is linear.
Prove Lemma 3.2.
Prove Lemma 3.4.
\(I_K\) is the identity when restricted to \(\mathcal{P}\).
Prove Lemma 3.6.
By combining together the local interpolators in each triangle of the triangulation, we obtain the global interpolator into the finite element space.
Let \(V_h\) be a finite element space constructed from a triangulation \(\mathcal{T}_h\) with finite elements \((K_i,\mathcal{P}_i,\mathcal{N}_i)\), each with a \(C^m\) geometric decomposition. The global interpolator \(\mathcal{I}_h\) is defined by \(\mathcal{I}_hu \in V_h\) such that
for each \(K \in \mathcal{T}_h\).
3.2. Measuring interpolation errors¶
A video recording of the following material is available here.
Imperial students can also watch this video on Panopto
Next we look at how well we can approximate continuous functions using the interpolation operator, i.e. we want to measure the approximation error \(\mathcal{I}_h u - u\). We are interested in integral formulations, so we want to use integral quantities to measure errors. We have already seen the \(L^2\) norm. It is also useful to take derivatives into account when measuring the error. To discuss higher order derivatives, we introduce the multi-index.
For \(d\)-dimensional space, a multi-index \(\alpha=(\alpha_1,\ldots,\alpha_d)\) assigns the number of partial derivatives in each Cartesian direction. We write \(|\alpha|=\sum_{i=1}^d\alpha_i\).
This means we can write mixed partial derivatives, for example if \(\alpha=(1,2)\) then
Now we can define some norms involving derivatives for measuring errors.
The \(H^k\) seminorm is defined as
where the sum is taken over all multi-indices of size \(k\) i.e. all the derivatives are of degree \(k\).
The \(H^k\) norm is defined as
where we conventionally write \(|u|_{H^0}=\|u\|_{L^2}\).
A video recording of the following material is available here.
Imperial students can also watch this video on Panopto
To help to estimate interpolation errors, we quote the following important result (which we will return to much later).
Let \(\Omega\) be an \(n\)-dimensional domain with Lipschitz boundary, and let \(u\) be a continuous function with \(k\) continuous derivatives, i.e. \(u \in C^{k,\infty}(\Omega)\). Let \(k\) be an integer with \(k>n/2\). Then there exists a constant \(C\) (depending only on \(\Omega\)) such that
See a functional analysis course or textbook.
This is extremely useful because it means that we can measure the \(H^k\) norm by integrating and know that it gives an upper bound on the value of \(u\) at each point. We say that \(u\) is in \(C^\infty(\Omega)\) if \(\|u\|_{C^\infty(\Omega)}<\infty\), and Sobolev’s inequality tells us that this is the case if \(\|u\|_{H^k(\Omega)}<\infty\).
This result can be easily extended to derivatives.
Let \(\Omega\) be a \(n\)-dimensional domain with Lipschitz boundary, and let \(u \in C^{k,\infty}(\Omega)\) Let \(k\) be an integer with \(k-m>n/2\). Then there exists a constant \(C\) (depending only on \(\Omega\)) such that
Just apply Sobolev’s inequality to the \(m\) derivatives of \(u\).
3.3. Approximation by averaged Taylor polynomials¶
A video recording of the following material is available here.
Imperial students can also watch this video on Panopto
The basic tool for analysing interpolation error for continuous functions is the Taylor series. Rather than taking the Taylor series about a single point, since we are interested in integral quantities, it makes sense to consider an averaged Taylor series over some region inside each cell. This will become important later when we start thinking about more general types of derivative that only exist in an integral sense.
Let \(\Omega\subset \mathbb{R}^n\) be a domain with diameter \(d\), that is star-shaped with respect to a ball \(B\) contained within \(\Omega\). For \(f\in C^{k,\infty}\) the averaged Taylor polynomial \(Q_{k,B}f\in \mathcal{P}_k\) is defined as
where \(T^kf\) is the Taylor polynomial of degree \(k\) of \(f\),
Show that
\[D^\beta Q_{k,B} f = Q_{k-|\beta|,B} D^\beta f,\]
where \(Q^l_B\) is the degree \(l\) averaged Taylor polynomial of \(f\), and \(D^\beta\) is the \(\beta\)-th derivative where \(\beta\) is a multi-index.
Now we develop an estimate of the error \(T^kf - f\).
A first video recording of the following material is available here.
Imperial students can also watch this video on Panopto
A second video recording of the following material is available here.
Imperial students can also watch this video on Panopto
Let \(\Omega\subset \mathbb{R}^n\) be a domain with diameter \(d\), that is star-shaped with respect to a ball \(B\) contained within \(\Omega\). Then there exists a constant \(C(k,n)\) such that for \(0\leq |\beta| \leq k+1\) and all \(f \in C^{k+1,\infty}(\Omega)\),
The Taylor remainder theorem (see a calculus textbook) gives
when \(f \in C^{k+1,\infty}\).
Integration over \(y\) in \(B\) and dividing by \(|B|\) gives
Then
Then
We will get the result by changing variables and exchanging the \(t\), \(y\) and \(x\) integrals. To avoid a singularity when \(t=0\) or \(t=1\), for each \(\alpha\) term we can split the \(t\) integral into \([0,1/2]\) and \([1/2,1]\). Call these terms I and II.
Denote by \(g_\alpha\) the extension by zero of \(D^\alpha f\) to \(\mathbb{R}^n\). Then
Similarly, for \(II\),
Hence, we obtain the required bounds for \(|\beta|=0\). For higher derivatives we use the fact that
which immediately leads to the estimate for \(|\beta|>0\).
Now we develop this into an estimate that depends on the diameter of the triangle we are interpolating to.
Let \(K_1\) be a triangle with diameter \(1\). There exists a constant \(C(k,n)\) such that
Take the maximum over the constants for the derivative contributions of the left-hand side with \(d=1\) and use the previous result.
3.4. Local and global interpolation errors¶
A video recording of the following material is available here.
Imperial students can also watch this video on Panopto
The following exercises give a specific example of the interpolation error results of this section without directly using the previous estimate (because they specialise to \(L^2\), 1D and linear elements).
Let \(w\in C^2([0,1])\), with \(w(0)=w(1)=0\). Show that
Hints: use the Schwarz inequality,
(which we shall discuss in more generality in Section 4), together with Rolle’s theorem.
Using the previous exercise, show that for all \(u\in C^2([0,1])\), there exists a constant \(c\) such that
where \(\mathcal{I}_{[0,1]}\) is the interpolator to the finite element with \(K=[0,1]\), \(P\) is the linear polynomials on \(K\), and the nodal variables are \(N_0[p]=p(0)\) and \(N_1[p]=p(1)\).
Using the previous exercise, show that for all \(u\in C^2([a,b])\), there exists a constant \(c\) such that
where \(\mathcal{I}_{[a,b]}\) is the interpolator to the finite element with \(K=[a,b]\), \(P\) is the linear polynomials on \(K\), and the nodal variables are \(N_0[p]=p(a)\) and \(N_1[p]=p(b)\).
Using the previous exercise, show that for a P1 finite element space defined on the interval \([a,b]\) with maximum mesh cell width \(h\), then there exists a constant \(c\) such that
where \(\mathcal{I}_h\) is the global nodal interpolator to the P1 finite element space.
Under the same assumptions as the previous exercise, prove the following finite element version of Sobolev’s inequality,
for all \(v \in V\), where \(V\) is the subspace of the P1 finite element space defined on a subdivision of the interval \([0,1]\) containing only functions \(v\) with \(v(0)=0\).
Now we will use the Taylor polynomial estimates to derive error estimates for the local interpolation operator. We start by looking at a triangle with diameter 1, and then use a scaling argument to obtain error estimates in terms of the diameter \(h\). It begins by getting the following bound.
Let \((K_1,\mathcal{P},\mathcal{N})\) be a finite element such that \(K_1\) is a triangle with diameter 1, and such that the nodal variables in \(\mathcal{N}\) involve only evaluations of functions or evaluations of derivatives of degree \(\leq l\), and \(\|N_i\|_{C^{l,\infty}(K_1)'} <\infty\),
Let \(k-l > n/2\), and \(u\in C^{k,\infty}(\Omega)\). Then
Let \(\{\phi_i\}_{i=1}^n\) be the nodal basis for \(\mathcal{P}\). Then
where the Sobolev inequality was used in the last line.
A video recording of the following material is available here.
Imperial students can also watch this video on Panopto
Now we can directly apply this to the interpolation operator error estimate on the triangle with diameter 1. It is the standard trick of adding and subtracting something, in this case the Taylor polynomial.
Let \((K_1,\mathcal{P},\mathcal{N})\) be a finite element such that \(K_1\) has diameter \(1\), and such that the nodal variables in \(\mathcal{N}\) involve only evaluations of functions or evaluations of derivatives of degree \(\leq l\), and \(\mathcal{P}\) contain all polynomials of degree \(k\) and below, with \(k>l+n/2\). Let \(u\in C^{k+1,\infty}(K_1)\). Then for \(i \leq k\), the local interpolation operator satisfies
where we used the fact that \(\mathcal{I}_{K_1}Q_{k,B}u = Q_{k,B}u\) in the second line and the previous lemma in the third line.
A video recording of the following material is available here.
Now we apply a scaling argument to translate this to triangles with diameter \(h\).
Let \((K,\mathcal{P},\mathcal{N})\) be a finite element such that \(K\) has diameter \(d\), and such that the nodal variables in \(\mathcal{N}\) involve only evaluations of functions or evaluations of derivatives of degree \(\leq l\), and \(\mathcal{P}\) contains all polynomials of degree \(k\) and below, with \(k>l+n/2\). Let \(u\in C^{k+1,\infty}(K)\). Then for \(i \leq k\), the local interpolation operator satisfies
where \(C_K\) is a constant that depends on the shape of \(K\) but not the diameter.
Consider the change of variables \(x \to \phi(x)=x/d\). This map takes \(K\) to \(K_1\) with diameter 1. Then
and taking the square root gives the result.
A video recording of the following material is available here.
Imperial students can also watch this video on Panopto
So far we have just developed an error estimate for the local interpolator on a single triangle. Now we extend this to finite element spaces defined on the whole triangulation.
Let \(\mathcal{T}\) be a triangulation of \(\Omega\) with finite elements \((K_i,\mathcal{P}_i,\mathcal{N}_i)\), such that the minimum aspect ratio \(\gamma\) of the triangles \(K_i\) satisfies \(\gamma>0\), and such that the nodal variables in \(\mathcal{N}\) involve only evaluations of functions or evaluations of derivatives of degree \(\leq l\), and \(\mathcal{P}\) contains all polynomials of degree \(k\) and below, with \(k>l+n/2\). Let \(u\in C^{k+1,\infty}(K_1)\). Let \(h\) be the maximum over all of the triangle diameters, with \(0\leq h<1\). Then for \(i\leq k\), the global interpolation operator satisfies
(Recalling that we use the “broken” finite element derivative in norms for \(\mathcal{I}_hu\) over \(\Omega\).
where the existence of the \(C_{\max}=\max_KC_K<\infty\) is due to the lower bound in the aspect ratio.
In this section, we have built a theoretical toolbox for the interpolation of functions to finite element spaces. In the next section, we move on to studying the solveability of finite element approximations.