Paper Title (use style: paper title)

(c

University of Sindh Journal of Information and Communication Technology (USJICT)

Volume 1, Issue 1, October 2017

 

ISSN: 2521-5582

Website: http://sujo.usindh.edu.pk/index.php/USJICT/ Published by University of Sindh, Jamshoro.

 

 

Tridiagonal Iterative Method for Linear Systems

 

Jinrui Guan1, Zubair Ahmed2, Aftab Ahmed Chandio2


1Department of Mathematics, Taiyuan Normal University, China

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

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

 

 

Abstract: In this study, we propose a tridiagonal iterative method to solve linear systems based on dominant tridiagonal entries. For solving a tridiagonal system, we incorporated the proposed method with Thomas algorithm in each step of the method. Moreover, this paper presents a comprehensive theoretical analysis, wherein we choose two well-known methods for comparison i.e., the Gauss-Seidel and Jacobi. The numerical experiment shows that our proposed iterative method is a feasible and effective method than the studied methods.

 

 

Keywords: Iterative method; tridiagonal system; Thomas algorithm, Jacobi and Gauss-Seidel

 

 


                                                                                                                    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.

Refbacks

  • There are currently no refbacks.


Copyright (c) 2017 Dr. Jinrui Guan, Dr. Zubair Ahmed Kalhoro, Dr. Aftab Ahmed Chandio



ISSN-E: 2523-1235, ISSN-P: 2521-5582

 Copyright © University of Sindh, Jamshoro. 2017 All Rights Reserved.  
Printing and Publication by: Sindh University Press. 


Journal Office, Institute of Information and Communication Technology, 
University of Sindh, Jamshoro, Sindh, Pakistan. 76080