Royal Society Publishing

On the convergence of second-order spectra and multiplicity

Lyonell Boulton, Michael Strauss

Abstract

The notion of second-order relative spectrum of a self-adjoint operator acting on a Hilbert space has been studied recently in connection with the phenomenon of spectral pollution in the Galerkin method. In this paper we examine how the second-order spectrum encodes precise information about the multiplicity of the isolated eigenvalues of the underlying operator. Our theoretical findings are supported by various numerical experiments on the computation of guaranteed eigenvalue inclusions via finite element bases.

1. Introduction

Let A be a self-adjoint operator acting on an infinite-dimensional Hilbert space Embedded Image and let λ be an isolated eigenvalue of A. For Embedded Image let Embedded Image, where Eμ is the spectral measure associated to A. The numerical estimation of λ, whenever Embedded Image constitutes a serious challenge in computational spectral theory. Indeed, it is well established that classical approaches, such as the Galerkin method, suffer from variational collapse under no further restrictions on the approximating space and therefore might lead to spectral pollution (see Rappaz et al. 1997; Dauge & Suri 2002; Lewin & Séré 2010; and references therein).

The notion of second-order relative spectrum, originated from Davies (1998), has recently allowed the formulation of a general pollution-free strategy for eigenvalue computation. This was proposed by Shargorodsky (2000) and subsequently examined by Levitin & Shargorodsky (2004), Boulton (2007), Boulton & Strauss (2007) and Strauss (in press). Numerical implementations of the general principle very much preserve the spirit of the Galerkin method and have presently been tested on applications from Stokes systems (Levitin & Shargorodsky 2004), solid-state physics (Boulton & Levitin 2007), magnetohydrodynamics (Strauss in press) and relativistic quantum mechanics (Boulton & Boussaid 2010).

In this paper we further examine the potential role of this pollution-free technique for robust computation of spectral inclusions. Our goal is twofold. On the one hand, we establish various abstract properties of limit sets of second-order relative spectra. On the other hand, we report on the outcomes of various numerical experiments. Both our theoretical and practical findings indicate that second-order spectra provide reliable information about the multiplicity of any isolated eigenvalue of A.

Section 2 is devoted to reformulating some of the concepts around the notion of second-order spectra in order to allow a more general setting. In this framework, we consider the natural notion of algebraic and geometric multiplicity of second-order spectral points (definition 2.2) and establish a ‘second-order’ spectral mapping theorem (lemma 2.6).

In §3 we pursue a detailed analysis of accumulation points of the second-order relative spectra on the real line. Our main contribution (theorem 3.4) is a significant improvement upon similar results previously found. It allows calculation of rigorous convergence rates when the test subspaces are generated by a non-orthogonal basis. Concrete applications include the important case of a finite-element basis, which was not covered by theorem 2.1 of Boulton (2007). Our present approach relies upon a homotopy argument, which yields a precise control on the multiplicity of the second-order spectral points. The argument is reminiscent of the method of proof of Goerisch theorem (see Plum 1990).

Theorem 3.4 also determines the precise manner in which second-order spectra encode information about the multiplicity of points in the spectrum of A. When an approximating space is ‘sufficiently close’ to the eigenspace corresponding to an eigenvalue of finite multiplicity, a finite set of conjugate pairs in the second-order spectrum becomes ‘isolated’ and clusters near the eigenvalue. It turns out that the total multiplicity of these conjugate pairs exactly matches the multiplicity of the eigenvalue. This indicates that second-order spectra capture, in a reliable manner, points to the discrete spectrum and their multiplicities, even under the above variational collapse condition. In §4 we examine the practical validity of this statement on benchmark differential operators for subspaces generated by a basis of finite elements.

A final appendix is aimed at finding the minimal region in the complex plane where the limit of second-order spectra is allowed to accumulate. It turns out that, modulo a subset of topological dimension zero, this minimal region is completely determined by the essential spectrum of A. This gives an insight on the difficulties involving the problem of finding conditions on the test subspaces to guarantee convergence to the essential spectrum.

(a) Notation

Below we will denote by D(A) the domain of A and by Spec(A) its spectrum. We decompose Spec(A) in the standard manner as the union of essential and discrete spectrum (see Kato 1980), and denote Embedded Image. Recall that the discrete spectrum is the set of isolated eigenvalues of finite multiplicity of A.

Let Embedded Image. Below Embedded Image will be the open disc in the complex plane with centre (a+b)/2 and radius (ba)/2, and Embedded Image. We allow Embedded Image or Embedded Image in the obvious way to denote half-planes or the whole of Embedded Image. For b=a, Embedded Image and Embedded Image.

Let Embedded Image be a Hilbert space. Let Embedded Image be an arbitrary subset and let Embedded Image be a finite subset. We will often writeEmbedded ImageHere, we include the possibility of Embedded Image and write Embedded Image.

