on convergence of graph Laplacian to manifold's Laplacian

Overview

The proof is a comparison argument at three levels. First, the surface problem is replaced by the Neumann Laplacian on the thin tube $D_r$; the normal direction contributes only high modes, so the first fixed eigenvalues differ from the Laplace-Beltrami eigenvalues by $O(r)$.

Second, a weighted finite-volume graph Laplacian $L_{\omega }$ is introduced on the cut cells of the lattice. Cell averages of smooth Neumann eigenfunctions give the upper bound for ${\lambda }_k(-L_{\omega },r)$.

Third, the lower bound is obtained by trilinear interpolation. A low-energy graph eigenspace is interpolated into $H^1(D_r)$; local $Q_1$ finite-element estimates control the continuum Dirichlet energy by the graph energy, while a discrete trace estimate controls cells cut by $\partial D_r$. The min-max principle on $D_r$ then forces the graph eigenvalues from below.

Finally, the weighted graph is compared with the unweighted graph. Since the two differ only in an $O(h)$ boundary layer, the resulting perturbation is lower order once $h\ll r$. Balancing the tube error $r$ and the boundary-layer error $h{r}^{-1}$ gives $r\asymp h^{1/2}$.

The proof has no new tools involved, hence not adequate for publication.

Statement and Notation

Let $\Gamma \subset {\mathbb{R}}^3$ be a connected closed $C^{\infty }$ surface with unit normal $\nu$. Let $d_{\Gamma }$ be the signed distance function and let

$$D_r:=\{x\in {\mathbb{R}}^3:|d_{\Gamma }(x)|<r\}.$$

Throughout $r>0$ is smaller than a fixed tubular radius of $\Gamma$. In this tube every point is written uniquely as

$$x=p+t\nu (p),p\in \Gamma ,|t|<r.$$

The surface eigenvalues are denoted by

$$-{\Delta }_{\Gamma }{\varphi }_j={\lambda }_j{\varphi }_j,0={\lambda }_0<{\lambda }_1\le {\lambda }_2\le \cdots ,$$

where the eigenfunctions are orthonormal in $L^2(\Gamma )$. Repeated eigenvalues are listed with multiplicity. All constants below may depend on $\Gamma$ and on a fixed spectral index $k$, but not on $r$ or on the lattice scale $h=n^{-1}$.

For $h=n^{-1}$ define

$$V_r:=D_r\cap h{\mathbb{Z}}^3,E_r:=\{x\sim y:x,y\in V_r,|x-y|=h\}.$$

The scaled graph Laplacian is

$$Lf(x)=h^{-2}\sum _{y\sim x}(f(y)-f(x)).$$

The inner product on functions on $V_r$ is

$$⟨f,g{⟩}_r:=h^3\sum _{x\in V_r}f(x)g(x).$$

Main estimate

Let ${\lambda }_k(-L,r)$ be the $k$th eigenvalue of $-L$ with respect to $⟨\cdot ,\cdot {⟩}_r$. For $0<h\ll r\ll 1$,

$$|{\lambda }_k(-L,r)-{\lambda }_k|\le C_k\left[\left(h({\lambda }_k+1{)}^{7/4}+r+h{r}^{-1}({\lambda }_k+1{)}^{5/2}\right){\lambda }_k+h{r}^{-1}({\lambda }_k+1{)}^{7/2}\right].$$

In particular, for fixed $k$, the choice $r\asymp h^{1/2}=n^{-1/2}$ gives

$$|{\lambda }_k(-L,r)-{\lambda }_k|\le C_k{n}^{-1/2}.$$

1. Eigenvalues on the Thin Tube

Let ${\mu }_j(r)$ be the Neumann eigenvalues of $-\Delta$ on $D_r$:

$$\begin{array}{rlrl}-\Delta {\psi }_j& ={\mu }_j(r){\psi }_j& & \text{in }{D}_r,\\ {\partial }_n{\psi }_j& =0& & \text{on }\partial D_r.\end{array}$$

