A property of eigenvalue bounds for a class of symmetric tridiagonal interval matrices

The eigenvalue bounds of interval matrices are often required in some mechanical and engineering fields. In this paper, we consider an interval eigenvalue problem with symmetric tridiagonal matrices. A theoretical result is obtained that under certain assumptions the upper and lower bounds of interval eigenvalues of the problem must be achieved just at some vertex matrices of the interval matrix. Then a sufficient condition is provided to guarantee the assumption to be satisfied. The conclusion is illustrated also by a numerical example. Copyright © 2010 John Wiley & Sons, Ltd.     

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.     

Bounds for the extremal eigenvalues of a class of symmetric tridiagonal matrices with applications

We consider a class of symmetric tridiagonal matrices which may be viewed as perturbations of Toeplitz matrices. The Toeplitz structure is destroyed since two elements on each off-diagonal are perturbed. Based on a careful analysis, we derive sharp bounds for the extremal eigenvalues of this class of matrices in terms of the original data of the given matrix. In this way, we also obtain a lower bound for the smallest singular value of certain matrices. Some numerical results indicate that our bounds are extremely good.     

Eigenvalue perturbation bounds for Hermitian block tridiagonal matrices

We derive new perturbation bounds for eigenvalues of Hermitian matrices with block tridiagonal structure. The main message of this paper is that an eigenvalue is insensitive to blockwise perturbation, if it is well-separated from the spectrum of the diagonal blocks nearby the perturbed blocks. Our bound is particularly effective when the matrix is block-diagonally dominant and graded. Our approach is to obtain eigenvalue bounds via bounding eigenvector components, which is based on the observation that an eigenvalue is insensitive to componentwise perturbation if the corresponding eigenvector components are small. We use the same idea to explain two well-known phenomena, one concerning aggressive early deflation used in the symmetric tridiagonal QR algorithm and the other concerning the extremal eigenvalues of Wilkinson matrices.     

On real eigenvalues of real tridiagonal matrices

Lower bounds for the number of different real eigenvalues as well as for the number of real simple eigenvalues of a class of real irreducible tridiagonal matrices are given. Some numerical implications are discussed.     

Homotopy method for the eigenvalues of symmetric tridiagonal matrices

We will present the homotopy method for finding eigenvalues of symmetric, tridiagonal matrices. This method finds eigenvalues separately, which can be a large advantage on systems with parallel processors. We will introduce the method and establish some bounds that justify the use of Newton’s method in constructing the homotopy curves.     

Inverse eigenvalue problems for Jacobi matrices

It is proved that a real symmetric tridiagonal matrix with positive codiagonal elements is uniquely determined by its eigenvalues and the eigenvalues of the largest leading principal submatrix, and can be constructed from these data. The matrix depends continuously on the data, but because of rounding errors the investigated algorithm might in practice break down for large matrices.     

Inertia‐based spectrum slicing for symmetric quadratic eigenvalue problems

In the quadratic eigenvalue problem (QEP) with all coefficient matrices symmetric, there can be complex eigenvalues. However, some applications need to compute real eigenvalues only. We propose a Lanczos‐based method for computing all real eigenvalues contained in a given interval of large‐scale symmetric QEPs. The method uses matrix inertias of the quadratic polynomial evaluated at different shift values. In this way, for hyperbolic problems, it is possible to make sure that all eigenvalues in the interval have been computed. We also discuss the general nonhyperbolic case. Our implementation is memory‐efficient by representing the computed pseudo‐Lanczos basis in a compact tensor product representation. We show results of computational experiments with a parallel implementation in the SLEPc library.     

Eigenvector sensitivity under general and structured perturbations of tridiagonal Toeplitz‐type matrices

The sensitivity of eigenvalues of structured matrices under general or structured perturbations of the matrix entries has been thoroughly studied in the literature. Error bounds are available, and the pseudospectrum can be computed to gain insight. Few investigations have focused on analyzing the sensitivity of eigenvectors under general or structured perturbations. This paper discusses this sensitivity for tridiagonal Toeplitz and Toeplitz‐type matrices.     

On eigenvalue perturbation bounds for Hermitian block tridiagonal matrices

In this paper, we give some structured perturbation bounds for generalized saddle point matrices and Hermitian block tridiagonal matrices. Our bounds improve some existing ones. In particular, the proposed bounds reveal the sensitivity of the eigenvalues with respect to perturbations of different blocks. Numerical examples confirm the theoretical results.     

Eigenvalues for infinite matrices

This paper is concerned with the problem of determining the location of eigenvalues for diagonally dominant infinite matrices; upper and lower bounds for eigenvalues are established. For tridiagonal matrices, a numerical procedure for improving the bounds is given, and the approximation of the eigenvectors is also discussed. The techniques are illustrated for the solution of the well-known Mathieu's equation.     

Accurate computations of matrices with bidiagonal decomposition using methods for totally positive matrices

