Orthonormal rational function vectors

Summary In this paper, we develop a matrix framework to solve the problem of finding orthonormal rational function vectors with prescribed poles with respect to a certain discrete inner product that is defined by a set of data points and corresponding weight vectors w_i,j. Our algorithm for solving the problem is recursive, and it is of complexity If all data points are real or lie on the unit circle, then the complexity is reduced by an order of magnitude.     

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.     

Relative perturbation results for eigenvalues and eigenvectors of diagonalisable matrices

Let and be a perturbed eigenpair of a diagonalisable matrixA. The problem is to bound the error in and . We present one absolute perturbation bound and two relative perturbation bounds. The absolute perturbation bound is an extension of Davis and Kahan's sin θ Theorem from Hermitian to diagonalisable matrices. The two relative perturbation bounds assume that and are an exact eigenpair of a perturbed matrixD ₁ AD ₂ , whereD ₁ andD ₂ are non-singular, butD ₁ AD ₂ is not necessarily diagonalisable. We derive a bound on the relative error in and a sin θ theorem based on a relative eigenvalue separation. The perturbation bounds contain both the deviation ofD ₁ andD ₂ from similarity and the deviation ofD ₂ from identity. This work was partially supported by NSF grant CCR-9400921.     

On close eigenvalues of tridiagonal matrices

Summary. A symmetric tridiagonal matrix with a multiple eigenvalue must have a zero subdiagonal element and must be a direct sum of two complementary blocks, both of which have the eigenvalue. Yet it is well known that a small spectral gap does not necessarily imply that some is small, as is demonstrated by the Wilkinson matrix. In this note, it is shown that a pair of close eigenvalues can only arise from two complementary blocks on the diagonal, in spite of the fact that the coupling the two blocks may not be small. In particular, some explanatory bounds are derived and a connection to the Lanczos algorithm is observed. The nonsymmetric problem is also included. Received April 8, 1992 / Revised version received September 21, 1994     

Computing spectral value sets using the subharmonicity of the norm of rational matrices

Spectral value sets (SVS) are structured versions of pseudospectra, a tool of matrix analysis that has been popularized by Trefethen and Godunov in recent years. The main result contained in this note is a new algorithm for calculating complex SVS which, using the subharmonicity of the norm of rational matrices, is able to save large amounts of computation whenever the initial set of interest Ω₀⊂ℂ is larger than the actual size of the SVS to be visualized. The algorithm, as a result of a corrector step, is also able to recover the subsets of the SVS which are not contained in Ω₀. Numerical examples are discussed which illustrate the advantages of the new method. This work has been financially supported by the Deutscher Akademischer Austauschdienst.     

Some lower bounds for the spectral radius of matrices using traces

Let A be an n×n matrix with eigenvalues λ₁,λ₂,…,λ_n, and let m be an integer satisfying rank(A)?m?n. If A is real, the best possible lower bound for its spectral radius in terms of m, trA and trA² is obtained. If A is any complex matrix, two lower bounds for are compared, and furthermore a new lower bound for the spectral radius is given only in terms of trA,trA²,‖A‖,‖A^∗A-AA^∗‖,n and m.     

Inside the eigenvalues of certain Hermitian Toeplitz band matrices

While extreme eigenvalues of large Hermitian Toeplitz matrices have been studied in detail for a long time, much less is known about individual inner eigenvalues. This paper explores the behavior of the jth eigenvalue of an n-by-n banded Hermitian Toeplitz matrix as n tends to infinity and provides asymptotic formulas that are uniform in j for 1≤j≤n. The real-valued generating function of the matrices is assumed to increase strictly from its minimum to its maximum, and then to decrease strictly back from the maximum to the minimum, having nonzero second derivatives at the minimum and the maximum. The results, which are of interest in numerical analysis, probability theory, or statistical physics, for example, are illustrated and underpinned by numerical examples.     

On the eigenvalues of a class of saddle point matrices

We study spectral properties of a class of block 2 × 2 matrices that arise in the solution of saddle point problems. These matrices are obtained by a sign change in the second block equation of the symmetric saddle point linear system. We give conditions for having a (positive) real spectrum and for ensuring diagonalizability of the matrix. In particular, we show that these properties hold for the discrete Stokes operator, and we discuss the implications of our characterization for augmented Lagrangian formulations, for Krylov subspace solvers and for certain types of preconditioners. The work of this author was supported in part by the National Science Foundation grant DMS-0207599 Revision dated 5 December 2005.     

A note on the eigenvalues of a special class of matrices

In the analysis of stability of a variant of the Crank-Nicolson (C-N) method for the heat equation on a staggered grid a class of non-symmetric matrices appear that have an interesting property: their eigenvalues are all real and lie within the unit circle. In this note we shall show how this class of matrices is derived from the C-N method and prove that their eigenvalues are inside [−1,1] for all values of m (the order of the matrix) and all values of a positive parameter σ, the stability parameter. As the order of the matrix is general, and the parameter σ lies on the positive real line this class of matrices turns out to be quite general and could be of interest as a test set for eigenvalue solvers, especially as examples of very large matrices.     

On spectral variations under bounded real matrix perturbations

Summary In this paper we investigate the set of eigenvalues of a perturbed matrix {ie509-1} whereA is given and ^{n × n}, ||< is arbitrary. We determine a lower bound for thisspectral value set which is exact for normal matricesA with well separated eigenvalues. We also investigate the behaviour of the spectral value set under similarity transformations. The results are then applied tostability radii which measure the distance of a matrixA from the set of matrices having at least one eigenvalue in a given closed instability domain _b.     