Let Embedded Image. We endow D(Ap) with the graph inner product defined for all u,v∈D(Ap) as Embedded Image. By construction, (D(Ap),〈·,·〉p) is a Hilbert space with the associated norm denoted by ∥·∥p. Below we will consider sequences of finite-dimensional subspaces Embedded Image growing towards D(Ap) with a given density property determined as follows:Embedded ImageNote that if Embedded Image, then Λ0=Λp for any Embedded Image. If Embedded Image and Embedded Image, then Embedded Image is dense norm ∥·∥p.

For a family of closed subsets Embedded Image, the limit set of this family is defined asEmbedded ImageThe limit set of a family of closed subsets is always closed.

Let Embedded Image be a basis for a subspace Embedded Image. Without further mention, we will identify Embedded Image with a corresponding Embedded Image via: Embedded Image and Embedded Image, where Embedded Image is the basis conjugate to {bj}. If the vectors bj are mutually orthogonal and ∥bj∥=1, then Embedded Image. Below the orthogonal projection onto Embedded Image is denoted by Embedded Image. When referring to sequences of subspaces Embedded Image we will use Pn instead. Clearly Embedded Image iff PnI strongly.

(b) Toy models of spectral pollution in the Galerkin method

We now present a series of examples which will later illustrate our main results. We follow theorem 2.1 of Levitin & Shargorodsky (2004) and remark 2.5 of Lewin & Séré (2010). Here and below we denote |v〉〈w|(u)=〈u,wv.

Example 1.1

Let Embedded Image. Let Embedded Image be an orthonormal set of vectors and let Embedded Image. Let Embedded Image defined in its maximal domain, where Embedded Image. Then, Embedded Image and so Embedded Image. Note that the resolvent of A is compact.

Example 1.2

If A is strongly indefinite and it has a compact resolvent, then there exists a sequence Embedded Image for all Embedded Image, such that Embedded Image Indeed, let Embedded Image where the eigenvalues are repeated according to multiplicity with Embedded Image and Embedded Image. Let Embedded Image be eigenvectors associated to Embedded Image and assume that Embedded Image is an orthonormal set. Let Embedded Image be an ordering of Embedded Image. For each Embedded Image, choose Embedded Image with λk<γj<λ+k for 1≤jn. Let θj∈(−π,π] be such that Embedded Image for 1≤jn and define Embedded Image The desired conclusion holds by taking Embedded Image

Example 1.3

Let Embedded Image and Embedded Image be as in example 1.1. Let Embedded Image For r>0, define Embedded Image in its maximal domain. Then Specess(A)={−1} and Embedded Image. It is not difficult to see that now Embedded Image where −1 is an eigenvalue of multiplicity n. Then, if r=2, the origin is an accumulation point of Embedded Image. Note that the resolvent of A is not compact and A is now semi-bounded below.

2. The second-order spectra of a self-adjoint operator

Definition 2.1

(see Levitin & Shargorodsky 2004). Given a non-trivial subspace Embedded Image, the second-order spectrum of A relative to Embedded Image is the setEmbedded Image

If Embedded Image, thenEmbedded ImageTypically, Embedded Image contains non-real points. From the definition, it follows that Embedded Image if and only if Embedded Image.

(a) Algebraic and geometric multiplicity

Let Embedded Image where the bj are linearly independent. Let Embedded Image be matrices with entries given byEmbedded Image2.1and Q(z)=B−2zL+z2M. It is readily seen that Embedded Image if and only ifEmbedded Image2.2By definition 2.1, Embedded Image is independent of the basis chosen. Since Embedded Image, it follows that Embedded Image consists of at most 2n points.

The quadratic eigenvalue problem (2.2) may be solved via suitable linearizations (see Gohberg et al. 2005). One such linearization is given by the matricesEmbedded ImageClearly, Embedded Image if and only if Embedded Image for some Embedded Image. Equivalently, one can consider the matrix Embedded Image whereEmbedded Image2.3so that Embedded Image. LetEmbedded ImageA straightforward calculation yields Embedded Image, so Q(z)⊕(−I) and Embedded Image are equivalent in the sense of matrix polynomials.

Every matrix polynomial is known to be equivalent to a diagonal matrix polynomial diag[i1(z),i2(z), … ,ir(z),0, … ,0], where the diagonal entries ij(z) are polynomials of the form Πk(zzjk)βjk with the property that ij(z) is divisible by ij−1(z). The factors (zzjk)βjk are called elementary divisors and the zjk are the eigenvalues. The degrees of the elementary divisors associated to a particular eigenvalue z0 are called the partial multiplicities at z0 (see Gohberg et al. 2005). For a linear matrix polynomial, such as Embedded Image, the degrees of the elementary divisors associated to a particular eigenvalue z0 coincide with the sizes of the Jordan blocks associated to z0 as an eigenvalue of Embedded Image. The notion of multiplicity of an eigenvalue now follows from the fact that two n×n matrix polynomials are equivalent if and only if they have the same collection of elementary divisors (see Gohberg et al. 2005, theorem A.6.2).

