Abstract
For the augmented system of linear equations, Golub, Wu and Yuan recently studied an SOR-like method (BIT 41(2001)71–85). By further accelerating it with another parameter, in this paper we present a generalized SOR (GSOR) method for the augmented linear system. We prove its convergence under suitable restrictions on the iteration parameters, and determine its optimal iteration parameters and the corresponding optimal convergence factor. Theoretical analyses show that the GSOR method has faster asymptotic convergence rate than the SOR-like method. Also numerical results show that the GSOR method is more effective than the SOR-like method when they are applied to solve the augmented linear system. This GSOR method is further generalized to obtain a framework of the relaxed splitting iterative methods for solving both symmetric and nonsymmetric augmented linear systems by using the techniques of vector extrapolation, matrix relaxation and inexact iteration. Besides, we also demonstrate a complete version about the convergence theory of the SOR-like method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arrow, K., Hurwicz, L., Uzawa, H.: Studies in Nonlinear Programming. Stanford University Press, Stanford, 1958
Axelsson, O.: Iterative Solution Methods. Cambridge University Press, Cambridge, 1994
Bai, Z.-Z.: Parallel Iterative Methods for Large-Scale Systems of Algebraic Equations, Ph.D. Thesis, Department of Mathematics, Shanghai University of Science and Technology, Shanghai, March, 1993
Bai, Z.-Z.: On the convergence of the generalized matrix multisplitting relaxed methods. Comm. Numer. Methods Engrg. 11, 363–371 (1995)
Bai, Z.-Z.: A class of modified block SSOR preconditioners for symmetric positive definite systems of linear equations. Adv. Comput. Math. 10, 169–186 (1999)
Bai, Z.-Z.: Modified block SSOR preconditioners for symmetric positive definite linear systems. Ann. Oper. Res. 103, 263–282 (2001)
Bai, Z.-Z., Golub, G.H., Pan, J.-Y.: Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems. Numer. Math. 98, 1–32 (2004)
Bai, Z.-Z., Li, G.-Q.: Restrictively preconditioned conjugate gradient methods for systems of linear equations. IMA J. Numer. Anal. 23, 561–580 (2003)
Bai, Z.-Z., Wang, D.-R.: Generalized matrix multisplitting relaxation methods and their convergence. Numer. Math. J. Chinese Univ. (English Ser.) 2, 87–100 (1993)
Bramble, J.H., Pasciak, J.E., Vassilev, A.T.: Analysis of the inexact Uzawa algorithm for saddle point problems. SIAM J. Numer. Anal. 34, 1072–1092 (1997)
Brezzi, F., Fortin, M.: Mixed and Hybrid Finite Element Methods. Springer-Verlag, New York and London, 1991
Chan, R.H., Ng, M.K.: Conjugate gradient methods for Toeplitz systems. SIAM Rev. 38, 427–482 (1996)
Elman, H.C., Golub, G.H.: Inexact and preconditioned Uzawa algorithms for saddle point problems. SIAM J. Numer. Anal. 31, 1645–1661 (1994)
Fischer, B., Ramage, R., Silvester, D.J., Wathen, A.J.: Minimum residual methods for augmented systems. BIT 38, 527–543 (1998)
Fortin, M., Glowinski, R.: Augmented Lagrangian Methods, Applications to the Numerical Solution of Boundary Value Problems. North-Holland, Amsterdam, 1983
Golub, G.H., Van Loan, C.F.: Matrix Computations. 3rd Edition, The Johns Hopkins University Press, Baltimore and London, 1996
Golub, G.H., Wu, X., Yuan, J.-Y.: SOR-like methods for augmented systems. BIT 41, 71–85 (2001)
Henrici, P.: Applied and Computational Complex Analysis. Vol. 1: Power Series, Integration, Conformal Mapping and Location of Zeros, John Wiley & Sons, New York, London and Sydney, 1974
Hestenes, M.R., Stiefel, E.L.: Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bureau Standards Section B 49, 409–436 (1952)
Hu, J.-G.: Convergence of a generalized iterative matrix. Math. Numer. Sinica 6, 174–181 (1984) (In Chinese)
Li, C.-J., Li, B.-J., Evans, D.J.: A generalized successive overrelaxation method for least squares problems. BIT 38, 347–356 (1998)
Li, C.-J., Li, Z., Evans, D.J., Zhang, T.: A note on an SOR-like method for augmented systems. IMA J. Numer. Anal. 23, 581–592 (2003)
Miller, J.J.H.: On the location of zeros of certain classes of polynomials with applications to numerical analysis. J. Inst. Math. Appl. 8, 397–406 (1971)
Ng, M.K.: Preconditioning of elliptic problems by approximation in the transform domain. BIT 37, 885–900 (1997)
Song, Y.-Z.: On the convergence of the generalized AOR method. Linear Algebra Appl. 256, 199–218 (1997)
Song, Y.-Z.: On the convergence of the MAOR method. J. Comput. Appl. Math. 79, 299–317 (1997)
Varga, R.S.: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, N.J., 1962
Wang, X.-M.: Generalized extrapolation principle and convergence of some generalized iterative methods. Linear Algebra Appl. 185, 235–272 (1993)
Wang, X.-M.: Convergence for a general form of the GAOR method and its application to the MSOR method. Linear Algebra Appl. 196, 105–123 (1994)
Young, D.M.: Iterative Solutions of Large Linear Systems. Academic Press, New York, 1971
Author information
Authors and Affiliations
Corresponding author
Additional information
Subsidized by The Special Funds For Major State Basic Research Projects (No. G1999032803) and The National Natural Science Foundation (No. 10471146), P.R. China
Rights and permissions
About this article
Cite this article
Bai, ZZ., Parlett, B. & Wang, ZQ. On generalized successive overrelaxation methods for augmented linear systems. Numer. Math. 102, 1–38 (2005). https://doi.org/10.1007/s00211-005-0643-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00211-005-0643-0