Lemma 1.1: tube comparison

For each fixed $k$,

$$|{\mu }_k(r)-{\lambda }_k|\le C_{k}r(1+{\lambda }_k).$$

Proof. In normal coordinates the Euclidean volume form has the expansion

$$dx=J_t(p)dS(p)dt,J_t(p)=\det (I-t{S}_p)=1+O(r),$$

where $S_p$ is the shape operator. The tangential metric on ${\Gamma }_t$ is also an $O(r)$ perturbation of the metric on $\Gamma$.

For the upper bound, lift the first $k+1$ surface eigenfunctions constantly in the normal direction:

$$h_j(p+t\nu (p)):={\varphi }_j(p),0\le j\le k.$$

If $u={\sum }_{j=0}^k{a}_j{h}_j$ and $\tilde{u}={\sum }_{j=0}^k{a}_j{\varphi }_j$, then

$${\int }_{D_r}|u{|}^{2}dx=2r(1+O(r)){\int }_{\Gamma }|\tilde{u}{|}^{2}dS$$

and

$${\int }_{D_r}|\nabla u{|}^{2}dx=2r(1+O(r)){\int }_{\Gamma }|{\nabla }_{\Gamma }\tilde{u}{|}^{2}dS.$$

The min-max principle therefore gives

$${\mu }_k(r)\le \underset{0\ne u\in \mathrm{span}(h_0,\dots ,h_k)}{\max }\frac{{\int }_{D_r}|\nabla u{|}^{2}dx}{{\int }_{D_r}|u{|}^{2}dx}\le (1+Cr){\lambda }_k.$$

For the lower bound, define the weighted normal average

$$\overline{v}(p):=\frac{{\int }_{-r}^{r}v(p,t)J_t(p)dt}{{\int }_{-r}^r{J}_t(p)dt}.$$

The one-dimensional Neumann Poincare inequality along normal fibers implies

$${\int }_{D_r}|v-\overline{v}{|}^{2}dx\le C{r}^2{\int }_{D_r}|{\partial }_{t}v{|}^{2}dx.$$

Jensen’s inequality and the metric expansion give

$$2r{\int }_{\Gamma }|{\nabla }_{\Gamma }\overline{v}{|}^{2}dS\le (1+Cr){\int }_{D_r}|\nabla v{|}^{2}dx.$$

Let $W_{k-1}$ be the span of the first $k$ lifted and normalized modes. If $v\perp W_{k-1}$ in $L^2(D_r)$, then $\overline{v}$ is orthogonal to ${\varphi }_0,\dots ,{\varphi }_{k-1}$ up to an $O(r)$ perturbation. Equivalently, after replacing the lifted basis by the Gram-Schmidt orthonormalization of $h_0,\dots ,h_{k-1}$, the perturbation is absorbed in the constants. Hence

$${\int }_{\Gamma }|{\nabla }_{\Gamma }\overline{v}{|}^{2}dS\ge ({\lambda }_k-Cr(1+{\lambda }_k)){\int }_{\Gamma }|\overline{v}{|}^{2}dS.$$

Combining this estimate with the normal Poincare inequality yields

$${\int }_{D_r}|\nabla v{|}^{2}dx\ge ({\lambda }_k-Cr(1+{\lambda }_k)){\int }_{D_r}|v{|}^{2}dx.$$

The max-min principle for the Neumann Laplacian gives the desired lower bound for ${\mu }_k(r)$. This proves the lemma. $\square$

2. The Weighted Graph Laplacian

Let

$$B_x:=x+[-h/2,h/2{)}^3,{\omega }_x:=|D_r\cap B_x|,$$

and set

$${\tilde{V}}_r:=\{x\in h{\mathbb{Z}}^3:{\omega }_x>0\},{\tilde{E}}_r:=\{x\sim y:x,y\in {\tilde{V}}_r,|x-y|=h\}.$$

Then $V_r\subset {\tilde{V}}_r\subset V_{r+\sqrt{3}h/2}$. The weighted inner product is