Definition 2.2

The geometric and algebraic multiplicities of Embedded Image are defined to be the geometric and algebraic multiplicity of z as an eigenvalue of Embedded Image.

Note that definition 2.2 is independent of the basis used to assemble the matrices B,L,M and Embedded Image. Indeed, let B,L,M be assembled with respect to a basis Embedded Image and Embedded Image with respect to a basis Embedded Image, where Embedded Image. Then,Embedded Imagewhere Nij=〈cj,b*i〉, and therefore Embedded Image and Embedded Image are equivalent.

(b) The approximate spectral distance

Suppose that the given basis Embedded Image of Embedded Image is orthonormal so that M=I in (2.1) and Q(z)=B−2zL+z2I. For Embedded Image, we define Embedded Image. The right-hand side of this expression is independent of the orthonormal basis chosen for Embedded Image. If Embedded Image, then Embedded Image and for Embedded Image we have Embedded Image. Furthermore, Embedded Image if and only if Embedded Image. The map Embedded Image is a Lipschitz subharmonic function (Davies 1998; Boulton 2007). Therefore, Embedded Image is completely characterized via the maximum principle.

(c) The spectrum and the second-order spectra

Let Embedded Image and Embedded Image. For all Embedded Image,Embedded Image2.4(see Shargorodsky 2000; Strauss in press). Thus, Embedded Image is a subset of Embedded Image for any sequence Embedded Image.

A growing interest in the second-order relative spectrum and corresponding limit sets has been stimulated by the following property: if Embedded Image, thenEmbedded Image2.5(see Levitin & Shargorodsky 2004; also lemma 2.3 below). Thus,Embedded Image2.6Therefore, intervals of inclusion for points in the spectrum of A can be obtained from Re z with a two-sided explicit residual given by |Im z|.

In fact, the order of magnitude of the residue in the approximation of Spec(A) by projecting Embedded Image into Embedded Image can be improved to |Im z|2, if some information on the localization of Spec(A) is at hand. Indeed, if Embedded Image and Embedded Image with Embedded Image, thenEmbedded Image2.7(see Boulton & Levitin 2007; Strauss in press).

The following lemma is an improvement upon theorem 5.2 of Shargorodsky (2000). It immediately implies equation (2.5).

Lemma 2.3

Let Embedded Image be such that Embedded Image. If Embedded Image, then Embedded Image whereEmbedded Image2.8

Proof.

Without loss of generality assume that Im z≥0, and consider the triangle Δazb. Let θ be the angle of Δazb at z. Since Embedded Image, then π/2<θπ. Let θ1 and θ2 be the angles at b and a. Then θ+θ1+θ2=π. The region Fz:={μz:μ∈Spec(A)} is contained in two sectors, one between the real line and the ray re−iθ1 (r≥0), the other between the real line and rei(π+θ2), where 0≤θ1+θ2<π/2. We have Embedded Image, and by the cosine rule, Embedded Image. Now Embedded Image is contained in a sector between the rays re−i2θ1 and rei2θ2. ThereforeEmbedded ImageBy virtue of the spectral theorem,Embedded ImageThe result follows from the Cauchy–Schwarz inequality.  ■

If Embedded Image, it follows from equation (2.5) that Embedded Image does not intersect Embedded Image. Therefore, Embedded Image. We now consider two examples where Embedded Image. The first one has a compact resolvent while the second one has −1 in the essential spectrum.

Example 2.4

Suppose that Embedded Image, Embedded Image and A are as in example 1.1. It is readily seen that Embedded Image.

Example 2.5

Suppose that Embedded Image, Embedded Image and A be as in example 1.3. It is readily seen that Embedded Image, where Embedded Image and Embedded Image. The geometric multiplicity of the second-order spectral point −1 is n−1 and its algebraic multiplicity is 2(n−1). As Embedded Image, the non-real point αn±iγnβ, where β=−1 for 0<r<1, β=−1±i for r=1 and Embedded Image for r>1. Hence, Embedded Image for r≠1.

(d) Mapping of second-order spectra

Lemma 2.6

For Embedded Image, let f(w)=aw+b, g(w)=cw+d and F(w)=f(w)g(w)−1. If ad≠cb and Embedded Image, thenEmbedded Image2.9Moreover, the algebraic and geometric multiplicities of z and F(z) coincide.

Proof.

Since g(A) preserves linear independence, a set of vectors Embedded Image is a basis for Embedded Image if and only if the corresponding set Embedded Image is a basis for Embedded Image. Let Embedded Image. It is readily seen that Embedded Image. Let Embedded Image, Embedded Image and Embedded Image. Then, Embedded Image for any Embedded Image, obtaining the left side from Embedded Image and the right side from {bj}. Let BLM be as in (2.1) for A and {bj}. Let Embedded Image be as in (2.1) for F(A) and Embedded Image. Let Embedded Image. ThenEmbedded ImageHere Embedded Image are arbitrary, so we deduce thatEmbedded Image2.10Thus, Embedded Image, and moreover, since the function (adcb)−2g(w)2 is analytical and non-zero at z, the algebraic and geometric multiplicities of z and F(z) are the same (see Gohberg et al. 2005, theorem A.6.6).  ■

