Banded Matrices and Discrete Sturm-Liouville Eigenvalue Problems

doi:10.1155/2009/362627

Research Article

Banded Matrices and Discrete Sturm-Liouville Eigenvalue Problems

Werner Kratz

Institute of Applied Analysis, University of Ulm, 89069 Ulm, Germany

Correspondence should be addressed to Werner Kratz,[email protected] Received 31 August 2009; Accepted 19 November 2009

Recommended by Ondˇrej Dosly

We consider eigenvalue problems for self-adjoint Sturm-Liouville difference equations of any even order. It is well known that such problems with Dirichlet boundary conditions can be transformed into an algebraic eigenvalue problem for a banded, real-symmetric matrix, and vice versa. In this article it is shown that such a transform exists for general separated, self-adjoint boundary conditions also. But the main result is an explicit procedurealgorithmfor the numerical computation of this banded, real-symmetric matrix. This construction can be used for numerical purposes, since in the recent paper by Kratz and Tentler2008there is given a stable and superfast algorithm to compute the eigenvalues of banded, real-symmetric matrices. Hence, the Sturm-Liouville problems considered here may now be treated by this algorithm.

Copyrightq2009 Werner Kratz. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

In1it was shown that every discrete Sturm-Liouville eigenvalue problemwhereΔwk wk 1−wk

L y

k:ⁿ

μ0−Δ^μ

rμkΔ^μyk 1−μ

λyk 1 for 0≤k≤N SL

with Dirichlet boundary conditionsy1−n · · · y0 yN 2−n · · · yN 1 0 is equivalent with an algebraic eigenvalue problem2for a symmetric, bandedN 1−n×N 1−n- matrix with bandwidth 2n 1, where N andnare fixed integers with 1 ≤ n ≤ N see1, Theorem 1, Remark 1i. Note thatSLis irrelevant forN−n 1 ≤ k ≤ Nin the case of Dirichlet boundary conditions, so that in 1equationSL is considered only for 0 ≤ k ≤ N−n.

In this article we treat the Sturm-Liouville difference equations SL with general separated, self-adjoint boundary conditions. These boundary conditions include the so-called natural boundary conditions, when no or “not enough” boundary conditions are imposed 3, page 51, equation2.3.9. More precisely, given SL and the imposed and natural boundary conditions, then we show that this eigenvalue problem is equivalent with an algebraic eigenvalue problem for a real-symmetric, banded matrix with bandwidth 2n 1, and we will construct this matrix explicity. For our general boundary conditions we must assume that the coefficientsr_nkare unequal to zero at “the beginning and at the end”see 4.7below. This leads via4or5to a numerical algorithm to compute the eigenvalues of these Sturm-Liouville eigenvalue problems.

Therefore the present paper is to some extent a continuation of the articles1,4. The paper4presents superfasti.e., withONnumerical operationsand stable algorithms for the computation of some of the eigenvalues for a real-symmetric and bandedN×Nmatrix with bandwidth 2n 1, wheren 2 or 3 for the most interesting division-free algorithms.

These algorithms are based on the bisection method, and they generalize the well-known procedure for real-symmetric and tridiagonal matrices. As is shown in1and used in4the algebraic eigenvalue problems for real-symmetric, banded matrices with bandwidth 2n 1 are equivalent to eigenvalue problems for self-adjoint Sturm-Liouville difference equations of order 2nwith Dirichlet boundary conditions. Hence, these discrete Sturm-Liouville eigenvalue problems can be treated by those algorithms.

Summarizing, the main goal of this article is to provide an algorithm to calculate some of the eigenvalues of eigenvalue problems for self-adjoint Sturm-Liouville difference equations with general separated, self-adjoint boundary conditions and not only for Dirichlet conditions as in 4, 5. To be more precise, we provide a construction to transform these eigenvalue problems into such eigenvalue problems with Dirichlet boundary conditions. This construction incorporates “somehow” the general boundary conditions into the first and last 2n equations of the Sturm-Liouville difference equations. These transformations are stable using essentially orthogonal transformsand the required computational work depends on n onlymost interesting n 2,3 but not on N, so that the overall combined with 4 algorithm remains superfasti.e., ONnumerical operationsand stable. Hence, the results of this paper are of interest mainly for numerical applications.

Because of our intention above this article, more precisely Sections2to5of it, consists essentially of the following central parts:

ideriving the transform to an explicit algebraic algebraic eigenvalue problem for a symmetric, banded matrix with bandwidth 2n 1,

iiproviding the required formulas, so that an implementation of the construction is easily

“accessible” for the reader,

iiiproving that the construction is always successful under the conditions4.4and 4.7 which is the contents ofTheorem 6.1.

This means that Sections2to5have to be quite technical. Our proceeding in these sections provides simultaneously the construction, the derivation, and the proof that the construction always works.

