One Approach to Construction of Bilateral Approximations Methods for Solution of Nonlinear Eigenvalue Problems ()
1. Introduction
Many theoretical and applied problems of mathematical physics, mechanics and engineering sciences lead to eigenvalue problems. The class of self-adjoint eigenvalue problems, perhaps the most important class of problems because numerous problems that occur in practice belong to this class. However, the eigenvalue problems that are important in practice, very rarely can be solved in a closed form, as a rule one must use numerical methods to solve them. Most numerical methods simply provide approximations to eigenvalues, but they do not make it possible to state how far the calculated eigenvalue is from the true one. Since the self-adjoint eigenvalue problem can have only real eigenvalues, the problem of obtaining approximations and corresponding error estimations of approximation accuracy is equivalent to the determination of upper and lower bounds for the eigenvalues.
Large interest in the eigenvalue bounds, take not only mathematicians, but also physicists, chemists, and engineers and it has many reasons. We name at least two of them here:
1) Lower bounds for eigenvalues are necessary in order to compare predictions of physical theories with experimental results; fine structure corrections in quantum mechanical problems.
2) The knowledge of boundaries for eigenvalues makes it possible in many cases to estimate the reliability of iterative approximation, that is at every step of iterative process to obtain the comfortable a posteriori estimate of error calculations.
For a large class of problems, good upper bounds for positive eigenvalues can be determined relatively easy by means of the Rayleigh-Ritz procedure. To estimate the accuracy of approximations, which are obtained by the Rayleigh-Ritz method, it is important to know at least rough approximations from below. Basically, there are three classes of methods for calculation the lower bounds for eigenvalues (disregarding the methods with a very limited scope of application):
1) The methods based on inclusion theorem.
2) The method of intermediate problems.
3) The Fichera method.
The methods based on inclusion theorems go back to G. Temple [1], L. Collatz [2], and N.J. Lehmann [3,4]. For these methods we need of rough a priori information on the localization of one of the eigenvalues, for example, we need to know:
—the lower bound of 
and
, then
.
In this direction we should note the work of A. V. Knyazev [5,6], B. N. Parlett [7], Behnke H. [8,9], Marmorino M.G. [10].
The method of intermediate problems was proposed by A. Weinstein [11]. Later on the method has been refined by N. Bazly, D. W. Fox, C. Beattie, and others (see [12- 14] and the bibliography in [10,14,15]). For this method one needs the eigenvectors of a neighbouring eigenvalue problem in a closed form. The essence of the method of intermediate problems is as follows: along with the selfadjoint operator 
whose eigenvalues are sought, the operator 
with known eigenvalues and eigenvectors, and such that the operator 
is positive, is considered. 
is called a basic operator. Its range probably lies below the spectrum of the operator
. Once the basic operator is selected, by means of the finite perturbation 
a monotonous sequence of intermediate operators 
spectra of which approximate the spectrum of operator 
from below is constructed.
The method, different from the method of intermediate problems was proposed by G. Fichera [16]. This method does not require constructing a base operator with a known spectrum, but has a narrower scope of application. It is applied to the operator
, the inverse to which is a compact operator, and the problem
, where
, 
, is solved. Then
.
This paper presents a new approach to construction the methods and algorithms of bilateral approximations of eigenvalues for nonlinear (with respect to spectral parameter) eigenvalue problems, wich have supra-linear speed of convergence. This approach does not use the concepts and apparatus of interval analysis (see, e.g. [20, 21]).
The idea of the approach proposed is that for a continuous monotone in a neighborhood of simple zero 
function
, which describes the nonlinear equation some auxiliary function 
that has the same zero as the function 
and such necessary properties that allow one to build the iterative processes which give monotonous bilateral (alternating or including) approximations to the root of a nonlinear equation [17-19] is constructed and investigated.
Within this approach, the algorithms of bilateral analogues of Newton’s method for finding the eigenvalues of nonlinear spectral problems are constructed and justified. The conditions on the initial approximations which provide the alternate approximations to the eigenvalue from two sides and ensure the convergence of iterative process, are obtained.
2. Statement of the Problem and Some Preliminary Results
We consider the nonlinear eigenvalue problem
, (1)
where 
is a square matrix of order
, all elements of which are sufficiently smooth (at least twice continuously differentiable) functions of the parameter
,
. Eigenvalues sought for solutions of the determinant equation
. (2)
To determine the isolated eigenvalue of matrix we propose and justify the Newton-type iterative processes that give the alternate approximations to the root of the Equation (2), i.e.
(3)
or
and the including monotonous bilateral approximations to the root, i.e.
(4)
without revealing in so doing the determinant
. This means that the left hand side of equation (2) in explicit form is not set, but the algorithm of finding the functions 
and thein derivatives 
and 
at a fixed value of the parameter
, using the LU-decomposition of the matrix 
is proposed. This algorithm is based on the fact that the matrix 
of the order
, in which at any given value 
the principal minors of all orders from 1 to 
differ from zero, by LU-decomposition can be written as
where 
is the lower triangular matrix with single diagonal elements, and 
is the upper triangular matrix. Then
Since the elements of a square matrix 
(and, therefore, the matrix
) are differentiable function, with respect to
, then for any 
we obtain that
,
where 
and 
are the elements of matrices 
and 
in such decompositions
(5)
whence we obtain
, 
,
(6)
The elements of matrices in the decompositions (5) can be calculated using the corresponding recurrent relations written out in [22] (see also [23,24]).
So, not knowing the explicit dependence 
on
, for any fixed 
we can find the value of 
and its derivatives. Therefore, for solving (2) we can use the methods that apply the derivatives, in particular, to construct the Newton-type methods, which give the bilateral approximation to the solution. This requires further study of the function
, which are realized later in the work.
Further, we demand 
to be a three times continuously differentiable function of real variable. By 
we denote an accurate simple root of equation (2) (
=0), in some neighborhood of which such behavior of function 
is possible.
1). Function 
is convex (
) and its derivative is
.
2). Function 
is concave (
) and its derivative is
.
3). Function 
is convex (
) and its derivative is
.
4). Function 
is concave (
) and its derivative is
.
3. Auxiliary Function and Its Properties
Along with 
we consider also a function
which obviously has the same zeros as the function
. It is easy to verify that 
is twice constinuously differentiable at the point of 
for which the relation
, 
is satisfied and which has the following properties.
Theorem 3.1. Let 
be a simple real root of Equation (2) in some neighborhood 
of which for the function 
one of the conditions (A)-(D) is satisfied. Then there is a neighborhood of the root
, in which:
1) when the condition (A) or (D) is satisfied, the function 
is a convex and monotonically increasing function, its derivative 
and it increases monotonically;
2) when the condition (B) or (C) is satisfied, the function 
is a concave and monotonically increasing function, its derivative 
and it monotonically decreases.
Proof. Let 
be a decreasing and convex with respect to 
on U function, that is, 
and 
(the case (A)).
Since the function
at the point 
is equal to zero, then because of continuity of 
there is such neighborhood of the root
in which
.
It follows that in the neighborhood 
the function is
, since
. (7)
Now from the mean value theorem, applied to differentiable functions 
on the interval 
we obtain
, 
whence it follows that the function 
is an increasing one.
Consider now the behavior of function 
in the neighborhood
, taking into account its image (7). For any 
and 
we obtain, respectively, the inequalities
(8)
since 
for 
and for 
. From the inequalities (8) it follows that in the neighborhood 
the derivative 
is increasing, and, consequently, the function 
is convex in this neighborhood of the root.
Similar statements about the function 
and its derivatives we obtain also for the cases (B), (C) and (D). But unlike the cases (A) and (D), in the cases (B) and (C) the function 
is concave. The theorem is proved.
Thus, Theorem 3.1 determines the properties of function
, and Figure 1 illustrates its behavior depends on the properties of function 
in some neighborhood of the root
.
4. Bilateral Analogues of Newton Method
Using the properties of functions
, we construct the sequence 
which has the property (3).
For the cases (A) and (D) iterative process can be rewritten in the form
(9)
and for the cases (B) and (C) as
(10)
.
Justification of bilateral convergence of iterative processes provide the following theorems.
Theorem 4.1. Let 
be a simple real root of equation (2) and let in some neighborhood of the root
,
Figure 1. Behavior of the functions f(λ) and z(λ) in the neighborhood of a simple real root λ* of functions f(λ).
in which
for three times continuously differentiable function 
that describes the equation (2.2), the condition (A) or (D) be satisfied, and for the function 
the inequalities
for
,
for
be satisfied, where
,
In addition, let the conditions
,
be satisfied, where
.
Then the iterative process (9), beginning with
, convergence to solution 
from both sides
and for the errors from the left and from the right the estimations
,
.
are fulfilled, respectively.
Theorem 4.2. Let 
be a simple real root of equation (2) and let in some neighborhood of the root
in which
for three times continuously differentiable function 
that describes the Equation (2), the condition (B) or (C) to be satisfied, and for the function 
the inequalities
for
,
for 
be satisfied, where
,
.
In addition, let the conditions
,
be satisfied, where
Then the iterative process (10), beginning with
, convergence to the solution 
from both sides
and for the errors from the left hand and from the right hand the estimation
,
.
are fulfilled, respectively.
Remark. Two different iterative processes (9) and (10) were used above to justify the alternate approximation in the ideal case, when the behavior of functions 
is known or easily investigates. Then alternate approximations come from
.
In practice, you can use any one of them for all cases (A)-(D) and regardless of which side (left or right from the root
) the initial approximation 
is and the algorithm adapts itself to bilateral approximations but then alternate approximations appear at least with
.
5. Algorithm of Alternate Approximations and Numerical Results
To test the proposed iterative processes consider the model eigenvalue problem with quadratic dependence on the parameter
, (11)
where
,
,
.
The eigenvalues will be found as solutions of the determinant equation
.
To this end we use the iterative process of alternate approximations (9), which is represented in equivalent form by replacing the function value and its derivatives at the required points by relations (6), which are obtained as a result of LU-decomposition of the matrix 
(5). As a result, the iterative process (9) takes the form
(12)
where 
are the elements of matrix 
and 
in the decompositions (5) at the fixed
, and 
are the elements of matrix 
in this decompositions (5) at the fixed
.
Thus, the algorithm can be written in the following.
Algorithm.
Step 1. Set the initial approximation 
to the 
-th eigenvalue of the problem (2.15).
Step 2. for m = 0,1,2, ··· to achieve the accuracy do Step 3. if m is even.
Step 4. Compute the values 
from the decompositions (5) at
.
Step 5. Compute the approximation to the eigenvalue 
by (12).
Step 6. go to step 10.
Step 7. if m is odd.
Step 8. Compute the values 
from the decompositions (5) at
.
Step 9. Compute the approximation to the eigenvalue 
by (12).
Step 10. end for m.
For numerous initial approximations all the eigenvalues of problem (11) were calculated. They fully coincide with the eigenvalues obtained by the usual Newton’s method. But the advantage of the algorithm is, in particular, that they give the bilateral approximations. It can be seen, having considered the Table 1 which shows the results of calculations for four eigenvalues. The first column shows the number of eigenvalue, the second shows the number of iterations, the third and fifth the obtained approximations are indicated, respectively, of the left hand and of the right hand, to the 
-th eigenvalue at each iteration, including the initial approximation. The value of the s-th eigenvalue is given in the fourth column. Calculations were carried out to within
.
The table shows that for the 1st and 2nd eigenvalues for the iterative process we obtain bilateral alternating approximations of the form
and for the 7th eigenvalue of the form
beginning with
. For the 8th eigenvalue we have obtained the also bilateral approximations similar as for the 7th one, but the alternating approximations come from
, i.e.
.
6. Conclusions
Approbation of constructed algorithms on model problems shows their reliability and efficiency, and also advantages in comparison with the usual Newton’s method in the sense that at every step of iterative process we obtain two-sided estimates of the desired solution, and hence at each step we obtain comfortable a posteriori error estimates .
The proposed approach can be applied to the linear eigenvalue problems with respect to the spectral parameter, moreover if it is compared with existing approaches for obtaining lower bounds of eigenvalues of self-adjoint spectral problems, the approach in contrast to:
the methods based on inclusion theorems (Temple, Krylov-Bogolyubov), does not require knowledge of the lower border of the following eigenvalue (assuming that the eigenvalues are arranged in ascending order) the method of intermediate problems and its various modifications does not require construction of a basic operator with known eigenvalues so that the differ-
Table 1. Bilateral approximations of the eigenvalues of the problem (11).
ence between self-adjoint operator of the original problem and the base one was a positive operator, and constraction of finite-dimentional perturbation of basic operator Fikera method and its modifications, does not require that the inverse to the original operator was compact operator and its construction.