3. Multiple points of the second-order spectra

(a) Neighbourhoods of the discrete spectrum

Throughout this section we assume thatEmbedded Image3.1Let 1j=1(λjε,λj+ε)(A), where ε>0 is small enough so that mj:=Rank(1j) is equal to the multiplicity of λj. Let Embedded Image be the total multiplicity of the group of eigenvalues λ1, … ,λs. We will denote by Embedded Image the eigenspace associated to the group of eigenvalues in (a,b), that is, Embedded Image. We fix orthonormal bases Embedded Image of Rank 1j and let Embedded Image be a corresponding basis of Embedded Image.

Lemma 3.1

Let Embedded Image. LetEmbedded Image3.2If the subspace Embedded Image is such thatEmbedded Imagethen Embedded Image.

Proof.

Let Embedded Image. Define Embedded Image where Embedded Image. Then Embedded Image is self-adjoint and Embedded Image. LetEmbedded Imagethen K(z) is a finite rank operator with range Embedded Image and Embedded Image. Evidently, Embedded Image is invertible and for all Embedded Image we haveEmbedded Imagewhere Embedded Image.

Let Embedded Image. For each eigenvector Embedded Image we assign a Embedded Image such that Embedded Image for p=0,1,2. In general Embedded Image; however, Embedded Image. The hypothesis on δ ensures thatEmbedded Imagewhere Embedded Image and Embedded Image.

Note that Embedded Image satisfies the hypothesis of lemma 2.3. Let α(z) be given by equation (2.8). ThenEmbedded Imagewhere β3(z)=α(z)−1|cz|−2[β2(z)+2|cz|2+α(z)]. ThusEmbedded ImageHence, for any Embedded Image,Embedded Image

LetEmbedded ImageThen Embedded Image. ThusEmbedded ImageThereforeEmbedded Image  ■

Lemma 3.2

Let λ∈Specdis(A) be an eigenvalue of multiplicity m. Denote by dλ=dist(λ,Spec(A)\{λ}). If Embedded Image, thenEmbedded Image3.3and λ as member of Embedded Image has geometric multiplicity m and algebraic multiplicity 2m.

Proof.

Assume that Embedded Image and zλ. Then, there exists a normalized Embedded Image, such that Embedded Image for all Embedded Image. In particular 〈u,uk〉=0 for each Embedded Image. If we take w=u above, thenEmbedded ImageThus, |Im z|=∥(A−Re z)u∥≠0 and 〈(A−Re z)u,u〉=0, so thatEmbedded ImageSince Embedded Image,Embedded Imagehowever, the right-hand side is strictly less that dλ, and equation (3.3) follows from the contradiction.

Let Embedded Image be a basis for Embedded Image and let B, L and M be the matrices (2.1) associated to this basis. Let v be can arbitrary member of Embedded Image. ThenEmbedded Imageso that Embedded Image. Hence,Embedded ImageSince Embedded Image, Embedded Image are eigenvectors of Embedded Image corresponding to the eigenvalue λ. For kj we have Embedded Image, so the vectors Embedded Image are linearly independent. There is a one-to-one correspondence between the eigenvectors of Embedded Image associated to λ and the eigenvectors of A associated to λ. Thus, the geometric multiplicity of Embedded Image is equal to m.

We now compute the algebraic multiplicity. Let Embedded Image and Embedded Image. IfEmbedded Imagethen Embedded Image and Embedded Image. ThereforeEmbedded ImagesoEmbedded Imagewhere Embedded Image. IfEmbedded Imagethen Embedded Image and Embedded Image. Therefore, Embedded Image. Thus, Embedded Image so that Embedded Image. This ensures that the spectral subspace associated with λ as eigenvalue of Embedded Image is given byEmbedded Image  ■

Lemma 3.3

Let Embedded Image be a Hilbert space and Embedded Image be a set of orthogonal vectors with Embedded Image for 1≤j≤m. Let Embedded Image be an n-dimensional subspace of Embedded Image where n≥m. Let Embedded Image, where Embedded Image is the orthogonal projection associated to Embedded Image. Let wj(t)=twj+(1−t)uj for t∈[0,1]. If Embedded Image for each 1≤j≤m, then there exist vectors {wm+1, … ,wn}, such that {w1(t), … ,wm(t),wm+1, … ,wn} is linearly independent for all t∈[0,1].

Proof.

