Extremal eigenvalue intervals of symmetric tridiagonal interval matrices

Computing the extremal eigenvalue bounds of interval matrices is non‐deterministic polynomial‐time (NP)‐hard. We investigate bounds on real eigenvalues of real symmetric tridiagonal interval matrices and prove that for a given real symmetric tridiagonal interval matrices, we can achieve its exact range of the smallest and largest eigenvalues just by computing extremal eigenvalues of four symmetric tridiagonal matrices.     

Eigenvalue estimates for preconditioned saddle point matrices

New accurate eigenvalue bounds for symmetric matrices of saddle point form are derived and applied for both unpreconditioned and preconditioned versions of the matrices. The estimates enable a better understanding of how preconditioners should be chosen. The preconditioners provide efficient iterative solution of the corresponding linear systems with, for some important applications, an optimal order of computational complexity. The methods are applied for Stokes problem and for linear elasticity problems. Copyright © 2005 John Wiley & Sons, Ltd.     

Bounds for the Perron root, singularity/nonsingularity conditions, and eigenvalue inclusion sets

Using a unified approach based on the monotonicity property of the Perron root and its circuit extension, a series of exact two-sided bounds for the Perron root of a nonnegative matrix in terms of paths in the associated directed graph is obtained. A method for deriving the so-called mixed upper bounds is suggested. Based on the upper bounds for the Perron root, new diagonal dominance type conditions for matrices are introduced. The singularity/nonsingularity problem for matrices satisfying such conditions is analyzed, and the associated eigenvalue inclusion sets are presented. In particular, a bridge connecting Gerschgorin disks with Brualdi eigenvalue inclusion sets is found. Extensions to matrices partitioned into blocks are proposed.     

Computation of bounds for eigenvalues of structures with interval parameters

In this paper, the computation of eigenvalue bounds for generalized interval eigenvalue problem is considered. Two algorithms based on the properties of continuous functions are developed for evaluating upper and lower eigenvalue bounds of structures with interval parameters. The method can provide the tightest bounds within a given precision. Numerical examples illustrate the effectiveness of the proposed method.     

非负矩阵最大特征值的新界值

对最大特征值的上下界进行估计是非负矩阵理论的重要部分,借助两个新的矩阵,从而得到一个判定非负矩阵最大特征值范围的界值定理,其结果比有关结论更加精确.     

Upper (lower) bounds of the eigenvalues,spread and the open problems for the real symmetric interval matrices

This work is concerned with exploring the upper bounds and lower bounds of the eigenvalues of real symmetric matrices of order n whose entries are in a given interval. It gives the maximum and minimum of the eigenvalues and the upper bounds of spread of real symmetric interval matrices in all cases. It also gives the answers of the open problems for the maximum and minimum of the eigenvalues of real symmetric interval matrices. Copyright © 2012 John Wiley & Sons, Ltd.     

Natural frequencies of structures with uncertain but nonrandom parameters

In this paper, we present a method for computing upper and lower bounds of the natural frequencies of a structure with parameters which are unknown, except for the fact that they belong to given intervals. These parameters are uncertain, yet they are not treated as being random, since no information is available on their probabilistic characteristics. The set of possible states of the system is described by interval matrices. By solving the generalized interval eigenvalue problem, the bounds on the natural frequencies of the structure with interval parameters are evaluated. Numerical results show that the proposed method is extremely effective.The research reported in this paper has been supported by the PRC National Natural Science Foundation and by the USA National Science Foundation Grant MSM-9215698 (Program Director Dr. K. P. Chong).     

非负矩阵最大特征值的估计法

通过构造一个新的矩阵,从而得到一个非负矩阵最大特征值的估计法,该方法将适用范围推广到一般非负矩阵,并通过实例验证了这种新方法精确度更高.     

On the sharpness of two-sided bounds for the Perron Root and of the related eigenvalue inclusion sets

The paper considers the sharpness problem for certain two-sided bounds for the Perron root of an irreducible nonnegative matrix. The results obtained are applied to prove the sharpness of the related eigenvalue inclusion sets in classes of matrices with fixed diagonal entries, bounded above deleted absolute row sums, and a partly specified irreducible sparsity pattern.     

Efficient computation of spectral bounds for Hessian matrices on hyperrectangles for global optimization

