Analysis of the Jacobi and Seidel methods convergence

Authors: Volkov N.S.
Published in issue: #2(91)/2024
DOI:
Category: Mathematics | Chapter: Computational Mathematics
Keywords: iterative methods, system of linear algebraic equations, simple iteration method, Jacobi method, Seidel method, quadratic equation, third degree algebraic equation, real matrix
Published: 01.05.2024

The paper analyzes the Jacobi and Seidel iterative methods convergence in solving the systems of linear algebraic equations (SLAE) with the real matrices. The convergence areas for both methods in SLAE with two and three unknowns are obtained. The convergence methods in SLAEs are statistically compared with the real matrices and the number of unknowns from two to five. Based on the analytical and statistical analysis performed, it was concluded that the Seidel method has better convergence compared to the Jacobi method. An example of the SLAE matrix is provided, where the Jacobi iterative method converges, but the Seidel method is not efficient.

References

[1] Bylina J., Bylina B. Combining Jacobi and Gauss-Seidel methods for solving Markov chains on computer clusters. International Multi-Conference on Computer Science and Information Technology, IEEE, 2008, pp. 263-268. https://doi.org/10.1109/IMCSIT.2008.4747250

[2] Nyutsi G., Schweitzer A., Meller M., Glocker S. Projective Jacobi and Gauss-Seidel methods on a GPU for non-smooth systems with multiple bodies. International Conferences on Technical Design and the conference "Computers and Information in Mechanical Engineering", American Society of Mechanical Engineers, 2014, vol. 46391, art. V006T10A013. https://doi.org/10.1115/DETC2014-34606

[3] Tarigan A.J.M., Mardiningsih M., Suwilo S. The search for alternative algorithms of the iteration method on a system of linear equation. Sinkron: jurnal dan penelitian teknik informatika, 2022, vol. 7 (4), pp. 2124–2424. https://doi.org/10.33395/sinkron.v7i4.11817

[4] Gunawardena A.D., Jain S.K., Snyder L. Modified iterative methods for consistent linear systems. Linear Algebra and Its Applications, 1991, vol. 154, pp. 123–143. https://doi.org/10.1016/0024-3795(91)90376-8

[5] Bagnara R. A unified proof for the convergence of Jacobi and Gauss-Seidel methods. SIAM review, 2001, vol. 37 (1), pp. 93–97. https://doi.org/10.1137/1037008

[6] Salkuyeh D.K. Generalized Jacobi and Gauss-Seidel methods for solving linear system of equations. A Journal of Chinese Universities. Numerical mathematics, 2007, vol. 16 (2), pp. 164–170.

[7] Milaszewicz J.P. Improving Jacobi and Gauss-Seidel iterations. Linear Algebra and its Applications, 1987, vol. 93, pp. 161–170. https://doi.org/10.1016/S0024-3795(87)90321-1

[8] Li W., Sun W. Modified Gauss-Seidel type methods and Jacobi type methods for Z-matrices. Linear Algebra and its Applications, 2000, vol. 317 (1–3), pp. 227–240. https://doi.org/10.1016/S0024- 3795(00)00140-3

[9] Tavakoli R., Davami P. A new parallel Gauss-Seidel method based on alternating group explicit method and domain decomposition method. Applied mathematics and computation, 2007, vol. 188 (1), pp. 713–719. https://doi.org/10.1016/j.amc.2006.10.023

[10] Koester D.P., Ranka S., Fox G.C. A parallel Gauss-Seidel algorithm for sparse power system matrices. Supercomputing’94: Proceedings of the 1994 ACM/IEEE Conference on Supercomputing, IEEE, 1994, pp. 184–193. https://doi.org/10.1145/602770.602806

[11] Amodio P., Mazzia F. A parallel Gauss-Seidel method for block tridiagonal linear systems. SIAM Journal on Scientific Computing, 1995, vol. 16 (6), pp. 1451–1461. https://doi.org/10.1137/0916084

[12] Chen W.Y. On the polynomials with all their zeros on the unit circle. Journal of mathematical analysis and applications, 1995, vol. 190 (3), pp. 714–724. https://doi.org/10.1006/jmaa.1995.1105

[13] Zadorozhny V.G. Conditions under which the roots of a polynomial lie inside a unit circle. Bulletin of the VSU. Series: System Analysis and Information Technologies, 2018, no. 2, pp. 22–25. (In Russ.). https://doi.org/10.17308/sait.2018.2/1206

[14] Konvalina J., Matache V. Palindromic polynomials with roots on the unit circle. Mathematical Calculations, 2004, vol. 26 (2), art. 39.

[15] Korsakov G.F. On the number of roots of a polynomial outside the circle. Mathematical Notes, 1973, vol. 13, no. 1, pp. 3-12. (In Russ.). https://doi.org/10.1007/BF01093620

[16] Joyal A., Labelle G., Rahman K. On the location of the zeros of polynomials. Canadian Mathematical Bulletin, 1967, volume 10 (1), pp. 53–63. https://doi.org/10.4153/CMB-1967-006-3

[17] Demer M. On the location of the zeros of complex polynomials. Journal of Inequalities in Pure and Applied Mathematics, 2006, vol. 7 (1).

[18] Frank E. On the zeros of polynomials with complex coefficients. Bulletin of the American Mathematical Society, 1946, pp. 144–157. https://doi.org/10.1090/S0002-9904-1946-08526-2

[19] Postnikov M.M. Stable polynomials. Moscow, Nauka, 1981, 176 p. (In Russ.).

[20] Khrapov P.V., Volkov N.S. Comparative analysis of iterative Jacobi and Gauss-Seidel methods. International Journal of Open Information Technologies, 2024, vol. 12, no. 2, pp. 23–34. (In Russ.).