nach oben

Numerical Algorithms

Erschienen in:

15.05.2019 | Original Paper

How to compute the minimum norm least squares solution of singular linear system by using the preconditioned HSS method?

verfasst von: Yue Hao, Ai-Li Yang, Yu-Jiang Wu

Erschienen in: Numerical Algorithms | Ausgabe 3/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

For the singular, non-Hermitian, and positive semi-definite system of linear equations Ax = b, we introduce a kind of preconditioners for the preconditioned Hermitian and skew-Hermitian splitting (PHSS) iteration method. Then, the iteration sequence generated by the corresponding PHSS iteration method converges to the minimum norm least squares solution A^‡b for any initial guess no matter the singular system of linear equations is consistent or inconsistent. In addition, a kind of PHSS preconditioners are derived from the PHSS iteration method. The PHSS preconditioned generalized minimum residual (PGMRES) methods also determine the minimum norm least squares solution of the consistent singular linear system at breakdown. Numerical experiments are used to verify the effectiveness and the robustness of the PHSS iteration method and the PHSS preconditioner.

Vorheriger Artikel Parameter-robust preconditioning for the optimal control of the wave equation

Nächster Artikel Sharp H1-norm error estimate of a cosine pseudo-spectral scheme for 2D reaction-subdiffusion equations

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Bai, Z.-Z.: Splitting iteration methods for non-Hermitian positive definite systems of linear equations. Hokkaido Math. J. 36(4), 801–814 (2007)MathSciNetMATHCrossRef

Bai, Z.-Z.: Optimal parameters in the HSS-like methods for saddle-point problems. Numer. Linear Algebra Appl. 16(6), 447–479 (2009)MathSciNetMATHCrossRef

Bai, Z.-Z.: On semi-convergence of Hermitian and skew-Hermitian splitting methods for singular linear systems. Computing 89(3), 171–197 (2010)MathSciNetMATHCrossRef

Bai, Z.-Z., Golub, G.H.: Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems. IMA J. Numer. Anal. 27(1), 1–23 (2007)MathSciNetMATHCrossRef

Bai, Z.-Z., Golub, G.H., Li, C.-K.: Convergence properties of preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite matrices. Math. Comput. 76(257), 287–298 (2007)MathSciNetMATHCrossRef

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 J. Sci. Comput. 26(3), 844–863 (2005)MathSciNetMATHCrossRef

Bai, Z.-Z., Golub, G.H., Ng, M.K.: Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl. 24(3), 603–626 (2003)MathSciNetMATHCrossRef

Bai, Z.-Z., Golub, G.H., Ng, M.K.: On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations. Numer. Linear Algebra Appl. 14(4), 319–335 (2007)MathSciNetMATHCrossRef

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), 1–32 (2004)MathSciNetMATHCrossRef

10.

Bai, Z.-Z., Ng, M.K., Wang, Z.-Q.: Constraint preconditioners for symmetric indefinite matrices. SIAM J. Matrix Anal. Appl. 31(2), 410–433 (2009)MathSciNetMATHCrossRef

11.

Barker, V.A.: Numerical solution of sparse singular systems of equations arising from ergodic Markov chains. Comm. Statist. Stoch. Model. 5(3), 335–381 (1989)MathSciNetMATHCrossRef

12.

Ben-Israel, A., Charnes, A.: Contributions to the theory of generalized inverses. J. Soc. Indust. Appl. Math. 11(3), 667–699 (1963)MathSciNetMATHCrossRef

13.

Berman, A., Plemmons, R.J.: Cones and iterative methods for best least squares solutions of linear systems. SIAM J. Numer. Anal. 11(1), 145–154 (1974)MathSciNetMATHCrossRef

14.

Berman, A., Plemmons, R.J.: Nonnegative matrices in the mathematical sciences. Society for Industrial and Applied Mathematics (1994)

15.

Bertaccini, D., Golub, G.H., Capizzano, S.S., Possio, C.T.: Preconditioned HSS methods for the solution of non-Hermitian positive definite linear systems and applications to the discrete convection-diffusion equation. Numer. Math. 99(3), 441–484 (2005)MathSciNetMATHCrossRef

16.

Bialecki, B., Remington, K.A.: Fourier matrix decomposition methods for the least squares solution of singular Neumann and periodic Hermite bicubic collocation problems. SIAM J. Sci. Comput. 16(2), 431–451 (1995)MathSciNetMATHCrossRef

17.

Chao, Z., Zhang, N.-M.: A generalized preconditioned HSS method for singular saddle point problems. Numer. Algor. 66(2), 203–221 (2014)MathSciNetMATHCrossRef

18.

