Comparative analysis of Jacobi and Gauss-Seidel iterative methods

Pavel Khrapov, Nikita Volkov

Abstract


The paper presents a comparative analysis of iterative numerical methods of Jacobi and Gauss-Seidel for solving systems of linear algebraic equations (SLAEs) with complex and real matrices. The ranges of convergence for both methods for SLAEs in two and three unknowns, as well as the interrelationships of these ranges are obtained. An algorithm for determining the convergence of methods for SLAEs using the complex analog of the Hurwitz criterion is constructed, the realization of this algorithm in Python in the case of SLAEs in three unknowns is given. A statistical comparison of the con- vergence of both methods for SLAEs with a real matrices and the number of unknowns from two to five is carried out.

Full Text:

PDF

References


Bylina, J., & Bylina, B. (2008, October). Merging Jacobi and Gauss-Seidel methods for solving Markov chains on computer clusters. In 2008 International Multiconference on Computer Science and Information Technology (pp. 263-268). IEEE. DOI: 10.1109/IMCSIT.2008.4747250

Nützi, G., Schweizer, A., Möller, M., & Glocker, C. (2014, August). Projective jacobi and gauss-seidel on the gpu for non-smooth multi-body systems. In International Design Engineering Technical Conferences and Computers and Information in Engineering Conference (Vol. 46391, p. V006T10A013). American Society of Mechanical Engineers. DOI: 10.1115/DETC2014-34606

Saad, Y., & Schultz, M. H. (1986). GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on scientific and statistical computing, 7(3), 856-869. DOI: 10.1137/0907058

Tarigan, A. J. M., Mardiningsih, M., & Suwilo, S. (2022). The search for alternative algorithms of the iteration method on a system of linear equation. Sinkron: jurnal dan penelitian teknik informatika, 7(4), 2124-2424. DOI: 10.33395/sinkron.v7i4.11817

Gunawardena, A. D., Jain, S. K., & Snyder, L. (1991). Modified iterative methods for consistent linear systems. Linear Algebra and Its Applications, 154, 123-143. DOI: 10.1016/0024-3795(91)90376-8

Bagnara, R. (1995). A unified proof for the convergence of Jacobi and Gauss–Seidel methods. SIAM review, 37(1), 93-97. DOI: 10.1137/1037008

Salkuyeh, D. K. (2007). Generalized Jacobi and Gauss-Seidel methods for solving linear system of equations. NUMERICAL MATHEMATICS-ENGLISH SERIES-, 16(2), 164.

Chen, W. Y. (1995). On the polynomials with all their zeros on the unit circle. Journal of mathematical analysis and applications, 190(3), 714-724. DOI: 10.1006/jmaa.1995.1105

Bharanedhar, S. V., Selvan, A. A., & Ghosh, R. (2023). Zeros of self-inversive polynomials with an application to sampling theory. Applied Mathematics and Computation, 439, 127547. DOI: 10.1016/j.amc.2022.127547

Milaszewicz, J. P. (1987). Improving jacobi and gauss-seidel iterations. Linear Algebra and Its Applications, 93, 161-170. DOI: 10.1016/S0024-3795(87)90321-1

Zadorozhniy, V. G. (2018). The conditions under which the roots of a polynomial lie inside the unit circle. Bulletin of VSU. Series: System Analysis and Information Technologies, 2, 22-25. https://www.elibrary.ru/item.asp?id=35449768

Sun, L. Y. (2005). A comparison theorem for the SOR iterative method. Journal of computational and applied mathematics, 181(2), 336-341. DOI: 10.1016/j.cam.2004.12.007

Ahmadi, A., Manganiello, F., Khademi, A., & Smith, M. C. (2021). A parallel Jacobiembedded Gauss-Seidel method. IEEE Transactions on Parallel and Distributed Systems, 32(6), 1452-1464. DOI: 10.1109/TPDS.2021.3052091

Postnikov, M. M. (1981). Stable polynomials. Nauka”, Moscow.

Gantmakher, F. R. (2000). The theory of matrices (Vol. 131). American Mathematical Soc.

Erd´elyi, T. (2001). On the zeros of polynomials with Littlewood-type coefficient constraints. Michigan Mathematical Journal, 49(1), 97-111. DOI: 10.1307/mmj/1008719037

Konvalina, J., & Matache, V. (2004). Palindrome-polynomials with roots on the unit circle. Comptes Rendus Mathematiques, 26(2), 39.

Mercer, I. D. (2006). Unimodular roots of special Littlewood polynomials. Canadian Mathematical Bulletin, 49(3), 438-447. DOI: 10.4153/CMB-2006-043-x

Kohno, T., Kotakemori, H., Niki, H., & Usui, M. (1997). Improving the modified GaussSeidel method for Z-matrices. Linear Algebra and its Applications, 267, 113-123. DOI: 10.1016/S0024-3795(97)00063-3

Li, W., & Sun, W. (2000). Modified Gauss–Seidel type methods and Jacobi type methods for Z-matrices. Linear Algebra and its Applications, 317(1-3), 227-240. DOI: 10.1016/S0024-3795(00)00140-3

Shang, Y. (2009). A distributed memory parallel Gauss–Seidel algorithm for linear algebraic systems. Computers & Mathematics with Applications, 57(8), 1369-1376. DOI: 10.1016/j.camwa.2009.01.034

Courtecuisse, H., & Allard, J. (2009, June). Parallel dense gauss-seidel algorithm on manycore processors. In 2009 11th IEEE International Conference on High Performance Computing and Communications (pp. 139-147). IEEE. DOI: 10.1109/HPCC.2009.51

Koester, D. P., Ranka, S., & Fox, G. C. (1994, November). A parallel Gauss-Seidel algorithm for sparse power system matrices. In Supercomputing’94: Proceedings of the 1994 ACM/IEEE Conference on Supercomputing (pp. 184-193). IEEE. DOI: 10.1145/602770.602806

Amodio, P., & Mazzia, F. (1995). A parallel Gauss–Seidel method for block tridiagonal linear systems. SIAM Journal on Scientific Computing, 16(6), 1451-1461. DOI: 10.1137/0916084

Tavakoli, R., & Davami, P. (2007). A new parallel Gauss–Seidel method based on alternating group explicit method and domain decomposition method. Applied mathematics and computation, 188(1), 713-719. DOI: 10.1016/j.amc.2006.10.023

Karunanithi, S., Gajalakshmi, N., Malarvizhi, M., & Saileshwari, M. (2018). A Study on comparison of Jacobi, Gauss-Seidel and SOR methods for the solution in system of linear equations. Int. J. of Math. Trends and Technology,(IJMTT), 56(4). DOI: 10.14445/22315373/IJMTTV56P531

Korsakov, G. F. (1973). The number of roots of a polynomial outside a circle. Mathematical notes of the Academy of Sciences of the USSR, 13, 3-8. DOI: 10.1007/BF01093620

Biberdorf, È. A. D. (2000). A Criterion for the Dichotomy of Roots of a Polynomial on the Unit Circle. Sibirskii Zhurnal Industrial'noi Matematiki, 3(1), 16-32. https://www.elibrary.ru/item.asp?id=9484660

Joyal, A., Labelle, G., & Rahman, Q. (1967). On the location of zeros of polynomials. Canadian mathematical bulletin, 10(1), 53-63. DOI: 10.4153/CMB-1967-006-3

Dehmer, M. (2006). On the location of zeros of complex polynomials. Journal of Inequalities in Pure and Applied Mathematics, 7(1).

Frank, E. (1946). On the zeros of polynomials with complex coefficients. DOI: 10.1090/S0002-9904-1946-08526-2


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162