一类三对角矩阵的特征值和特征向量的研究

讨论了一种三对角矩阵的特征值和特征向量.按矩阵右下角对角元素的参数分为两类,得出特征值和特征向量的结论或数值算法.举例说明了算法的有效性.     

The Significant Order of Symmetric Tridiagonal Matrices

It is demonstrated that an eigenvalue of a symmetric tridiagonalmatrix as calculated by the Sturm sequence bisection procedure,is determined in general by a leading principal partition ofthe whole matrix. The order of this leading principal partitionis called the significant order of the matrix. The significantorder depends upon the specific eigenvalue being calculated,and upon the working precision of the computer. This numericalphenomenon may be employed to accelerate the bisection procedure.In applications it either indicates the adequacy or otherwiseof the working precision for finite matrices, or in the caseof theoretically infinite matrices, the effective truncationorder for the precision employed.     

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

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

Perturbation of Eigenpairs of Factored Symmetric Tridiagonal Matrices

Suppose that an indefinite symmetric tridiagonal matrix permits triangular factorization T = LDL ^t . We provide individual condition numbers for the eigenvalues and eigenvectors of T when the parameters in L and D suffer small relative perturbations. When there is element growth in the factorization, then some pairs may be robust while others are sensitive. A 4 × 4 example shows the limitations of standard multiplicative perturbation theory and the efficacy of our new condition numbers.     

Distribution of Eigenvalues of Real Symmetric Palindromic Toeplitz Matrices and Circulant Matrices

Consider the ensemble of real symmetric Toeplitz matrices, each independent entry an i.i.d. random variable chosen from a fixed probability distribution p of mean 0, variance 1, and finite higher moments. Previous investigations showed that the limiting spectral measure (the density of normalized eigenvalues) converges weakly and almost surely, independent of p, to a distribution which is almost the standard Gaussian. The deviations from Gaussian behavior can be interpreted as arising from obstructions to solutions of Diophantine equations. We show that these obstructions vanish if instead one considers real symmetric palindromic Toeplitz matrices, matrices where the first row is a palindrome. A similar result was previously proved for a related circulant ensemble through an analysis of the explicit formulas for eigenvalues. By Cauchy’s interlacing property and the rank inequality, this ensemble has the same limiting spectral distribution as the palindromic Toeplitz matrices; a consequence of combining the two approaches is a version of the almost sure Central Limit Theorem. Thus our analysis of these Diophantine equations provides an alternate technique for proving limiting spectral measures for certain ensembles of circulant matrices. A. Massey’s current address: Department of Mathematics, UCLA, Los Angeles, CA 90095, USA. e-mail: amassey3102@math.ucla.edu.     

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.     

The Eigenvalues of Very Sparse Random Symmetric Matrices

Let W _n be an n × n random symmetric sparse matrix with independent identically distributed entries such that the values 1 and 0 are taken with probabilities p/n and 1-p/n, respectively; here is independent of n. We show that the limit of the expected spectral distribution functions of W _n has a discrete part. Moreover, the set of positive probability points is dense in (- +). In particular, the points , and 0 belong to this set.     

A Low-Complexity Divide-and-Conquer Method for Computing Eigenvalues and Eigenvectors of Symmetric Band Matrices

A framework for an efficient low-complexity divide-and-conquer algorithm for computing eigenvalues and eigenvectors of an n × n symmetric band matrix with semibandwidth b n is proposed and its arithmetic complexity analyzed. The distinctive feature of the algorithm—after subdivision of the original problem into p subproblems and their solution—is a separation of the eigenvalue and eigenvector computations in the central synthesis problem. The eigenvalues are computed recursively by representing the corresponding symmetric rank b(p–1) modification of a diagonal matrix as a series of rank-one modifications. Each rank-one modifications problem can be solved using techniques developed for the tridiagonal divide-and-conquer algorithm. Once the eigenvalues are known, the corresponding eigenvectors can be computed efficiently using modified QR factorizations with restricted column pivoting. It is shown that the complexity of the resulting divide-and-conquer algorithm is O (n ² b ²) (in exact arithmetic).This revised version was published online in October 2005 with corrections to the Cover Date.     

On Parallel Fast Jacobi Algorithm for the Eigenproblem of Real Symmetric Matrices

