Verified numerical computations for multiple and nearly multiple eigenvalues of elliptic operators

In this paper, we propose a numerical method to verify bounds for multiple eigenvalues for elliptic eigenvalue problems. We calculate error bounds for approximations of multiple eigenvalues and base functions of the corresponding invariant subspaces. For matrix eigenvalue problems, Rump (Linear Algebra Appl. 324 (2001) 209) recently proposed a validated numerical method to compute multiple eigenvalues. In this paper, we extend his formulation to elliptic eigenvalue problems, combining it with a method developed by one of the authors (Jpn. J. Indust. Appl. Math. 16 (1998) 307).     

Perturbation analysis of singular subspaces and deflating subspaces

Summary. Perturbation expansions for singular subspaces of a matrix and for deflating subspaces of a regular matrix pair are derived by using a technique previously described by the author. The perturbation expansions are then used to derive Fr\'echet derivatives, condition numbers, and th-order perturbation bounds for the subspaces. Vaccaro's result on second-order perturbation expansions for a special class of singular subspaces can be obtained from a general result of this paper. Besides, new perturbation bounds for singular subspaces and deflating subspaces are derived by applying a general theorem on solution of a system of nonlinear equations. The results of this paper reveal an important fact: Each singular subspace and each deflating subspace have individual perturbation bounds and individual condition numbers. Received July 26, 1994     

Sylvester方程在矩阵扰动分析中的应用

§1.引言 矩阵扰动分析的研究对于矩阵论的发展及数值分析问题计算结果的分析和处理都有重要意义.有关特征值、广义特征值及最小二乘问题的主要研究结果均含于[1]中,[5]运用二次方程根的判别法通过对代数Ricatti方程的解的估计给出了QR分解因子及Cholesky因子的扰动分析,但论证方法及所得结果都比较复杂且所求条件很强.[3]和     

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 the eigenvalues of specially low-rank perturbed matrices

We study the eigenvalues of a matrix A perturbed by a few special low-rank matrices. The perturbation is constructed from certain basis vectors of an invariant subspace of A, such as eigenvectors, Jordan vectors, or Schur vectors. We show that most of the eigenvalues of the low-rank perturbed matrix stayed unchanged from the eigenvalues of A; the perturbation can only change the eigenvalues of A that are related to the invariant subspace. Existing results mostly studied using eigenvectors with full column rank for perturbations, we generalize the results to more general settings. Applications of our results to a few interesting problems including the Google’s second eigenvalue problem are presented.     

ARNOLDI TYPE ALGORITHMS FOR LARGE UNSYMMETRIC MULTIPLE EIGENVALUE PROBLEMS

1.IntroductionTheLanczosalgorithm[Zo]isaverypowerfultoolforextractingafewextremeeigenvaluesandassociatedeigenvectorsoflargesymmetricmatrices[4'5'22].Sincethe1980's,considerableattentionhasbeenpaidtogeneralizingittolargeunsymmetricproblems.Oneofitsgen...     

矩阵特征值问题的Bendixson定理的改进

任一n×n矩阵A可分解为A=B C,其中B=1/2(A A~H),C=1/2(A-A~H)。Bendixson定理的主要内容是:λ_j(A)(j=1,2,…,n)落在矩形区域F上,而构成F的四个边的直线分别为x=max(λ_j(B)),x=min(λ_j(B)),y=max(-iλ_j(C)),y=min(-iλ_j(C))。本文给出用B,C的特征值和矩阵A的正规性偏离度对A的特征值的进一步估计。     

广义特征值的扰动界限(Ⅰ)

到目前为止,关于广义特征值的扰动,已经建立了一些界限估计,但一般正则对的扰动界限难以算出.首先,定义某些基本参数,并利用这些参数建立几个关于一般正则矩阵对的广义特征值的扰动定理.这些定理给出的扰动界限的上界估计,一般是可以算出的.     

On the closeness of eigenvalues and singular values for almost normal matrices

