×

Generalized ASOR and modified ASOR methods for saddle point problems. (English) Zbl 1400.65020

Summary: Recently, the accelerated successive overrelaxation- (SOR-) like (ASOR) method was proposed for saddle point problems. In this paper, we establish a generalized accelerated SOR-like (GASOR) method and a modified accelerated SOR-like (MASOR) method, which are extension of the ASOR method, for solving both nonsingular and singular saddle point problems. The sufficient conditions of the convergence (semiconvergence) for solving nonsingular (singular) saddle point problems are derived. Finally, numerical examples are carried out, which show that the GASOR and MASOR methods have faster convergence rates than the SOR-like, generalized SOR (GSOR), modified SOR-like (MSOR-like), modified symmetric SOR (MSSOR), generalized symmetric SOR (GSSOR), generalized modified symmetric SOR (GMSSOR), and ASOR methods with optimal or experimentally found optimal parameters when the iteration parameters are suitably chosen.

MSC:

65F10 Iterative numerical methods for linear systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Benzi, M.; Golub, G. H.; Liesen, J., Numerical solution of saddle point problems, Acta Numerica, 14, 1-137, (2005) · Zbl 1115.65034 · doi:10.1017/S0962492904000212
[2] Bai, Z.-Z.; Golub, G. H.; Pan, J.-Y., Preconditioned HERmitian and skew-HERmitian splitting methods for non-HERmitian positive semidefinite linear systems, Numerische Mathematik, 98, 1, 1-32, (2004) · Zbl 1056.65025 · doi:10.1007/s00211-004-0521-1
[3] Brezzi, F.; Fortin, M., Mixed and Hybrid Finite Element Methods, (1991), New York, NY, USA: Springer, New York, NY, USA · Zbl 0788.73002 · doi:10.1007/978-1-4612-3172-1
[4] Yuan, J.-Y., Numerical methods for generalized least squares problems, Journal of Computational and Applied Mathematics, 66, 1-2, 571-584, (1996) · Zbl 0858.65043 · doi:10.1016/0377-0427(95)00167-0
[5] Bai, Z.-Z.; Parlett, B. N.; Wang, Z.-Q., On generalized successive overrelaxation methods for augmented linear systems, Numerische Mathematik, 102, 1, 1-38, (2005) · Zbl 1083.65034 · doi:10.1007/s00211-005-0643-0
[6] Chao, Z.; Zhang, N.-M.; Lu, Y.-Z., Optimal parameters of the generalized symmetric SOR method for augmented systems, Journal of Computational and Applied Mathematics, 266, 52-60, (2014) · Zbl 1293.65046 · doi:10.1016/j.cam.2014.01.023
[7] Darvishi, M. T.; Hessari, P., Symmetric SOR method for augmented systems, Applied Mathematics and Computation, 183, 1, 409-415, (2006) · Zbl 1111.65029 · doi:10.1016/j.amc.2006.05.094
[8] Golub, G. H.; Wu, X.; Yuan, J.-Y., SOR-like methods for augmented systems, BIT Numerical Mathematics, 41, 1, 71-85, (2001) · Zbl 0991.65036 · doi:10.1023/a:1021965717530
[9] Guo, P.; Li, C.-X.; Wu, S.-L., A modified SOR-like method for the augmented systems, Journal of Computational and Applied Mathematics, 274, 58-69, (2015) · Zbl 1296.65055 · doi:10.1016/j.cam.2014.07.002
[10] Li, J.-C.; Kong, X., Optimal parameters of GSOR-like methods for solving the augmented linear systems, Applied Mathematics and Computation, 204, 1, 150-161, (2008) · Zbl 1159.65038 · doi:10.1016/j.amc.2008.06.010
[11] Shao, X.-H.; Li, Z.; Li, C.-J., Modified SOR-like method for the augmented system, International Journal of Computer Mathematics, 84, 11, 1653-1662, (2007) · Zbl 1141.65024 · doi:10.1080/00207160601117313
[12] Bai, Z.-Z.; Wang, Z.-Q., On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra and Its Applications, 428, 11-12, 2900-2932, (2008) · Zbl 1144.65020 · doi:10.1016/j.laa.2008.01.018
[13] Bramble, J. H.; Pasciak, J. E.; Vassilev, A. T., Analysis of the inexact Uzawa algorithm for saddle point problems, SIAM Journal on Numerical Analysis, 34, 3, 1072-1092, (1997) · Zbl 0873.65031 · doi:10.1137/s0036142994273343
[14] Cao, Y.; Jiang, M.-Q.; Yao, L.-Q., New choices of preconditioning matrices for generalized inexact parameterized iterative methods, Journal of Computational and Applied Mathematics, 235, 1, 263-269, (2010) · Zbl 1202.65039 · doi:10.1016/j.cam.2010.05.054
[15] Cao, Y.; Yi, S.-C., A class of Uzawa-PSS iteration methods for nonsingular and singular non-Hermitian saddle point problems, Applied Mathematics and Computation, 275, 41-49, (2016) · doi:10.1016/j.amc.2015.11.049
[16] Elman, H. C.; Golub, G. H., Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM Journal on Numerical Analysis, 31, 6, 1645-1661, (1994) · Zbl 0815.65041 · doi:10.1137/0731085
[17] Yun, J.-H., Variants of the Uzawa method for saddle point problem, Computers & Mathematics with Applications, 65, 7, 1037-1046, (2013) · Zbl 1266.65057 · doi:10.1016/j.camwa.2013.01.037
[18] Zhang, J.-J.; Shang, J.-J., A class of Uzawa-SOR methods for saddle point problems, Applied Mathematics and Computation, 216, 7, 2163-2168, (2010) · Zbl 1207.65036 · doi:10.1016/j.amc.2010.03.051
[19] Bai, Z.-Z., Optimal parameters in the HSS-like methods for saddle-point problems, Numerical Linear Algebra with Applications, 16, 6, 447-479, (2009) · Zbl 1224.65081 · doi:10.1002/nla.626
[20] Bai, Z.-Z.; Golub, G. H., Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems, IMA Journal of Numerical Analysis, 27, 1, 1-23, (2007) · Zbl 1134.65022 · doi:10.1093/imanum/drl017
[21] Bai, Z.-Z.; Golub, G. H.; Li, C.-K., Optimal parameter in Hermitian and skew-Hermitian splitting method for certain two-by-two block matrices, SIAM Journal on Scientific Computing, 28, 2, 583-603, (2006) · Zbl 1116.65039 · doi:10.1137/050623644
[22] Bai, Z.-Z.; Golub, G. H.; Lu, L.-Z.; Yin, J.-F., Block triangular and skew-Hermitian splitting methods for positive-definite linear systems, SIAM Journal on Scientific Computing, 26, 3, 844-863, (2005) · Zbl 1079.65028 · doi:10.1137/s1064827503428114
[23] Bai, Z.-Z.; Golub, G. H.; Ng, M. K., Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM Journal on Matrix Analysis and Applications, 24, 3, 603-626, (2003) · Zbl 1036.65032 · doi:10.1137/s0895479801395458
[24] Jiang, M.-Q.; Cao, Y., On local Hermitian and skew-Hermitian splitting iteration methods for generalized saddle point problems, Journal of Computational and Applied Mathematics, 231, 2, 973-982, (2009) · Zbl 1221.65091 · doi:10.1016/j.cam.2009.05.012
[25] Bai, Z.-Z.; Li, G.-Q., Restrictively preconditioned conjugate gradient methods for systems of linear equations, IMA Journal of Numerical Analysis, 23, 4, 561-580, (2003) · Zbl 1046.65018 · doi:10.1093/imanum/23.4.561
[26] Bai, Z.-Z.; Wang, Z.-Q., Restrictive preconditioners for conjugate gradient methods for symmetric positive definite linear systems, Journal of Computational and Applied Mathematics, 187, 2, 202-226, (2006) · Zbl 1083.65045 · doi:10.1016/j.cam.2005.03.044
[27] Bai, Z.-Z., Structured preconditioners for nonsingular matrices of block two-by-two structures, Mathematics of Computation, 75, 254, 791-815, (2006) · Zbl 1091.65041 · doi:10.1090/S0025-5718-05-01801-6
[28] Bai, Z.-Z.; Ng, M. K.; Wang, Z.-Q., Constraint preconditioners for symmetric indefinite matrices, SIAM Journal on Matrix Analysis and Applications, 31, 2, 410-433, (2009) · Zbl 1195.65033 · doi:10.1137/080720243
[29] Pan, J.-Y.; Ng, M. K.; Bai, Z.-Z., New preconditioners for saddle point problems, Applied Mathematics and Computation, 172, 2, 762-771, (2006) · Zbl 1088.65040 · doi:10.1016/j.amc.2004.11.016
[30] Li, X.; Wu, Y.-J.; Yang, A.-L.; Yuan, J.-Y., Modified accelerated parameterized inexact Uzawa method for singular and nonsingular saddle point problems, Applied Mathematics and Computation, 244, 552-560, (2014) · Zbl 1336.65042 · doi:10.1016/j.amc.2014.07.031
[31] Liang, Z.-Z.; Zhang, G.-F., On semi-convergence of a class of Uzawa methods for singular saddle-point problems, Applied Mathematics and Computation, 247, 397-409, (2014) · Zbl 1338.65085 · doi:10.1016/j.amc.2014.08.103
[32] Zhang, G.-F.; Wang, S.-S., A generalization of parameterized inexact Uzawa method for singular saddle point problems, Applied Mathematics and Computation, 219, 9, 4225-4231, (2013) · Zbl 06447233 · doi:10.1016/j.amc.2012.10.116
[33] Zhang, N.-M.; Lu, T.-T.; Wei, Y.-M., Semi-convergence analysis of Uzawa methods for singular saddle point problems, Journal of Computational and Applied Mathematics, 255, 334-345, (2014) · Zbl 1291.65116 · doi:10.1016/j.cam.2013.05.015
[34] Zheng, B.; Bai, Z.-Z.; Yang, X., On semi-convergence of parameterized Uzawa methods for singular saddle point problems, Linear Algebra and Its Applications, 431, 5–7, 808-817, (2009) · Zbl 1173.65026 · doi:10.1016/j.laa.2009.03.033
[35] Njeru, P. N.; Guo, X.-P., Accelerated SOR-like method for augmented linear systems, BIT Numerical Mathematics, (2015) · Zbl 1341.65015 · doi:10.1007/s10543-015-0571-z
[36] Young, D. M., Iterative Solution of Large Linear Systems, (1971), New York, NY, USA: Academic Press, New York, NY, USA · Zbl 0231.65034
[37] Wang, S.-S.; Zhang, G.-F., Preconditioned AHSS iteration method for singular saddle point problems, Numerical Algorithms, 63, 3, 521-535, (2013) · Zbl 1279.65037 · doi:10.1007/s11075-012-9638-y
[38] Yang, A.-L.; Wu, Y.-J., The Uzawa-HSS method for saddle-point problems, Applied Mathematics Letters, 38, 38-42, (2014) · Zbl 1314.65055 · doi:10.1016/j.aml.2014.06.018
[39] Yang, A.-L.; Li, X.; Wu, Y.-J., On semi-convergence of the Uzawa-HSS method for singular saddle-point problems, Applied Mathematics and Computation, 252, 88-98, (2015) · Zbl 1338.65090 · doi:10.1016/j.amc.2014.11.100
[40] Miao, S.-X.; Cao, Y., Semi-convergence of the generalized local HSS method for singular saddle point problems, Revista de la Unión Matemática Argentina, 55, 2, 71-80, (2014) · Zbl 1308.65046
[41] Zhu, M.-Z., A generalization of the local Hermitian and skew-Hermitian splitting iteration methods for the non-Hermitian saddle point problems, Applied Mathematics and Computation, 218, 17, 8816-8824, (2012) · Zbl 1245.65039 · doi:10.1016/j.amc.2012.02.040
[42] Zhou, L.-J.; Zhang, N.-M., Semi-convergence analysis of GMSSOR methods for singular saddle point problems, Computers & Mathematics with Applications, 68, 5, 596-605, (2014) · Zbl 1362.65042 · doi:10.1016/j.camwa.2014.07.003
[43] Zhang, L.-T.; Huang, T.-Z.; Cheng, S.-H.; Wang, Y.-P., Convergence of a generalized MSSOR method for augmented systems, Journal of Computational and Applied Mathematics, 236, 7, 1841-1850, (2012) · Zbl 1244.65050 · doi:10.1016/j.cam.2011.10.016
[44] Chen, C.-R.; Ma, C.-F., A generalized shift-splitting preconditioner for saddle point problems, Applied Mathematics Letters, 43, 49-55, (2015) · Zbl 1315.65030 · doi:10.1016/j.aml.2014.12.001
[45] Chen, C.-R.; Ma, C.-F., A generalized shift-splitting preconditioner for singular saddle point problems, Applied Mathematics and Computation, 269, 947-955, (2015) · doi:10.1016/j.amc.2015.08.020
[46] Fan, H.-T.; Zheng, B., A preconditioned GLHSS iteration method for non-Hermitian singular saddle point problems, Computers & Mathematics with Applications, 67, 3, 614-626, (2014) · Zbl 1350.65021 · doi:10.1016/j.camwa.2013.12.006
[47] Zhang, G.-F.; Liao, L.-D.; Liang, Z.-Z., On parameterized generalized skew-Hermitian triangular splitting iteration method for singular and nonsingular saddle point problems, Applied Mathematics and Computation, 254, 340-359, (2015) · Zbl 1410.65111 · doi:10.1016/j.amc.2014.12.120
[48] Zhang, G.-F.; Lu, Q.-H., On generalized symmetric SOR method for augmented systems, Journal of Computational and Applied Mathematics, 219, 1, 51-58, (2008) · Zbl 1196.65071 · doi:10.1016/j.cam.2007.07.001
[49] Wu, S.-L.; Huang, T.-Z.; Zhao, X.-L., A modified SSOR iterative method for augmented systems, Journal of Computational and Applied Mathematics, 228, 1, 424-433, (2009) · Zbl 1167.65016 · doi:10.1016/j.cam.2008.10.006
[50] Bai, Z.-Z.; Wang, L.; Yuan, J.-Y., Weak-convergence theory of quasi-nonnegative splittings for singular matrices, Applied Numerical Mathematics. An IMACS Journal, 47, 2, 75-89, (2003) · Zbl 1044.65022 · doi:10.1016/S0168-9274(03)00057-6
[51] Berman, A.; Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences, (1979), New York, NY, USA: Academic Press, New York, NY, USA · Zbl 0484.15016
[52] Berman, A.; Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences, (1994), Philadelphia, Pa, USA: Society for Industrial and Applied Mathematics, Philadelphia, Pa, USA · doi:10.1137/1.9781611971262
[53] Li, X.; Yang, A.-L.; Wu, Y.-J., Parameterized preconditioned HERmitian and skew-HERmitian splitting iteration method for saddle-point problems, International Journal of Computer Mathematics, 91, 6, 1224-1238, (2014) · Zbl 1304.65129 · doi:10.1080/00207160.2013.829216
[54] Cao, Y.; Du, J.; Niu, Q., Shift-splitting preconditioners for saddle point problems, Journal of Computational and Applied Mathematics, 272, 239-250, (2014) · Zbl 1303.65012 · doi:10.1016/j.cam.2014.05.017
[55] Cao, Y.; Jiang, M.-Q.; Zheng, Y.-L., A splitting preconditioner for saddle point problems, Numerical Linear Algebra with Applications, 18, 5, 875-895, (2011) · Zbl 1249.65065 · doi:10.1002/nla.772
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.