As already said the asserted equivalence inTheorem 6.1is not the crucial result of this article. Actually, under the assumptions4.4and4.7this equivalence may be shown quite easily using Lemma 2.3and Proposition 3.2. Moreover, assumption4.4is necessary and sufficient for self-adjointnesssee, e.g.,3, Proposition 2.1.1or elsewhere, if4.7holds.

The assumption 4.7 is also necessary for all considered boundary conditions simultaneously, but for a particular boundary condition it may be weakened. But this can be seen during the procedure. The equivalence viaLemma 2.3andProposition 3.2directly leads in general to a banded symmetric matrix with larger bandwidth. On the other hand the “minimal bandwidth” tridiagonal i.e.,n 1 can always be achieved in a stable way by the well- known methods of Givens and Householder, but these algorithms requireON²numerical operations as discussed in4, which would make our whole approach obsolete.

Note that our main goal is equivalence to an “ordinary” algebraic eigenvalue problem for a real-symmetric and banded matric rather than to some matrix pencil or generalized eigenvalue problem of the formEY λAY. This is so, because the algorithm via bisection works only for these algebraic eigenvalue problems, which are well posed, while those general problems are in general not well posed. Note also that the equivalence to “some matrix pencil” can be seen immediately fromSLor4.1and also4.2. Moreover, the reduction of separated boundary conditions to Dirichlet boundary conditions via an extension of the system to a larger interval is also well known for discrete Hamiltonian or symplectic systemssee, e.g., 6or7. Hence, this reduction combined with the transformation of the Sturm-Liouville equationsSLto a linear Hamiltonian system byLemma 2.2would also lead to a problem with Dirichlet boundary conditions but for a larger matrix, more precisely, it would lead to some matrix pencil possible also with larger bandwidth, which cannot be treated by the algorithms of4,5.

The discussion of assumption4.7 in the Concluding Remarks ofSection 6 does not focus on the necessity or sufficiency of it. It is quite “natural” to assume that the leading coefficientrnknever vanishes, because it is the case in most applications. But the main point is that the incorporation of our general boundary conditions into the the difference equations by our construction leads in general to problems with Dirichlet boundary conditions, but where the leading coefficient may vanish for somek’s at the beginning and the end. Therefore, algorithms via corresponding Hamiltonian or Riccati equations cannot be used anymore, so that the division-free algorithms i.e., no divisions by rnk are needed as remarked in Concluding RemarksiofSection 6.

Let us shortly motivate why to consider the discrete Sturm-Liouville eigenvalue problems of this article, particularly forn2 andn3, and for general boundary conditions.

iThe discretization of a second order Sturm-Liouville equation ry

qyλy 1.1

of higher order leads to a banded matrix with bandwidth 2n 1 withn > 1, and then even Dirichlet boundary conditions ya yb 0 lead for the discrete problem to the boundary conditionsy0yN 10, which have to be complemented by additional “natural boundary conditions” in the usual way. Therefore, such problems of second order with Dirichlet boundary conditions cannot be treatedat least for higher-order discretizationdirectly by the algorithm of4. By using the construction of this article we obtain faster algorithms than the known ones.

iiLinear discretization of 4th- and 6th-order Sturm-Liouville difference equations leads to bandwidths 5 and 7, and the numerical treatment of Dirichlet boundary conditions via4requires also the construction of this article.

Let us shortly discuss the setup of this paper. In the next section we provide the formulae, which transform the difference equations SL into the corresponding matrix equation

seeLemma 2.1belowbased on1. InSection 3we derive via partial summation the so- called Dirichlet’s formula, which yields the crucial identities3.3. InSection 4we formulate our discrete Sturm-Liouville eigenvalue problems. In particular, we introduce based on 8 and discuss shortly the corresponding general separated, self-adjoint boundary conditions.

In Section 5 we carry out our construction of the symmetric, banded matrix, so that the corresponding algebraic eigenvalue problem is equivalent with our Sturm-Liouville problem.

Hence, our proceeding in Sections 2 to 5 provides simultaneously the construction, the derivation, and the proof that the construction always works. This is formulated as our main result in the lastSection 6by adding some concluding remarks.

2. Discrete Sturm-Liouville Difference Equations, Banded Matrices, and Hamiltonian Systems

Letn ∈N, and let realsrμkforμ∈ {0,1, . . . , n}andk ∈Zbe given. Then, fory yk_k∈Z, we consider the Sturm-Liouville difference operatorLydefined by

L y

k:ⁿ

μ0

−Δ^μ

r_μkΔ^μy_{k 1−μ}

fork∈Z, 2.1

whereΔis the forward difference operator, that is,Δwk : wk 1−wk, which will always operate with respect to the variablek. Then, by1, Theorem 1, we have that

L y

k Ay

k 1 fork∈Z, 2.2

whereA a_μνis a symmetric, banded matrix with bandwidth 2n 1, given by

ak 1,k 1 t −1^tn

μt

μ νt

μ ν

μ ν−t

rμk ν,

ak 1,k 1−t −1^tn

μt

μ−t ν0

μ ν

μ ν t

rμk ν