$$⟨f,g{⟩}_{\omega ,r}:=\sum _{x\in {\tilde{V}}_r}f(x)g(x){\omega }_x,\Vert f{\Vert }_{\omega ,r}^2:=⟨f,f{⟩}_{\omega ,r}.$$

The weighted graph Laplacian is

$$L_{\omega }f(x):=h^{-5}\sum _{y\sim x}{\omega }_y(f(y)-f(x)).$$

Its quadratic form is

$$q_{\omega }(f):=⟨-L_{\omega }f,f{⟩}_{\omega ,r}=\frac{h^{-5}}{2}\sum _{x\in {\tilde{V}}_r}\sum _{y\sim x}{\omega }_x{\omega }_y(f(x)-f(y){)}^2.$$

Define the piecewise-constant reconstruction and the cell-average projection by

$$\Pi f:=\sum _{x\in {\tilde{V}}_r}f(x)1_{D_r\cap B_x},{\Pi }^{\ast }g(x):={\omega }_x^{-1}{\int }_{D_r\cap B_x}g(z)dz.$$

Then $\Vert \Pi f{\Vert }_{L^2(D_r)}=\Vert f{\Vert }_{\omega ,r}$.

Lemma 2.1: consistency of cell averages

For every $g\in W^{1,\infty }(D_r)\cap H^1(D_r)$,

$$q_{\omega }({\Pi }^{\ast }g)\le {\int }_{D_r}|\nabla g{|}^{2}dz+Ch\Vert \nabla g{\Vert }_{L^{\infty }(D_r)}^2,$$

and

$$\Vert g-\Pi {\Pi }^{\ast }g{\Vert }_{L^2(D_r)}\le Ch{r}^{1/2}\Vert \nabla g{\Vert }_{L^{\infty }(D_r)}.$$

Proof. Split ${\tilde{V}}_r=V_i\cup V_b$, where

$$V_i:=\{x\in {\tilde{V}}_r:B_x\subset D_r\},V_b:={\tilde{V}}_r\setminus V_i.$$

The boundary set $V_b$ is contained in an $O(h)$-neighborhood of $\partial D_r$, hence $|V_b|\le C{h}^{-2}$. If $x\in V_i$ and $y=x\pm h{e}_j$, then ${\omega }_x={\omega }_y=h^3$ unless $y$ lies in the boundary layer. For an interior edge,

$${\Pi }^{\ast }g(x)-{\Pi }^{\ast }g(y)=h^{-3}{\int }_{B_x}(g(z)-g(z\pm h{e}_j))dz.$$

By Cauchy-Schwarz and the fundamental theorem of calculus,

$$|{\Pi }^{\ast }g(x)-{\Pi }^{\ast }g(y){|}^2\le h^{-3}{\int }_{B_x}{\left|{\int }_0^h{\partial }_{j}g(z\pm s{e}_j)ds\right|}^{2}dz\le h^{-2}{\int }_0^h{\int }_{B_x}|{\partial }_{j}g(z\pm s{e}_j){|}^{2}dzds.$$

Multiplication by the weight factor $h^{-5}{\omega }_x{\omega }_y=h$ and summation over all interior edges gives at most ${\int }_{D_r}|\nabla g{|}^2$. The remaining edges have at least one endpoint in $V_b$. There are $O(h^{-2})$ such edges, and each contributes at most

$$C{h}^{-5}{h}^6(h\Vert \nabla g{\Vert }_{\infty }{)}^2=C{h}^3\Vert \nabla g{\Vert }_{\infty }^2.$$

Thus the total boundary contribution is $O(h)\Vert \nabla g{\Vert }_{\infty }^2$.

For the second estimate, on each cell $D_r\cap B_x$,

$${\int }_{D_r\cap B_x}|g(z)-{\Pi }^{\ast }g(x){|}^{2}dz\le C{h}^2{\omega }_x\Vert \nabla g{\Vert }_{L^{\infty }(D_r)}^2.$$

