Convergence properties of the symmetric and unsymmetric successive overrelaxation methods and related methods
HTML articles powered by AMS MathViewer
- by David M. Young PDF
- Math. Comp. 24 (1970), 793-807 Request permission
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
-
R. DeVogelaere, "Overrelaxations," Notices Amer. Math. Soc., v. 5, 1958, p. 147. Abstract #539–53.
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.
- Louis W. Ehrlich, The block symmetric successive overrelaxation method, J. Soc. Indust. Appl. Math. 12 (1964), 807–826. MR 196950 D. J. Evans & C. V. D. Forrington, "An iterative process for optimizing symmetric overrelaxation," Comput. J., v. 6, 1964, pp. 271–273. 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.
- G. J. Habetler and E. L. Wachspress, Symmetric successive overrelaxation in solving diffusion difference equations, Math. Comp. 15 (1961), 356–362. MR 129139, DOI 10.1090/S0025-5718-1961-0129139-9 W. Kahan, Gauss-Seidel Methods of Solving Large Systems of Linear Equations, Ph.D. Thesis, University of Toronto, 1958.
- M. S. Lynn, On the equivalence of $\textrm {SOR}, \textrm {SSOR}$ and $\textrm {USSOR}$ as applied to $\sigma _{1}$-ordered systems of linear equations, Comput. J. 7 (1964), 72–75. MR 179920, DOI 10.1093/comjnl/7.1.72 Leland K. McDowell, Variable Successive Overrelaxation, Report No. 244, Dept. of Computer Sciences, University of Illinois, September 18, 1967.
- A. M. Ostrowski, On the linear iteration procedures for symmetric matrices, Rend. Mat. e Appl. (5) 14 (1954), 140–163. MR 70261
- John W. Sheldon, On the numerical solution of elliptic difference equations, Math. Tables Aids Comput. 9 (1955), 101–112. MR 74929, DOI 10.1090/S0025-5718-1955-0074929-1
- J. W. Sheldon, On the spectral norms of several iterative processes, J. Assoc. Comput. Mach. 6 (1959), 494–505. MR 128608, DOI 10.1145/320998.321003
- Richard S. Varga, A comparison of the successive overrelaxation method and semi-iterative methods using Chebyshev polynomials, J. Soc. Indust. Appl. Math. 5 (1957), 39–46. MR 90129
- Eugene L. Wachspress, Iterative solution of elliptic systems, and applications to the neutron diffusion equations of reactor physics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1966. MR 0234649
- David Young, Iterative methods for solving partial difference equations of elliptic type, Trans. Amer. Math. Soc. 76 (1954), 92–111. MR 59635, DOI 10.1090/S0002-9947-1954-0059635-7 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. 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.
- David M. Young, Convergence properties of the symmetric and unsymmetric successive overrelaxation methods and related methods, Math. Comp. 24 (1970), 793–807. MR 281331, DOI 10.1090/S0025-5718-1970-0281331-4
Additional Information
- © Copyright 1970 American Mathematical Society
- Journal: Math. Comp. 24 (1970), 793-807
- MSC: Primary 65.35
- DOI: https://doi.org/10.1090/S0025-5718-1970-0281331-4
- MathSciNet review: 0281331