If a1w1+⋯+amwm=0, where not all of the aj=0, we would haveEmbedded Imagewhich contradicts Hölder’s inequality. Hence, necessarily {w1, … ,wm} is linearly independent. Let {wm+1, … ,wn} be any completion of {w1, … ,wm} to a basis of Embedded Image. Let t∈[0,1]. Suppose now that a1w1(t)+⋯+amwm(t)+am+1wm+1+⋯+anwn vanishes. ThenEmbedded ImageThe two terms on the right-hand side are orthogonal and therefore each must vanish. As the set {w1, … ,wn} is linearly independent, all aj=0.  ■

(b) The main result

Theorem 3.4

Let a,b∉Spec(A). Assume that condition (3.1) holds for a group of eigenvalues {λ1< … <λs} with corresponding multiplicities mj and their total multiplicity is Embedded Image. Let Embedded Image. Let κ=d2/γ where γ is defined by equation (3.2). LetEmbedded ImageIf Embedded Image is such that Embedded Image for an orthonormal set of eigenfunctions Embedded Image associated to Embedded Image, thenEmbedded Image3.4and the total algebraic multiplicity of Embedded Image is 2mj.

Proof.

Let Embedded Image and Embedded Image, thenEmbedded ImageIn order to find the right-hand side, we may assume without loss of generality that a=−r and b=r. If z=x+iy where x2+y2=r, thenEmbedded ImageWe also assume that x≥0 as the case where x<0 can be treated analogously. A straightforward calculation yieldsEmbedded Imagehence lemma 3.1 applied to the interval Embedded Image ensures (3.4).

We now prove the second part of the theorem. Let Embedded Image, Embedded Image and define subspaces Embedded Image for t∈[0,1] (see lemma 3.3). Note that Embedded Image is also an orthogonal set in D(A2) and Embedded Image. Since κε2<m−1/2, we get Embedded Image for all t∈[0,1]. Now,Embedded Imagethus Embedded Image, and by virtue of lemma 3.1 we obtainEmbedded ImageDenote by Embedded Image the linearization matrix defined as in equation (2.3) for Embedded Image. According to lemma 3.2, the algebraic multiplicities of Embedded Image is 2mj. If we let πj(t) be the spectral projection associated to Embedded Image thenEmbedded ImageThus, πj(t)→πj(1) as t→1. By virtue of lemma 4.10 of §1.4.6 in Kato (1980), it is guaranteed that Rank πj(0)=Rank πj(1).  ■

An immediate consequence of theorem 3.4 is the fact that, if a sequence of test subspaces Embedded Image approximates a normalized eigenfunction u associated to a simple eigenvalue λ at a given rate in the graph norm of A2, ∥uunD(A2)=δ(n)→0 for Embedded Image, then there exist a conjugate pair Embedded Image such that |λzn|=O(δ1/2). Simple examples show that this estimate is sub-optimal.

Example 3.5

Let Embedded Image. Let Embedded Image, where Embedded Image and βn→0. Then Embedded Image where γninβn for Embedded Image. On the other hand, ∥Ap((αn−1)e0+βnen)∥∼npβn for p=0,1,2. Thus, |γn|∼n while Embedded Image. Moreover, we observe that in general Embedded Image might diverge as Embedded Image and still we might be able to recover |γn|→0; take for instance βn=1/n3/2.

An application of lemma 2.6 yields convergence to eigenvalues under the weaker assumption Embedded Image.

Corollary 3.6

Let Embedded Image be such thatEmbedded Image. If Embedded Image, then Embedded Image.

Proof.

Pick ε>0 such that Embedded Image. Let μ∈(a,a+ε). Let g(w)=wμ and h(z)=g(z)−1. The operator h(A) is bounded and g(w) satisfies the hypothesis of lemma 2.6. Let Embedded Image. Then Embedded Image. Indeed, any Embedded Image can be expressed as u=g(A)v for v∈D(A), and since Embedded Image, we can find Embedded Image such that g(A)vng(A)v. By virtue of theorem 3.4,Embedded ImageThe fact that g(w) is a conformal mapping, lemma 2.6 and the spectral mapping theorem ensure the desired conclusion.  ■

Example 3.7

Let A be the operator of examples 1.3 and 2.5. By virtue of (2.5) and corollary 3.6, Embedded Image for any Embedded Image.

Corollary 3.8

Let A be an operator with a compact resolvent. For all Embedded Image, Embedded Image .

When A is not semi-bounded, this statement is in stark contrast to Example 1.2.

4. Numerical applications

The identity (2.6) leads to guaranteed intervals of enclosures for λ∈Specdisc(A). Theorem 3.4 yields a priori upper bounds for the length of these enclosure in terms of bounds on the distance from the test space, Embedded Image, to an orthonormal basis of eigenfunctions Embedded Image. In practice, these upper bounds are computed from interpolation estimates for bases of Embedded Image. We now examine various aspects of the applicability of these results.

(a) On multiplicity and approximation

