SOR-like methods with optimization model for augmented linear systems. (English) Zbl 1392.65079
Summary: There has been a lot of study on the SOR-like methods for solving the augmented system of linear equations since the outstanding work of Golub, Wu and Yuan [G. H. Golub et al., BIT 41, No. 1, 71–85 (2001; Zbl 0991.65036)] was presented fifteen years ago. Based on the SOR-like methods, we establish a class of accelerated SOR-like methods for large sparse augmented linear systems by making use of optimization technique, which will find the optimal relaxation parameter \(\omega\) by optimization models. We demonstrate the convergence theory of the new methods under suitable restrictions. The numerical examples show these methods are effective.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F50 | Computational methods for sparse matrices |
| 15A06 | Linear equations (linear algebraic aspects) |
Citations:
Zbl 0991.65036References:
| [1] | [1]ArrowK., HurwiczL., and UzawaH., Studies in Nonlinear Programming, Stanford University Press, Stanford, 1958. · Zbl 0091.16002 |
| [2] | [2]BaiZ. Z., Optimal parameters in the HSS-like methods for saddle-point problems, Numer. Linear Algebra Appl., 16(2009), pp. 447-479.10.1002/nla.626 · Zbl 1224.65081 |
| [3] | [3]BaiZ. Z., Structured preconditioners for nonsingular matrices of block two-by-two structures, Math. Comput., 75 (2006), pp. 791-815. · Zbl 1091.65041 |
| [4] | [4]BaiZ. Z., and ChiX. B., Asymptotically optimal successive overrelaxation methods for systems of linear equations, J. Comput. Math., 21(5) (2003), pp. 603-612. · Zbl 1031.65050 |
| [5] | [5]BaiZ. Z., and GolubG. H., Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems, IMA J. Numer. Anal., 27(1) (2007), pp. 1-23. · Zbl 1134.65022 |
| [6] | [6]BaiZ. Z., GolubG. H., and NgM. K., On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations, Numer. Linear Algebra Appl., 14 (2007), pp. 319-335.10.1002/nla.517 · Zbl 1199.65097 |
| [7] | [7]BaiZ. Z., GolubG. H., and PanJ. Y., Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems, Numer. Math., 98 (2004), pp. 1-32.10.1007/s00211-004-0521-1 · Zbl 1056.65025 |
| [8] | [8]BaiZ. Z., ParlettB. N., and WangZ. Q., On generalized successive overrelaxatioon methods for augmented linear systems, Numer. Math., 102 (2005), pp. 1-38.10.1007/s00211-005-0643-0 · Zbl 1083.65034 |
| [9] | [9]BenziM., and GolubG. H., A preconditioner for generalized saddle point problems, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 20-41.10.1137/S0895479802417106 · Zbl 1082.65034 |
| [10] | [10]BenziM., GolubG. H., and LiesenJ., Numerical solution of saddle point problems, Acta Numerica, 14 (2005), pp. 1-137.10.1017/S0962492904000212S0962492904000212 · Zbl 1115.65034 |
| [11] | [11]BjörckA., Numerical stablity of methods for solving augmented systems. in Proceedings from Recent Developments in Optimization Theory and Nonlinear Analysis, Jerusalem, 1995, CensorY. and ReichS., eds., Contemp. Math., 204, Amer. Math. Soc., Providence, RI, (1997), pp. 51-60. · Zbl 0868.65025 |
| [12] | [12]BrambleJ. H., PasciakJ. E., and VassilevA. T., Analysis of the inexact Uzawa algorithm for saddle point problems, SIAM J. Numer. Anal.34 (1997), pp. 1072-1092.10.1137/S0036142994273343 · Zbl 0873.65031 |
| [13] | [13]ChaoZ., and ChenG. L., Semi-convergence analysis of the Uzawa-SOR methods for singular saddle point problems, Appl. Math. Letter, 35 (2014), pp. 52-57.10.1016/j.aml.2014.04.014 · Zbl 1314.65046 |
| [14] | [14]ChaoZ., ZhangN. M., and LuY. Z., Optimal parameters of the generalized symmetric SOR method for augmented system, J. Comput. Appl. Math., 266 (2014), pp. 52-60.10.1016/j.cam.2014.01.023 · Zbl 1293.65046 |
| [15] | [15]DarvishiM. T., and HessariP., Symmetric SOR method for augumented systems, Appl. Math. Comput., 173(1) (2006), pp. 404-420. · Zbl 1111.65029 |
| [16] | [16]ElmanH. C., and GolubG. H., Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal., 31 (1994), pp. 1645-1661.10.1137/0731085 · Zbl 0815.65041 |
| [17] | [17]ElmanH., and SilvesterD., Fast nonsymmetric iteration and preconditioning for Navier-Stokes equations, SIAM J. Sci. Comput., 17 (1996), pp. 33-46.10.1137/0917004 · Zbl 0843.65080 |
| [18] | [18]Fischer, RamageA., SilvesterD. J., and WathenA. J., Minimum residual methods for augmented systems, BIT, 38 (1998), pp. 527-543.10.1007/BF02510258 · Zbl 0914.65026 |
| [19] | [19]FortinM., and GlowinskiR., Augmented Lagrangian Methods, Applications to the Numerical Solution of Boundary Value Problems, Amsterdam: North-Holland, 1983. · Zbl 0525.65045 |
| [20] | [20]GolubG. H., WuX., and YuanJ. Y., SOR-like methods for augumented systems, BIT, 41 (2001), pp. 71-85.10.1023/A:1021965717530 · Zbl 0991.65036 |
| [21] | [21]GuoP., LiC. X., and WuS. L.. A modified SOR-like method for the augmented systems, J. Comput. Appl. Math., 274 (2015), pp. 58-69.10.1016/j.cam.2014.07.002 · Zbl 1296.65055 |
| [22] | [22]LiZ., LiC.J., and EvansD. J., Chebyshev acceleration for SOR-like method, Inter. J. Comput. Math., 82(5) (2005), pp. 583-593.10.1080/00207160512331331129 · Zbl 1074.65042 |
| [23] | [23]LiangZ. Z., and ZhangG. F., Modified unsymmetric SOR method for augmented systems, Appl. Math. Comput., 234 (2014), pp. 584-598. · Zbl 1298.65059 |
| [24] | [24]NelderJ. A., and MeadR., A simplex method for function minimization, Comput. J., 7 (1965), pp. 308-313.10.1093/comjnl/7.4.308 · Zbl 0229.65053 |
| [25] | [25]ShaoX. H., LiZ., and LiC. J., Modified SOR-like methods for the augmented systems, Inter. J. Comput. Math., 84 (2007), pp. 1653-1662.10.1080/00207160601117313 · Zbl 1141.65024 |
| [26] | [26]SunJ. G., Structured backward errors for KKT systems, Linear Algebra Appl., 288 (1999), pp. 75-88.10.1016/S0024-3795(98)10184-2 · Zbl 0936.65070 |
| [27] | [27]WenR. P., WangC. L., and YanX. H., Generalization of the nonstationary multisplitting iterative method for symmetric positive definite linear systems, Appl. Math. Comput., 216 (2010), pp. 1707-1714. · Zbl 1195.65042 |
| [28] | [28]WenR. P., MengG. Y., and WangC. L., Quasi-Chebyshev accelerated iteration methods based on optimization for linear systems, Comput. Math. Appl., 66 (2013), pp. 934-942.10.1016/j.camwa.2013.06.016 · Zbl 07863331 |
| [29] | [29]WrightS., Stablity of augmented system factorizations in interior-point methods, SIAM J. Matrix Anal. Appl., 18 (1997) 191-222.10.1137/S0895479894271093 · Zbl 0878.65041 · doi:10.1137/S0895479894271093 |
| [30] | [30]YuanJ. Y., Numerical methods for generalized least squares problems, J. Comput. Appl. Math., 66 (1996), pp. 571-584.10.1016/0377-0427(95)00167-0 · Zbl 0858.65043 |
| [31] | [31]ZhangG. F., and LuQ. H., On generalized symmetric SOR method for augumented systems, J. Comput. Appl. Math., 219 (2008), pp. 51-58.10.1016/j.cam.2007.07.001 · Zbl 1196.65071 |
| [32] | [32]ZhangJ. J., and ShangJ. J., A class of Uzawa-SOR methods for saddle point problem, Appl. Math. Comput., 216 (2010), pp. 2163-2168. · Zbl 1207.65036 |
| [33] | [33]ZhengB., WangK., and WuY. J., SSOR-like methods for saddle point problem, Inter. J. Comput. Math., 86 (2009), pp. 1405-1423.10.1080/00207160701871835 · Zbl 1180.65041 |
| [34] | [34]ZhengQ. Q., and MaC. F., A new SOR-Like method for the saddle point problems, Appl. Math. Comput., 233 (2014), pp. 421-429. · Zbl 1336.65050 |
| [35] | [35]ZhengQ. Q., and MaC. F., A class of triangular splitting methods for saddle point problems, J. Comput. Appl. Math., 298 (2016), pp. 13-23.10.1016/j.cam.2015.11.026 · Zbl 1332.65048 |
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.
