Inversion of general tridiagonal matrices

In the current work, the authors present a symbolic algorithm for finding the inverse of any general nonsingular tridiagonal matrix. The algorithm is mainly based on the work presented in [Y. Huang, W.F. McColl, Analytic inversion of general tridiagonal matrices, J. Phys. A 30 (1997) 7919–7933] and [M.E.A. El-Mikkawy, A fast algorithm for evaluating nth order tridiagonal determinants, J. Comput. Appl. Math. 166 (2004) 581–584]. It removes all cases where the numeric algorithm in [Y. Huang, W.F. McColl, Analytic inversion of general tridiagonal matrices, J. Phys. A 30 (1997) 7919–7933] fails. The symbolic algorithm is suited for implementation using Computer Algebra Systems (CAS) such as MACSYMA, MAPLE and MATHEMATICA. An illustrative example is given.     

周期三对角矩阵逆的一种新算法

给出了一类周期三对角矩阵逆的新的递归算法.新方法充分利用周期三对角矩阵的结构特点,采用递归方法将高阶周期三对角矩阵求逆转化为低阶周期三对角矩阵的求逆.并同时得到简化的计算方法,方法可以有效地减少运算量和存储量,计算精度也有明显的优势.数值实验表明此算法是有效的.     

Direct and inverse spectral problems for a class of non-self-adjoint periodic tridiagonal matrices

The spectral properties of a class of tridiagonal matrices are investigated. The reconstruction of matrices of this special class from given spectral data is also studied. Necessary and sufficient conditions for that reconstruction are found. The obtained results extend some results on the direct and inverse spectral problems for periodic Jacobi matrices and for some non-self-adjoint tridiagonal matrices.     

离散Lyapunov矩阵方程X—AXB=C的一种数值解法

本文提供了求解离散Lyapunov矩阵方程的一种数值解法。首先讨论了系数矩阵为三对角形矩阵的公式解法,然后通过相似变换,将该方法推广到一般情形。     

A note on representations for the inverses of tridiagonal matrices

In this note, we propose an explicit representation with the nested sums for the entries of the inverses of general tridiagonal nonsingular matrices. Its equivalence with other particular representations, based on the combinatorial expressions or the continued fractions, is considered. In addition, an analytical representation for the entries of the finite sections of the resolvent of Jacobi matrices, in terms of its related orthogonal polynomials, is observed.     

广义周期七对角矩阵的求逆新算法

讨论了广义周期七对角矩阵的求逆问题,利用七对角矩阵的特殊结构,通过矩阵的广义LU分解,给出了一种求解广义周期七对角逆矩阵的新型算法,该算法不需要对矩阵的各阶顺序主子式做任何限制并且适用于多种计算机代数系统,如：Mathematics,Macsyma,Matlab和Maple等.最后通过算例来说明了算法的有效性。     

矩阵特征值分离度的下界

这里λ_n<λ_(n-1)<…<λ_1。 分离度是矩阵特征值计算中的一个有用的概念,它与矩阵特征值计算的难易程度关系极为密切。估计分离度的界限,能够预测用特定方法计算特征值的运算次数,这个课题是M.Newman提出的。 众所周知,求矩阵特征值等价于高次方程求根。有关多项式根的分离度(其定义与(1)类似),在[1],[2]中有了一些结果。但是,它们都含有多项式的系数,对于矩阵,使用     

Inversion of band matrices

In this paper, a formula for inverting general band matrices is established. It takes a simple form when the matrices are tridiagonal, and as a special case it includes the Bukhberger-Emel'yanenko algorithm for symmetric tridiagonal matrices.     

On the inverse of a general tridiagonal matrix

In the current paper a new efficient computational algorithm to find the inverse of a general tridiagonal matrix is presented. The algorithm is suited for implementation using computer algebra systems such as MAPLE, MATHEMATICA, MATLAB and MACSYMA. Symbolic and numeric examples are given.     

Extremal eigenvalue intervals of symmetric tridiagonal interval matrices

Computing the extremal eigenvalue bounds of interval matrices is non‐deterministic polynomial‐time (NP)‐hard. We investigate bounds on real eigenvalues of real symmetric tridiagonal interval matrices and prove that for a given real symmetric tridiagonal interval matrices, we can achieve its exact range of the smallest and largest eigenvalues just by computing extremal eigenvalues of four symmetric tridiagonal matrices.     

A method of congruent type for linear systems with conjugate-normal coefficient matrices

Minimal residual methods, such as MINRES and GMRES, are well-known iterative versions of direct procedures for reducing a matrix to special condensed forms. The method of reduction used in these procedures is a sequence of unitary similarity transformations, while the condensed form is a tridiagonal matrix (MINRES) or a Hessenberg matrix (GMRES). The algorithm CSYM proposed in the 1990s for solving systems with complex symmetric matrices was based on the tridiagonal reduction performed via unitary congruences rather than similarities. In this paper, we construct an extension of this algorithm to the entire class of conjugate-normal matrices. (Complex symmetric matrices are a part of this class.) Numerical results are presented. They show that, on many occasions, the proposed algorithm has a superior convergence rate compared to GMRES.     