2.3

for 0≤t≤nand allk∈Z.

This formula yields the following.

Lemma 2.1. Fork∈Zandy y_νν∈Zdefine vectors

x_k:

y_{k 1−n νn−1}

ν0, v_k: L

y

k ν

_n−1

ν0. 2.4

Then,

v_k Δ^Tkx_k Mk x_{k n} Δk nx_{k 2n}, 2.5

whereMk∈R^n×nis a symmetric matrix, and where

Δk

⎛

⎜⎜

⎜⎝

−1ⁿr_nk · · · 0 ... ... ...

· · · −1ⁿrnk n−1

⎞

⎟⎟

⎟⎠∈R^n×n 2.6

is lower triangular, and it is invertible, ifr_nν/0 fork≤ν≤k n−1. Moreover, the equation

v_kλx_{k n} 2.7

is equivalent with

L y

k νλyk 1 ν for 0≤ν≤n−1. 2.8

Next, we have by1, Lemma 3or9, Remark 2the following.

Lemma 2.2. Fork∈Zandy yν_ν∈Zdefine vectors

xk:

Δ^νyk−ν_n−1

ν0, uk:

⎛

⎝ ⁿ

μν 1−Δ^μ−ν−1

rμkΔ^μyk 1−μ⎞

⎠

n−1

ν0

. 2.9

Then, for anyk∈Z, the equation

L y

k νλyk 1 ν 2.10

is equivalent with the Hamiltonian system

Δx_kAx_{k 1} B_ku_k, Δu_k

C_k−λC

x_{k 1}−A^Tu_k, 2.11

provided thatrnk/0, where one uses the following notation:A,Bk,Ck,Caren×n-matrices defined by

A:

⎛

⎜⎜

⎜⎜

⎜⎜

⎝

0 1 · · · 0 ... ... ... ...

0 · · · 0 1 0 · · · 0 0

⎞

⎟⎟

⎟⎟

⎟⎟

⎠

, Bk: 1

rnkB withB:diag0, . . . ,0,1,

C_k:diagr0k, . . . , r_n−1k, C:diag1,0, . . . ,0.

2.12

For the next lemma; see, for example,10, formulae6and9for the case of constant coefficients. It follows easily from our formulae 2.4 and 2.9 by computing the finite differences viaΔ^νw_kν

μ0

_ν

μ

−1^ν−μw_{k μ}.

Lemma 2.3. Letxk(correspondlyxk n),xk, andukbe defined by2.4and2.9. Then,

x_kTx_k, u_kT1kx_x T2kx_{k n}, 2.13

where T

−1^ν_n−1−μ

ν

0≤μ,ν≤n−1 is invertible with T⁻¹

−1^n−1−ν _μ

n−1−ν

0≤μ,ν≤n−1, and whereT1k,T2karen×n-matrices with

T2k

⎛

⎜⎜

⎜⎝

· · · −1ⁿ⁻¹rnk n−1 ... ... ...

−1⁰r_nk · · · 0

⎞

⎟⎟

⎟⎠, 2.14

andT2kis invertible, ifr_nν/0 fork≤ν≤k n−1.

3. Dirichlet’s Formula

The next lemma is a discrete version of the continuous Dirichlet’s formula3, Lemma 8.4.3.

Lemma 3.1. Fork ∈Zand two sequencesy y_νν∈Z,y y_νν∈Zlet the operatorL, the vectors xk,uk,xk,uk, and the matricesBandCkbe defined as in the previous section by2.1andLemma 2.2.

Then, for anyk∈Z,

y_{k 1}L y

kⁿ

μ0

rμkΔ^μy_{k 1−μ}Δ^μyk 1−μ−Δ x^T_kuk

x^T_{k 1}C_kx_{k 1} r_nkx_{k 1}−x_k^TBx_{k 1}−x_k−Δ x^T_ku_k

.

3.1

Proof. A straight forward calculation using2.1and2.9yields Δ

x^T_ku_k

x^T_{k 1}Δu_k Δx^T_k

u_k

ⁿ⁻¹

μ0

Δ^μy_{k 1−μ} ⁿ

ρμ 1

−1^ρ−μ−1Δ^ρ−μ

r_ρkΔ^ρy_{k 1−ρ}

n−1 μ0

Δ^{μ 1}y_k−μ ⁿ

ρμ 1

−1^ρ−μ−1Δ^ρ−μ−1

rρkΔ^ρyk 1−ρ

ⁿ

μ1

Δ^μy_{k 1−μ}rμkΔ^μyk 1−μ

y_{k 1}ⁿ

ρ1

−1^ρ−1Δ^ρ

rρkΔ^ρyk 1−ρ

ⁿ

μ0

rμkΔ^μy_{k 1−μ}Δ^μyk 1−μ−y_{k 1}L y

k,

3.2

which proves our assertion3.1using also the definition ofC_kandBbyLemma 2.2.

Proposition 3.2. The matricesT,T1k,T2k, andΔkfrom Lemmas2.3and2.1satisfy