Jacobi algorithm has been developed for the eigenproblem of real symmetric matrices, singular value decomposition of matrices and least squares of the overdetermined system on a parallel computer. In this paper, the parallel schemes and fast algorithm are discussed, and the error analysis and a new bound are presented.     

求分块三对角矩阵和分块周期三对角矩阵逆矩阵的快速算法

给出了分块三对角矩阵逆矩阵的快速算法,并利用所给算法得到了求分块周期三对角矩阵逆矩阵的快速算法.最后通过算例表示算法的有效性.     

Distribution of Eigenvalues for the Ensemble of Real Symmetric Toeplitz Matrices

Consider the ensemble of real symmetric Toeplitz matrices whose entries are i.i.d. random variable from a fixed probability distributionpof mean 0,variance 1, and finite moments of all order. The limiting spectral measure (the density of normalized eigenvalues) converges weakly to a new universal distribution with unbounded support, independent of pThis distribution’s moments are almost those of the Gaussian’s, and the deficit may be interpreted in terms of obstructions to Diophantine equations; the unbounded support follows from a nice application of the Central Limit Theorem. With a little more work, we obtain almost sure convergence. An investigation of spacings between adjacent normalized eigenvalues looks Poissonian, and not GOE. A related ensemble (real symmetric palindromic Toeplitz matrices) appears to have no Diophantine obstructions, and the limiting spectral measure’s first nine moments can be shown to agree with those of the Gaussian; this will be considered in greater detail in a future paper.     

由三个特殊次序向量对构造三对角对称矩阵

讨论利用给定的三个特殊次序向量对构造不可约三对角矩阵、Jacobi矩阵和负Jacobi矩阵的反问题.在求解方法中,将已知的一些关系式等价地转化为线性方程组,利用线性方程组有解的条件,得到了所研究问题有惟一解的充要条件,并给出了数值算法和例子.     

Solving Symmetric Arrowhead and Special Tridiagonal Linear Systems by Fast Approximate Inverse Preconditioning

A new class of approximate inverses for arrowhead and special tridiagonal linear systems, based on the concept of sparse approximate Choleski-type factorization procedures, are introduced for computing fast explicit approximate inverses. Explicit preconditioned iterative schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of symmetric linear systems. A theorem on the rate of convergence of the explicit preconditioned conjugate gradient scheme is given and estimates of the computational complexity are presented. Applications of the proposed method on linear and nonlinear systems are discussed and numerical results are given.     

Fast and Stable Reduction of Diagonal Plus Semi-Separable Matrices to Tridiagonal and Bidiagonal Form

A two-way chasing algorithm to reduce a diagonal plus a symmetric semi-separable matrix to a symmetric tridiagonal one and an algorithm to reduce a diagonal plus an unsymmetric semi-separable matrix to a bidiagonal one are considered. Both algorithms are fast and stable, requiring a computational cost of N ², where N is the order of the considered matrix.     

Fine Spectra of Tridiagonal Toeplitz Matrices

Ukrainian Mathematical Journal - The fine spectra of n-banded triangular Toeplitz matrices and (2n+1)-banded symmetric Toeplitz matrices were computed in (M. Altun, Appl. Math. Comput., 217,...     

三对角矩阵的亚正定性

讨论了比三对角矩阵更广泛的一类矩阵的亚正定性,从而给出了三对角矩阵是亚正定矩阵的充分条件.     

Minimum Permanents of Tridiagonal Doubly Stochastic Matrices

We determine the minimum permanents and minimizing matrices of the tridiagonal doubly stochastic matrices and of certain doubly stochastic matrices with prescribed zero entries.     

G-函数与分块阵的特征值分布

利用由Nowosad和Hoffman提出的G-函数概念来刻划分块阵的特征值分布,对块对角占代性进行了G-函数推广,并研究它们的本质联系,获得了分块阵特征值若干包含域,以及M矩阵的充分条件．所得结果较已有结果,明显具有一般性．     

三对角矩阵求逆问题的思考——从一道课本习题谈起

矩阵求逆是矩阵代数中的一个重要运算,逆矩阵的获得却困难重重.文中介绍一个三对角形矩阵求逆的新思路,它可以作为求解逆矩阵问题的一个“解题模块”,学习线性代数课程的一个“认知结构”,也可以作为教育数学的一个案例.