Suppose that λ is of multiplicity m, so that (3.4) ensures an upper bound on the estimation of λ by m conjugate pairs of Embedded Image. If Embedded Image captures well a basis of only l<m eigenfunctions and rather poorly the remaining ml elements of Embedded Image, then it would be expected that only l conjugate pairs of Embedded Image will be close to λ while the remaining ml will lie far from this eigenvalue. We can illustrate this locking effect on the multiplicity in a simple numerical experiment.

Let Embedded Image subject to Dirichlet boundary conditions on Embedded Image. Then Embedded Image and a family of eigenfunctions is given by Embedded Image. Some eigenvalues of A are simple and some are multiple. In particular, the ground eigenvalue 2=1+1 is simple and 1+k2 for k=2,3,4,5 are double. Contrast between the two eigenfunctions uk1 and u1k will increase as k increases. The former will be highly oscillatory in the x-direction while the latter will be so in the y-direction. If Embedded Image captures well oscillations in only one direction, we should expect one conjugate pair of Embedded Image to be close to 1+k2 and the other to be not so close to this eigenvalue.

In order to implement a finite element scheme for the computation of the second-order spectra of the Dirichlet Laplacian, the condition Embedded Image prescribes the corresponding basis to be at least C1-conforming. We let Embedded Image be generated by a basis of Argyris elements on given triangulations of Ω. Contrast between the residues in the interpolation of u1k and uk1 is achieved by considering triangulation that are stretched either in the x or in the y direction (figure 1b).

Figure 1.

(a) Change in the length of the enclosure predicted by (2.6) for the eigenvalues λ=1+k2 of the two-dimensional Dirichlet Laplacian on [0,π]2. (b) Corresponding mesh for the first six iterates of (a) graph.

Below, we generate triangulations with a fixed total number of 240 elements, resulting from diagonally bisecting a decomposition of Ω as the union of 120 rectangles of equal ratio. We consider mesh with s=3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30 and 40 elements of equal size on the lower edge Embedded Image. We then compute the pairs Embedded Image, which are closer to the eigenvalues 1+k2 than to any other point in Spec(A). We know that Re z1k(s)±|Im z1k(s)| and Re zk1(s)±|Im zk1(s)| are guaranteed bounds for this eigenvalue.

Even though we have the same number of elements in each of the above mesh, in general they do not have the same amount of elements intersecting ∂Ω. Then typically Embedded Image for st, although these numbers do not differ substantially. The precise dimension of the test spaces are: Embedded Image, Embedded Image, Embedded Image, Embedded Image, Embedded Image and Embedded Image.

In figure 1 we have depicted the residues 2|Im z1k(s)| and 2|Im zk1(s)| for each one of the eigenvalues 1+k2 in the vertical axis, versus s in the horizontal axis on a semi-log scale. The graph suggests that the order of approximation for all the eigenvalues changes by at least two orders of magnitude as s varies. The minimal residue in the approximation of the ground eigenvalue is achieved when s=10 and s=12. This corresponds to low contrast in the basis of Embedded Image. When the eigenvalue is multiple, however, the minimal residue is achieved by increasing the contrast in the basis. As this contrast increases, one conjugate pair will get closer to the real axis while the other will move away from it. The greater the k is, the greater contrast is needed to achieve a minimal residue and the further away the conjugate pairs travel from each other.

This experiment suggests a natural extension for theorem 3.4. If only l<m members of Embedded Image are close to Embedded Image, then only l conjugate pairs on Embedded Image will be close to the corresponding eigenvalue. At present it is not clear whether a more precise statement in this respect can be formulated along the lines of theorem 3.4.

(b) Optimality of convergence to eigenvalues

We saw in example 3.5 that the upper bound established in theorem 3.4 is sub-optimal. We now examine this assertion from a computational perspective.

Let Embedded Image acting on Embedded Image, where V is a smooth real-valued bounded potential. Let D(A)={uH2[0,π]:u(0)=u(π)=0}, so that A defines a self-adjoint semi-bounded operator. Note that λ∈Spec(A)=Specdisc(A) if and only if λ solves the Sturm–Liouville eigenvalue problem Au=λu subject to homogeneous Dirichlet boundary conditions at 0 and π.

Let Ξ be an equidistant partition of [0,π] into n sub-intervals Il=[xl−1,xl] of length h=π/n=xlxl−1. LetEmbedded Imagebe the finite element space generated by Ck-conforming elements of order r subject to Dirichlet boundary conditions at 0 and π. An implementation of standard interpolation error estimates for finite elements combined with theorem 3.4 ensures the following.

Lemma 4.1

Let A, Embedded Image and Embedded Image be as above. Let Spec(A)={λ12< … }. Let aj= (1/4)λj+(3/4)λj−1 and bj=(1/4)λj+(3/4)λj+1, where Embedded Image. For all r>k≥3, there exist a constant c>0, dependent on j, k and r, but independent of h, such that Embedded Image for all h>0 sufficiently small.

Proof.

