1. Introduction

Suppose the linear system of equations

(1)

is such that is an , is the right-hand side vector, and is the vector of unknown. All the numerical methods for solution of a linear system can be categorised into two thus; direct and iterative methods.

A direct method is one that produces the exact solution of a linear system by performing a prescribed, finite number of operations (steps), if there were no round-off error. Examples of direct methods for solving linear systems include, graphical method, matrix inversion method, Cramer’s rule, elimination of unknowns, Gaussian elimination and LU decomposition. However, because direct methods are mostly restricted to small systems of linear equations, iterative methods remain the dominating and preferred techniques for solving very large linear systems.

An iterative method for solving a linear system consists of a process whereby the system is converted into an equivalent system of the form

(2)

What follows next is application of the general linear iteration formula

(3)

where , referred to as the Iteration matrix, is a matrix depending upon A and x, and is a column vector. At each step of the iteration a solution vector, , that more accurately approximates the solution to the linear system

than its predecessor, is produced. This sequence should be so defined that . For any iteration to be convergent, the spectral radius of the iteration matrix must be less than 1[1].

Iterative methods are further classified into two main types, namely, stationary and nonstationary iterative methods. Stationary iterative methods are those methods that can be expressed in the form

(4)

where neither G nor k depend upon the iteration count n[2]. Stationary methods are simpler to implement and understood compared to nonstationary methods. However, they are usually not effective when used alone; hence the need to implement them along with preconditioners.If we assume that , where is the identity matrix, the strictly lower triangular part of A, and the strictly upper triangular part of A, then the successive overrelaxation method as invented by[3] has the following matrix from

(5)

where is the SOR iteration matrix. Various authors have introduced preconditioners for accelerating the convergence of the SOR method[4 -9].

2. Materials and Methods

Consider the preconditioner , where

(6)

The above preconditioning matrix is applied to the coefficient matrix A of system (1) thus

(7)

which results into the equivalent preconditioned system

(8)

where and . The preconditioned coefficient matrix is further analyzed as follows.

(9)

(10)

(11)

Further splittings of the bracket terms in (11) are obtained as follows.

(12)

(13)

Thus

(14)

or equivalently

(15)

where is the diagonal, and are strictly lower and strictly upper triangular parts of respectively.

The application of overrelaxation parameter to the preconditioned linear system (8) yields

(16)

where,

(17)

(18)

Thus

(19)

is a regular splitting of , where

(20)

Hence, the following preconditioned SOR iterative scheme is obtained.

(21)

And the preconditioned SOR iterative matrix has the representation

(22)

Similarly,

(23)

is another splitting of the the preconditioned coefficient matrix , with

(24)

And this leads to the second preconditioned SOR iterative scheme

(25)

with the second preconditioned iterative matrix having the representation

(26)

3. Convergence Analysis

Convergence of the preconditioned iterative schemes (21) and (25) is established by showing that the spectral radii of the and are less than 1 in each case.

Lemma 3.1 (Varga[10] ): Let be an irreducible matrix. Then,

i. has a positive real eigenvalue equal to its spectral

radius.

ii. To there corresponds an eigenvector .

iii. increases when any entry of increases.

iv. is a simple eigenvalue of.

Lemma 3.2 (Varga[10] ): Let be a nonnegative matrix. Then

i. If for some nonnegative vector, then

.

ii. If for some positive vector x, then. Moreover, if is irreducible and if for some nonnegative vector x, then and x is a positive vector.

Lemma 3.1 (Li and Sun[11] ): Let be an splitting of. Then the splitting is convergent, i.e., , if and only if is a nonsingular matrix.

By employing the foregoing lemmas (lemmas 3.1 - 3.3), the next three theorems are proposed to establish convergence of the preconditioned iterative methods.

Theorem 3.1: Let be the SOR iteration matrix while and be the preconditioned SOR iteration matrices. If is an irreducible matrix with, and, then, and are nonnegative and irreducible matrices.

Proof

Since is an matrix, and Now, , for. Thus. Hence, is a nonnegative matrix.

One can also obtain that for,

(27)

(28)

(29)

Since is irreducible, so also is, because it inherits the nonzero structure of the irreducible matrix. The same thing applies to the matrix since the coefficients of are different from zero and less than 1 in absolute value. Hence, is an irreducible matrix.

(30)

Since, for and. Consequently, one can find that. Hence is a nonnegative matrix.

Now,

(31)

(32)

(33)

(34)

(35)

(36)

where and and denote the strictly lower and strictly upper parts of the matrix respectively. is irreducible, since it inherits the nonzero structure of the irreducible matrix

Now,

(37)

(38)

(39)