Summing over $x$ gives $C{h}^2|D_r|\Vert \nabla g{\Vert }_{\infty }^2$. Since $|D_r|=O(r)$, the stated $L^2$ bound follows. $\square$

Lemma 2.2: weighted upper bound

Let ${\lambda }_k(-L_{\omega },r)$ be the $k$th eigenvalue of $-L_{\omega }$ in $L_{\omega }^2({\tilde{V}}_r)$. Then

$${\lambda }_k(-L_{\omega },r)\le \left(1+C_{k}h({\lambda }_k+1{)}^{7/4}+C_{k}r\right){\lambda }_k+C_{k}h{r}^{-1}({\lambda }_k+1{)}^{7/2}.$$

Proof. Let $G_k:=\mathrm{span}({\psi }_0,\dots ,{\psi }_k)$, where ${\psi }_j$ are the Neumann eigenfunctions on $D_r$. The thin-tube elliptic estimate

$$\Vert \nabla g{\Vert }_{L^{\infty }(D_r)}\le C_k{r}^{-1/2}({\mu }_k(r)+1{)}^{7/4}\Vert g{\Vert }_{L^2(D_r)},g\in G_k,$$

is obtained by applying local elliptic estimates to $(-\Delta +1)g$ and rescaling the normal coordinate. Lemma 2.1 gives

$$q_{\omega }({\Pi }^{\ast }g)\le {\int }_{D_r}|\nabla g{|}^{2}dz+C_{k}h{r}^{-1}({\mu }_k(r)+1{)}^{7/2}\Vert g{\Vert }_{L^2(D_r)}^2.$$

The same lemma gives

$$\Vert {\Pi }^{\ast }g{\Vert }_{\omega ,r}=\Vert \Pi {\Pi }^{\ast }g{\Vert }_{L^2(D_r)}\ge \left(1-C_{k}h({\mu }_k(r)+1{)}^{7/4}\right)\Vert g{\Vert }_{L^2(D_r)}.$$

Therefore

$$\frac{q_{\omega }({\Pi }^{\ast }g)}{\Vert {\Pi }^{\ast }g{\Vert }_{\omega ,r}^2}\le \left(1+C_{k}h({\mu }_k(r)+1{)}^{7/4}\right)\frac{{\int }_{D_r}|\nabla g{|}^2}{{\int }_{D_r}|g{|}^2}+C_{k}h{r}^{-1}({\mu }_k(r)+1{)}^{7/2}.$$

Taking the maximum over $G_k$ and then using min-max gives

$${\lambda }_k(-L_{\omega },r)\le \left(1+C_{k}h({\mu }_k(r)+1{)}^{7/4}\right){\mu }_k(r)+C_{k}h{r}^{-1}({\mu }_k(r)+1{)}^{7/2}.$$

Lemma 1.1 replaces ${\mu }_k(r)$ by ${\lambda }_k$ and proves the estimate. $\square$

3. Trilinear Interpolation and the Weighted Lower Bound

Let ${\mathcal{Q}}_h$ be the Cartesian mesh of cubes

$$Q=a+[0,h{]}^3,a\in h{\mathbb{Z}}^3.$$

For a grid function $f$ define $I_{h}f$ to be the standard trilinear interpolant on every cube whose vertices are in the one-layer enlargement of ${\tilde{V}}_r$. On the $O(h)$ boundary layer of $D_r$ we use the restriction of the same local trilinear polynomial. Values needed outside ${\tilde{V}}_r$ are filled by the nearest value in ${\tilde{V}}_r$; this affects only the boundary layer and is estimated below. The resulting function is in $H^1(D_r)$.

Lemma 3.1: one-cube interpolation estimates

Let $Q=a+[0,h{]}^3$ and let $I_{Q}f$ be the trilinear interpolant of the eight nodal values of $f$ on $Q$. Then

$${\int }_Q|\nabla I_{Q}f{|}^{2}dz\le h\sum _{e\subset Q}{c}_e|{\delta }_{e}f{|}^2,0\le c_e\le 1,$$

