Analyzing the convergence factor of residual inverse iteration

We will establish here a formula for the convergence factor of the method called residual inverse iteration, which is a method for nonlinear eigenvalue problems and a generalization of the well-known inverse iteration. The formula for the convergence factor is explicit and involves quantities associated with the eigenvalue to which the iteration converges, in particular the eigenvalue and eigenvector. Residual inverse iteration allows for some freedom in the choice of a vector w _k and we can use the formula for the convergence factor to analyze how it depends on the choice of w _k . We also use the formula to illustrate the convergence when the shift is close to the eigenvalue. Finally, we explain the slow convergence for double eigenvalues by showing that under generic conditions, the convergence factor is one, unless the eigenvalue is semisimple. If the eigenvalue is semisimple, it turns out that we can expect convergence similar to the simple case.     

Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem

Eigenvalues and eigenvectors of a large sparse symmetric matrix A can be found accurately and often very quickly using the Lanczos algorithm without reorthogonalization. The algorithm gives essentially correct information on the eigensystem of A, although it does not necessarily give the correct multiplicity of multiple, or even single, eigenvalues. It is straightforward to determine a useful bound on the accuracy of every eigenvalue given by the algorithm. The initial behavior of the algorithm is surprisingly good: it produces vectors spanning the Krylov subspace of a matrix very close to A until this subspace contains an exact eigenvector of a matrix very close to A, and up to this point the effective behavior of the algorithm for the eigenproblem is very like that of the Lanczos algorithm using full reorthogonalization. This helps to explain the remarkable behavior of the basic Lanczos algorithm.     

Closed-form solution of a maximization problem

According to the characterization of eigenvalues of a real symmetric matrix A, the largest eigenvalue is given by the maximum of the quadratic form 〈xA, x〉 over the unit sphere; the second largest eigenvalue of A is given by the maximum of this same quadratic form over the subset of the unit sphere consisting of vectors orthogonal to an eigenvector associated with the largest eigenvalue, etc. In this study, we weaken the conditions of orthogonality by permitting the vectors to have a common inner product r where 0 ≤ r < 1. This leads to the formulation of what appears—from the mathematical programming standpoint—to be a challenging problem: the maximization of a convex objective function subject to nonlinear equality constraints. A key feature of this paper is that we obtain a closed-form solution of the problem, which may prove useful in testing global optimization software. Computational experiments were carried out with a number of solvers. We dedicate this paper to the memory of our great friend and colleague, Gene H. Golub.     

Coefficients of ergodicity and the scrambling index

For a primitive stochastic matrix S, upper bounds on the second largest modulus of an eigenvalue of S are very important, because they determine the asymptotic rate of convergence of the sequence of powers of the corresponding matrix. In this paper, we introduce the definition of the scrambling index for a primitive digraph. The scrambling index of a primitive digraph D is the smallest positive integer k such that for every pair of vertices u and v, there is a vertex w such that we can get to w from u and v in D by directed walks of length k; it is denoted by k(D). We investigate the scrambling index for primitive digraphs, and give an upper bound on the scrambling index of a primitive digraph in terms of the order and the girth of the digraph. By doing so we provide an attainable upper bound on the second largest modulus of eigenvalues of a primitive matrix that make use of the scrambling index.     

Extreme value analysis for the sample autocovariance matrices of heavy-tailed multivariate time series

We provide some asymptotic theory for the largest eigenvalues of a sample covariance matrix of a p-dimensional time series where the dimension p = p _n converges to infinity when the sample size n increases. We give a short overview of the literature on the topic both in the light- and heavy-tailed cases when the data have finite (infinite) fourth moment, respectively. Our main focus is on the heavy-tailed case. In this case, one has a theory for the point process of the normalized eigenvalues of the sample covariance matrix in the iid case but also when rows and columns of the data are linearly dependent. We provide limit results for the weak convergence of these point processes to Poisson or cluster Poisson processes. Based on this convergence we can also derive the limit laws of various function als of the ordered eigenvalues such as the joint convergence of a finite number of the largest order statistics, the joint limit law of the largest eigenvalue and the trace, limit laws for successive ratios of ordered eigenvalues, etc. We also develop some limit theory for the singular values of the sample autocovariance matrices and their sums of squares. The theory is illustrated for simulated data and for the components of the S&P 500 stock index.     

Well-posedness and stability of the repairable system with N failure modes and one standby unit

