×

The steepest descent of gradient-based iterative method for solving rectangular linear systems with an application to Poisson’s equation. (English) Zbl 1482.65052

Summary: We introduce an effective iterative method for solving rectangular linear systems, based on gradients along with the steepest descent optimization. We show that the proposed method is applicable with any initial vectors as long as the coefficient matrix is of full column rank. Convergence analysis produces error estimates and the asymptotic convergence rate of the algorithm, which is governed by the term \(\sqrt{1-\kappa^{-2}}\), where \(\kappa\) is the condition number of the coefficient matrix. Moreover, we apply the proposed method to a sparse linear system arising from a discretization of the one-dimensional Poisson equation. Numerical simulations illustrate the capability and effectiveness of the proposed method in comparison to the well-known and recent methods.

MSC:

65F10 Iterative numerical methods for linear systems
41A60 Asymptotic approximations, asymptotic expansions (steepest descent, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] James, W. D., Applied Numerical Linear Algebra (1997), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia · Zbl 0879.65017
[2] Young, D. M., Iterative Solution of Large Linear Systems (1971), New York: Academic Press, New York · Zbl 0231.65034
[3] Albrechtt, P.; Klein, M. P., Extrapolated iterative methods for linear systems, SIAM J. Numer. Anal., 21, 1, 192-201 (1984) · Zbl 0531.65015 · doi:10.1137/0721014
[4] Hallett, A. J.H., The convergence of accelerated overrelaxation iterations, Math. Comput., 47, 175, 219-223 (1986) · Zbl 0605.65018 · doi:10.2307/2008090
[5] Ding, F.; Chen, T., Gradient based iterative algorithms for solving a class of matrix equations, IEEE Trans. Autom. Control, 50, 8, 1216-1221 (2005) · Zbl 1365.65083 · doi:10.1109/TAC.2005.852558
[6] Ding, F.; Chen, T., Hierarchical gradient-based identification of multivariable discrete-time systems, Automatica, 41, 2, 315-325 (2005) · Zbl 1073.93012 · doi:10.1016/j.automatica.2004.10.010
[7] Ding, F.; Chen, T., Hierarchical least squares identification methods for multivariable systems, IEEE Trans. Autom. Control, 50, 3, 397-402 (2005) · Zbl 1365.93551 · doi:10.1109/TAC.2005.843856
[8] Ding, F.; Liu, P. X.; Ding, J., Iterative solutions of the generalized Sylvester matrix equations by using the hierarchical identification principle, Appl. Math. Comput., 197, 1, 41-50 (2008) · Zbl 1143.65035 · doi:10.1016/j.amc.2007.07.040
[9] Niu, Q.; Wang, X.; Lu, L. Z., A relaxed gradient based algorithm for solving Sylvester equation, Asian J. Control, 13, 3, 461-464 (2011) · Zbl 1242.65081 · doi:10.1002/asjc.328
[10] Wang, X.; Dai, L.; Liao, D., A modified gradient based algorithm for solving Sylvester equation, Appl. Math. Comput., 218, 9, 5620-5628 (2012) · Zbl 1250.65063 · doi:10.1016/j.amc.2011.11.055
[11] Xie, Y.; Ma, C. F., The accelerated gradient based iterative algorithm for solving a class of generalized Sylvester-transpose matrix equation, Appl. Math. Comput., 273, 15, 1257-1269 (2016) · Zbl 1410.65129 · doi:10.1016/j.amc.2015.07.022
[12] Zhang, X.; Sheng, X., The relaxed gradient based iterative algorithm for the symmetric (skew symmetric) solution of the Sylvester equation \({AX+XB=C}\), Math. Probl. Eng., 2017 (2017) · Zbl 1426.65056 · doi:10.1155/2017/1624969
[13] Sheng, X.; Sun, W., The relaxed gradient based iterative algorithm for solving matrix equations, Comput. Math. Appl., 74, 3, 597-604 (2017) · Zbl 1382.65093 · doi:10.1016/j.camwa.2017.05.008
[14] Sheng, X., A relaxed gradient based algorithm for solving generalized coupled Sylvester matrix equations, J. Franklin Inst., 355, 10, 4282-4297 (2018) · Zbl 1390.93305 · doi:10.1016/j.jfranklin.2018.04.008
[15] Li, M.; Liu, X.; Ding, F., The gradient based iterative estimation algorithms for bilinear systems with autoregressive noise, Circuits Syst. Signal Process., 36, 11, 4541-4568 (2017) · Zbl 1373.93095 · doi:10.1007/s00034-017-0527-4
[16] Sun, M.; Wang, Y.; Liu, J., Two modified least-squares iterative algorithms for the Lyapunov matrix equations, Adv. Differ. Equ., 2019, 1 (2019) · Zbl 1485.65048 · doi:10.1186/s13662-019-2253-7
[17] Zhu, M. Z.; Zhang, G. F.; Qi, Y. E., On single-step HSS iterative method with circulant preconditioner for fractional diffusion equations, Adv. Differ. Equ., 2019, 1 (2019) · Zbl 1487.65126 · doi:10.1186/s13662-019-2353-4
[18] Zhang, H. M.; Ding, F., A property of the eigenvalues of the symmetric positive definite matrix and the iterative algorithm for coupled Sylvester matrix equations, J. Franklin Inst., 351, 1, 340-357 (2014) · Zbl 1293.15006 · doi:10.1016/j.jfranklin.2013.08.023
[19] Zhang, H. M.; Ding, F., Iterative algorithms for \({X+A^TX^{-1}A=I}\) by using the hierarchical identification principle, J. Franklin Inst., 353, 5, 1132-1146 (2016) · Zbl 1336.93066 · doi:10.1016/j.jfranklin.2015.04.003
[20] Ding, F.; Zhang, H., Brief paper - Gradient-based iterative algorithm for a class of the coupled matrix equations related to control systems, IET Control Theory Appl., 8, 15, 1588-1595 (2014) · doi:10.1049/iet-cta.2013.1044
[21] Xie, L.; Ding, J.; Ding, F., Gradient based iterative solutions for general linear matrix equations, Comput. Math. Appl., 58, 7, 1441-1448 (2009) · Zbl 1189.65083 · doi:10.1016/j.camwa.2009.06.047
[22] Xie, L.; Liu, Y. J.; Yang, H. Z., Gradient based and least squares based iterative algorithms for matrix equations \({AXB+CX^TD=F}\), Appl. Math. Comput., 217, 5, 2191-2199 (2010) · Zbl 1210.65097 · doi:10.1016/j.amc.2010.07.019
[23] Ding, F.; Lv, L.; Pan, J., Two-stage gradient-based iterative estimation methods for controlled autoregressive systems using the measurement data, Int. J. Control. Autom. Syst., 18, 886-896 (2020) · doi:10.1007/s12555-019-0140-3
[24] Ding, F.; Xu, L.; Meng, D., Gradient estimation algorithms for the parameter identification of bilinear systems using the auxiliary model, J. Comput. Appl. Math., 369 (2020) · Zbl 1431.93058 · doi:10.1016/j.cam.2019.112575
[25] Ding, F.; Chen, T., Iterative least-squares solutions of coupled Sylvester matrix equations, Syst. Control Lett., 54, 2, 95-107 (2005) · Zbl 1129.65306 · doi:10.1016/j.sysconle.2004.06.008
[26] Ding, F.; Chen, T., On iterative solutions of general coupled matrix equations, SIAM J. Control Optim., 44, 6, 2269-2284 (2006) · Zbl 1115.65035 · doi:10.1137/S0363012904441350
[27] Edwin, K. P.C.; Stanislaw, H. Z., An Introduction to Optimization (2001), New York: Wiley-Interscience, New York · Zbl 1056.90129
[28] Barzilai, J.; Borwein, J., Two point step size gradient methods, IMA J. Numer. Anal., 8, 1, 141-148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[29] Yuan, Y. X., Step-sizes for the gradient method, AMS/IP Stud. Adv. Math., 42, 785-797 (2008) · Zbl 1172.90509
[30] Dai, Y. H.; Yuan, J. Y.; Yuan, Y., Modified two-point step-size gradient methods for unconstrained optimization, Comput. Optim. Appl., 22, 103-109 (2002) · Zbl 1008.90056 · doi:10.1023/A:1014838419611
[31] Dai, Y.H., Fletcher, R.: On the asymptotic behaviour of some new gradient methods. Numerical analysis report NA/212, Department of Mathematics, University of Dundee, Scotland, UK (2003)
[32] Dai, Y. H.; Yuan, Y., Analysis of monotone gradient methods, J. Ind. Manag. Optim., 1, 2, 181-192 (2005) · Zbl 1071.65084 · doi:10.3934/jimo.2005.1.181
[33] Fletcher, R.: On the Brazilar-Borwein method. Research report, University of Dundee, Scotland, UK (2001)
[34] Yuan, Y.: A new stepsize for the steepest descent method. Research report, Institute of Computional Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, China (2004)
[35] Stephen, P. B.; Lieven, V., Convex Optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049
[36] Zhong, Z. B., On Hermitian and skew-Hermitian spliting iteration methods for continuous Sylvester equations, J. Comput. Math., 29, 2, 185-198 (2011) · Zbl 1249.65090 · doi:10.4208/jcm.1009-m3152
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.