Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Convergence properties of the symmetric and unsymmetric successive overrelaxation methods and related methods

Author: David M. Young
Journal: Math. Comp. 24 (1970), 793-807
MSC: Primary 65.35
MathSciNet review: 0281331
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The paper is concerned with variants of the successive overrelaxation method (SOR method) for solving the linear system $ Au = b$. Necessary and sufficient conditions are given for the convergence of the symmetric and unsymmetric SOR methods when $ A$ is symmetric. The modified SOR, symmetric SOR, and unsymmetric SOR methods are also considered for systems of the form $ {D_1}{u_1} - {C_U}{u_2} = {b_1}, - {C_L}{u_1} + {D_2}{u_2} = {b_2}$ where $ {D_1}$ and $ {D_2}$ are square diagonal matrices. Different values of the relaxation factor are used on each set of equations. It is shown that if the matrix corresponding to the Jacobi method of iteration has real eigenvalues and has spectral radius $ \bar \mu < 1$, then the spectral radius of the matrix $ G$ associated with any of the methods is not less than that of the ordinary SOR method with $ \omega = 2{(1 + {(1 - {\bar \mu ^2})^{1/2}})^{ - 1}}$. Moreover, if the eigenvalues of $ G$ are real then no improvement is possible by the use of semi-iterative methods.

References [Enhancements On Off] (What's this?)

  • [1] R. DeVogelaere, "Overrelaxations," Notices Amer. Math. Soc., v. 5, 1958, p. 147. Abstract #539-53.
  • [2] E. D'Sylva & G. A. Miles, "The S.S.O.R. iteration scheme for equations with $ {\sigma _1}$-ordering," Comput. J., v. 6, 1963/64, pp. 366-367. MR 28 #1772.
  • [3] Louis W. Ehrlich, "The block symmetric successive overrelaxation method," J. Soc. Indust. Appl. Math., v. 12, 1964, pp. 807-826. MR 33 #5134. MR 0196950 (33:5134)
  • [4] D. J. Evans & C. V. D. Forrington, "An iterative process for optimizing symmetric overrelaxation," Comput. J., v. 6, 1964, pp. 271-273.
  • [5] G. H. Golub & R. S. Varga, "Chebychev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods. I, II," Numer. Math., v. 3, 1961, pp. 147-168. MR 26 #3207; 3208.
  • [6] G. J. Habetler & E. L. Wachspress, "Symmetric successive overrelaxation in solving diffusion difference equations," Math. Comp., v. 15, 1961, pp. 356-362. MR 23 #B2176. MR 0129139 (23:B2176)
  • [7] W. Kahan, Gauss-Seidel Methods of Solving Large Systems of Linear Equations, Ph.D. Thesis, University of Toronto, 1958.
  • [8] M. S. Lynn, "On the equivalence of SOR, SSOR, and USSOR as applied to $ {\sigma _1}$-ordered systems of linear equations," Comput. J., v. 7, 1964, pp. 72-75. MR 31 #4157. MR 0179920 (31:4157)
  • [9] Leland K. McDowell, Variable Successive Overrelaxation, Report No. 244, Dept. of Computer Sciences, University of Illinois, September 18, 1967.
  • [10] A. M. Ostrowski, "On the linear iteration procedures for symmetric matrices," Rend. Mat. e Appl., v. 14, 1954, pp. 140-163. MR 16, 1155. MR 0070261 (16:1155e)
  • [11] J. W. Sheldon, "On the numerical solution of elliptic difference equations," Math. Tables Aids Comput., v. 9, 1955, pp. 101-112. MR 17, 668. MR 0074929 (17:668c)
  • [12] J. W. Sheldon, "On the spectral norms of several iterative processes," J. Assoc. Comput. Mach., v. 6, 1959, pp. 494-505. MR 23 #B1647. MR 0128608 (23:B1647)
  • [13] Richard S. Varga, "A comparison of the successive overrelaxation method and semiiterative methods using Chebychev polynomials," J. SIAM, v. 5, 1957, pp. 39-46. MR 19, 772. MR 0090129 (19:772d)
  • [14] E. L. Wachspress, Iterative Solution of Elliptic Systems and Applications to the Neutron Diffusion Equations of Reactor Physics, Prentice-Hall, Englewood Cliffs, N. J., 1966. MR 0234649 (38:2965)
  • [15] David M. Young, "Iterative methods for solving partial difference equations of elliptic type," Trans. Amer. Math. Soc., v. 76, 1954, pp. 92-111. MR 15, 562. MR 0059635 (15:562b)
  • [16] David M. Young, Mary F. Wheeler & James A. Downing, On the Use of the Modified Successive Overrelaxation Method with Several Relaxation Factors, Proc. IFIP 65, W. A. Kalenich (editor), Spartan Books, Washington, D. C., 1965.
  • [17] David M. Young & David R. Kincaid, Norms of the Successive Overrelaxation Method and Related Methods, Computation Center Report TNN-94, University of Texas, Austin, September 1969.
  • [18] David M. Young, Convergence Properties of the Symmetric and Unsymmetric Successive Overrelaxation Methods and Related Methods, Computation Center Report TNN-96, University of Texas, Austin, September 1969. MR 0281331 (43:7049)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65.35

Retrieve articles in all journals with MSC: 65.35

Additional Information

Keywords: Successive overrelaxation method, modified SOR, symmetric SOR, unsymmetric SOR, relaxation factor, spectral radius, virtual spectral radius, positive definite, $ {A^{1/2}}$-norm, semi-iterative method, cyclic Chebyshev semi-iterative method
Article copyright: © Copyright 1970 American Mathematical Society

American Mathematical Society