It is proved that a matrix is almost normal if and only if its singular values are close to the absolute values of its eigenvalues. In the special case when the spectral norm and spectral radius are close, it is proved that the dominating eigenvalue is well conditioned. A refinement of a perturbation theorem by Henrici is proved, and its numerical behavior is compared with adaptations of the Gerschgorin theorem. It is specially devised for almost triangular matrices.     

Krylov eigenvalue strategy using the FEAST algorithm with inexact system solves

The FEAST eigenvalue algorithm is a subspace iteration algorithm that uses contour integration to obtain the eigenvectors of a matrix for the eigenvalues that are located in any user‐defined region in the complex plane. By computing small numbers of eigenvalues in specific regions of the complex plane, FEAST is able to naturally parallelize the solution of eigenvalue problems by solving for multiple eigenpairs simultaneously. The traditional FEAST algorithm is implemented by directly solving collections of shifted linear systems of equations; in this paper, we describe a variation of the FEAST algorithm that uses iterative Krylov subspace algorithms for solving the shifted linear systems inexactly. We show that this iterative FEAST algorithm (which we call IFEAST) is mathematically equivalent to a block Krylov subspace method for solving eigenvalue problems. By using Krylov subspaces indirectly through solving shifted linear systems, rather than directly using them in projecting the eigenvalue problem, it becomes possible to use IFEAST to solve eigenvalue problems using very large dimension Krylov subspaces without ever having to store a basis for those subspaces. IFEAST thus combines the flexibility and power of Krylov methods, requiring only matrix–vector multiplication for solving eigenvalue problems, with the natural parallelism of the traditional FEAST algorithm. We discuss the relationship between IFEAST and more traditional Krylov methods and provide numerical examples illustrating its behavior.     

On condition numbers of a nondefective multiple eigenvalue of a nonsymmetric matrix pencil

This paper considers the condition numbers of a nondefective multiple eigenvalue of a nonsymmetric matrix pencil. Based on the directional derivatives of a nondefective multiple eigenvalue of a nonsymmetric matrix pencil analytically dependent on several parameters, different condition numbers of a nondefective multiple eigenvalue are introduced. The computable expressions and bounds of introduced condition numbers are derived. Moreover, some results on the perturbation of a nondefective multiple eigenvalue of a nonsymmetric matrix pencil are given.     

Sensitivity Analysis of Multiple Eigenvalues (Ⅱ)

This paper discusses the sensitivity of semisimple multiple eigenvalues and corresponding invariant subspaces of a complex (or real) $n\times n$ matrix analytically dependent on several parameters. Some results of this paper may be useful for investigating robust multiple eigenvalue assignment in control system design.     

Backward perturbation analysis of certain characteristic subspaces

Summary This paper gives optimal backward perturbation bounds and the accuracy of approximate solutions for subspaces associated with certain eigenvalue problems such as the eigenvalue problemAx=x, the generalized eigenvalue problem Ax=Bx, and the singular value decomposition of a matrixA. This paper also gives residual bounds for certain eigenvalues, generalized eigenvalues and singular values.This subject was supported by the Swedish Natural Science Research Council and the Institute of Information Processing of the University of Umeå.     

An algorithm for numerical determination of the structure of a general matrix

An algorithm, proposed by V. N. Kublanovskaya, for solving the complete eigenvalue problem of a degenerate (that is defective and/or derogatory) matrix, is studied theoretically and numerically. It uses successiveQR-factorizations to determine annihilated subspaces.An adaptation of the algorithm is developed which, applied to a matrix with a very ill-conditioned eigenproblem, computes a degenerate matrix. The difference between these matrices is small, measured in the spectral norm. The degenerate matrix will appear in a standard form, whose eigenvalues and principal vectors can be computed in a numerically stable manner.Numerical examples are given.     

Eigenvalues of graded matrices and the condition numbers of a multiple eigenvalue