We compare two established and a new method for the calculation of spectral bounds for Hessian matrices on hyperrectangles by applying them to a large collection of 1,522 objective and constraint functions extracted from benchmark global optimization problems. Both the tightness of the spectral bounds and the computational effort of the three methods, which apply to $C^2$ functions ${\varphi }:\mathbb{R }^n\rightarrow \mathbb{R }$ that can be written as codelists, are assessed. Specifically, we compare eigenvalue bounds obtained with the interval variant of Gershgorin’s circle criterion (Adjiman et al. in Comput Chem Eng 22(9):1137–1158, 1998; Gershgorin in Izv. Akad. Nauk SSSR, Ser. fizmat. 6:749–754, 1931), Hertz (IEEE Trans Autom Control 37:532–535, 1992) and Rohn’s (SIAM J Matrix Anal Appl 15(1):175–184, 1994) method for tight bounds of interval matrices, and a recently proposed Hessian matrix eigenvalue arithmetic (Mönnigmann in SIAM J. Matrix Anal. Appl. 32(4): 1351–1366, 2011), which deliberately avoids the computation of interval Hessians. The eigenvalue arithmetic provides tighter, as tight, and less tight bounds than the interval variant of Gershgorin’s circle criterion in about 15, 61, and 24 % of the examples, respectively. Hertz and Rohn’s method results in bounds that are always as tight as or tighter than those from Gershgorin’s circle criterion, and as tight as or tighter than those from the eigenvalue arithmetic in 96 % of the cases. In 4 % of the examples, the eigenvalue arithmetic results in tighter bounds than Hertz and Rohn’s method. This result is surprising, since Hertz and Rohn’s method provides tight bounds for interval matrices. The eigenvalue arithmetic provides tighter bounds in these cases, since it is not based on interval matrices.     

Calculating the minimal/maximal eigenvalue of symmetric parameterized matrices using projection

In applications of linear algebra including nuclear physics and structural dynamics, there is a need to deal with uncertainty in the matrices. We focus on matrices that depend on a set of parameters ω and we are interested in the minimal eigenvalue of a matrix pencil ( A , B ) with A , B symmetric and B positive definite. If ω can be interpreted as the realization of random variables, one may be interested in statistical moments of the minimal eigenvalue. In order to obtain statistical moments, we need a fast evaluation of the eigenvalue as a function of ω . Because this is costly for large matrices, we are looking for a small parameterized eigenvalue problem whose minimal eigenvalue makes a small error with the minimal eigenvalue of the large eigenvalue problem. The advantage, in comparison with a global polynomial approximation (on which, e.g., the polynomial chaos approximation relies), is that we do not suffer from the possible nonsmoothness of the minimal eigenvalue. The small‐scale eigenvalue problem is obtained by projection of the large‐scale problem. Our main contribution is that, for constructing the subspace, we use multiple eigenvectors and derivatives of eigenvectors. We provide theoretical results and document numerical experiments regarding the beneficial effect of adding multiple eigenvectors and derivatives.     

Eigenvectors of interval matrices over max–plus algebra

The behaviour of a discrete-event dynamic system is often conveniently described using a matrix algebra with operations max and plus. Such a system moves forward in regular steps of length equal to the eigenvalue of the system matrix, if it is set to operate at time instants corresponding to one of its eigenvectors. However, due to imprecise measurements, it is often unappropriate to use exact matrices. One possibility to model imprecision is to use interval matrices. We show that the problem to decide whether a given vector is an eigenvector of one of the matrices in the given matrix interval is polynomial, while the complexity of the existence problem of a universal eigenvector remains open. As an aside, we propose a combinatorial method for solving two-sided systems of linear equations over the max–plus algebra.     

Conditioning analysis of block incomplete factorizations and its application to elliptic equations

Summary. The paper deals with eigenvalue estimates for block incomplete factorization methods for symmetric matrices. First, some previous results on upper bounds for the maximum eigenvalue of preconditioned matrices are generalized to each eigenvalue. Second, upper bounds for the maximum eigenvalue of the preconditioned matrix are further estimated, which presents a substantial improvement of earlier results. Finally, the results are used to estimate bounds for every eigenvalue of the preconditioned matrices, in particular, for the maximum eigenvalue, when a modified block incomplete factorization is used to solve an elliptic equation with variable coefficients in two dimensions. The analysis yields a new upper bound of type for the condition number of the preconditioned matrix and shows clearly how the coefficients of the differential equation influence the positive constant . Received March 27, 1996 / Revised version received December 27, 1996     

