A. Ndanusa, K. R. Adeboye
Department of Mathematics and Statistics, Federal University of Technology, Minna, Nigeria
Correspondence to: A. Ndanusa, Department of Mathematics and Statistics, Federal University of Technology, Minna, Nigeria.
Email:  
Copyright © 2012 Scientific & Academic Publishing. All Rights Reserved.
Abstract
A preconditioner of the type for speeding up convergence of the successive overrelaxation (SOR) iterative method for solving linear system is proposed. Two forms of the preconditioned SOR iteration are obtained and implemented, under limited conditions imposed on the coefficient matrix of the original linear system. Convergence properties are analyzed and established in conformity with standard procedures. The rates of convergence of the preconditioned iterations are shown to supersede that of the SOR method. Numerical experiments confirmed the established theoretical results.
Keywords:
Spectral Radius, Preconditioner, Iterative Matrix, Linear System, Lmartices
Cite this paper:
A. Ndanusa, K. R. Adeboye, "Preconditioned SOR Iterative Methods for Lmartices", American Journal of Computational and Applied Mathematics, Vol. 2 No. 6, 2012, pp. 300305. doi: 10.5923/j.ajcam.20120206.08.
1. Introduction
Suppose the linear system of equations  (1) 
is such that is an , is the righthand 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 roundoff 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. Theni. 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 matrixNow,  (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) ProofFrom 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) ProofFrom 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 GaussSeidel 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 GaussSeidel iteration matrix and be the preconditioned GaussSeidel iteration matrix. If is an irreducible matrix with, then(i) (ii) (iii) Corollary 3.2 Let be the GaussSeidel iteration matrix and be the preconditioned GaussSeidel 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 SORtype 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.
References
[1]  William F. Ames, Numerical methods for partial differential equations, 2nd ed., Thomas Nelson & Sons Ltd, Great Britain, 1977. 
[2]  Richard Barrett, Michael Berry, Tony F. Chan, James Demmel, June M. Donato, Jack Dongarra, Victor Eijkhout, Roldan Pozo, Charles Romine, Henk Van der Vorst, Templates for the solution of linear systems: Building blocks for iterative methods, SIAM, Philadelphia, PA, 1994. 
[3]  David M. Young “Iterative methods for solving partial difference equations of elliptic type”, Doctoral Thesis, Harvard University, Cambridge, 1950. 
[4]  Mehdi Dehghan, Masoud Hajarian, “Improving Preconditioned SORType Iterative Methods for Lmartices”, International Journal for Numerical Methods in Biomedical Engineering, no.27, pp.774784, 2011. 
[5]  Abdulrahman Ndanusa, “Preconditioned successive overrelaxation iterative method for solving partial differential equations of elliptic type”, Doctoral Thesis, Federal University of Technology, Minna, Nigeria, 2012. 
[6]  ShiLiang Wu, CuiXia Li, TingZhu Huang, “Improvements of Preconditioned SOR Iterative Methods for Lmartices”, WSEAS Transactions on Mathematics, vol.12, no.9, 2010. 
[7]  D. J. Evans, M. M. Martins, M. E. Trigo, “The AOR iterative method for new preconditioned linear systems”, Elsevier Science, Journal of Computational and Applied Mathematics”, no.132, pp. 461466, 2001. 
[8]  Hongjuan Wang, Yaotang Li, “A new preconditioned AOR iterative method for Lmartices”, Elsevier Science, Journal of Computational and Applied Mathematics”, no.229, pp. 4753, 2009. 
[9]  Davod Khojasteh Salkuyeh, Yousef Abdolalizadeh, “On the preconditioning of the AOR iterative methods for Mmartices”, International Journal of Applied Mathematics and Computation, vol.3, no.2, 2011. 
[10]  Richard S. Varga, Matrix iterative analysis, 2nd ed., PrenticeHall, Englewood Cliffs, New Jersey, USA, 1981. 
[11]  Wen Li, Weiwei Sun, “Modified GaussSeidel type methods and Jacobi type methods for Zmartices”, Elsevier Science, Linear Algebra and its Applications, no.317, pp.227240, 2000. 