T2k −T^TΔkand T1kT is symmetric. 3.3

Proof. We consider the functional F_k : v^T_k−nx_k, with v_k−n and x_k defined by 2.4 of Lemma 2.1, where we putxk−n0. Then, by2.5ofLemma 2.1we have that

Fkx^T_k{Mk−nxk Δk xk n}. 3.4

From the definition ofv_k−nby2.4and Dirichlet’s formula3.1we obtain that

Fkⁿ⁻¹

ν0

L y

k−n νy_{k−n ν 1}

ⁿ⁻¹

ν0

x^T_{k−n ν 1}C_{k−n ν}x_{k−n ν 1} r_nk−n ν

×xk−n ν 1−xk−n ν^TBxk−n ν 1−xk−n ν

−x^Tu^k

k−n

x^T_kSx_k−x^T_ku_k

by2.13of Lemma 2.3 x^T_kSx_k−x^T_k

T^T₋₁

T1kx_k T2kx_{k n},

3.5

whereS is a symmetric matrix. Comparing this last formulaobserve that xk,xk,xk n are completely freewith3.4we can conclude that

− T^T₋₁

T2k Δk, and T^T₋₁

T1kis symmetric, 3.6

becauseMk−nis symmetric byLemma 2.1. This yields our assertion3.3.

4. Discrete Sturm-Liouville Eigenvalue Problems with Separated, Self-Adjoint Boundary Conditions

Let integers n, N ∈ Nwith N ≥ 2nsee5.4belowand real coefficientsr_μkbe given.

Then, we consider the following discrete eigenvalue problem, which we will denote byE.

It consists of theN 1 self-adjoint Sturm-Liouville difference equations of even order 2nsee SL, Lemmas2.1and2.2above:

L y

kⁿ

μ0−Δ^μ

r_μkΔ^μy_{k 1−μ}

λy_{k 1} for 0≤k≤N, 4.1

and it consists of the 2n linearly independent, separated, and self-adjoint boundary conditions

R^∗₀x0 R0u00 4.2

at the beginning, and

R^∗_{N 1}x_{N 1} R_{N 1}u_{N 1}0 4.3

at the end, wherex0,u0,xN 1,uN 1 are defined by2.9ofLemma 2.2, and where the real n×n-matricesR^∗₀,R0,R^∗_{N 1},R_{N 1}satisfy the following conditions:

rank R^∗₀, R0

rank

R^∗_{N 1}, R_{N 1}

n, R^∗₀R^T₀, R^∗_{N 1}R^T_{N 1} are symmetric. 4.4

By Lemma 2.3,4.2and 4.3lead to the following equivalent conditions onx0,xn,xN 1, x_{N 1 n}, defined by2.4, that is, ony_1−n, . . . , y_nand ony_{N 2−n}, . . .,y_{N 1 n}, respectively:

R^∗_bx0 Rbxn0, whereR^∗_b:

R^∗₀T⁻¹ R0T10

, Rb :R0T20, 4.5

R^∗_ex_{N 1} R_ex_{N 1 n}0, 4.6

where R^∗_e : {R^∗_{N 1}T⁻¹ RN 1T1N 1},Re : RN 1T2N 1, and whereT, T1·, T2· are defined byLemma 2.3. Moreover, the equivalence of4.2,4.3with4.5,4.6requires

the assumption thatT20andT2N 1are invertible, which means byLemma 2.3that r_n0· · ·r_nn−1r_nN 1· · ·r_nN n/0. 4.7

We assume this from now on.

The self-adjointness of E follows from general theory of linear Hamiltonian difference systems11, and from the equivalence of our difference equation4.1with such systems, which is stated in Lemma 2.2. In addition, the self-adjointness of the boundary conditions via the assumption4.4is stated or discussed, for example, in3, Definition 2.1.2, 8, Remark 2iii,12, Proposition 2, or7, Definition 1.

5. Construction of the Symmetric, Banded Matrix

First, byLemma 2.1, the Sturm-Liouville difference equations4.1may be written in matrix notation, namely,

Ayλy, 5.1

where the coefficient matrix is of the form

A

⎛

⎜⎜

⎜⎝

Δ^T0 M0 Δn · · · 0 0 0

... ... ...

0 0 0 · · · Δ^TN 1−n MN 1−n ΔN 1

⎞

⎟⎟

⎟⎠ 5.2

which is∈R^{N 1×N 1 2n}, and where y

y_1−n, . . . , y_{N 1 n}

x^T₀,x^T_n, . . . ,x_{N 1−n}^T ,x^T_{N 1}

∈R^{N 1 2n}, y

y1, . . . , yN 1

x^T_n, . . . ,x^T_{N 1−n}

∈R^{N 1},

5.3

and where we have written the firstnand the lastnrows ofA in blocked form according to 2.4 and 2.5 of Lemma 2.1. It is the aim of this section to incorporate the boundary conditions 4.2or 4.5and 4.3 or4.6 into the firstnand the lastnequations of4.1, that is, the first and last block rows ofA, respectively. This requires in general that

