1. Introduction

Consider the linear systems of equations

(1.1)

where A= (a_ij) be an NxN non- singular matrix with non-zero diagonal elements, U and b are N-dimensional vectors. For the determination of the N-dimensional solution vector U of Eq. (1.1) using a stationary first order iterative method, which can be written in the form of

(1.2)

The Gauss-Seidel method is more efficient if it combined with other method, [1]. It has also been proved that if A is strictly diagonally dominant or irreducible diagonally dominant or symmetric positive definite matrix, the Gauss-Seidel method converges for any initial approximation On the other hand [1] developed the method called generalized Gauss-Seidel method and the result shows that the method is more efficient than conventional Gauss-Seidel method. Author [2], indicated that the basic idea behind the first order stationary iterative method is how to write Eq. (1.2) and the choice of initial approximation to guarantee the convergence of the method. In this paper, the generalized Gauss-Seidel method is refined and compared its efficiency with the other methods.

Some of the basic definition of terms used in the this paper given here as under

Definition 1: A matrix A is said to be an M-matrix if it satisfies the following four properties

Definition 2: A banded matrix is a square matrix with zeros after “m” elements above and below the main diagonal, where m is less than the size of the matrix (i.e if the matrix is then ). In this case where bandedness mater, “m” is usually significantly less than N.

2. Preliminary

Considering the system of equations given in Eq. (1.1) and using splitting procedures in [1], we obtain:

(2.1)

where be a banded matrix of band width 2m+1 defined as

and are strictly lower and upper triangular part of the matrix respectively, and defined as follows.

Then, the Generalized Gauss-Seidel method for the solution of Eq. (1.1) is defined as

(2.2)

Where is generalized Gauss-Seidel iteration matrix and its corresponding iteration vector.

3. Description of the Method

Meaningful modifications of the iterative matrix will reduce the spectral radius and increases the rate of convergence of the method, [5] and [7]. The objective of this section is to develop refinement of generalized Gauss-Seidel (RGGS). Assume be an initial approximation for the solution of the linear system Eq. (1.1), and

After n iterations, we can have

it implies that

Now we refine this to obtain solution as

Let be an approximation for the solution of linear system Eq. (1.1). i.e; where u is the exact solution of Eq. (1.1). Here all are unknown, so we define it as

(3.1)

Making use of Eq. (2.2) and (3.1) we obtain the refinement of generalized Gauss-Seidel (RGGS) method as:

(3.2)

From the Eq. (3.2), we obtain the iterative refinement formula in matrix form as

Further, from Eq. (2.2), we obtain

(3.3)

where is the refinement of generalized Gauss-Seidel iteration matrix.

4. Condition on the Convergence of the Method

Theorem 1:- Let A be a strictly diagonally dominant (SDD) matrix. Then for any natural number the GGS method is convergent for any initial guess

Proof: - see [1]

Theorem 2:- Let be an M-matrix. Then for a given natural number generalized Gauss-Seidel method is convergent for any initial guess

Proof: - see [1].

Theorem 3:- If A is strictly diagonally dominant matrix then the refinement of generalized Gauss-Seidel method converges for any choice of the initial approximation

Proof:- Let be the exact solution of Eq. (1.1) and A be SDD matrix. Then generalized Gauss- Seidel method is convergent as proved by [1]. If then

From Theorem 4.1, likewise we have

Therefore,

Hence refinement of generalized Gauss-Seidel method is convergent.

Theorem 4:- let be an M-matrix. Then for a given natural number , the refinement of generalized Gauss-Seidel method converges for any choice of the initial approximation

Proof:- It follows from Theorem 2 and Theorem 3.

Theorem 5:- If A is row strictly diagonally dominant matrix then

Proof:- By Theorem 1 and convergence Theorem given by [4],

Theorem 6:- i) If A is SDD matrix, then

ii) If A is an M- matrix, then

Proof:-i) By the convergence Theorem of [4], we have

where is the spectral radius of generalized Gauss-Seidel method. Again by Theorem 5, we have

(4.1)

As a result of Eq. (4.1), we have

Therefore,

ii) Similar to (i) above, one can complete the proof the Theorem.

Remark: - We observe that the iterative matrix of refinement of generalized Gauss-Seidel is the square of generalized Gauss-Seidel iterative matrix. i.e. . As it can be easily realized If GGS method converges then Thus, if the GGS and RGGS method converge, the RGGS method converges faster than the GGS method.

5. Numerical Experiments

The major factors to be considered in comparing different numerical methods are the accuracy of numerical solution and its computational time, [9]. The same author, indicated that the comparison of numerical methods is not simply because of their performance may depend on the characteristic of the problem at hand. It should also be noted that there are other factors to be considered, such as stability, versatility, proof against run-time error, and so on which are being considered in most of the MATLAB built-in routines, [10]. Upon this, the efficiency of RGGS was compared with SOR and RGJ of [5] by considering two model problems in which it reduced to system of linear equations of which its coefficient matrix is either M-matrix or diagonal dominant matrix and also it illustrate the theory developed in this paper. Data about iteration number and computational times (in seconds) obtained using RGGS, SOR and RGJ is used for the analysis of the result.

1. Consider the system of linear equations, which obtained from the finite difference approximation of the mixed boundary value problem considered by Jain and et al [8] on page 106.

2. Consider a system of linear equations, which is reduced from the boundary value problem, where on the boundary. By applying Galerkin Method with triangular element and considering the symmetry of the boundary, Jain and et al [8].

The coefficient matrix of the first example is an M-Matrix whereas the second one is diagonal dominant for which the mentioned methods are convergent for any initial vector. Results produced by the two linear systems of equation are given in the Tables 1 and 2 respectively.

Table 1. Linear System of Equations of Order 6X6

Table 2. Linear Systems of Equations of Order 4 X4

6. Discussion and Conclusions

The Refinement of Generalized Gauss-Seidel method for solving linear systems of equation has been presented. Two examples, which obtained from boundary value problems and reduced to systems of linear equations of 6 x6 and 4 x 4 by finite difference approximation and finite element method respectively, were studied using MATLAB version 7.60(R2008a) software. The results obtained by Refinement of generalized Gauss-Seidel are compared with that of Refinement of generalized Jacobi and Successive-Over Relaxation as presented by Table 1 and Table 2. The analysis of results shows that RGGS method takes shorter time, 0.003789 seconds and 0.002961 seconds for the 6 x 6 and 4 x 4 linear equations respectively. In terms of number of iterations required to converge to the exact solution, the RGGS method takes about 6 iteration for each problem as compared to other methods, namely; SOR (14 iteration for 6x6 and 9 iteration for 4x4 system of equations) and RGJ (10 iteration for 6x6 and 11 iteration for 4x4 system of equations) with 510^-6 error of tolerance. On the other hand, methods which register small number of iteration demands less computer storage to store its data, [3], as a result RGGS demands less computer storage to store its data relative to SOR and RGJ. Thus, in all the parameters considered in this paper, i.e. CPU runtime, number of iteration and memory storage, the Refinement of generalized Gauss- Seidel is more efficient than the other methods considered when the coefficient matrix is either an M-matrix or diagonal dominant matrix.

ACKNOWLEDGEMENTS

The author would like to express his sincere gratitude to Dr. Gemechis File for constructive comments during the development of this paper and the acknowledgement also goes to Mr. Hailu Muleta for a kind cooperation while coding the iteration of the examples on MatLab Software.