where the sum is over the twelve edges of $Q$ and ${\delta }_{e}f$ is the difference of the endpoint values. In particular, after summing over full interior cubes, the interpolated energy is bounded by the corresponding graph energy. Moreover,

$${\int }_Q|I_{Q}f-P_{Q}f{|}^{2}dz\le C{h}^2{\int }_Q|\nabla I_{Q}f{|}^{2}dz,$$

where $P_{Q}f$ is the average of $I_{Q}f$ on $Q$.

Proof. Write $z=a+h\xi$, $\xi \in [0,1{]}^3$, and let

$$I_{Q}f(a+h\xi )=\sum _{\alpha \in \{0,1{\}}^3}{f}_{\alpha }\prod _{j=1}^3{\ell }_{{\alpha }_j}({\xi }_j),{\ell }_0(s)=1-s,{\ell }_1(s)=s.$$

For example,

$${\partial }_1{I}_{Q}f=h^{-1}\sum _{{\alpha }_2,{\alpha }_3\in \{0,1\}}(f_{1{\alpha }_2{\alpha }_3}-f_{0{\alpha }_2{\alpha }_3}){\ell }_{{\alpha }_2}({\xi }_2){\ell }_{{\alpha }_3}({\xi }_3).$$

The coefficients in this convex combination are nonnegative and sum to one. Jensen’s inequality gives

$$|{\partial }_1{I}_{Q}f{|}^2\le h^{-2}\sum _{{\alpha }_2,{\alpha }_3}|f_{1{\alpha }_2{\alpha }_3}-f_{0{\alpha }_2{\alpha }_3}{|}^2{\ell }_{{\alpha }_2}({\xi }_2){\ell }_{{\alpha }_3}({\xi }_3).$$

After integration over $Q$, this is bounded by $h$ times a convex weighted sum of the four squared edge differences in the $e_1$ direction. The same argument in the other two coordinate directions proves the gradient estimate. The stated summed form follows because each full-grid edge is counted with total weight at most one. The second estimate is the Poincare inequality on the cube applied to $I_{Q}f$. $\square$

Lemma 3.2: discrete trace estimate in the tube

Let $U_h$ be the union of grid cells meeting the boundary layer $\{z\in D_r:\mathrm{dist}(z,\partial D_r)\le Ch\}$. If $q_{\omega }(f)\le \Lambda \Vert f{\Vert }_{\omega ,r}^2$, then

$$\Vert f{\Vert }_{\omega ,U_h}^2\le C\frac{h}{r}(1+r^2\Lambda )\Vert f{\Vert }_{\omega ,r}^2.$$

Proof. Work in normal coordinates and partition $\Gamma$ into surface patches of diameter comparable to $h$. Above each patch the lattice points form, up to a uniformly bounded overlap, normal strings of length comparable to $r$ and mesh size $h$. It suffices to prove the corresponding one-dimensional statement. For a sequence $a_0,\dots ,a_M$ with $Mh\simeq r$,

$$h\sum _{j\le C}|a_j{|}^2+h\sum _{j\ge M-C}|a_j{|}^2\le C\frac{h}{r}h\sum _{j=0}^M|a_j{|}^2+Chr\sum _{j=0}^{M-1}{\left|\frac{a_{j+1}-a_j}{h}\right|}^{2}h.$$

This follows by writing each boundary value as the average of the string plus the telescoping sum from the boundary to the interior, and then applying Cauchy-Schwarz. Summing these inequalities over the tangential patches gives the stated estimate, because the normal edge contribution is bounded by $q_{\omega }(f)$ and $q_{\omega }(f)\le \Lambda \Vert f{\Vert }_{\omega ,r}^2$. $\square$

Lemma 3.3: interpolation estimate on low-energy subspaces

Suppose $F$ is a finite-dimensional subspace of grid functions such that

$$q_{\omega }(f)\le \Lambda \Vert f{\Vert }_{\omega ,r}^2,f\in F.$$

Then, for all $f\in F$,