N≥2n. 5.4

As a result we will obtain an algebraic eigenvalue problem for a symmetric, banded matrix of sizeN 1−r_b −r_e×N 1−r_b −r_ewith integersr_b, r_e ∈ {0, . . . , n} depending on the boundary conditions. This algebraic eigenvalue problem will be equivalent with our given Sturm-Liouville eigenvalue problemEfrom Section 4under the assumptions4.4 and4.7.

5.1. Boundary Conditions at the Beginning

We consider the boundary conditions4.2or4.5at the beginning by assuming4.4and 4.7. Hence,T20andΔ0are invertible by Lemmas 2.1and 2.3. LetX,Ube realn×n- matrices such thatsee4.5

X^TUU^TX, X^TU−U^TXI, and X is invertible, C1

whereX : −Δ⁻¹0R^∗_b^T,U:R^T_b.The existenceincluding constructionfollows from3, Corollary 3.3.9, because

rank

X^T, U^T

n, U^TXX^TU 5.5

holds. This follows from4.4and4.5by the calculations

rank

R0T20,

R^∗₀T⁻¹ R0T10 Δ^T₋₁

0

rank R0, R^∗₀

n,

R0T20Δ⁻¹0

R^∗₀T⁻¹ R0T10_T −R0

R^∗_0T

−R0T^TT₁^T0R^T₀

5.6

is symmetric, where we used3.3ofProposition 3.2. Moreover,C1and5.5imply by3, Proposition 1.1.5that

UX^T−UX^T I, andXX^T, UU^T are symmetric. 5.7

We conclude fromC1and5.7that our boundary conditions4.2or4.5are equivalent with

−XX^TΔ^T0x0 XU^Txn0. 5.8

SinceXX^T is real-symmetric by5.7, there exists by the spectral theorem13an orthogonal matrixV such that

V^TXX^TV 0 0

0 D

, 5.9

whereD∈R^{n−rb×n−rb}is diagonal and invertible, so that rbn−rankXn−rankR^∗_b n−rank

R^∗₀ R0T10T

. 5.10

We use this block structure from now on including the extreme casesrb 0 andrbn, where the zero-matrices orDdo not occur. By the Gram-Schmidt processor QR-factorization13, there exists an orthogonal matrixQ ∈ R^{n−rb×n−rb}such thatQ^TΔ22is lower triangular, where

V^TΔn : _Δ

11Δ12

Δ21Δ22

∈ R^n×n with the blockstructure above, that is,Δ11 ∈ R^rb×rb. ThenV : V_{I 0}

0Q

is orthogonal, and

S:V^T

−XX^T V

0 0 0 S22

, 5.11

whereS22 −Q^TDQis symmetric and invertible. Let

R:V^TXU^TV

R11 R12

R21 R22

. 5.12

By5.5andC1, rankS, R n, and

SR^T

0 0 S22R^T₁₂ S22R^T₂₂

−V^TXX^TUX^TV 5.13

is symmetric. Hence,R120, becauseS22is invertible, and rank_{0 0 R}

11 0 0S22R21 R22

n, so thatR11

is invertible.

Altogether, we have constructedV ∈R^n×nsuch that

S:−V^TXX^TV 0 0

0 S22

5.14

with a symmetric and invertible matrixS22∈R^{n−rb×n−rb}, whererb n−rankX,

R:V^TXU^TV

R11 0 R21 R22

C2

with an invertible matrixR11∈R^rb×rband so thatS22R^T₂₂is symmetric, and

Δ:V^TΔn

⎛

⎝Δ11 Δ12

Δ21 Δ22

⎞

⎠, 5.15

so thatΔ22 ∈R^{n−rb×n−rb}is lower triangular, and whereV is orthogonal.

It follows immediately fromC1andC2that our boundary conditions4.2or4.5 are equivalent with

SV^TΔ^T0x0 RV^Txn0, 5.16

and therefore with

x1n 0, x20 −S⁻¹₂₂R22x2n, 5.17

where

x0:V^TΔ^T0x0

x10 x20

, x n:V^Txn

x1n x2n

5.18

withx10, x1n∈R^rbwhilex10andx2nremain free.

We say that5.18is the boundary conditions in normalized form.

Now, we consider the firstnequations or the first block row of our difference equations 4.1or5.1, that is, byLemma 2.1and5.2,

v0 Δ^T0x0 M0 x_n Δnx_2nλx_n. 5.19

We obtain from5.7and5.8that

Δ^T0x0

UX^T−UX^T

Δ^T0x0, −UX^TΔ^T0x0−XU^Txn. 5.20

Hence, under5.8 i.e., the boundary conditions,5.19 is equivalent with use also the notation of5.18andC2

0V^T

UX^TΔ^T0x0−UU^T

xn V^T{M0−λI}Vxn V^TΔn x2n

