TY - JOUR
ID - 81543
TI - A Numerical Method for Eigensolution of Tridiagonal Matrices
JO - Journal of Algorithms and Computation
JA - JAC
LA - en
SN - 2476-2776
AU - Shojaei, Iman
AU - Rahami, Hossein
AD - Align Technology Inc, San Jose, CA 95134, USA
AD - School of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran
Y1 - 2021
PY - 2021
VL - 53
IS - 1
SP - 97
EP - 115
KW - iterative method
KW - eigensolution
KW - repetitive tridiagonal matrices
KW - non-repetitive tridiagonal matrices
KW - Efficient Solution
KW - system of linear equations
DO - 10.22059/jac.2021.81543
N2 - In this paper we have developed an iterative method to solve eigenproblem for non-repetitive tridiagonal matrices. The importance of eigensolution for tridiagonal matrices is that in many algorithms the eigneproblem for an arbitrary matrix is first converted to the eigenproblem for a tridiagonal matrix and then the problem is tackled. Our proposed method was developed through taking advantages of some unique properties of repetitive and non-repetitive tridiagonal matrices. First, we established closed-form solutions for the system of linear equations $ bf{Mx=f} $ for the condition $ mathbf{M} $ is tridiagonal. When $ mathbf{M} $ is a repetitive tridiagonal matrix, the unknown vector $ mathbf{x} $, the vector $ mathbf{f} $, and the coefficient matrix $ mathbf{M} $ are expanded using orthogonal basis of matrix $ mathbf{M} $ and closed-form relationships are obtained. For non-repetitive matrix $ mathbf{M} $, the tridiagonal matrix algorithm is used to efficiently solve the matrix equation. We then using orthogonal basis of matrix $ mathbf{M} $ and closed-form relationships are obtained. For non-repetitive matrix $ mathbf{M} $, the tridiagonal matrix algorithm is used to efficiently solve the matrix equation. We then implemented these solutions in an iterative relationship for eigenproblem where eigenpairs of non-repetitive tridiagonal matrices were obtained through successive solution of the tridiagonal matrix equation efficiently solved above. Furthermore, closed-form relationships for eigenpairs of repetitive tridiagonal matrices were implemented in the algorithm as start point for eigensolution of non-repetitive tridiagonal matrices so that the required number of iterations was significantly reduced. Computational complexity of the proposed method is $ O(n^2) $ that is competitive with the best existing algorithms in literature. As indicated through several numerical examples, the advantages of the proposed algorithm include high rate of convergence, computational efficiency in each iteration, simple implementation, and availability of an objective start point for initialization.
UR - https://jac.ut.ac.ir/article_81543.html
L1 - https://jac.ut.ac.ir/article_81543_f245166d44046556266d8232c4fde63b.pdf
ER -