Use the well-known estimate ∥vvhHp[0,π]chr+1−p, where Embedded Image is the finite element interpolant of Embedded Image and note that all eigenvalues of A are simple while their associated eigenfunctions are Embedded Image.  ■

Therefore, each individual eigenvalue λj is approximated by second-order spectral points at a rate O(h(r−3)/2) for test subspaces generated by a basis of C3-conforming finite elements of order r>4. Because of the high regularity required on the approximating basis, this result is only of limited practical use. In fact, only k≥1 (and r≥3) is required for Embedded Image. The following simple numerical experiment confirms that the exponent predicted by lemma 4.1 can be improved.

Example 4.2

Suppose that V =0 so that Embedded Image. In figure 2 we have fixed an equidistant partition Ξ and let Embedded Image be the space of Hermite elements of order r=3,4,5 satisfying Dirichlet boundary conditions in 0 and π. We then find the conjugate pairs Embedded Image, which are close to λj=j2 in Spec(A) for j=1,2,3,4,5.

Figure 2.

See example 4.2. (a) Log–log plot of 2|Im zh1r(j)| versus element sizes. (b) Value of p such that |Im zh1r(j)|∼hp found via linear fittings. Black, order 3; dark grey, order 4; light grey, order 5; line with circles, λ=1; line with crosses, λ=4; line with triangles, λ=9; line with squares, λ=16; line with crosses, λ=25.

Example 4.3

The previous example suggests an order of approximation of the eigenvalue λ from its closest Embedded Image of Embedded Image Indeed, interpolation by Hermite elements of order r has an H2-error proportional to hr−1. The same convergence rate is confirmed by example 3.5. Let Embedded Image be the Mathieu potential. Let Embedded Image be as in example 4.2. The exponents p reported in table 1 further confirm this conjecture.

View this table:
Table 1.

Eigenvalue enclosures for the Mathieu Schrödinger operator. See examples 4.3 and 4.4. We have computed the enclosures of λj by direct application of (2.6) and by the improved bound (2.7). Here, Embedded Image has been chosen.

It is well established that the error in the estimation of the eigenvalues of a one-dimensional elliptic problem of order 2p by the Galerkin method using Hermite elements of order r is proportional to h2(r+1−p). If A is a second-order differential operator, the quadratic eigenvalue problem (2.2) gives rise to a non-self-adjoint fourth-order problem, which is to be solved by a projection-type method. Thus, example 4.3 is consistent with this estimate if we consider the improved enclosure (2.7).

(c) Improved accuracy

Guaranteed enclosures for λ∈Specdisc(A) can be improved by combining (2.7) with (2.6). For this we should find an upper bound Embedded Image, a lower bound Embedded Image and Embedded Image such that Embedded Image Here μ and ν can be elements of the discrete or the essential spectrum of A. The preliminary bounds a and b can be found from Embedded Image or by analytical means. If ba is sufficiently large and |Im z| is sufficiently small, then (2.7) improves upon (2.6). This technique can be implemented as follows.

Example 4.4

Let Embedded Image, Embedded Image and Embedded Image for r=3,4,5 be as in examples 4.2 and 4.3. In table 1 we have computed inclusions for the first five eigenvalues of A by directly employing (2.6) and by the technique described in the previous paragraph. In the latter case, we have found aj=a from the computed upper bound for λj−1<λj (Embedded Image) using (2.6). Similarly for bj=b. Compare these calculations with those of Arbenz (1983).

We can also consider an example from solid-state physics to illustrate the case where μ and ν are not in the discrete spectrum.

Example 4.5

Let Embedded Image on Embedded Image, where Embedded Image. Then A is a semi-bounded operator but now Specess(A) consists of an infinite number of non-intersecting bands, separated by gaps, determined by the periodic part of the potential. The endpoints of these bands can be found analytically. They correspond to the so called Mathieu characteristic values. The addition of a fast decaying perturbation gives rise to a non-trivial discrete spectrum. Non-degenerate isolated eigenvalues can appear below the bottom of the essential spectrum or in the gaps between bands.

In table 2 we report on computation of inclusions for the first three eigenvalues in Specdisc(A): Embedded Image, λ2 in the first gap of the essential spectrum and λ3 in the second gap. No other eigenvalue is to be found in any of these gaps. Here Embedded Image is the space of Hermite elements of order 3 on a mesh of 20l segments of equal size h=0.1 in [−l,l] subject to Dirichlet boundary conditions at ±l. For the improved enclosure, a and b are approximations of the endpoints of the gaps where the λj lie.

View this table:
Table 2.

Enclosures for eigenvalues of the perturbed periodic Schrödinger operator. Enclosures for the first three eigenvalues of the operator in example 4.5. The numerical values of a and b are found in Abramowitz & Stegun (1964).