Inverses of tridiagonal Toeplitz and periodic matrices with applications to mechanics

The linear algebraic equation Ax = b with tridiagonal coefficient matrix of A is solved by the analytical matrix inversion. An explicit formula is known if A is a Toeplitz matrix. New formulas are presented for the following cases: (1) A is of Toeplitz type except that A(1, 1) and A(n, n) are different from the remaining diagonal elements. (2) A is p-periodic (p > 1), by which is meant that in each of the three bands of A a group of p elements is periodically repeated. (3) The tridiagonal matrix A is composed of periodic submatrices of different periods. In cases (2) and(3) the problem of matrix inversion is reduced to a second-order difference equation with periodic coefficients. The solution is based on Floquet's theorem. It is shown that for p = 1 the formulae found for periodic matrices reduce to special forms valid for Toeplitz matrices. The results are applied to problems of elastostatics and of vibration theory.     

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

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

The {\cal {D Q R}} algorithm, basic theory, convergence, and conditional stability

Summary. We describe a fast matrix eigenvalue algorithm that uses a matrix factorization and reverse order multiply technique involving three factors and that is based on the symmetric matrix factorization as well as on –orthogonal reduction techniques where is computed from the given matrix . It operates on a similarity reduction of a real matrix to general tridiagonal form and computes all of 's eigenvalues in operations, where the part of the operations is possibly performed over , instead of the 7–8 real flops required by the eigenvalue algorithm. Potential breakdo wn of the algorithm can occur in the reduction to tridiagonal form and in the –orthogonal reductions. Both, however, can be monitored during the computations. The former occurs rather rarely for dimensions and can essentially be bypassed, while the latter is extremely rare and can be bypassed as well in our conditionally stable implementation of the steps. We prove an implicit theorem which allows implicit shifts, give a convergence proof for the algorithm and show that is conditionally stable for general balanced tridiagonal matrices . Received April 25, 1995 / Revised version received February 9, 1996     

Hankel matrices and quadratic forms

A characterization of finite Hankei matrices is given and it is shown that such matrices arise naturally as matrix representations of scaled trace forms of field extensions and etale algebras. An algorithm is given for calculating the signature and the Hasse invariant of these scaled trace forms.     

Finding the Maximal Eigenpair for a Large,Dense,Symmetric Matrix based on Mufa Chen's Algorithm

A hybrid method is presented for determining maximal eigenvalue and its eigenvector(called eigenpair)of a large,dense,symmetric matrix.Many problems require finding only a small part of the eigenpairs,and some require only the maximal one.In a series of papers,efficient algorithms have been developed by Mufa Chen for computing the maximal eigenpairs of tridiagonal matrices with positive off-diagonal elements.The key idea is to explicitly construet effective initial guess of the maximal eigenpair and then to employ a self-closed iterative algorithm.In this paper we will extend Mufa Chen's algorithm to find maximal eigenpair for a large scale,dense,symmetric matrix.Our strategy is to first convert the underlying matrix into the tridiagonal form by using similarity transformations.We then handle the cases that prevent us from applying Chen's algorithm directly,e.g.,the cases with zero or negative super-or sub-diagonal elements.Serval numerical experiments are carried out to demonstrate the efficiency of the proposed hybrid method.     

A breakdown-free algorithm for computing the determinants of periodic tridiagonal matrices

Numerical Algorithms - In this paper, we present a new breakdown-free recursive algorithm for computing the determinants of periodic tridiagonal matrices via a three-term recurrence. Even though...     

Inversion of tridiagonal matrices

Summary This paper presents a simple algorithm for inverting nonsymmetric tridiagonal matrices that leads immediately to closed forms when they exist. Ukita's theorem is extended to characterize the class of matrices that have tridiagonal inverses.Journal Paper No. J-10137 of the Iowa Agriculture and Home Economics Experiment Station, Ames, Iowa. Project 1669, Partial support by National Institutes of Health, Grant GM 13827     

The inverse eigenvalue problem for Hermitian matrices whose graphs are cycles

In 1979, Ferguson characterized the periodic Jacobi matrices with given eigenvalues and showed how to use the Lanzcos Algorithm to construct each such matrix. This article provides general characterizations and constructions for the complex analogue of periodic Jacobi matrices. As a consequence of the main procedure, we prove that the multiplicity of an eigenvalue of a periodic Jacobi matrix is at most 2.     

STABLE DOUBLE LR ALGORITHM AND ITS ERROR ANALYSIS

In this paper, the normative matrices and their double LR transformation with origin shifts are defined, and the essential relationship between the double LR transformation of a normative matrix and the QR transformation of the related symmetric tridiagonal matrix is proved. We obtain a stable double LR algorithm for double LR transformation of normative matrices and give the error analysis of our algorithm. The operation number of the stable double LR algorithm for normative matrices is only four sevenths of the rational QR algorithm for reed symmetric tridiagonal matrices.