A class of sign‐symmetric P‐matrices including all nonsingular totally positive matrices and their inverses as well as tridiagonal nonsingular H‐matrices is presented and analyzed. These matrices present a bidiagonal decomposition that can be used to obtain algorithms to compute with high relative accuracy their singular values, eigenvalues, inverses, or their LDU factorization. Copyright © 2012 John Wiley & Sons, Ltd.     

Direct and Inverse Eigenvalue Problems for Diagonal-Plus-Semiseparable Matrices

In this paper we study both direct and inverse eigenvalue problems for diagonal-plus-semiseparable (dpss) matrices. In particular, we show that the computation of the eigenvalues of a symmetric dpss matrix can be reduced by a congruence transformation to solving a generalized symmetric definite tridiagonal eigenproblem. Using this reduction, we devise a set of recurrence relations for evaluating the characteristic polynomial of a dpss matrix in a stable way at a linear time. This in turn allows us to apply divide-and-conquer eigenvalue solvers based on functional iterations directly to dpss matrices without performing any preliminary reduction into a tridiagonal form. In the second part of the paper, we exploit the structural properties of dpss matrices to solve the inverse eigenvalue problem of reconstructing a symmetric dpss matrix from its spectrum and some other informations. Finally, applications of our results to the computation of a QR factorization of a Cauchy matrix with real nodes are provided.     

Eigenvalues of Symmetric Tridiagonal Matrices: A Fast, Accurate and Reliable Algorithm

An algorithm is developed for obtaining eigenvalues of real,symmetric, tridiagonal matrices. It combines dynamically Given'smethod of bisection and the use of Sturm sequences with variousacceleration devices. A FORTRAN IV computer implementation of the algorithm was usedon ten test matrices found in the literature. The new methodis as precise and reliable as the best published program (Kahan& Varah, 1966), it is never slower, and in at least onecase is two and half times faster than the Kahan and Varah program.     

On the eigenvalues of some tridiagonal matrices

A solution is given for a problem on eigenvalues of some symmetric tridiagonal matrices suggested by William Trench. The method presented can be generalizable to other problems.     

Homotopy algorithm for symmetric eigenvalue problems

Summary The homotopy method can be used to solve eigenvalue-eigenvector problems. The purpose of this paper is to report the numerical experience of the homotopy method of computing eigenpairs for real symmetric tridiagonal matrices together with a couple of new theoretical results. In practice, it is rerely of any interest to compute all the eigenvalues. The homotopy method, having the order preserving property, can provide any specific eigenvalue without calculating any other eigenvalues. Besides this advantage, we note that the homotopy algorithm is to a large degree a parallel algorithm. Numerical experimentation shows that the homotopy method can be very efficient especially for graded matrices.Research was supported in part by NSF under Grant DMS-8701349     

A New Algorithm for the Symmetric Tridiagonal Eigenvalue Problem

We apply a novel approach to approximate within ϵ to all the eigenvalues of an n × n symmetric tridiagonal matrix A using at most n²([3 log₂(625n⁶)] + (83n − 34)[log₂ (log₂((λ₁ − λ_n)/(2ϵ))/log₂(25_n))]) arithmetic operations where λ₁ and λ_n denote the extremal eigenvalues of A. The algorithm can be modified to compute any fixed numbers of the largest and the smallest eigenvalues of A and may also be applied to the band symmetric matrices without their reduction to the tridiagonal form.     

Eigenvalues and eigenvectors of symmetric centrosymmetric matrices

It is proved that the eigenvectors of a symmetric centrosymmetric matrix of order N are either symmetric or skew symmetric, and that there are ?N/2? symmetric and ?N/2? skew symmetric eigenvectors. Some previously known but widely scattered facts about symmetric centrosymmetric matrices are presented for completeness. Special cases are considered, in particular tridiagonal matrices of both odd and even order, for which it is shown that the eigenvectors corresponding to the eigenvalues arranged in descending order are alternately symmetric and skew symmetric provided the eigenvalues are distinct.     

Application of a block modified Chebyshev algorithm to the iterative solution of symmetric linear systems with multiple right hand side vectors

Summary. An adaptive Richardson iteration method is described for the solution of large sparse symmetric positive definite linear systems of equations with multiple right-hand side vectors. This scheme ``learns' about the linear system to be solved by computing inner products of residual matrices during the iterations. These inner products are interpreted as block modified moments. A block version of the modified Chebyshev algorithm is presented which yields a block tridiagonal matrix from the block modified moments and the recursion coefficients of the residual polynomials. The eigenvalues of this block tridiagonal matrix define an interval, which determines the choice of relaxation parameters for Richardson iteration. Only minor modifications are necessary in order to obtain a scheme for the solution of symmetric indefinite linear systems with multiple right-hand side vectors. We outline the changes required. Received April 22, 1993     

一种三对角矩阵的特征值及其应用

给出了一种三对角矩阵的特征值和特征向量的算法,利用矩阵方法和对称多项式证明了一些与Lucas数以及第一类Chebyshev多项式有关的三角恒等式.