View source for Eigen values of differential operators, numerical methods

Methods for computing the eigen values and corresponding eigen functions of differential operators. Oscillations of a bounded elastic body are described by the equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e0351601.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e0351602.png" /> is some differential expression. If one seeks solutions of (1) of the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e0351603.png" /></td> </tr></table>

the following equation for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e0351604.png" /> is obtained:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e0351605.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

within a bounded domain, under certain homogeneous conditions on the boundary. The values of the parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e0351606.png" /> for which there exist non-zero solutions of (2) satisfying the homogeneous boundary conditions are called eigen values, and the corresponding solutions eigen functions. The resulting eigen value problem consists of determining the eigen values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e0351607.png" /> and the eigen functions corresponding to them (see [[#References|[1]]], [[#References|[2]]]).

The numerical solution of this problem proceeds in three steps:

1) reduction of the problem to a simpler one, for example, to an algebraic (discrete) problem (see [[#References|[7]]], [[#References|[16]]]);

2) specification of the precision of this discrete problem;

3) calculation of the eigen values for the discrete problem (see [[#References|[3]]], [[#References|[6]]] and [[Linear algebra, numerical methods in|Linear algebra, numerical methods in]]).

==Reduction to a discrete problem.==
The reduction of problem (2) to a discrete model is usually carried out using the [[Grid method|grid method]] and [[Projection methods|projection methods]]. It is natural to require that the basic properties of the original problem, such as the self-adjointness of an operator, be preserved in its discrete analogue.

One method of reduction is the integro-interpolation method. For example, consider the problem

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e0351608.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e0351609.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>

This problem arises, for example, in the study of transverse vibrations of a non-homogeneous string and longitudinal vibrations of a non-homogeneous rod.

On the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516010.png" />, one introduces the uniform grid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516011.png" /> with nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516014.png" />. To every node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516016.png" />, is assigned an elementary domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516017.png" />. Integration of equation (3) over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516018.png" /> yields

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516019.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>

Let

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516020.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516021.png" /></td> </tr></table>

Then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516022.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>

Substituting (6) into (5), one obtains

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516023.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516024.png" /> is the described grid function. The boundary conditions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516026.png" /> reduce to an algebraic eigen value problem:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516027.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516028.png" /> is tri-diagonal symmetric matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516029.png" />.

The variational-difference method of reduction to a discrete problem is used when the eigen value problem can be formulated as a variational one. For example, the eigen values of the problem (3), (4) are the stationary values of the functional

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516030.png" /></td> </tr></table>

By changing the integrals to quadrature sums and the derivatives to difference relations, the discrete analogue of this functional has the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516031.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516032.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516033.png" /> is the difference analogue of the coefficient <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516034.png" />, which can be calculated by formula (6). The discrete analogue of the problem (3), (4) is obtained from the necessary condition for an extremum:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516035.png" /></td> </tr></table>

Differentiation again leads to the problem (7) (see [[#References|[9]]]).

The projection-difference method of reduction to a discrete problem consists of the following. One chooses a linearly independent system of coordinate functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516037.png" />, and a linearly independent system of projection functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516038.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516039.png" />. One seeks approximate eigen functions in the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516040.png" /></td> </tr></table>

The coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516041.png" /> and the approximate eigen values are determined by the condition

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516042.png" /></td> <td valign="top" style="width:5%;text-align:right;">(8)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516043.png" /> is the scalar product in the Hilbert space. When the coordinate and projection systems coincide, one talks of the Bubnov–Galerkin method. If, in addition, the operator of the differential problem is self-adjoint, the method is called the Raleigh–Ritz method. In particular, for problem (3), (4), if all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516044.png" /> satisfy (4), condition (8) takes the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516045.png" /></td> <td valign="top" style="width:5%;text-align:right;">(9)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516046.png" /></td> </tr></table>

In order to simplify the derivation of the algebraic problem, one chooses an almost-orthogonal system of functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516047.png" />.

By taking as coordinate and projection systems functions of the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516048.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516049.png" />, it follows from (9) that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516050.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516051.png" /></td> </tr></table>

where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516052.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516053.png" /></td> </tr></table>

Thus, together with the boundary conditions, one obtains a generalized eigen value problem:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516054.png" /></td> </tr></table>

Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516055.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516056.png" /> are tri-diagonal symmetric matrices of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516057.png" />.

These methods also yield discrete models of other equations. For example, for a rod:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516058.png" /></td> </tr></table>

for a membrane:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516059.png" /></td> </tr></table>

and for a plate:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516060.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516061.png" /></td> </tr></table>

The eigen vectors corresponding to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516062.png" /> satisfy the homogeneous system of algebraic equations:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516063.png" /></td> </tr></table>

The problem of finding all eigen values and eigen vectors of a matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516064.png" /> is called the [[Complete problem of eigen values|complete problem of eigen values]], and the problem of finding some eigen values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516065.png" /> is called the [[Partial problem of eigen values|partial problem of eigen values]].

In the case of algebraic systems corresponding to a given problem, the latter problem arises most frequently. The application of traditional solution methods requires a considerable amount of calculation, in view of the poor separation of the eigen values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035160/e03516066.png" />. In this case it is more effective to use modified gradient methods with spectrally equivalent operators (see [[#References|[17]]]- [[#References|[19]]]) and multi-grid methods (see [[#References|[20]]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S. Gould,   "Variational methods for eigenvalue problems" , Univ. Toronto Press  (1957)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L. Collatz,   "Eigenwertaufgaben mit technischen Anwendungen" , Akad. Verlagsgesell. Geest u. Portig K.-D.  (1949)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  D.K. Faddeev,   V.N. Faddeeva,   "Computational methods of linear algebra" , Freeman  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  V.V. Voevodin,   "Numerical methods of algebra" , Moscow  (1966)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  J.H. Wilkinson,   "The algebraic eigenvalue problem" , Oxford Univ. Press  (1969)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  B.N. Parlett,   "The symmetric eigenvalue problem" , Prentice-Hall  (1980)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  V.K. Saul'ev,   "On estimating the error in finding eigenfunctions by the finite difference method"  ''Vychisl. Mat.'' , '''1'''  (1957)  pp. 87–115  (In Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  A.N. Tikhonov,   A.A. Samarskii,   "The Sturm–Liouville difference problem"  ''USSR Comput. Math. Math. Phys.'' , '''1''' :  4  (1961)  pp. 939–961  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''1''' :  5  (1961)  pp. 784–805</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  A.A. Samarskii,   "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D.  (1984)  (Translated from Russian)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  Shou Hao,   "The Sturm–Liouville difference problem for a fourth order equation with discontinuous coefficients"  ''USSR Comput. Math. Math. Phys.'' , '''3''' :  6  (1963)  pp. 1383–1406  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''3''' :  6  (1963)  pp. 1014–1031</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  V.G. Prikazchikov,   "High-accuracy homogeneous difference schemes for the Sturm–Liouville problem"  ''USSR Comput. Math. Math. Phys.'' , '''9''' :  2  pp. 76–106  ''Zh. Vychisl. Mat. Mat. Fiz.'' , '''9''' :  2  (1969)  pp. 315–336</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  V.G. Prikazchikov,   "A difference eigenvalue problem for a second-order operator with mixed boundary conditions"  ''USSR Comput. Math. Math. Phys.'' , '''22''' :  3  (1982)  pp. 165–172  ''Zh. Vychisl. Mat. Mat. Fiz.'' , '''22''' :  3  (1982)  pp. 655–662</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  V.G. Prikazchikov,   A.N. Khimich,   "The eigenvalue difference problem for the fourth order elliptic operator with mixed boundary conditions"  ''USSR. Comput. Math. Math. Phys.'' , '''25''' :  5  (1985)  pp. 137–144  ''Zh. Vychisl. Mat. Mat. Fiz.'' , '''25'''  (1985)</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  B.N. Bublik,   "The numerical solution of problems in the dynamics of plates and hulls" , Kiev  (1969)  (In Russian)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  G.J. Fix,   "An analyse of the finite element method" , Prentice-Hall  (1973)</TD></TR><TR><TD valign="top">[16]</TD> <TD valign="top">  P.G. Ciarlet,   "The finite element method for elliptic problems" , North-Holland  (1978)</TD></TR><TR><TD valign="top">[17]</TD> <TD valign="top">  B.A. Samokish,   "The method of steepest descent in the eigen elements problem for semi-bounded operators"  ''Izv. Vyssh. Uchebn. Zaved. Mat.'' , '''5''' :  6  (1958)  pp. 105–114  (In Russian)</TD></TR><TR><TD valign="top">[18]</TD> <TD valign="top">  E.G. D'yakonov,   M.Yu. Orekhov,   "Minimization of the computational labor in determining the first eigen values of differential operators"  ''Math. Notes'' , '''27'''  (1980)  pp. 382–391  ''Mat. Zametki'' , '''27''' :  5  (1980)  pp. 795–812</TD></TR><TR><TD valign="top">[19]</TD> <TD valign="top">  V.G. Prikazchikov,   ''Differentsial'nye Uravn.'' , '''22'''  (1986)  pp. 1268–1271</TD></TR><TR><TD valign="top">[20]</TD> <TD valign="top">  W. Hackbusch,   "On the computation of approximate eigen values and eigen functions of elliptic operators of means of a multi-grid method"  ''SIAM. J. Num. Anal.'' , '''16''' :  2  (1979)  pp. 201–215</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P.B. Bailey,   M.K. Gordon,   L.F. Shampine,   "Automatic solution of the Sturm–Liouville problem"  ''ACM Trans. Math. Software'' , '''4'''  (1978)  pp. 193–208</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H.O. Kreiss,   "Difference approximation for boundary and eigen values problems for ordinary differential equations"  ''Math. Comp.'' , '''26'''  (1972)  pp. 605–624</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.S. Bramley,   S.C.R. Dennis,   "The calculation of eigenvalues for the stationary perturbation of Poiseuille flow using initial value methods"  ''Math. Anal. Appl.'' , '''101'''  (1984)  pp. 30–38</TD></TR></table>