| Peer-Reviewed

On Optimal Parameter Not Only for the SOR Method

Received: 15 October 2019     Accepted: 18 November 2019     Published: 22 November 2019
Views:       Downloads:
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
  • 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
  • Institute of Computer Science, Lublin University of Technology, Nadbystrzycka, Lublin, Poland

  • Sections