R^Tx 0

M0 −λI

xn Δ x2n,

5.21

whereM0 _M

11M12

M21M22

:V^T{M0−UU^T}Vis symmetric byLemma 2.1and5.7. Hence, byC2, equation5.19is equivalent withunder the boundary conditions5.18

x10 −

R^T₁₁₋₁

−R^T₂₁S⁻¹₂₂R22x2n M12x2n Δ11Δ12

x_2n

, 5.22

{M−λI}x2n Δ21Δ22

x_2n0, whereM:−R^T₂₂S⁻¹₂₂R22 M22. 5.23

Now, 5.22 defines x10 independently of λ, which was free by 5.18. Note that M is symmetric, becauseM0andUU^T are symmetric byLemma 2.1and5.7. Moreover,Δ22

is lower triangular by C2, so that5.23leads to bandwidth 2n 1 and symmetry. More precisely, we drop the first n rb columns of A, and the firstnrows are replaced by the following rows, which constitute the first n−r_b rows of the symmetric, banded matrix under

construction:

MΔ21Δ220· · ·0

, where M:−R^T₂₂S⁻¹₂₂R22 M22 ∈R^{n−rb×n−rb}, C3

and where_M

11M12

M21M22

:V^T{M0−UU^T}V. The nextnequations of4.1are given by

Δ^Tn xn {Mn−λI}x2n Δ2n x3n0, 5.24

whereΔ^Tnxn Δ^Tx n Δ21Δ22^Tx2nbyC2, becausex1n 0 by5.18. Hence, the nextnrows fromn−r_b 1, . . . ,2n−r_bof our matrix under construction have to be defined by

⎛

⎝

⎛

⎝Δ^T₂₁ Δ^T₂₂

⎞

⎠ Mn Δ2n 0· · ·0

⎞

⎠. C4

This completes the construction concerning the boundary conditions at the beginning. Thus, possible eigenvectors have to be of the formx^T₂n, yn 1, . . ., where the boundary conditions are satisfied by putting x1n 0 and defining x20 and x10 by 5.18 and 5.22, respectively.

5.2. Boundary Conditions at the End

We proceed similarly as in the previous subsection. Therefore, we can skip some details. We shall use for convenience the same notation for auxiliary matrices or vectors here, but of course, with a different meaning. Observe that the situation is nevertheless not symmetricsee the concluding remarksiibelow.

We consider the boundary conditions4.3or4.6at the end by assuming4.4and 4.7, so thatT2N 1andΔN 1are invertible. LetX,Ube realn×n-matrices such that see4.6

X^TUU^TX, X^TU−U^TXI, and X is invertible, C5

whereX: ReΔ⁻¹N 1^T,U: R^∗_e^T.

These matrices exist, because5.5holds by4.4and4.6. Note that

X−TR^T_{N 1} 5.25

byProposition 3.2and4.6. Moreover,5.7holds as before. Hence, the boundary conditions 4.3or4.6are equivalent with

XU^TxN 1 XX^TΔN 1xN 1 n0. 5.26

By the spectral theorem there exists an orthogonal matrixV such that

V^TXX^TV D 0

0 0

, 5.27

whereD∈R^{n−re×n−re}is diagonal and invertible, so that

ren−rankXn−rankRen−rankRN 1. 5.28

As before we use this block structure including the extreme cases re 0 and re n. By QR-factorization there exists an orthogonal matrixQ ∈ R^{n−re×n−re}such thatQ^TΔ^T₁₁is upper triangular, whereΔN 1−nV :_Δ

11Δ12

Δ21Δ22

with the blockstructure above, that is,Δ22∈R^re×re. ThenV :V_Q0

0 I

is orthogonal, and

S:V^T

−XX^T V

S11 0 0 0

, 5.29

whereS11 −Q^TDQis symmetric and invertible. Let

R:V^TXU^TV

R11 R12

R21 R22

. 5.30

By5.5andC5we obtain thatR21 0 and thatR22is invertible.

Altogether, we have constructedV ∈R^n×nsuch that

S:−V^TXX^TV

S11 0 0 0

5.31

with a symmetric and invertible matrixS11∈R^{n−re×n−re}, whereren−rankX,

R:V^TXU^TV

R11 R12

0 R22

C6

with an invertible matrixR22∈R^re×reand so thatS11R^T₁₁is symmetric, and

Δ: ΔN 1−nV

⎛

⎝Δ11 Δ12

Δ21 Δ22

⎞

⎠, 5.32

so thatΔ^T₁₁ ∈R^{n−re×n−re}is upper triangular, and whereVis orthogonal.

It follows fromC5andC6that our boundary conditions4.3or4.6or5.26are equivalent with

RV^Tx_{N 1} SV^TΔN 1x_{N 1 n}0, 5.33

and therefore with

x2N 1 0, x1N 1 n −S⁻¹₁₁R11x1N 1, where

xN 1 :V^TxN 1

x1N 1 x2N 1

,

