On Algebraic Structure of Improved Gauss-Seidel Iteration

Authors: O. M. Bamigbola, A. A. Ibrahim

Abstract:

Analysis of real life problems often results in linear systems of equations for which solutions are sought. The method to employ depends, to some extent, on the properties of the coefficient matrix. It is not always feasible to solve linear systems of equations by direct methods, as such the need to use an iterative method becomes imperative. Before an iterative method can be employed to solve a linear system of equations there must be a guaranty that the process of solution will converge. This guaranty, which must be determined apriori, involve the use of some criterion expressible in terms of the entries of the coefficient matrix. It is, therefore, logical that the convergence criterion should depend implicitly on the algebraic structure of such a method. However, in deference to this view is the practice of conducting convergence analysis for Gauss- Seidel iteration on a criterion formulated based on the algebraic structure of Jacobi iteration. To remedy this anomaly, the Gauss- Seidel iteration was studied for its algebraic structure and contrary to the usual assumption, it was discovered that some property of the iteration matrix of Gauss-Seidel method is only diagonally dominant in its first row while the other rows do not satisfy diagonal dominance. With the aid of this structure we herein fashion out an improved version of Gauss-Seidel iteration with the prospect of enhancing convergence and robustness of the method. A numerical section is included to demonstrate the validity of the theoretical results obtained for the improved Gauss-Seidel method.

Keywords: Linear system of equations, Gauss-Seidel iteration, algebraic structure, convergence.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1096293

References:

[1] A. K. Aziz, Numerical solution of differential equations. New York: Van Nostrand, 1969.
[2] R. Bagnara, A unified proof for the convergence of Jacobi and Gauss- Seidel methods. California: SIAM, 1995.
[3] R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. M. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine and H. van der Vorst, Templates for the solution of linear systems: Building blocks for iterative methods. Philadephia: SIAM Publications, 1993.
[4] B. Carnahan. Applied numerical analysis. New York: John Wiley and Sons, 1980.
[5] P. Demidovich. Computational mathematics. Moscow: MIR Publishers, 1981.
[6] N. Douglas. A concise introduction to numerical analysis. Minnesota: Institute for Mathematics and its Application, 2001.
[7] M. V. P. Garcia, C. Humes Jr. and J. M. Stern. Generalized line criterion for Gauss-Seidel method. Computational and Applied Mathematics, vol.22 no.1, (2003), pp. 91-97.
[8] A. Greenbaum. Iterative methods for solving linear systems. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1997.
[9] A. S. Householder. Theory of matrices in numerical analysis. Johnson: Blaisdell Publishing Company, 1964.
[10] A. A. Ibrahim. Characterisation and application of stationary iterative methods. University of Ilorin, Nigeria: Unpublished Ph.D. Thesis, 2014.
[11] C. T. Kelly. Iterative methods for linear and nonlinear equations. Philadelphia: SIAM, 1995.
[12] P. Lax. Functional analysis. New York: John Wiley and Sons, 2002.
[13] C. D. Meyer. Matrix analysis and applied linear algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2000.
[14] S. Richard. Matrix iterative analysis. New Jersey: Prentice-Hall, 1962.
[15] Y. Saad. Iterative Methods for sparse linear systems, 2nd edition. New York: PWS Publishing, 2000.
[16] Y. Saad and H. A. van der Vorst. Iterative solution of linear systems in the 20th Century. J. Comput. Appl. Math., 123 (2000), pp. 1-33.
[17] A. Sidi. Development of iterative techniques and extrapolation methods for Drazin inverse solution of consistent or inconsistent singular linear systems. Linear Algebra Appl., 167 (1992), pp. 171-203.
[18] G. D. Smith. Partial differential equations. Oxford: Oxford University Press, 1978.
[19] R. S. Varga. Matrix iterative analysis. New Jersy: Prentice-Hall, Englewood Cliffs, 1962.
[20] D. M. Young. Survey of Numerical Methods. Massachusetts: Addison Wesley, 1972.
[21] D. M. Young. Iterative solution of large linear systems. New York: Academic Press, 1971.