The matrix is irreducible, since the coefficients of are different from zero and less than one in absolute value. Therefore, the matrix is irreducible. Hence is a nonnegative and irreducible matrix.

Similarly, consider

(40)

(41)

(42)

(43)

(44)

Using similar arguments it is conclusive that is a nonnegative and irreducible matrix. The proof is completed.

Theorem 3.2: Let and be the SOR and preconditioned SOR iteration matrices respectively. If and if is an irreducible with. Then,

(i)

(ii)

(iii)

Proof

From Theorem 3.1, and are nonnegative and irreducible matrices. Suppose then there exists a positive vector, such that

(45)

That is,

(46)

(47)

Therefore, for this

(48)

(49)

From equation (47)

(50)

(51)

(52)

(53)

(54)

(55)

(56)

(57)

Let, where. Then, because,. Also, , since. Therefore, So, , since.

i. If, then but not equal to 0.

Therefore,

(58)

From Lemma 3.2, one obtains

(59)

ii. If, then

Therefore,

(60)

From Lemma 3.2, we have

(61)

iii. If, then but not equal to 0.

Therefore,

(62)

From Lemma 3.2, we have

(63)

The proof is completed.

Theorem 3.3: Let and be the SOR and the preconditioned SOR iteration matrices respectively. If and if is an irreducible matrix with. Then,

(i)

(ii)

(iii)

Proof

From Theorem 3.1, and are nonnegative and irreducible matrices. Suppose, then there exists a positive vector, such that

(64)

That is,

(65)

(66)

Therefore, for this,

(67)

(68)

(69)

From equation (66)

(70)

(71)

(72)

(73)

(74)

Let, with. It is clear that, since, ,and Since is a nonsingular matrix, we let be a splitting of some matrix, i.e., Also, is an matrix and. Thus, is an splitting. Now, is a strictly lower triangular matrix, and by implication its eigenvalues lie on its main diagonal; in this case they are all zeros. Therefore, since is a convergent splitting. By the foregoing, is an splitting and. Lemma 3.3 is invoked in order to establish that is an matrix. Since K is an matrix, by definition, . Thus, and.

If, then but not equal to 0.

Therefore,

(75)

From Lemma 3.2, we have

(76)

ii. If, then

Therefore,

(77)

From Lemma 3.2, we have

(78)

iii. If, then but not equal to 0.

Therefore,

(79)

From Lemma 3.2, we have

(80)

The proof is completed.

If in and the relaxation parameter, the iteration matrices of the Gauss-Seidel method results in each case. Therefore, the following corollaries are direct implications of Theorem 3.1 and Theorem 3.2.

Corollary 3.1 Let be the Gauss-Seidel iteration matrix and be the preconditioned Gauss-Seidel iteration matrix. If is an irreducible matrix with, then

(i)

(ii)

(iii)

Corollary 3.2 Let be the Gauss-Seidel iteration matrix and be the preconditioned Gauss-Seidel iteration matrix. If is an irreducible matrix with then

(i)

(ii)

(iii)

4. Numerical Experiments

Example 4.1 Consider a matrix of the form.

Table 1 displays the results of comparing the spectral radius es of iterative matrices corresponding to the matrix in example 4.1.

Table 1 compares the spectral radiuses of iteration matrices. It reveals that the two preconditioned SOR iteration matrices exhibit faster convergence than the SOR, because the spectral radiuses of are less than the spectral radius of , for all values of relaxation parameter.

Example 4.2 Consider a matrix of the form.

The results of example 4.2 are displayed in Table 2 as follows.

Table 1. Result of Spectral Radiuses of      ,       and       Iterative Matrices for Example 4.1

Table 2. Result of Spectral Radiuses of      ,       and      Iterative Matrices for Example 4.2

Table 2 goes further to confirm the efficiency of the preconditioned iterations by revealing that the spectral radiuses of the preconditioned iterative matrices are less than the spectral radius of the SOR iterative matrix. That is, , for all values of relaxation parameter.

5. Conclusions

In this research work, a preconditioning matrix is introduced. Two different forms of the preconditioned SOR-type iterations are formulated for the preconditioner. Some theorems are proposed and proven in order to establish the validity and efficiency of the preconditioned iterations. The preconditioned iterations are shown to satisfy standard convergence criteria under mild conditions imposed on the coefficient matrix of the linear system. Based on the results obtained, it is instructive to conclude that the preconditioned SOR iterative methods presented in this research work provide better and faster convergence properties than the SOR.

ACKNOWLEDGEMENTS

The authors would like express their indebtedness to all those whose works were cited in this paper, and all others who were not cited, but nevertheless contributed in various capacities toward the success of this work. The authors remain grateful.