Summary This paper concerns two closely related topics: the behavior of the eigenvalues of graded matrices and the perturbation of a nondefective multiple eigenvalue. We will show that the eigenvalues of a graded matrix tend to share the graded structure of the matrix and give precise conditions insuring that this tendency is realized. These results are then applied to show that the secants of the canonical angles between the left and right invariant of a multiple eigenvalue tend to characterize its behavior when its matrix is slightly perturbed.This work was supported in part by the Air Force Office of Sponsored Research under Contract AFOSR-87-0188     

On condition numbers of polynomial eigenvalue problems

In this paper, we investigate condition numbers of eigenvalue problems of matrix polynomials with nonsingular leading coefficients, generalizing classical results of matrix perturbation theory. We provide a relation between the condition numbers of eigenvalues and the pseudospectral growth rate. We obtain that if a simple eigenvalue of a matrix polynomial is ill-conditioned in some respects, then it is close to be multiple, and we construct an upper bound for this distance (measured in the euclidean norm). We also derive a new expression for the condition number of a simple eigenvalue, which does not involve eigenvectors. Moreover, an Elsner-like perturbation bound for matrix polynomials is presented.     

A Brauer’s theorem and related results

Given a square matrix A, a Brauer’s theorem [Brauer A., Limits for the characteristic roots of a matrix. IV. Applications to stochastic matrices, Duke Math. J., 1952, 19(1), 75–91] shows how to modify one single eigenvalue of A via a rank-one perturbation without changing any of the remaining eigenvalues. Older and newer results can be considered in the framework of the above theorem. In this paper, we present its application to stabilization of control systems, including the case when the system is noncontrollable. Other applications presented are related to the Jordan form of A and Wielandt’s and Hotelling’s deflations. An extension of the aforementioned Brauer’s result, Rado’s theorem, shows how to modify r eigenvalues of A at the same time via a rank-r perturbation without changing any of the remaining eigenvalues. The same results considered by blocks can be put into the block version framework of the above theorem.     

Perturbation theory of selfadjoint matrices and sign characteristics under generic structured rank one perturbations

For selfadjoint matrices in an indefinite inner product, possible canonical forms are identified that arise when the matrix is subjected to a selfadjoint generic rank one perturbation. Genericity is understood in the sense of algebraic geometry. Special attention is paid to the perturbation behavior of the sign characteristic. Typically, under such a perturbation, for every given eigenvalue, the largest Jordan block of the eigenvalue is destroyed and (in case the eigenvalue is real) all other Jordan blocks keep their sign characteristic. The new eigenvalues, i.e. those eigenvalues of the perturbed matrix that are not eigenvalues of the original matrix, are typically simple, and in some cases information is provided about their sign characteristic (if the new eigenvalue is real). The main results are proved by using the well known canonical forms of selfadjoint matrices in an indefinite inner product, a version of the Brunovsky canonical form and on general results concerning rank one perturbations obtained.     

Error bounds for non-selfadjoint PDE eigenvalue problems

We introduce a posteriori bounds for the eigenfunctions (eigenvalues) of non-selfadjoint diagonalizable PDE-eigenvalue problems which incorporates an inexact solution of the corresponding generalized matrix eigenvalue problem. The estimates combine the standard perturbation results with the saturation assumption for the eigenfunctions. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An integral method for solving nonlinear eigenvalue problems

We propose a numerical method for computing all eigenvalues (and the corresponding eigenvectors) of a nonlinear holomorphic eigenvalue problem that lie within a given contour in the complex plane. The method uses complex integrals of the resolvent operator, applied to at least k column vectors, where k is the number of eigenvalues inside the contour. The theorem of Keldysh is employed to show that the original nonlinear eigenvalue problem reduces to a linear eigenvalue problem of dimension k. No initial approximations of eigenvalues and eigenvectors are needed. The method is particularly suitable for moderately large eigenvalue problems where k is much smaller than the matrix dimension. We also give an extension of the method to the case where k is larger than the matrix dimension. The quadrature errors caused by the trapezoid sum are discussed for the case of analytic closed contours. Using well known techniques it is shown that the error decays exponentially with an exponent given by the product of the number of quadrature points and the minimal distance of the eigenvalues to the contour.