Knowledge, even approximate, of the extremal eigenvalues of the, large, positive definite, global stiffness matrix generated by the finite-element method (see  ), is essential for assessing the correctness of the numerical solution of the global algebraic system of equations set up by this variational method. Other numerical procedures related to this large algebraic system, such as iterative solution methods, are also greatly affected by the condition number, the ratio of the largest to the smallest eigenvalue, of the matrix (see  ). In this note we, theoretically and numerically, examine various practical procedures for the numerical, a-posteriori, ever better, bounding of the eigenvalues of the large global stiffness matrices generated by the finite-element method, predominantly based on a preparatory, most favorable, similarity transformation. Special attention is paid in this note to the common class of matrices having non-positive off-diagonal entries (see    ). For such matrices, application of the Gershgorin bounding method may be most conveniently carried out by a mere matrix vector multiplication, which may be, in turn, very effectively carried out on the element level (see  ).
2. Gershgorin’s Eigenvalue Bounds
The utterly simple Gershgorin and Rayleigh eigenvalue bound theorems (see   ) are of such fundamental importance in computational linear algebra that we find it good to fully repeat them here.
Throughout this paper we denote a number by a lower case Greek letter, a vector by a lower case Roman letter, and a matrix by an upper case Roman letter.
The eigenvalue spectrum of real symmetric matrix A is real. For such a matrix Gershgorin’s theorem assumes the simpler form.
Theorem (Gershgorin). Let be symmetric, and so of a real eigensystem. Then every eigenvalue of A lies in, or on the end points of, at least one of the intervals
for every eigenvalue of A.
Proof. Let λ be an eigenvalue of A and the corresponding eigenvector, so that . Assume that for this λ the kth component of , is largest in magnitude and is normalized so that and , . The kth equation of is then
since . We do not know what k is, but are sure that λ certainly lies in one of these intervals. □
Gershgorin’s theorem readily provides outside bounds on all eigenvalues of matrix A.
3. Positive-Definite Matrices with Non-Positive Off-Diagonal Entries
Positive definite and symmetric global stiffness matrices of a positive diagonal and non-negative off-diagonal entries are common in the finite elements, or finite differences, method. For such matrices the application of the Gershgorin theorem simplifies into a mere matrix-vector multiplication operation, efficiently carried out as a summation of such multiplications on the element level of the global mesh (see  ).
Say matrix A is symmetric, and positive (semi) definite, and of non-positive off-diagonal entries, then obviously
where is the smallest eigenvalue of matrix A, and the largest. If matrix A is symmetric and positive definite, then . For example
Gershgorin’s theorem correctly predicts here that matrix A is, at least, positive semi-definite, but it fails to ascertain that it is actually positive definite, with a positive lowest eigenvalue. To obtain a more realistic, nontrivial, lower bound on the lowest eigenvalue of matrix A we resort to similarity transformations designed to rescue the lower bound from triviality.
4. Rayleigh Quotient
Let matrix be real and symmetric. If is an eigenvector of A for corresponding eigenvalue , , then , or . The rational function, for variable vector
is the Rayleigh quotient of matrix A. It has some interesting properties of great practical and theoretical reach.
First property: The quotient produces very accurate eigenvalue approximations from even not so good eigenvector approximations. Indeed, let v be an eigenvector corresponding to some , and let
where is the error vector.
since , implying that also . Thus, here
Rayleigh quotient produces a very accurate, , approximation to an eigenvalue from an approximation x to the corresponding eigenvalue that is not very accurate, only . Conversely, a very good approximation to an eigenvalue does not imply it coming from a very good approximation to an eigenvector.
Second property: If , then for any vector
The Rayleigh quotient provides inner bounds on all eigenvalues of symmetric matrix A. Hence the Rayleigh bounds and the Gershgorin bounds complement each other.
Theorem (Rayleigh.) Let the eigenvalues of be arranged in the ascending order , with orthogonal eigenvectors . Then
with the lower equality holding if and only if , and the upper inequality holding if and only if . Also
with the lower equality holding if and only if , and the upper if and only if . The two inequalities reduce to
for arbitrary, nonzero, .
Proof. Vector , orthogonal to has the unique expansion
We normalize x by
and use this equation to eliminate from to be left with
By assumption if and hence
or , with equality holding if and only if
In case of distinct eigenvalues, , equality holds if and only if , and . If eigenvalues repeat and , then need not be zero, but equality still holds if and only if x is in the invariant subspace spanned by the eigenvectors of .
To prove the upper bound we use
to eliminate it from , so as to be left with
and with equality holding if and only if . The proof to the second part of the theorem is the same. □
5. Perron’s Theorem on Positive Matrices
Positive matrices are common in the finite-element method. The following is a symmetric version of Perron’s theorem on positive matrices (see  ).
Theorem (Perron). If A is a symmetric positive matrix, , then the eigenvector corresponding to the largest (positive) eigenvalue of A is positive and unique.
Proof. If is a unit eigenvector corresponding to , and is such that , then
and is certainly positive. Moreover, since the components of cannot have different signs, for this would contradict the assumption that maximizes . Say then that . But none of the components can be zero since , and obviously . Hence .
There can be no other positive vector orthogonal to , and so the eigenvector, and also the largest eigenvalue , are unique. □
The following is another important and useful statement on positive matrices.
Theorem. Suppose that A has a positive inverse . Let x be any vector satisfying , , . Then
Proof. Obviously so that
To prove the other bound write , observe that , and have that
Hence, if , then
This completes the proof.
6. Similarity Transformation, Similar Matrices
We will make also great use of the following fact.
Theorem. If is an eigenvalue of matrix A, then is also an eigenvalue of similar matrix . Similar matrices A and have the same eigenvalues.
Proof. We have
and the result follows. □
In this note we are greatly interested in accurate eigenvectors.
To fix ideas consider the typical finite-elements, or finite-differences, matrix
The matrix A is symmetric and positive definite, , with a corresponding eigenvector that is positive. The fact that is completely positive is a manifestation of the physical fact that a point force applied to the system causes all free points of the system to move, and all in the same direction.
To save Gershgorin’s theorem from the trivial, and useless prediction , we propose to similarly transform matrix A with a positive diagonal matrix D, , such that
The fact that diagonal matrix D is positive, , guarantees that similar matrix retains the entry sign pattern of original matrix A. Namely, , .
For example, with
Now Gershgorin’s theorem correctly recognizes that matrix A is positive definite.
For a better bound, matrix D needs to raise the lowest entry and to lower the highest entry of . Thus,
The optimal D is for which all entries of are equal, or
Namely, the optimal D is such that De is the eigenvector corresponding to the lowest eigenvalue of matrix A. With such a better D, obtained here by inverse iterations on, the here positive, , , we have
Taking the diagonal entries of matrix D as vector x we obtain from Rayleigh’s quotient
which are good enclosing bounds.
As for the highest eigenvalue of matrix A, , we have from Gershgorin and Rayleigh that
with x obtained by the application of three steps of the power method to matrix A starting with to have a reasonable approximate for the eigenvector corresponding to the highest eigenvalue of A.
Next we turn our attention to more realistic finite element examples.
7. Taut String (Cable)
The basic issues of this paper are best illustrated on some concrete cases. First we consider the one-dimensional problem of the taut string discretized by n linear finite elements of which the element stiffness matrix is
in which is the size of the element, n being the number of mesh subdivisions. Little element matrix k is positive semi-definite with a zero eigenvalue for eigenvector . Element stiffness matrix k is, moreover, such that , , and of this sign pattern is also any global matrix A assembled from it.
We assemble the element k matrices into the global matrix A, here over a mesh of five elements, impose the essential boundary condition of a fixed end point by deleting the first row and first column of the assembled global matrix, and are left with
Global stiffness matrix A is now positive definite, . Matrix A is, moreover, tridiagonal with non-positive off-diagonal entries .
We know (see   ) that as the size of matrix increases, its lowest eigenvalue decreases, actually .
8. Taut String, Similarity Transformation Followed by a Gershgorin Bound
Being keenly interested in an actual, numerical lower bound on we naively apply Gershgorin’s theorem directly to global stiffness matrix A of Equation (40) and obtain from it the disappointing
The bounding fails to confirm that matrix A is positive definite, only that it is positive semi-definite. We remark that the lower Gershgorin bound is obtained here as
inasmuch as and .
To avert a trivial Gershgorin bound we propose to similarly transform matrix A into P−1AP with a positive diagonal matrix P to facilitate the inversion, and subsequent matrix-matrix multiplications, while still maintaining .
For example, we take and have
triumphantly ascertaining that global stiffness matrix A is indeed positive definite.
We have already remarked that we desire matrix P to be such that all entries of are nearly equal, or that
or that Pe is the (positive) eigenvector corresponding to .
How to efficiently get good approximations to the first eigenvector of global stiffness matrix A is the subject of the rest of this note.
9. Taut String, Linearization of the Characteristic Polynomial
We know that as the size of matrix increases, its lowest eigenvalue decreases, tending to zero, actually (see again   ). We start the linearization by writing
and have by a successive linearization for of each equation that, approximately
and it follows that the eigenvector corresponding to the lowest eigenvalue of matrix A is approximately
We put and have from
the reasonable bounds
10. Taut String, Quadratization of the Characteristic Polynomial
Keeping quadratic terms of in the characteristic equation of matrix we have for vector x of Equation (46) the five quadratically curtailed equations of :
The success of the linearization, or quadratization, of the characteristic equation hinges on the theoretically assured fact (see   ) that , and that as the size of the finite-elements global stiffness matrix A increases further decreases.
11. Taut String, Linearization Following a Shift
To work with a matrix of a lesser minimal eigenvalue we turn to the shifted matrix
from which we get the approximate linear characteristic polynomial
12. Taut String, Shifted Power Method
We continue with our quest for good approximations to the fundamental eigenvector of the finite elements global stiffness matrix A. We propose to first iterate for the highest eigenvalue and the corresponding eigenvector. We choose to use the power method since it requires but one vector-matrix multiplication per step. We start with
Then we undertake the shift
and apply to it the power method starting now with
to successively have
as upper and lower bounds on .
13. Hanging String
The freely down hanging string (see  ) is of zero tension at the free lower end, and with the tension growing linearly towards the fixed upper hanging point, that carries the entire weight of the string.
The element stiffness matrix of the hanging string of size h is
assembled into the global stiffness matrix
including the essential boundary condition of zero movement of the hanging point. Global stiffness matrix A factors as
showing matrix A to be symmetric and positive definite. In fact, and .
We are seeking good lower and upper bounds on , the lowest eigenvalue of global stiffness A.
14. Hanging String, Linearization of the Characteristic Polynomial
Here we have
with the linearized characteristic polynomial for
from which we get
and then the reasonable bounds
15. Hanging String, Second Sweep for a Linearized Characteristic Polynomial
Now we undertake the shift
intended to further reduce , and have for
a linearization resulting in
and then the linearized characteristic polynomial
From this we have
by which we compute for original matrix A
and , translating into the good bounds
16. Hanging String, Quadratization of the Characteristic Polynomial
Here, for vector x of Equation (75), and the quadratization of we have
and, from the last equation of , the quadratic approximate characteristic polynomial
and have from this that
17. Hanging String, Power Method
The global stiffness matrix we take is still the modest
with corresponding eigenvectors
We start the power method with
to successively produce
It follows then, from Rayleigh and Gershgorin, that
18. Hanging String, Shifted Power Method
Next we turn our attention to computing, an ever better, approximation to , the lowest eigenvalue of global stiffness matrix A of the hanging string. For this we take the shifted matrix
The power method applied to matrix B converges now to , the eigenvector corresponding to the lowest eigenvalue of original matrix A.
We start with
and repeatedly compute
and have that
which we gladly accept.
19. The Four-Nodes Rectangular Membrane Element
Next we move on to two dimensional finite-element membrane problems, or the boundary value problem
where n is an outwardly normal to boundary S encompassing domain D.
The element stiffness and mass matrices for the rectangular four-nodes membrane finite element of sides a and b are
respectively. If , then
Element stiffness matrix k of Equation (97) is of a positive diagonal and non-positive off-diagonal entries, and hence such is also any global matrix assembled from it.
Global stiffness matrix A for the modest mesh is
with, as expected, and . The eigenvalues and eigenvectors of global stiffness A are
20. Rectangular Membrane, Power Method
We prefer the power method as it requires only a vector-matrix multiplication, We start the method with the initial
and keep multiplying, or raising to ever higher power, to have.
such that, by Rayleigh and Gershgorin
21. Rectangular Membrane. Shifted Power Method
Now we go after the, more interesting, lowest eigenvalue of the global stiffness matrix A and replace it by the shifted matrix
We start with and continue to have
which we appraise as quite good and tight numerical bounds.
22. Triangular Membrane, Triangular Finite Elements
The linear, first order, membrane finite element stiffness matrix k for a triangle of sides and area T is
where are the constant matrices
Otherwise, the element stiffness matrix is written, by the aid of the law of the cosines, as
where is the angle opposite . If , then , and so is any global stiffness matrix assembled from it.
We consider now an equilateral triangular membrane discretized by four equilateral triangular finite elements per side. The membrane is held fixed on one side, to produce the 10 × 10 symmetric and positive definite global stiffness matrix
with, as expected, and . The ten computed eigenvalues of this matrix are:
23. Triangular Membrane, Power Method
We start our iterative quest for the highest eigenvalue of matrix A with , and then continue with the power method to have
and thus, by Rayleigh and Gershgorin
24. Triangular Membrane, Shifted Power Method
Next we turn our attention to the lowest eigenvalue of global stiffness matrix A of the triangular membrane. For this we apply the power method again, but this time to the shifted matrix
in which is the rayleigh quotient for obtained by the power method in the previous section.
We start with an arbitrary and continue with the shifted power method to have
In this note we have considered the common case of the positive definite and symmetric global finite element stiffness matrices having non positive off-diagonal entries. The finite element global stiffness matrix readily becomes very large with an ever smaller least eigenvalue.
We have shown here how optimal similarity transformations of this matrix, requiring only matrix-vector multiplication, lead to eminently practical and reliable numerical iterative algorithms for tight realistic Rayleigh and Gershgorin bounds on the least eigenvalue of this large finite-elements global stiffness matrix.
 Fried, I. (1973) Bounds on the Spectral and Maximum Norms of the Finite Element Stiffness, Flexibility and Mass Matrices. International Journal of Solids and Structures, 9, 1013-1034.
 Fujimoto, T. and Ranade, R. (2004) Two Characterizations of Inverse-Positive Matrices: The Hawkins-Simon Condition and the Le Chatelier-Braun Principle. Electronic Journal of Linear Algebra, 11, 59-65.
 Fried, I. (1970) A Computational Procedure for the Solution of Large Problems Arising from the Finite Element Method. International Journal for Numerical Methods in Engineering, 2, 477-494.
 Scott, D.S. (1985) On the Accuracy of the Gershgorin Circle Theorem for Bounding the Spread of a Real Symmetric Matrix. Linear Algebra and Applications, 65, 147-155.