On Optimal Parameter Not Only for the SOR Method

Stanislaw Marian Grzegorski

doi:doi:10.11648/j.acm.20190805.11

| Peer-Reviewed

On Optimal Parameter Not Only for the SOR Method

Stanislaw Marian Grzegorski

Published in Applied and Computational Mathematics (Volume 8, Issue 5)

Received: 15 October 2019 Accepted: 18 November 2019 Published: 22 November 2019

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

The Jacobi, Gauss-Seidel and SOR methods belong to the class of simple iterative methods for linear systems. Because of the parameter , the SOR method is more effective than the Gauss-Seidel method. Here, a new approach to the simple iterative methods is proposed. A new parameter q can be introduced to every simple iterative method. Then, if a matrix of a system is positive definite and the parameter q is sufficiently large, the method is convergent. The original Jacobi method is convergent only if the matrix is diagonally dominated, while the Jacobi method with the parameter q is convergent for every positive definite matrix. The optimality criterion for the choice of the parameter q is given, and thus, interesting results for the Jacobi, Richardson and Gauss-Seidel methods are obtained. The Gauss-Seidel method with the parameter q, in a sense, is equivalent to the SOR method. From the formula for the optimal value of q results the formula for optimal value of . Up to present, this formula was known only in special cases. Practical useful approximate formula for optimal value  is also given. The influence of the parameter q on the speed of convergence of the simple iterative methods is shown in a numerical example. Numerical experiments confirm: for very large scale systems the speed of convergence of the SOR method with optimal or approximate parameter  is near the same (in some cases better) as the speed of convergence of the conjugate gradients method.

Published in	Applied and Computational Mathematics (Volume 8, Issue 5)
DOI	10.11648/j.acm.20190805.11
Page(s)	82-87
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2019. Published by Science Publishing Group

Keywords

Iterative Methods for Linear Systems, Optimal Parameter for SOR Method, Positive Definite Matrices

References

[1]	I. Koutis, G. L. Miller, R. Peng, A fast solver for a class of linear systems, Communications of the ACM 55 (10) (2010) 99-107.
[2]	E. G. Boman, B. Hendrickson, S. Vavasis, Solving elliptic finite element systems in near-linear time with support preconditioners, SIAM J. Numer. Anal. 46 (6) (2008) 3264-3284.
[3]	J. D. Hogg, J. A. Scott, A fast and robust mixed-precision solver for the solution of sparse symmetric linear systems, ACM Trans. on Math. Soft. 37 (2) (2010).
[4]	J. Stoer, R. Bulirsch, Introduction to Numerical Analysis, Third Ed., Springer Verlag, 2002.
[5]	Y. Saad, Iterative Methods for Sparse Linear Systems, Second Ed., SIAM Press, 2016.
[6]	D. S. Watkins, Fundamentals of Matrix Computations, Second Ed., Wiley, 2002.
[7]	D. M. Young, Iterative Solutions of Large Linear Systems, Academic Press, New York, 1971, reprinted by Dover 2003.
[8]	C. G. Broyden, On the convergence criteria for the method of successive over-relaxation, Mathematics of Computation 18 (85) (1964) 136-141.
[9]	S. Yang, M. K. Gobbert, The optimal relaxation parameter for the SOR method applied to the Poisson equation in any space dimensions, Appl. Math. Letters, 22 (2009) 325-331.
[10]	J. W. Demmel, Applied Numerical Linear Algebra, SIAM Press, 1997.
[11]	I. K. Youssef, S. M. Ali, M. Y. Hamada, On the Line Successive Overrelaxation Method, Applied and Computational Mathematics, 5, 3 (2016) 103-106.
[12]	Cheng-yi Zhang, Zichen Xue, A convergence analysis of SOR iterative methods for linear systems with week H-matrices, Open Mathematics, 2016.
[13]	S. Karunanithi, N. Gajalakshmi, M. Malarvishi, M. Saileshwari, 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, 2018.
[14]	O. Nevanlinna, How fast can iterative methods be? In “Recent Advances in Iterative Methods”, ed. by G. Golub, A. Greenbaum, M. Luskin, Math. and its Appl., 60 (2012) 135-148.
[15]	H. Woźniakowski, Round-off error analysis of iterations for large linear systems, Numer. Math., 30 (1978) 301-314.

Cite This Article

Plain Text BibTeX RIS

APA Style

Stanislaw Marian Grzegorski. (2019). On Optimal Parameter Not Only for the SOR Method. Applied and Computational Mathematics, 8(5), 82-87. https://doi.org/10.11648/j.acm.20190805.11

Copy | Download

ACS Style

Stanislaw Marian Grzegorski. On Optimal Parameter Not Only for the SOR Method. Appl. Comput. Math. 2019, 8(5), 82-87. doi: 10.11648/j.acm.20190805.11

Copy | Download

AMA Style

Stanislaw Marian Grzegorski. On Optimal Parameter Not Only for the SOR Method. Appl Comput Math. 2019;8(5):82-87. doi: 10.11648/j.acm.20190805.11

Copy | Download