Since the eigenvectors of A decay exponentially fast as Embedded Image, the members of Specdisc(A) are close to eigenvalues of the regular Sturm–Liouville problem Au=λu, subject to u(−l)=u(l)=0, for sufficiently large Embedded Image. The numerical method considered in this example does not distinguish between the Embedded Image and the large Embedded Image eigenvalue problem. For instance, the inclusion found for λ1 is also an inclusion for the Dirichlet ground eigenvalue of Embedded Image. In the case of λ2 and λ3, which lie in gaps of Specess(A), they should be close to high-energy eigenvalues of the finite interval problem. Indeed, for the parameters considered in table 2, the inclusion for λ2 is also an inclusion for the 17th eigenvalue of Embedded Image. Similarly that for λ3 is an inclusion for the 65th eigenvalue of Embedded Image.

Acknowledgements

We are grateful to M. Langer for fruitful discussions. L.B. wishes to acknowledge the hospitality of Ceremade where part of this research was carried out. M.S. gratefully acknowledges the support of EPSRC grant no. EP/E037844/1.

  • Received May 5, 2010.
  • Accepted July 9, 2010.

Appendix A. Accumulation points outside the real line

Since Embedded Image is second countable and the essential spectrum of A is closed, there always exists a family of open intervals Embedded Image such that Embedded Image. Throughout this section we will be repeatedly referring to the following two A-dependent regions of the complex plane: Embedded Image, where Embedded Image. For Embedded Image and ε>0 we will denote the open ε-neighbourhood of Ω by Embedded Image.

Lemma A.1

Let Embedded Image be compact and such that Embedded Image. Let Embedded Image. There exists Embedded Image and N>0 such that Embedded Image for all Embedded Image and n≥N.

Proof.

It follows from lemmas 2.3 and 3.1 applied in (aj+ε,bjε), where Embedded Image is a finite covering of Embedded Image, by analogous arguments as in the proof of theorem 3.4.  ■

Combining this lemma with an argument as in the proof of corollary 3.6, we immediately achieve a generalization of corollary 3.8:Embedded ImageWe now examine accumulation of Embedded Image in compact subsets of Embedded Image.

Lemma A.2

Let c∈Specess(A). For any given Embedded Image and δ>0 there exists Embedded Image such that

(i) ∥xl∥=1 for all l=1, … ,m

(ii) Embedded Image for all Embedded Image and p,q=0,1

(iii) Embedded Image where Embedded Image for any l=1, … ,m.

Proof.

If c is isolated from the other points in the spectrum, the proof is elementary. Otherwise, there exists clc, such that cl∈Spec(A)\{c}. By substituting cl by a sub-sequence if necessary, we can assume that |clc|=δ(l)<δ/2 for 0<δ(l+1)<δ(l), such that Embedded Image If we pick xl∈1(cl−(δ(l)/2),cl+(δ(l)/2))(A) for l=1, … ,m with ∥xl∥=1, the desired conclusion is guaranteed.  ■

For c1c2c3 denote Embedded Image.

Lemma A.3

Let Embedded Image. For δ>0 let x1,x2,x3∈D(A) be such that (i)–(iii) of lemma A.2 hold for m=3. There exist Embedded Image independent of δ such that if Embedded Image, the polynomial 〈Ay,Ay〉−2λ〈Ay,y〉+λ2〈y,y〉 has roots λ+=z+O(δ) and λ=z+O(δ).

Proof.

The cases where Embedded Image for Embedded Image are easy, so we assume that c1<c2<c3. Moreover, without loss of generality we can fix c1=−1, c2=c, where |c|<1 and c3=1. Then z and Embedded Image are roots of the polynomial Embedded Image for z=ae. If Embedded Image we getEmbedded ImageThe solution of the systemEmbedded Imageis Embedded Image, Embedded Image and Embedded Image, where Embedded Image. The proof is completed by an elementary trigonometric argument, showing that β±≥0 for any Embedded Image.  ■

Theorem A.4

Let Embedded Image be compact. For all ε>0 there exists Embedded Image such that Embedded Image.

Proof.

Let Embedded Image and ε>0 be fixed. Since Embedded Image is compact, there exists Embedded Image, such that Embedded Image. The proof will be completed if Embedded Image is such that Embedded Image. Below we will choose δ>0 small enough.

Let Embedded Image be such that Embedded Image. By virtue of lemma A2 there is a family of vectors Embedded Image, such that: ∥xkj∥=1 for all k=1,2,3 and j=1, … ,n; Embedded Image for all Embedded Image and p,q=0,1; Embedded Image, where Embedded Image for any k=1,2,3 and j=1, … ,n. Let αkj=αk be as in lemma A3 for z=zj. Choosing δ>0 small enough and defining Embedded Image and Embedded Image completes the proof.  ■

This result has two straightforward consequences. Given any compact subset Embedded Image, there exists Embedded Image, such that Embedded Image. Evidently, Embedded Image might fall outside Λ0 in general. On the other hand, we can always find Embedded Image, such that Embedded Image.

References

View Abstract