Chen, F., Liu, Q.-Q.: On semi-convergence of modified HSS iteration methods. Numer. Algor. 64(3), 507–518 (2013)MathSciNetMATHCrossRef

19.

Dou, Y., Yang, A.-L., Wu, Y.-J.: Modified parameterized inexact Uzawa method for singular saddle-point problems. Numer. Algor. 72(2), 325–339 (2016)MathSciNetMATHCrossRef

20.

Elman, H.C.: Preconditioning for the steady-state Navier–Stokes equations with low viscosity. SIAM J. Sci. Comput. 20(4), 1299–1316 (1999)MathSciNetMATHCrossRef

21.

Golub, G.H., Huang, L.C., Simon, H., Tang, W.-P.: A fast Poisson solver for the finite difference solution of the incompressible Navier–Stokes equations. SIAM J. Sci. Comput. 19(5), 1606–1624 (1998)MathSciNetMATHCrossRef

22.

Harlow, F.H., Welch, J.E.: Numerical calculation of time-dependent viscous incompressible flow of fluid with free surface. Phys. Fluids 8(12), 2182–2189 (1965)MathSciNetMATHCrossRef

23.

Kammerer, W.J., Nashed, M.Z.: On the convergence of the conjugate gradient method for singular linear operator equations. SIAM J. Numer. Anal. 9(1), 165–181 (1972)MathSciNetMATHCrossRef

24.

Li, W., Liu, Y.-P., Peng, X.-F.: The generalized HSS method for solving singular linear systems. J. Comput. Appl. Math. 236(9), 2338–2353 (2012)MathSciNetMATHCrossRef

25.

Penrose, R.: A generalized inverse for matrices. Math. Proc. Camb. Phil. Soc. 51(3), 406–413 (1955)MATHCrossRef

26.

Santos, C.H., Silva, B.P.B., Yuan, J.-Y.: Block SOR methods for rank-deficient least-squares problems. J. Comput. Appl. Math. 100(1), 1–9 (1998)MathSciNetMATHCrossRef

27.

Wang, S.-S., Zhang, G.-F.: Preconditioned AHSS iteration method for singular saddle point problems. Numer. Algor. 63(3), 521–535 (2013)MathSciNetMATHCrossRef

28.

Wu, X., Silva, B.P.B., Yuan, J.-Y.: Conjugate gradient method for rank deficient saddle point problems. Numer. Algor. 35(2-4), 139–154 (2004)MathSciNetMATHCrossRef

29.

Yang, A.-L., Dou, Y., Wu, Y.-J., Li, X.: On generalized parameterized inexact Uzawa methods for singular saddle-point problems. Numer. Algor. 69(3), 579–593 (2015)MathSciNetMATHCrossRef

30.

Zhang, G.-F., Wang, S.-S.: A generalization of parameterized inexact Uzawa method for singular saddle point problems. Appl. Math. Comput. 219(9), 4225–4231 (2013)MathSciNetMATH

31.

Zhang, N.-M.: A note on preconditioned GMRES for solving singular linear systems. BIT Numer. Math. 50(1), 207–220 (2010)MathSciNetMATHCrossRef

32.

Zhang, N.-M., Lu, T.-T., Wei, Y.-M.: Semi-convergence analysis of Uzawa methods for singular saddle point problems. J. Comput. Appl. Math. 255, 334–345 (2014)MathSciNetMATHCrossRef

33.

Zhang, N.-M., Shen, P.: Constraint preconditioners for solving singular saddle point problems. J. Comput. Appl. Math. 238, 116–125 (2013)MathSciNetMATHCrossRef

34.

Zheng, B., Bai, Z.-Z., Yang, X.: On semi-convergence of parameterized Uzawa methods for singular saddle point problems. Linear Algebra Appl. 431(5), 808–817 (2009)MathSciNetMATHCrossRef

Titel: How to compute the minimum norm least squares solution of singular linear system by using the preconditioned HSS method?
verfasst von: Yue Hao
Ai-Li Yang
Yu-Jiang Wu
Publikationsdatum: 15.05.2019
Verlag: Springer US
Erschienen in: Numerical Algorithms / Ausgabe 3/2020
Print ISSN: 1017-1398
Elektronische ISSN: 1572-9265
DOI: https://doi.org/10.1007/s11075-019-00721-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 3/2020

Quadrature rules from a RII type recurrence relation and associated quadrature rules on the unit circle

An augmented Lagrangian proximal alternating method for sparse discrete optimization problems

Optimal inverse projection of floating-point addition

Error bounds for linear complementarity problems of S-QN matrices

A Picard-type iterative algorithm for general variational inequalities and nonexpansive mappings

Parameter-robust preconditioning for the optimal control of the wave equation

Premium Partner