On Algebraic Structure of Improved Gauss-Seidel Iteration

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.

• O. M. Bamigbola
• A. A. Ibrahim

• Linear system of equations
• Gauss-Seidel iteration
• algebraic structure
• convergence.

[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.