@article{10.11648/j.acm.20190805.11,
  author = {Stanislaw Marian Grzegorski},
  title = {On Optimal Parameter Not Only for the SOR Method},
  journal = {Applied and Computational Mathematics},
  volume = {8},
  number = {5},
  pages = {82-87},
  doi = {10.11648/j.acm.20190805.11},
  url = {https://doi.org/10.11648/j.acm.20190805.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20190805.11},
  abstract = {The Jacobi, Gauss-Seidel and SOR methods belong to the class of simple iterative methods for linear systems. Because of the parameter , the SOR method is more effective than the Gauss-Seidel method. Here, a new approach to the simple iterative methods is proposed. A new parameter q can be introduced to every simple iterative method. Then, if a matrix of a system is positive definite and the parameter q is sufficiently large, the method is convergent. The original Jacobi method is convergent only if the matrix is diagonally dominated, while the Jacobi method with the parameter q is convergent for every positive definite matrix. The optimality criterion for the choice of the parameter q is given, and thus, interesting results for the Jacobi, Richardson and Gauss-Seidel methods are obtained. The Gauss-Seidel method with the parameter q, in a sense, is equivalent to the SOR method. From the formula for the optimal value of q results the formula for optimal value of . Up to present, this formula was known only in special cases. Practical useful approximate formula for optimal value  is also given. The influence of the parameter q on the speed of convergence of the simple iterative methods is shown in a numerical example. Numerical experiments confirm: for very large scale systems the speed of convergence of the SOR method with optimal or approximate parameter  is near the same (in some cases better) as the speed of convergence of the conjugate gradients method.},
 year = {2019}
}

Copy | Download

TY - JOUR
T1 - On Optimal Parameter Not Only for the SOR Method
AU - Stanislaw Marian Grzegorski
Y1 - 2019/11/22
PY - 2019
N1 - https://doi.org/10.11648/j.acm.20190805.11
DO - 10.11648/j.acm.20190805.11
T2 - Applied and Computational Mathematics
JF - Applied and Computational Mathematics
JO - Applied and Computational Mathematics
SP - 82
EP - 87
PB - Science Publishing Group
SN - 2328-5613
UR - https://doi.org/10.11648/j.acm.20190805.11
AB - The Jacobi, Gauss-Seidel and SOR methods belong to the class of simple iterative methods for linear systems. Because of the parameter , the SOR method is more effective than the Gauss-Seidel method. Here, a new approach to the simple iterative methods is proposed. A new parameter q can be introduced to every simple iterative method. Then, if a matrix of a system is positive definite and the parameter q is sufficiently large, the method is convergent. The original Jacobi method is convergent only if the matrix is diagonally dominated, while the Jacobi method with the parameter q is convergent for every positive definite matrix. The optimality criterion for the choice of the parameter q is given, and thus, interesting results for the Jacobi, Richardson and Gauss-Seidel methods are obtained. The Gauss-Seidel method with the parameter q, in a sense, is equivalent to the SOR method. From the formula for the optimal value of q results the formula for optimal value of . Up to present, this formula was known only in special cases. Practical useful approximate formula for optimal value  is also given. The influence of the parameter q on the speed of convergence of the simple iterative methods is shown in a numerical example. Numerical experiments confirm: for very large scale systems the speed of convergence of the SOR method with optimal or approximate parameter  is near the same (in some cases better) as the speed of convergence of the conjugate gradients method.
VL - 8
IS - 5
ER -

Copy | Download

Author Information

Stanislaw Marian Grzegorski

Institute of Computer Science, Lublin University of Technology, Nadbystrzycka, Lublin, Poland

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Stanislaw Marian Grzegorski. (2019). On Optimal Parameter Not Only for the SOR Method. Applied and Computational Mathematics, 8(5), 82-87. https://doi.org/10.11648/j.acm.20190805.11

Copy | Download

ACS Style

Stanislaw Marian Grzegorski. On Optimal Parameter Not Only for the SOR Method. Appl. Comput. Math. 2019, 8(5), 82-87. doi: 10.11648/j.acm.20190805.11

Copy | Download

AMA Style

Stanislaw Marian Grzegorski. On Optimal Parameter Not Only for the SOR Method. Appl Comput Math. 2019;8(5):82-87. doi: 10.11648/j.acm.20190805.11

Copy | Download

@article{10.11648/j.acm.20190805.11,
  author = {Stanislaw Marian Grzegorski},
  title = {On Optimal Parameter Not Only for the SOR Method},
  journal = {Applied and Computational Mathematics},
  volume = {8},
  number = {5},
  pages = {82-87},
  doi = {10.11648/j.acm.20190805.11},
  url = {https://doi.org/10.11648/j.acm.20190805.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20190805.11},
  abstract = {The Jacobi, Gauss-Seidel and SOR methods belong to the class of simple iterative methods for linear systems. Because of the parameter , the SOR method is more effective than the Gauss-Seidel method. Here, a new approach to the simple iterative methods is proposed. A new parameter q can be introduced to every simple iterative method. Then, if a matrix of a system is positive definite and the parameter q is sufficiently large, the method is convergent. The original Jacobi method is convergent only if the matrix is diagonally dominated, while the Jacobi method with the parameter q is convergent for every positive definite matrix. The optimality criterion for the choice of the parameter q is given, and thus, interesting results for the Jacobi, Richardson and Gauss-Seidel methods are obtained. The Gauss-Seidel method with the parameter q, in a sense, is equivalent to the SOR method. From the formula for the optimal value of q results the formula for optimal value of . Up to present, this formula was known only in special cases. Practical useful approximate formula for optimal value  is also given. The influence of the parameter q on the speed of convergence of the simple iterative methods is shown in a numerical example. Numerical experiments confirm: for very large scale systems the speed of convergence of the SOR method with optimal or approximate parameter  is near the same (in some cases better) as the speed of convergence of the conjugate gradients method.},
 year = {2019}
}

Copy | Download