xN 1 n :V^TΔN 1xN 1 n

x1N 1 n x2N 1 n

5.34

with x2N 1,x2N 1 n∈R^re,x1N 1, andx2N 1 nremaining free. We say that 5.34is the boundary conditionsat the endin normalized form.

Next, we consider the lastnequations of our difference equations4.1or5.1, that is, byLemma 2.1and5.2,

v_{N 1−n} Δ^TN 1−nx_{N 1−n} MN 1−nx_{N 1} ΔN 1x_{N 1 n} λx_{N 1}. 5.35

Then, under5.34 i.e., the boundary conditionsthis is equivalent withusing the notation of5.34andC6

Δ^TxN 1−n V^T{MN 1−n−λI}V

x1N 1 0

xN 1 n0, 5.36

that is

Δ^T₁₁,Δ^T₂₁

x_{N 1−n} M11−λI, M12

x1N 1 0

x1N 1 n 0, Δ^T₁₂,Δ^T₂₂

xN 1−n M21, M22−λI

x1N 1 0

x2N 1 n 0,

5.37

where_M

11M12

M21M22

:V^TMN 1−nV is symmetric byLemma 2.1. Hence, byC6, equation 5.35is equivalent withunder the boundary conditions5.34

x2N 1 n −

Δ^T₁₂,Δ^T₂₂

xN 1−n−M21x1N 1, 5.38

Δ^T₁₁,Δ^T₂₁

xN 1−n {M−λI}x1N 1 0, whereM:M11−S⁻¹₁₁R11. 5.39

Now,5.38definesx2N 1 nindependently ofλ, which was free by5.34. Note thatMis symmetric, becauseMN 1−nis symmetric byLemma 2.1and becauseS⁻¹₁₁R11is symmetric

byC6. Moreover,Δ^T₁₁is upper triangular byC6, so that5.39leads to bandwidth 2n 1 and symmetry. More precisely, we drop the lastn r_ecolumns ofA, and the lastnrows are replaced by the following rows, which constitute the lastn−rerows of the symmetric, banded matrix under construction:

0· · ·0 Δ^T₁₁Δ^T₂₁ M

, whereM:M11−S⁻¹₁₁R11∈R^{n−re×n−re}, C7

and where_M

11M12

M21M22

:V^TMN 1−nV.

The last but onenequations of4.1are given by

Δ^TN 1−2nxN 1−2n {MN 1−2n−λI}xN 1−n ΔN 1−n xN 10. 5.40 Note that for 2n≤N <3nthis overlaps with5.24of the previous subsection, andΔN 1− 2nmay have been changed by the construction there. We use here this newΔN 1−2n fromSection 5.1, but note that it is irrelevant here. ByC6and5.34we have that

ΔN 1−nxN 1 Δ x_{N 1}

⎛

⎝Δ11

Δ21

⎞

⎠x1N 1. 5.41

Hence, thenrows before then−rerows ofC7of our matrix under construction have to be defined by

⎛

⎝0· · ·0 Δ^TN 1−2n MN 1−2n

⎛

⎝Δ11

Δ21

⎞

⎠

⎞

⎠. C8

This completes the construction. Thus, possible eigenvectors must be of the form x^T₂n, y_{n 1}, . . . , y_{N 1−n}, x^T₁N 1

∈R^{N 1−rb−re}. 5.42

6. Main Result and Concluding Remarks

Altogether we have shown by the construction ofSection 5the following result.

Theorem 6.1. Assume4.4and 4.7. Then the construction ofSection 5 transforms the Sturm- Liouville eigenvalue problemE(given by4.1and4.2) ofSection 4into an equivalent algebraic eigenvalue problem for a real-symmetric, banded matrix with bandwidth 2n 1. This matrix is of size N 1−rb−re×N 1−rb−rewithrb, re∈ {0,1, . . . , n}given by5.10and5.28, and it is constructed fromA(defined by5.2) byC1–C8.

Concluding Remarks

iBy our theorem every discrete Sturm-Liouville eigenvalue problemEis equivalent with an algebraic eigenvalue problem for a banded, symmetric matrix under the assumptions4.4

and 4.7. On the other hand, by 1, Remark 1i, such an algebraic eigenvalue problem is equivalent with a discrete Sturm-Liouville eigenvalue problem with Dirichlet boundary conditions. Moreover, ifrnk/0 for allk, then our eigenvalue problemEcan be written as an eigenvalue problem for a corresponding Hamiltonian system or symplectic system14 according toLemma 2.2. Note that it is quite natural to assume that the leading coefficient r_nknever vanishes, because it is the case in most applications. But the main point is that the incorporation of our general boundary conditions into the difference equations by our construction leads in general to a problem where the leading coefficient may vanish for somek’s at the beginning and the end. To be more precise, our construction may cause that matrix elementsak,k n become zero at the beginning and at the end, so that its equivalent Sturm-Liouville problem with Dirichlet boundary conditions will not satisfyr_nk/0 for allk anymore, becausea_{k,k n} −1ⁿr_nk nby2.3. Hence, it cannot be written as an eigenvalue problem for a linear Hamiltonian difference system, so that the corresponding recursion formulaebased on the Hamiltonian or associated Riccati difference system4,11cannot be applied for numerical purposes as in4, Theorems A and 2. Therefore, divisions byr_nk must be avoided, which is done by the division-free algorithms presented in4,5. Hence, these division-free algorithms are crucial for our purposes.