The well-posedness and stability of the repairable system with N failure modes and one standby unit were discussed by applying the c₀ semigroups theory of function analysis. Firstly, the integro-differential equations described the system were transformed into some abstract Cauchy problem of Banach space. Secondly, the system operator generates positive contractive c₀ semigroups T(t) and so the well-posedness of the system was obtained. Finally, the spectral distribution of the system operator was analyzed. It was proven that 0 is strictly dominant eigenvalue of the system operator and the dynamic solution of the system converges to the steady-state solution. The steady-state solution was shown to be the eigenvector of the system operator corresponding to the eigenvalue 0. At the same time the dynamic solution exponentially converges to the steady-state solution.     

Error bounds in the isometric Arnoldi process

Error bounds for the eigenvalues computed in the isometric Arnoldi method are derived. The Arnoldi method applied to a unitary matrix U successively computes a sequence of unitary upper Hessenberg matrices H_k, k = 1,2,… The eigenvalues of the H_k's are increasingly better approximations to eigenvalues of U. An upper bound for the distance of the spectrum of H_k from the spectrum of U, and an upper bound for the distance between each individual eigenvalue of H_k and one of U are given. Between two eigenvalues of H_k on the unit circle, there is guaranteed to lie an eigenvalue of U. The results are applied to a problem in signal processing.     

An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalue of any tree

A Bethe tree B_d,k is a rooted unweighted of k levels in which the root vertex has degree equal to d, the vertices at level j(2?j?k-1) have degree equal to (d+1) and the vertices at level k are the pendant vertices. In this paper, we first derive an explicit formula for the eigenvalues of the adjacency matrix of B_d,k. Moreover, we give the corresponding multiplicities. Next, we derive an explicit formula for the simple nonzero eigenvalues, among them the largest eigenvalue, of the Laplacian matrix of B_d,k. Finally, we obtain upper bounds on the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any tree T. These upper bounds are given in terms of the largest vertex degree and the radius of T, and they are attained if and only if T is a Bethe tree.     

Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start

We study Lanczos and polynomial algorithms with random start for estimating an eigenvector corresponding to the largest eigenvalue of an n × n large symmetric positive definite matrix. We analyze the two error criteria: the randomized error and the randomized residual error. For the randomized error, we prove that it is not possible to get distribution-free bounds, i.e., the bounds must depend on the distribution of eigenvalues of the matrix. We supply such bounds and show that they depend on the ratio of the two largest eigenvalues. For the randomized residual error, distribution-free bounds exist and are provided in the paper. We also provide asymptotic bounds, as well as bounds depending on the ratio of the two largest eigenvalues. The bounds for the Lanczos algorithm may be helpful in a practical implementation and termination of this algorithm. © 1998 John Wiley & Sons, Ltd.     

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.     

Bound states of a two-boson system on a two-dimensional lattice

We consider a Hamiltonian of a two-boson system on a two-dimensional lattice Z². The Schrödinger operator H(k₁, k₂) of the system for k₁ = k₂ = π, where k = (k₁, k₂) is the total quasimomentum, has an infinite number of eigenvalues. In the case of a special potential, one eigenvalue is simple, another one is double, and the other eigenvalues have multiplicity three. We prove that the double eigenvalue of H(π,π) splits into two nondegenerate eigenvalues of H(π, π ? 2β) for small β > 0 and the eigenvalues of multiplicity three similarly split into three different nondegenerate eigenvalues. We obtain asymptotic formulas with the accuracy of β² and also an explicit form of the eigenfunctions of H(π, π ?2β) for these eigenvalues.     

Approximation of eigenvalues below the essential spectra of singular second-order symmetric linear difference equations

This paper is concerned with approximation of eigenvalues below the essential spectra of singular second-order symmetric linear difference equations with at least one endpoint in the limit point case. A sufficient condition is firstly given for that the k-th eigenvalue of a self-adjoint subspace (relation) below its essential spectrum is exactly the limit of the k-th eigenvalues of a sequence of self-adjoint subspaces. Then, by applying it to singular second-order symmetric linear difference equations, the approximation of eigenvalues below the essential spectra is obtained, i.e., for any given self-adjoint subspace extension of the corresponding minimal subspace, its k-th eigenvalue below its essential spectrum is exactly the limit of the k-th eigenvalues of a sequence of constructed induced regular self-adjoint subspace extensions.     

Oja神经网络模型的有限逸时性

