Convergence properties of the symmetric and unsymmetric successive overrelaxation methods and related methods
Author:
David M. Young
Journal:
Math. Comp. 24 (1970), 793807
MSC:
Primary 65.35
MathSciNet review:
0281331
Fulltext PDF Free Access
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 . Necessary and sufficient conditions are given for the convergence of the symmetric and unsymmetric SOR methods when is symmetric. The modified SOR, symmetric SOR, and unsymmetric SOR methods are also considered for systems of the form where and 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 , then the spectral radius of the matrix associated with any of the methods is not less than that of the ordinary SOR method with . Moreover, if the eigenvalues of are real then no improvement is possible by the use of semiiterative methods.
 [1]
R. DeVogelaere, "Overrelaxations," Notices Amer. Math. Soc., v. 5, 1958, p. 147. Abstract #53953.
 [2]
E. D'Sylva & G. A. Miles, "The S.S.O.R. iteration scheme for equations with ordering," Comput. J., v. 6, 1963/64, pp. 366367. MR 28 #1772.
 [3]
Louis
W. Ehrlich, The block symmetric successive overrelaxation
method, J. Soc. Indust. Appl. Math. 12 (1964),
807–826. 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. 271273.
 [5]
G. H. Golub & R. S. Varga, "Chebychev semiiterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods. I, II," Numer. Math., v. 3, 1961, pp. 147168. MR 26 #3207; 3208.
 [6]
G.
J. Habetler and E.
L. Wachspress, Symmetric successive overrelaxation in
solving diffusion difference equations, Math.
Comp. 15 (1961),
356–362. MR 0129139
(23 #B2176), http://dx.doi.org/10.1090/S00255718196101291399
 [7]
W. Kahan, GaussSeidel Methods of Solving Large Systems of Linear Equations, Ph.D. Thesis, University of Toronto, 1958.
 [8]
M.
S. Lynn, On the equivalence of
𝑆𝑂𝑅,𝑆𝑆𝑂𝑅 and
𝑈𝑆𝑆𝑂𝑅 as applied to
𝜎₁ordered systems of linear equations, Comput. J.
7 (1964), 72–75. 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. (5) 14 (1954),
140–163. MR 0070261
(16,1155e)
 [11]
John
W. Sheldon, On the numerical solution of elliptic
difference equations, Math. Tables Aids
Comput. 9 (1955),
101–112. MR 0074929
(17,668c), http://dx.doi.org/10.1090/S00255718195500749291
 [12]
J.
W. Sheldon, On the spectral norms of several iterative
processes, J. Assoc. Comput. Mach. 6 (1959),
494–505. MR 0128608
(23 #B1647)
 [13]
Richard
S. Varga, A comparison of the successive overrelaxation method and
semiiterative methods using Chebyshev polynomials, J. Soc. Indust.
Appl. Math. 5 (1957), 39–46. MR 0090129
(19,772d)
 [14]
Eugene
L. Wachspress, Iterative solution of elliptic systems, and
applications to the neutron diffusion equations of reactor physics,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1966. MR 0234649
(38 #2965)
 [15]
David
Young, Iterative methods for solving partial
difference equations of elliptic type, Trans.
Amer. Math. Soc. 76
(1954), 92–111. MR 0059635
(15,562b), http://dx.doi.org/10.1090/S00029947195400596357
 [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 TNN94, University of Texas, Austin, September 1969.
 [18]
David
M. Young, Convergence properties of the
symmetric and unsymmetric successive overrelaxation methods and related
methods, Math. Comp. 24 (1970), 793–807. MR 0281331
(43 #7049), http://dx.doi.org/10.1090/S00255718197002813314
 [1]
 R. DeVogelaere, "Overrelaxations," Notices Amer. Math. Soc., v. 5, 1958, p. 147. Abstract #53953.
 [2]
 E. D'Sylva & G. A. Miles, "The S.S.O.R. iteration scheme for equations with ordering," Comput. J., v. 6, 1963/64, pp. 366367. MR 28 #1772.
 [3]
 Louis W. Ehrlich, "The block symmetric successive overrelaxation method," J. Soc. Indust. Appl. Math., v. 12, 1964, pp. 807826. 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. 271273.
 [5]
 G. H. Golub & R. S. Varga, "Chebychev semiiterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods. I, II," Numer. Math., v. 3, 1961, pp. 147168. 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. 356362. MR 23 #B2176. MR 0129139 (23:B2176)
 [7]
 W. Kahan, GaussSeidel 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 ordered systems of linear equations," Comput. J., v. 7, 1964, pp. 7275. 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. 140163. 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. 101112. 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. 494505. 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. 3946. 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, PrenticeHall, 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. 92111. 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 TNN94, 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 TNN96, 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
DOI:
http://dx.doi.org/10.1090/S00255718197002813314
PII:
S 00255718(1970)02813314
Keywords:
Successive overrelaxation method,
modified SOR,
symmetric SOR,
unsymmetric SOR,
relaxation factor,
spectral radius,
virtual spectral radius,
positive definite,
norm,
semiiterative method,
cyclic Chebyshev semiiterative method
Article copyright:
© Copyright 1970
American Mathematical Society