iiNote that in contrast to the corresponding continuous Sturm-Liouville problems or the corresponding Hamiltonian differential systems, there is no symmetry with respect to the endpoints in the discrete case. This is quite obvious by the difference equation4.1with forward differences. Therefore the treatment of the boundary conditions at the endpoints in the subsections above had to be done separately. Actually the results of this treatment are quite different as can be seen also from the next remark.

iiiWe discuss the extreme casesr_b, r_e 0 or nof our construction. It follows from 5.10and5.28thatrb 0 if and only ifR^∗_bis invertible, that is,x0 −R^∗_b⁻¹Rbxnby4.5 this includes Dirichlet conditionsx00 forRb0.

r_b n if and only ifR^∗_b 0, that is,x_n 0 by 4.5 so thatx0 or x0 is free.r_e 0 if and only if Re or RN 1 is invertible, that is, xN 1 n −R⁻¹_e R^∗_exN 1 by4.6 or uN 1

−R⁻¹_{N 1}R^∗_{N 1}xN 1 by4.3 this includes natural boundary conditions uN 1 0 forR^∗_{N 1} 0.

r_enif and only ifR_e0, that is,x_{N 1}x_{N 1}0Dirichlet conditions.

Hence, our construction leads to the maximal sizeN 1×N 1 i.e.,r_b r_e0of the constructed matrix for Dirichlet conditionsx0x00more general forx0−R^∗_b⁻¹Rbxnat the beginning and for natural boundary conditionsmore general forx_{N 1 n}−R⁻¹_e R^∗_ex_{N 1} at the end. The construction leads to the minimal sizeN 1−2n×N 1−2nforx_n0or for freex0at the beginning and for Dirichlet conditionsxN 1xN 10 at the end.

Acknowledgment

This research is supported by Grant KR 1157/2-1 of DFG.

References

1 W. Kratz, “Banded matrices and difference equations,” Linear Algebra and Its Applications, vol. 337, no.

1–3, pp. 1–20, 2001.

2 J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, UK, 1965.

3 W. Kratz, Quadratic Functionals in Variational Analysis and Control Theory, vol. 6 of Mathematical Topics, Akademie, Berlin, Germany, 1995.

4 W. Kratz and M. Tentler, “Recursion formulae for the characteristic polynomial of symmetric banded matrices,” Linear Algebra and Its Applications, vol. 428, no. 11-12, pp. 2482–2500, 2008.

5 M. Tentler, Rekursionsformeln zur Berechnung der charakteristischen Polynome von symmetrischen Bandmatrizen, Dissertation, Universit¨at Ulm, Ulm, Germany, 2008.

6 M. Bohner, O. Doˇsl ´y, and W. Kratz, “Discrete Reid roundabout theorems,” Dynamic Systems and Applications, vol. 8, no. 3-4, pp. 345–352, 1999.

7 O. Doˇsl ´y and W. Kratz, “Oscillation and spectral theory for symplectic difference systems with separated boundary conditions,” to appear in Journal of Difference Equations and Applications.

8 M. Bohner, O. Doˇsl ´y, and W. Kratz, “An oscillation theorem for discrete eigenvalue problems,” The Rocky Mountain Journal of Mathematics, vol. 33, no. 4, pp. 1233–1260, 2003.

9 M. Bohner and O. Doˇsl ´y, “Disconjugacy and transformations for symplectic systems,” The Rocky Mountain Journal of Mathematics, vol. 27, no. 3, pp. 707–743, 1997.

10 M. Bohner, O. Doˇsl ´y, and W. Kratz, “Inequalities and asymptotics for Riccati matrix difference operators,” Journal of Mathematical Analysis and Applications, vol. 221, no. 1, pp. 262–286, 1998.

11 C. D. Ahlbrandt and A. C. Peterson, Discrete Hamiltonian Systems: Difference Equations, Continued Fractions, and Riccati Equation, vol. 16 of Kluwer Texts in the Mathematical Sciences, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1996.

12 O. Doˇsl ´y and W. Kratz, “Oscillation theorems for symplectic difference systems,” Journal of Difference Equations and Applications, vol. 13, no. 7, pp. 585–605, 2007.

13 G. Strang, Linear Algebra and Its Applications, Academic Press, New York, NY, USA, 1976.

14 M. Bohner, O. Doˇsl ´y, and W. Kratz, “Sturmian and spectral theory for discrete symplectic systems,”

Transactions of the American Mathematical Society, vol. 361, no. 6, pp. 3109–3123, 2009.