View source for Eigen values of integral operators, numerical methods

<!--
e0351701.png
$#A+1 = 79 n = 0
$#C+1 = 79 : ~/encyclopedia/old_files/data/E035/E.0305170 Eigen values of integral operators, numerical methods
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

Numerical methods for computing the complete spectrum of an integral operator or a part of it (usually one is required to find one or two eigen values of minimal or maximal modulus).

This is often accompanied by the problem of finding numerical approximations of the eigen functions or, more generally, of the root functions, of a given integral operator, corresponding to the desired eigen values. The most important problem is that of finding the eigen values (and eigen functions) of a Fredholm linear integral operator (cf. [[Fredholm-operator(2)|Fredholm operator]]).

==Numerical methods for determining the eigen values of Fredholm integral operators.==
The eigen value and eigen function problems for a Fredholm integral operator consist of finding the complex numbers  $  \lambda $
for which there is a non-trivial solution (in a given class of functions) of the integral equation

$$ \tag{1 }
\lambda A \phi  = \ 
\lambda \int\limits _ { D }
K ( x, s) \phi ( s)  ds  =  \phi ( x).
$$

Here,  $  K ( x, s) $
is a function (or matrix function) of two groups of variables  $  x $
and  $  s $
such that the integral operator with kernel  $  K $
is a Fredholm operator on the given class of functions, and  $  D $
is a domain in a Euclidean space  $  \mathbf R  ^ {m} $. 
The class of functions may be the space  $  C ( D) $
of continuous functions on  $  D $, 
the space  $  L _ {2} ( D) $
of square-integrable functions on  $  D $
or some other function space.

The basic approximation method for solving the eigen value problem (1) is as follows. One chooses some approximation of the integral operator in (1) (see [[Fredholm equation, numerical methods|Fredholm equation, numerical methods]]), e.g., the integral is replaced by a quadrature formula:

$$ \tag{2 }
\int\limits _ { D }
K ( x, s) \phi ( s)  ds  \approx \ 
\sum _ {i = 1 } ^ { N } 
a _ {i}  ^ {(} N)
K ( x, s _ {i} )
\phi ( s _ {i} )  = \ 
\widetilde{A}  \phi ,
$$