$${\int }_{D_r}|\nabla I_{h}f{|}^{2}dz\le (1+Ch)q_{\omega }(f)+C\frac{h}{r}(1+r^2\Lambda )(\Lambda +1)\Vert f{\Vert }_{\omega ,r}^2,$$

and

$$\Vert I_{h}f{\Vert }_{L^2(D_r)}^2\ge \left(1-C{h}^2(\Lambda +1)-C\frac{h}{r}(1+r^2\Lambda )\right)\Vert f{\Vert }_{\omega ,r}^2.$$

Proof. On cubes lying a distance at least $Ch$ from $\partial D_r$, all nodal control volumes have full weight $h^3$. The summed form of Lemma 3.1 bounds the interpolated energy on these cubes by the interior part of $q_{\omega }(f)$ with leading constant one.

It remains to estimate the cubes meeting the boundary layer. Lemma 3.1 bounds their contribution by $Ch$ times the squared edge differences in an $O(h)$ enlargement of that layer. The portion of those edge differences already present in $q_{\omega }$ is absorbed into $(1+Ch)q_{\omega }(f)$. The values inserted in the one-layer extension and the cut-cell terms are controlled by Lemma 3.2; the resulting contribution is

$$C\frac{h}{r}(1+r^2\Lambda )(\Lambda +1)\Vert f{\Vert }_{\omega ,r}^2.$$

This proves the gradient estimate.

For the norm estimate, use the standard mass-lumping estimate for $Q_1$ elements. On a full cube $Q$,

$$\left|{\int }_Q|I_{Q}f{|}^{2}dz-\frac{h^3}{8}\sum _{a\in \mathcal{V}(Q)}|f(a){|}^2\right|\le C{h}^2{\int }_Q|\nabla I_{Q}f{|}^{2}dz,$$

where $\mathcal{V}(Q)$ denotes the eight vertices of $Q$. Summing this estimate over the interior cubes and using the bounded overlap of vertex stars gives

$$\Vert I_{h}f{\Vert }_{L^2(D_r\setminus U_h)}^2\ge \Vert f{\Vert }_{\omega ,r;D_r\setminus U_h}^2-C{h}^2{\int }_{D_r}|\nabla I_{h}f{|}^{2}dz.$$

The part of the mass in $U_h$ is controlled by Lemma 3.2. Combining this trace bound with the gradient estimate already proved gives

$$\Vert I_{h}f{\Vert }_{L^2(D_r)}^2\ge \left(1-C{h}^2(\Lambda +1)-C\frac{h}{r}(1+r^2\Lambda )\right)\Vert f{\Vert }_{\omega ,r}^2.$$

This proves the lemma. $\square$

Lemma 3.4: weighted lower bound

For each fixed $k$,

$${\lambda }_k(-L_{\omega },r)\ge \left(1-C_{k}h({\lambda }_k+1{)}^{7/4}-C_{k}r-C_{k}h{r}^{-1}({\lambda }_k+1{)}^{5/2}\right){\lambda }_k-C_{k}h{r}^{-1}({\lambda }_k+1{)}^{7/2}.$$

Proof. Let $F_k$ be the span of the first $k+1$ eigenvectors of $-L_{\omega }$. By Lemma 2.2,

$${\lambda }_k(-L_{\omega },r)\le C_k({\lambda }_k+1)$$

for $h$ and $r$ sufficiently small. Therefore Lemma 3.3 applies on $F_k$ with $\Lambda =C_k({\lambda }_k+1)$. The lower bound on $\Vert I_{h}f{\Vert }_{L^2(D_r)}$ implies that $I_h$ is injective on $F_k$, so $I_h{F}_k$ has dimension $k+1$. The continuum min-max principle on $D_r$ gives

$${\mu }_k(r)\le \underset{0\ne f\in F_k}{\max }\frac{{\int }_{D_r}|\nabla I_{h}f{|}^{2}dz}{{\int }_{D_r}|I_{h}f{|}^{2}dz}.$$

Using Lemma 3.3 in this quotient yields