O ja连续型全反馈神经网络模型可以有效计算实对称矩阵的主特征向量,该网络的动态行为由描述其模型的微分方程所决定,详细研究了O ja动力系统的稳定性问题.对于非正定实对称矩阵最大特征根为零,且至少有一特征根为负的情形,证明了从单位球外出发的解并不一定必然导致有限逸时,完善了O ja模型计算实对称矩阵主特征向量的收敛性结果,数值实验结果进一步验证了理论分析的正确性.     

A modified Leverrier-Faddeev algorithm for matrices with multiple eigenvalues

The Leverrier algorithm as modified by Faddeev gives the characteristic equation of a matrix A, its inverse, and the eigenvector corresponding to a simple eigenvalue λ of A. These results are extended (1) to give a generalized inverse when A is not of full rank and (2) to examine the modification required when λ is a multiple eigenvalue.     

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.     

A global harmonic Arnoldi method for large non-Hermitian eigenproblems with an application to multiple eigenvalue problems

The global Arnoldi method can be used to compute exterior eigenpairs of a large non-Hermitian matrix A, but it does not work well for interior eigenvalue problems. Based on the global Arnoldi process that generates an F-orthonormal basis of a matrix Krylov subspace, we propose a global harmonic Arnoldi method for computing certain harmonic F-Ritz pairs that are used to approximate some interior eigenpairs. We propose computing the F-Rayleigh quotients of the large non-Hermitian matrix with respect to harmonic F-Ritz vectors and taking them as new approximate eigenvalues. They are better and more reliable than the harmonic F-Ritz values. The global harmonic Arnoldi method inherits convergence properties of the harmonic Arnoldi method applied to a larger matrix whose distinct eigenvalues are the same as those of the original given matrix. Some properties of the harmonic F-Ritz vectors are presented. As an application, assuming that A is diagonalizable, we show that the global harmonic Arnoldi method is able to solve multiple eigenvalue problems both in theory and in practice. To be practical, we develop an implicitly restarted global harmonic Arnoldi algorithm with certain harmonic F-shifts suggested. In particular, this algorithm can be adaptively used to solve multiple eigenvalue problems. Numerical experiments show that the algorithm is efficient for the eigenproblem and is reliable for quite ill-conditioned multiple eigenproblems.     

A semi-iterative method for real spectrum singular linear systems with an arbitrary index

In this paper we develop a semi-iterative method for computing the Drazin-inverse solution of a singular linear system Ax = b, where the spectrum of A is real, but its index (i.e., the size of its largest Jordan block corresponding to the eigenvalue zero) is arbitrary. The method employs a set of polynomials that satisfy certain normalization conditions and minimize some well-defined least-squares norm. We develop an efficient recursive algorithm for implementing this method that has a fixed length independent of the index of A. Following that, we give a complete theory of convergence, in which we provide rates of convergence as well. We conclude with a numerical application to determine eigenprojections onto generalized eigenspaces. Our treatment extends the work of Hanke and Hochbruck (1993) that considers the case in which the index of A is 1.     

Computing an Eigenvector of a Monge Matrix in Max-Plus Algebra

The problem of finding one eigenvector of a given Monge matrix A in a max-plus algebra is considered. For a general matrix, the problem can be solved in O(n ³) time by computing one column of the corresponding metric matrix Δ(A _λ), where λ is the eigenvalue of A. An algorithm is presented, which computes an eigenvector of a Monge matrix in O(n ²) time.     

Universal bounds for eigenvalues of the biharmonic operator on Riemannian manifolds

In this paper we consider eigenvalues of the Dirichlet biharmonic operator on compact Riemannian manifolds with boundary (possibly empty) and prove a general inequality for them. By using this inequality, we study eigenvalues of the Dirichlet biharmonic operator on compact domains in a Euclidean space or a minimal submanifold of it and a unit sphere. We obtain universal bounds on the (k+1)th eigenvalue on such objects in terms of the first k eigenvalues independent of the domains. The estimate for the (k+1)th eigenvalue of bounded domains in a Euclidean space improves an important inequality obtained recently by Cheng and Yang.     

Verified error bounds for eigenvalues of geometric multiplicity <Emphasis Type="Italic">q</Emphasis> and corresponding invariant subspaces

In this paper, we generalize the algorithm described by Rump and Graillat to compute verified and narrow error bounds such that a slightly perturbed matrix is guaranteed to have an eigenvalue with geometric multiplicity q within computed error bounds. The corresponding invariant subspace can be directly obtained by our algorithm. Our verification method is based on border matrix technique. We demonstrate the performance of our algorithm for matrices of dimension up to hundreds with non-defective and defective eigenvalues.