where the  $  s _ {i} $
are nodes of the quadrature formula and the  $  a _ {i}  ^ {(} N) $
are its weights (see [[#References|[3]]]–[[#References|[5]]]).

Instead of (1), one considers the problem of finding the eigen values and corresponding root spaces of some matrix naturally connected with the approximation (2). Namely,

$$ \tag{3 }
\lambda
\sum _ {i = 1 } ^ { N } 
a _ {i}  ^ {(} N)
K ( s _ {j} , s _ {i} )
\widetilde \phi   ( s _ {i} )  = \ 
\widetilde \phi   ( s _ {j} ),\ \ 
j = 1 \dots N.
$$

To solve (3), one can use any of the methods of linear algebra for finding eigen values and eigen vectors, or, more generally, root spaces (see [[Linear algebra, numerical methods in|Linear algebra, numerical methods in]]). The resulting eigen values and eigen vectors of the algebraic problem (3) will be close to certain eigen values and eigen vectors of the original problem (1), provided that the operators  $  A $
and  $  \widetilde{A}  $
are close in some specific sense. Instead of (2), other approximations of the integral operator can also be used. The original problem (1) is thus reduced to an algebraic problem analogous to (3). The investigation of the distance between the solutions of the problems (1) and (3) is carried out by methods of functional analysis within the framework of the general theory of approximation methods. The eigen value problem (1) is then treated as a problem of finding the eigen values of some completely-continuous operator  $  A $
acting on a Banach space  $  \Phi $:

$$ \tag{4 }
\lambda  A \phi  =  \phi .
$$

Problem (3) is treated as the eigen value problem for an operator  $  \widetilde{A}  $
which is close to  $  A $
but, generally speaking, acts on another space  $  \widetilde \Phi   $(
related to  $  \Phi $):

$$ \tag{5 }
\lambda  \widetilde{A}  \widetilde \phi    =  \widetilde \phi   .
$$

In the general theory of approximation methods, one can prove various theorems about the distance between solutions of problems (4) and (5). As an example of such a statement one can mention the following. Let  $  A _ {n} $
be a sequence of operators acting on  $  \Phi $, 
and let

$$ 
\lim\limits _ {n \rightarrow \infty } \ 
\| A _ {n} - A \|  =  0.
$$

Then

$$ 
\overline{ {\cup _ { n } \sigma ( A _ {n} ) }}\;
 \supseteq  \sigma ( A),
$$

where  $  \sigma ( \cdot ) $
is the spectrum of the corresponding operator. In this case, every  $  \widetilde \Phi   $
coincides with  $  \Phi $.

The majority of general estimates of the distance between the eigen values and eigen vectors of the approximation problem (5) to those of (4) are not effective: they contain constants whose values are usually not known. To control the precision in such cases one can use a sequence of eigen values (vectors) approximating the desired eigen value (vector) in (1) (or (4)). It is advisable to construct such a sequence without appealing directly to a sequence of problems of the type (5) with successive refinements of  $  \widetilde{A}  $, 
since this course leads to very cumbersome calculations. Instead of this, one can apply various refinement algorithms (for example, based on [[Perturbation theory|perturbation theory]]).

==Generalized eigen value problems.==
In applications one also encounters a more general problem than (4), namely that of finding critical parameters of eigen value type. Such problems can be formulated in abstract form as follows.

One has to find values of the parameter  $  \lambda $
for which the equation

$$ \tag{6 }
A ( \lambda , \phi )  =  \phi
$$

has more than one solution in  $  \phi $(
where  $  A $
is some non-linear integral operator on a Banach space  $  \Phi $
which depends on the complex parameter  $  \lambda $).

In problem (6) there can be further restrictions on  $  \| \phi \| $
and on  $  \lambda $(
for example, one can ask for only those  $  \lambda $
that satisfy the condition  $  | \lambda | \leq  R $, 
where  $  R $
is given, and  $  \| \phi \| \leq  R $).

Problem (6) is closely connected with various problems about bifurcation points in non-linear integral equations. A case of interest is that in which  $  A ( \lambda , \phi ) $
is linear in  $  \phi $, 
but  $  \lambda $
does not enter the equation multiplicatively. The general problem on bifurcation points can be reduced to this form. Moreover, the problem of determining the eigen values of the linear operator (1) that lie in the disc  $  | \lambda | \leq  R $, 
for fixed  $  R $, 
reduces to the more general problem (6), in which the operator  $  A ( \lambda , \phi ) $
is linear in  $  \phi $
and has a finite-dimensional range. In fact, let  $  \widehat{A}  $
be an integral operator with a degenerate kernel and close in norm to  $  A $: 
$  \| \widehat{A}  - A \| \leq  \delta $. 
Equation (1) can be rewritten as:

$$ 
[ E + \lambda ( \widehat{A}  - A)] \phi  =  \lambda \widehat{A}  \phi .
$$

If  $  | \lambda | < 1/ \delta $, 
then  $  E + \lambda ( \widehat{A}  - A) $
is invertible, and the eigen values  $  \lambda $
with  $  | \lambda | < 1/ \delta $
can be found from the relation

$$ \tag{7 }
Z  =  \lambda \widehat{A} 
( E + \lambda ( \widehat{A}  - A))  ^ {-} 1 Z,
$$

where  $  Z = [ E + \lambda ( \widehat{A}  - A)] \phi $. 
Equation (7) is equivalent (with respect to  $  Z $) 
to some system of linear algebraic equations. By putting its determinant equal to zero, one obtains an equation whose roots are eigen values of the integral operator (1). This argument is valid in general for an arbitrary completely-continuous operator  $  A $
on a Banach space  $  \Phi $, 
provided that it admits an approximation in norm by operators with a finite-dimensional range. The construction (7) can also be used to obtain a refinement of an approximate eigen value (and eigen function).

The general problem (6) can (by approximating  $  A $) 
be reduced by approximation to a finite-dimensional problem of type (6). In the case of more complex problems of this type, the Monte-Carlo method can be used (see [[#References|[7]]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  L.V. Kantorovich,   V.I. Krylov,   "Approximate methods of higher analysis" , Noordhoff  (1958)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  M.A. Krasnosel'skii,   G.M. Vainikko,   P.P. Zabreiko,   et al.,   "Approximate solution of operator equations" , Wolters-Noordhoff  (1972)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  I.S. Berezin,   N.P. Zhidkov,   "Computing methods" , Pergamon  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  V.I. Krylov,   V.V. Bobkov,   P.I. Monastyrnyi,   "Numerical methods" , '''2''' , Moscow  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  I.P. Mysovskikh,   "On interpolation by polynomials in two variables"  ''Metod. Vychisl.'' , '''8'''  (1973)  pp. 3–114  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  G.I. Marchuk,   V.I. Lebedev,   "Numerical methods in the theory of neutron transport" , Harwood  (1986)  (Translated from Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  V.S. Vladimirov,   I.M. Sobol',   "Computation of the least eigen value of the Peierls equation by the Monte Carlo method"  ''Vychisl. Mat.'' , '''3'''  (1958)  pp. 130–137  (In Russian)</TD></TR></table>

====Comments====
Instead of  "generalized eigen value problem" , the phrase  "non-linear eigenvalue problem for an integral operator47J10non-linear eigen value problem"  is also used. Moreover, what is called  "eigen value"  in the article is also called  "characteristic value of an integral operator45C05characteristic value" , while the term  "eigen value"  is (more frequently) used for complex numbers  $  \mu $
such that the equation  $  A \phi = \mu \phi $
has a non-trivial solution.

For many concrete methods of approximating  $  A $
by  $  A _ {n} $, 
the condition  $  \lim\limits _ {n \rightarrow \infty }   \| A _ {n} - A \| = 0 $
used above is too strong. Instead, one typically has that  $  A _ {n} $[[
Pointwise convergence|converges pointwise]] to  $  A $
and that  $  \{ A _ {n} \} $
is collectively compact (i.e., for all bounded sets  $  B $, 
$  {\cup _ {n \in \mathbf N }  A _ {n} ( B) } bar $
is compact). For convergence results for eigen values of  $  A _ {n} $
to those of  $  A $
in this framework see, e.g., [[#References|[a1]]], Chapt. 4.

In the Western literature, detailed accounts of the topic of the article are given, e.g., in [[#References|[a2]]], Chapt. 3, and [[#References|[a3]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P.M. Anselone,   "Collectively compact operator approximation theory and applications to integral equations" , Prentice-Hall  (1971)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  C.T.H. Baker,   "The numerical treatment of integral equations" , Clarendon Press  (1977)  pp. Chapt. 4</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  F. Chatelin,   "Spectral approximation of linear operators" , Acad. Press  (1983)</TD></TR></table>