$${\mu }_k(r)\le \left(1+C_{k}h({\lambda }_k+1{)}^{7/4}+C_{k}h{r}^{-1}({\lambda }_k+1{)}^{5/2}\right){\lambda }_k(-L_{\omega },r)+C_{k}h{r}^{-1}({\lambda }_k+1{)}^{7/2}.$$

Solving this inequality for ${\lambda }_k(-L_{\omega },r)$ and then applying Lemma 1.1 gives the claimed lower bound. $\square$

4. Passage to the Unweighted Graph

The remaining issue is that $L_{\omega }$ uses cut-cell volumes, whereas $L$ uses the uniform volume $h^3$ on lattice points lying inside $D_r$. Let

$$q_r(f):=⟨-Lf,f{⟩}_r=\frac{h}{2}\sum _{x\in V_r}\sum _{y\sim x}(f(x)-f(y){)}^2.$$

Lemma 4.1: smooth boundary-layer comparison

Let $g\in W^{1,\infty }(D_r)$. Then

$$\left|\Vert {\Pi }^{\ast }g{\Vert }_{\omega ,r}^2-\Vert {\Pi }^{\ast }g{\Vert }_r^2\right|\le Ch\Vert g{\Vert }_{L^{\infty }(D_r)}^2,$$

and

$$\left|q_{\omega }({\Pi }^{\ast }g)-q_r({\Pi }^{\ast }g)\right|\le Ch\Vert \nabla g{\Vert }_{L^{\infty }(D_r)}^2.$$

Proof. If $B_x\subset D_r$, then ${\omega }_x=h^3$ and the two norms coincide at $x$. The norm difference is supported on lattice points whose cubes meet $\partial D_r$. This set has $O(h^{-2})$ elements and each term has size at most $h^3\Vert g{\Vert }_{\infty }^2$, which proves the norm estimate. The form estimate is similar: only boundary-layer edges differ, there are $O(h^{-2})$ of them, and along such an edge

$$|{\Pi }^{\ast }g(x)-{\Pi }^{\ast }g(y)|\le Ch\Vert \nabla g{\Vert }_{\infty }.$$

After multiplication by the graph scaling $h^{-2}$ and the volume weight $h^3$, the total contribution is $O(h)\Vert \nabla g{\Vert }_{\infty }^2$. $\square$

Lemma 4.2: unweighted interpolation lower bound

Suppose $F$ is a finite-dimensional subspace of functions on $V_r$ such that

$$q_r(f)\le \Lambda \Vert f{\Vert }_r^2,f\in F.$$

Then the trilinear interpolant satisfies

$${\int }_{D_r}|\nabla I_{h}f{|}^{2}dz\le (1+Ch)q_r(f)+C\frac{h}{r}(1+r^2\Lambda )(\Lambda +1)\Vert f{\Vert }_r^2,$$

and

$$\Vert I_{h}f{\Vert }_{L^2(D_r)}^2\ge \left(1-C{h}^2(\Lambda +1)-C\frac{h}{r}(1+r^2\Lambda )\right)\Vert f{\Vert }_r^2.$$

Proof. This is the unweighted analogue of Lemma 3.3. On interior cubes the proof is identical, because the unweighted control volume is exactly $h^3$. On cubes meeting $\partial D_r$, the same one-dimensional trace inequality used in Lemma 3.2 gives

$$\Vert f{\Vert }_{r,U_h}^2\le C\frac{h}{r}(1+r^2\Lambda )\Vert f{\Vert }_r^2.$$

This controls both the boundary part of the interpolated energy and the boundary part of the mass. The interior mass comparison is again the $Q_1$ mass-lumping estimate, which gives the $C{h}^2(\Lambda +1)$ term. $\square$

Proof of the main theorem. For the upper bound, use the trial space ${\Pi }^{\ast }{G}_k$, where $G_k=\mathrm{span}({\psi }_0,\dots ,{\psi }_k)$. Lemma 4.1 and the thin-tube elliptic estimates