On extremum properties of orthogonal quotients matrices

In this paper we explore the extremum properties of orthogonal quotients matrices. The orthogonal quotients equality that we prove expresses the Frobenius norm of a difference between two matrices as a difference between the norms of two matrices. This turns the Eckart-Young minimum norm problem into an equivalent maximum norm problem. The symmetric version of this equality involves traces of matrices, and adds new insight into Ky Fan’s extremum problems. A comparison of the two cases reveals a remarkable similarity between the Eckart-Young theorem and Ky Fan’s maximum principle. Returning to orthogonal quotients matrices we derive “rectangular” extensions of Ky Fan’s extremum principles, which consider maximizing (or minimizing) sums of powers of singular values.     

Tensor properties of multilevel Toeplitz and related matrices

A general proposal is presented for fast algorithms for multilevel structured matrices. It is based on investigation of their tensor properties and develops the idea recently introduced by Kamm and Nagy in the block Toeplitz case. We show that tensor properties of multilevel Toeplitz matrices are related to separation of variables in the corresponding symbol, present analytical tools to study the latter, expose truncation algorithms preserving the structure, and report on some numerical results confirming advantages of the proposal.     

Backward errors for eigenproblem of two kinds of structured matrices

In this paper, we consider backward errors in the eigenproblem of symmetric centrosymmetric and symmetric skew-centrosymmetric matrices. By making use of the properties of symmetric centrosymmetric and symmetric skew-centrosymmetric matrices, we derive explicit formulae for the backward errors of approximate eigenpairs.     

Eigenvalue computation for unitary rank structured matrices

In this paper we describe how to compute the eigenvalues of a unitary rank structured matrix in two steps. First we perform a reduction of the given matrix into Hessenberg form, next we compute the eigenvalues of this resulting Hessenberg matrix via an implicit QR-algorithm. Along the way, we explain how the knowledge of a certain ‘shift’ correction term to the structure can be used to speed up the QR-algorithm for unitary Hessenberg matrices, and how this observation was implicitly used in a paper due to William B. Gragg. We also treat an analogue of this observation in the Hermitian tridiagonal case.     

On some new inclusion theorems for the eigenvalues of partitioned matrices

Summary Some new results of Gershgorin type for partitioned matrices have been obtained using the so-called departure from normality of the diagonal blocks. This has been shown to improve the existing results at least in the case where diagonal blocks are simultaneously nearly defective and nearly normal. Also a set of Gershgorin-like circles is found such that each of them contains at least one eigenvalue (even if no separation takes place). As a corollary it is shown that every classical Gershgorin circle of a normal matrix contains at least one eigenvalue.     

The rational Krylov algorithm for nonsymmetric eigenvalue problems. III: Complex shifts for real matrices

A new algorithm for the computation of eigenvalues of a nonsymmetric matrix pencil is described. It is a generalization of the shifted and inverted Lanczos (or Arnoldi) algorithm, in which several shifts are used in one run. It computes an orthogonal basis and a small Hessenberg pencil. The eigensolution of the Hessenberg pencil, gives Ritz approximations to the solution of the original pencil. It is shown how complex shifts can be used to compute a real block Hessenberg pencil to a real matrix pair.Two applicationx, one coming from an aircraft stability problem and the other from a hydrodynamic bifurcation, have been tested and results are reported.Dedicated to Carl-Erik Fröberg on the occasion of his 75th birthday.     

The QRPS algorithm: A generalization of the QR algorithm for the singular values decomposition of rectangular matrices

A generalization of the QR algorithm proposed by Francis [2] for square matrices is introduced for the singular values decomposition of arbitrary rectangular matrices. Geometrically the algorithm means the subsequent orthogonalization of the image of orthonormal bases produced in the course of the iteration. Our purpose is to show how to get a series of lower triangular matrices by alternate orthogonal-upper triangular decompositions in different dimensions and to prove the convergence of this series.     

Jacobi matrices for sums of weight functions

Orthogonal polynomials are conveniently represented by the tridiagonal Jacobi matrix of coefficients of the recurrence relation which they satisfy. LetJ ₁ andJ ₂ be finite Jacobi matrices for the weight functionsw ₁ andw ₂, resp. Is it possible to determine a Jacobi matrix \(\tilde J\) , corresponding to the weight functions \(\tilde w\) =w ₁+w ₂ using onlyJ ₁ andJ ₂ and if so, what can be said about its dimension? Thus, it is important to clarify the connection between a finite Jacobi matrix and its corresponding weight function(s). This leads to the need for stable numerical processes that evaluate such matrices. Three newO(n ²) methods are derived that “merge” Jacobi matrices directly without using any information about the corresponding weight functions. The first can be implemented using any of the updating techniques developed earlier by the authors. The second new method, based on rotations, is the most stable. The third new method is closely related to the modified Chebyshev algorithm and, although it is the most economical of the three, suffers from instability for certain kinds of data. The concepts and the methods are illustrated by small numerical examples, the algorithms are outlined and the results of numerical tests are reported.     

The general coupled matrix equations over generalized bisymmetric matrices

In the present paper, by extending the idea of conjugate gradient (CG) method, we construct an iterative method to solve the general coupled matrix equations