A New Numerical Solution for System of Linear Equations

Document Type : Research Paper


1 Align Technology Inc, San Jose, CA 95134, USA

2 School of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran


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.