$$\Vert {\psi }_j{\Vert }_{L^{\infty }(D_r)}\le C_k{r}^{-1/2}({\mu }_k(r)+1{)}^{5/4}\Vert {\psi }_j{\Vert }_{L^2(D_r)},$$ $$\Vert \nabla {\psi }_j{\Vert }_{L^{\infty }(D_r)}\le C_k{r}^{-1/2}({\mu }_k(r)+1{)}^{7/4}\Vert {\psi }_j{\Vert }_{L^2(D_r)}$$

show that replacing $q_{\omega }$ and $\Vert \cdot {\Vert }_{\omega ,r}$ by $q_r$ and $\Vert \cdot {\Vert }_r$ changes the Rayleigh quotient by at most the relative term $C_{k}h{r}^{-1}({\lambda }_k+1{)}^{5/2}$ and the additive term $C_{k}h{r}^{-1}({\lambda }_k+1{)}^{7/2}$. Combining this with Lemma 2.2 yields

$${\lambda }_k(-L,r)\le \left(1+C_{k}h({\lambda }_k+1{)}^{7/4}+C_{k}r+C_{k}h{r}^{-1}({\lambda }_k+1{)}^{5/2}\right){\lambda }_k+C_{k}h{r}^{-1}({\lambda }_k+1{)}^{7/2}.$$

For the lower bound, let $F_k$ be the span of the first $k+1$ eigenvectors of $-L$ on $V_r$. The upper bound just proved implies

$${\lambda }_k(-L,r)\le C_k({\lambda }_k+1)$$

for small $h$ and $r$. Therefore Lemma 4.2 applies to $F_k$ with $\Lambda =C_k({\lambda }_k+1)$. Since $I_h$ is injective on $F_k$, the min-max principle on $D_r$ gives

$${\mu }_k(r)\le \underset{0\ne f\in F_k}{\max }\frac{{\int }_{D_r}|\nabla I_{h}f{|}^{2}dz}{{\int }_{D_r}|I_{h}f{|}^{2}dz}.$$

Using Lemma 4.2 in this quotient and then solving for ${\lambda }_k(-L,r)$ gives

$${\lambda }_k(-L,r)\ge \left(1-C_{k}h({\lambda }_k+1{)}^{7/4}-C_{k}r-C_{k}h{r}^{-1}({\lambda }_k+1{)}^{5/2}\right){\lambda }_k-C_{k}h{r}^{-1}({\lambda }_k+1{)}^{7/2},$$

where Lemma 1.1 was used to replace ${\mu }_k(r)$ by ${\lambda }_k$. The two inequalities prove the asserted estimate. Taking $r\asymp h^{1/2}$ proves the corollary for fixed $k$. $\square$

Numerical Check

For the unit sphere $\Gamma =S^2$, the Laplace-Beltrami spectrum is $\ell (\ell +1)$ with multiplicity $2\ell +1$. Thus

$${\lambda }_1={\lambda }_2={\lambda }_3=2,{\lambda }_4=\cdots ={\lambda }_8=6.$$

The numerical experiment uses the spherical shell $||x|-1|<r$ with $r=n^{-1/2}$ and lattice resolutions

$$n=8,16,24,32,40,48,56,64.$$

The figure uses actual sparse graph eigenvalues computed by block LOBPCG for $-L$, with the constant vector constrained out. Projected spherical harmonics are used only as initial guesses for the iteration, not as a prescribed eigenspace. For the plotted modes the largest relative residual is about $5.1\times 10^{-4}$.

The log-log error plot is consistent with the predicted $n^{-1/2}$ scale. The fourth eigenvalue converges more slowly because it is the first member of the five-dimensional $\ell =2$ eigenspace and is more visibly affected by the cubic anisotropy of the lattice.

See Also

• on degree of mapping and Lipschitz constant --- Both use volume distortion estimates to pass between local and global geometric information.
• on Moser iteration --- Bootstrap and trace estimates of the same type appear when controlling discrete eigenfunctions uniformly.