(c

Tridiagonal Iterative Method for Linear Systems

Jinrui Guan¹, Zubair Ahmed², Aftab Ahmed Chandio²

¹Department of Mathematics, Taiyuan Normal University, China

²Institute of Mathematics and Computer Science, University of Sindh, Jamshoro, Pakistan

[email protected], [email protected], [email protected]

                                                                                                                    I.          Introduction and Preliminaries

Consider the linear system

,             (1)

where  is a non-singular matrix with dominant tridiagonal parts, i.e., the entries in the tridiagonal parts are very large compared with other entries. In some applications, such as numerical solution of differential equations [4, 6], we encounter such type of the problem in linear systems. The well-known iterative method, i.e., Gauss-Seidel and Jacobi iterative methods are not very effective for such type of systems due to special structure of the nonsingular matrix. In this study, we present an updated version of the iterative method for tridiagonal linear systems. Each step of this method is required for solving a tridiagonal system by Thomas algorithm. We provide some theoretical analysis for this new iterative method. The numerical experiment shows that our proposed iterative method is a feasible and effective method. The following are some notations and preliminaries.

Definition 1.1. Let . If  for all , then  is a strictly diagonally dominant matrix (SDD). If there is a positive diagonal matrix  so  is a SDD matrix, then  is a generalized strictly diagonally dominant matrix, denoted by GDDM.

Lemma 1.1. (see [5, 14]) If  is a GDDM, then  is nonsingular and for .

A group of numerical methods for solving linear system  is the splitting methods as follows [6, 8, 14]. Let , where  is a non-singular matrix, then we have the iterative form,

,

or

,        (2)

where  is a given initial vector.

Different splitting of  induce different iterative methods. The classical iterative methods include:

a)       Jacobi method: , , where  is the diagonal part of .

b)       Gauss-Seidel method: , , here D is diagonal part of A, U is strictly upper part and L is strictly lower part of triangular matrix A respectively.

c)       SOR method: , , where  is a parameter and  be as above.

Other iterative methods include AOR, two-stage iterative methods, multisplitting iterative methods, HSS method, QR method, and etc. For more details we refer to [1, 7, 9, 11, 15, 17].

We have the following results for the convergence of the iterative method (2).

Lemma 1.2. (see [5, 6, 8, 14]) The iterative method (2) is converge for any initial vector  if  .

Consider the tridiagonal linear system, where

and. The Thomas algorithm for solving such a system is as follows [12, Chapter 3.7] . Let the LU decomposition of  be as:

, .

By using following relations, the coefficients  and  can be computed easily.

, , , .

Then the given tridiagonal system  can be reduced into two bi-diagonal systems  and . For  we have

, , ,

and for  we have

, , .

The algorithm involves only  flops:  flops for generate the LU decomposition and flops for solving the two bi-diagonal systems. It is showed in [12, 13] that when  is a DDM or SPD the algorithm is very stable.

We organize the rest of the paper as follows. Section 2 gives updated version of iterative method and then some convergence analysis. In section 3 we use some numerical experiments to show the efficiency of the new iterative method. The conclusion is drawn in section 4.