An inequality for nonnegative matrices and the inverse eigenvalue problem

We present two versions of the same inequality, relating the maximal diagonal entry of a nonnegative matrix to its eigenvalues. We demonstrate a matrix factorization of a companion matrix, which leads to a solution of the nonnegative inverse eigenvalue problem (denoted the nniep) for 4×4 matrices of trace zero, and we give some sufficient conditions for a solution to the nniep for 5×5 matrices of trace zero. We also give a necessary condition on the eigenvalues of a 5×5 trace zero nonnegative matrix in lower Hessenberg form. Finally, we give a brief discussion of the nniep in restricted cases.     

The unitary completion and QR iterations for a class of structured matrices

We consider the problem of completion of a matrix with a specified lower triangular part to a unitary matrix. In this paper we obtain the necessary and sufficient conditions of existence of a unitary completion without any additional constraints and give a general formula for this completion. The paper is mainly focused on matrices with the specified lower triangular part of a special form. For such a specified part the unitary completion is a structured matrix, and we derive in this paper the formulas for its structure. Next we apply the unitary completion method to the solution of the eigenvalue problem for a class of structured matrices via structured QR iterations.

     

Numerical enclosure for multiple eigenvalues of an Hermitian matrix whose graph is a tree

In this paper we consider a numerical enclosure method for multiple eigenvalues of an Hermitian matrix whose graph is a tree. If an Hermitian matrix A whose graph is a tree has multiple eigenvalues, it has the property that matrices which are associated with some branches in the undirected graph of A have the same eigenvalues. By using this property and interlacing inequalities for Hermitian matrices, we show an enclosure method for multiple eigenvalues of an Hermitian matrix whose graph is a tree. Since we do not generally know whether a given matrix has exactly a multiple eigenvalue from approximate computations, we use the property of interlacing inequalities to enclose some eigenvalues including multiplicities.In this process, we only use the enclosure of simple eigenvalues to enclose a multiple eigenvalue by using a computer and interval arithmetic.     

Linear parameterized inverse eigenvalue problem of bisymmetric matrices

In this paper, we consider the linear parameterized inverse eigenvalue problem of bisymmetric matrices which is described as follows:     

Exact bounds for the sensitivity analysis of structures with uncertain-but-bounded parameters

Based on interval mathematical theory, the interval analysis method for the sensitivity analysis of the structure is advanced in this paper. The interval analysis method deals with the upper and lower bounds on eigenvalues of structures with uncertain-but-bounded (or interval) parameters. The stiffness matrix and the mass matrix of the structure, whose elements have the initial errors, are unknown except for the fact that they belong to given bounded matrix sets. The set of possible matrices can be described by the interval matrix. In terms of structural parameters, the stiffness matrix and the mass matrix take the non-negative decomposition. By means of interval extension, the generalized interval eigenvalue problem of structures with uncertain-but-bounded parameters can be divided into two generalized eigenvalue problems of a pair of real symmetric matrix pair by the real analysis method. Unlike normal sensitivity analysis method, the interval analysis method obtains informations on the response of structures with structural parameters (or design variables) changing and without any partial differential operation. Low computational effort and wide application rang are the characteristic of the proposed method. Two illustrative numerical examples illustrate the efficiency of the interval analysis.     

Error analysis for the computation of zeros of regular Coulomb wave function and its first derivative

In 1975 one of the coauthors, Ikebe, showed that the problem of computing the zeros of the regular Coulomb wave functions and their derivatives may be reformulated as the eigenvalue problem for infinite matrices. Approximation by truncation is justified but no error estimates are given there.

The class of eigenvalue problems studied there turns out to be subsumed in a more general problem studied by Ikebe et al. in 1993, where an extremely accurate asymptotic error estimate is shown.

In this paper, we apply this error formula to the former case to obtain error formulas in a closed, explicit form.

     

THE EIGENVALUE PERTURBATION BOUND FOR ARBITRARY MATRICES

In this paper we present some new absolute and relative perturbation bounds for theeigenvalue for arbitrary matrices, which improves some recent results. The eigenvalueinclusion region is also discussed.