Iman Shojaei; Hossein Rahami
Abstract
In this paper we have developed a numerical method for solving system of linear equations through taking advantages of properties of repetitive tridiagonal matrices. A system of linear equations is usually obtained in the final step of many science and engineering problems such as problems involving ...
Read More
In this paper we have developed a numerical method for solving system of linear equations through taking advantages of properties of repetitive tridiagonal matrices. A system of linear equations is usually obtained in the final step of many science and engineering problems such as problems involving partial differential equations. In the proposed algorithm, the problem is first solved for repetitive tridiagonal matrices (i.e., system of linear equations) and a closed-from relationship is obtained. This relationship is then used for solving a general matrix through converting the matrix into a repetitive tridiagonal matrix and a remaining matrix that is moved to the right-hand side of the equation. Therefore, the problem is converted into a repetitive tridiagonal matrix problem where we have a vector of unknowns on the right-hand side (in addition to the left-hand side) of the equation. The problem is solved iteratively by first using an initial guess to define the vector on the right-hand side of the equation and then solving the problem using the closed-from relationship for repetitive tridiagonal matrices. The new obtained solution is then substituted in the right-hand side of the equation and the tridiagonal problem is solved again. This process is carried out iteratively until convergence is achieved. Computational complexity of the method is investigated and efficiency of the method is shown through several examples. As indicated in the examples, one of the advantages of the proposed method is its high rate of convergence in problems where the given matrix includes large off-diagonal entries. In such problems, methods like Jacobi, Gauss-Seidel, and Successive Over-Relaxation will either have a low rate of convergence or be unable to converge.
Iman Shojaei; Hossein Rahami
Abstract
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 ...
Read More
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.
